2

对于我在观察到的网络上进行的计算，我遇到了这个问题。

让我们想象一个随机图G(N,p)，其中N是节点数，p是在任何节点n i和n j之间形成边的概率。该图是无向的。

然后让我们将一定数量的x节点（比如 5）标记为特殊的。那么一个节点与这些特殊节点中的任何一个具有边的概率（ p s ）是多少。

我对如何自己解决这个问题几乎没有什么想法。我想答案将分两步：

首先，因为我想我将不得不承认所有可能的N个节点图来为我的概率计算制作事件。我认为如果S=N(N-1)/2可能有S(S-1)/2可能的图表，但这些可能性并不相同，所以我很茫然。其次，我理解到特殊节点的链接概率必须接近 1，因为特殊节点 ( x ) 的数量接近N，并且p s =p如果x=1。

感谢任何提示。谢谢

4

1 回答 1

4

对于非特殊节点，存在x从该节点到特殊节点的潜在边。对于任何这样的潜在边，边不在图中的概率是1-p。假设独立，它避开所有特殊节点的概率为(1-p)^x。互补概率是你所寻求的，它是

1 - (1-p)^x

对于特殊节点，给定特殊节点连接到其他特殊节点之一的概率为

1 - (1-p)^(x-1)

您可以通过各种方式组合这些答案。随机选择一个节点。它是特殊的或具有将其连接到特殊节点的边的概率为：

x/N + (N-x)/N * [1-(1-p)^x]

它有一条边连接到一个特殊节点的概率是：

x/N * [1 - (1-p)^(x-1)] + (N-x)/N * [1 - (1-p)^x]

在所有情况下——这些趋向于 1，因为 x 趋向于 N。

由于这是堆栈溢出，因此需要进行一些编程。这是一个 Python 3 Monte Carlo 模拟，它似乎暗示了随机选择的节点是特殊节点或与特殊节点相邻的概率公式的准确性：

import random

#The following function returns a random graph on nodes
#0,1,...,N-1 where edges are chosen with probability p
#The graph is returned as a dictionary keyed by the 
#The corresponding values are sorted lists of adjacent nodes

def randGraph(N,p):

    #initialize G:
    G = {}
    for i in range(N):
        G[i] = []

    #iterate through potential edges:
    for i in range(N-1):
        for j in range(i+1,N):
            if random.random() < p:
                G[i].append(j)
                G[j].append(i)

    #sort adjacency lists before returning:
    for i in G:
        G[i].sort()
    return G

#A function to determine the number of nodes
#in a graph that are either
#special or connected to a special,
#where special means: 0,1,2,...,x

def specialsAndFriends(G,x):
    count = 0
    for i in G:
        if (i<x) or (len(G[i]) > 0 and G[i][0] < x):
            count +=1
    return count

#now -- a Monte Carlo simulation:

def estimateProb(N,p,x,trials = 1000):
    estimates = []
    for i in range(trials):
        G = randGraph(N,p)
        estimates.append(specialsAndFriends(G,x)/N)
    return sum(estimates)/trials

#compare with:

def exactProb(N,p,x):
    return x/N + (N-x)/N * (1 - (1-p)**x)

（Python 2 需要将例如 x/N 调整为 float(x)/N）。

样本输出：

>>> estimateProb(100,0.25,10)
0.9496800000000086
>>> 
>>> exactProb(100,0.25,10)
0.9493178367614746
于 2016-04-05T17:51:24.137 回答