math - 在随机图中: What is the probability that a node has a link to any node on a list x defined special nodes?

Question

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

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

然后让我们将一定数量的 x 个节点(例如 5 个)标记为特殊节点。那么节点与这些特殊节点中的任何一个具有边缘的概率 (p_s) 是多少。

令人不安的是，我自己对如何解决这个问题几乎没有什么想法。我想答案将分两步进行:

首先，因为我想我将不得不承认 N 个节点的所有可能图来为我的概率计算创建事件。我认为如果 S=N(N-1)/2 则可能有 S(S-1)/2 个可能的图，但这些图的可能性并不相同，所以我我不知所措。 其次，我知道当特殊节点的数量 (x) 接近 N 时，到特殊节点的链接概率必须接近 1，并且 p_s =p 如果 x=1。

感谢您的任何提示。谢谢

Answer 1

对于非特殊节点，从该节点到特殊节点有 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。

由于这是 Stack Overflow，因此需要进行一些编程。这是一个 Python 3 蒙特卡罗模拟，似乎表明了随机选择的节点是特殊节点或与特殊节点相邻的概率公式的准确性:

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