在随机图中：节点对列表 x 定义的特殊节点上的任何节点具有 link 的概率是多少？

Question

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

让我们想象一个随机图 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.

感谢任何提示。谢谢

Answer 1

对于非特殊节点，从该节点到特殊节点有 x 条潜在边。对于任何这样的潜在边，边 not 在图中的概率是 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]

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

由于这是 Stack Overflow，因此需要进行一些编程。这是一个 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

在随机图中：节点对列表 x 定义的特殊节点上的任何节点具有 link 的概率是多少？

In a random graph: What is the probability that a node has a link to any node on a list x defined special nodes?

math

graph-theory

probability-theory

sna

network-analysis