В случайном графе: какова вероятность того, что узел имеет ссылку на любой узел в списке x определенных специальных узлов?

Для неспециального узла существует 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, которая, кажется, предполагает точность формулы для вероятности того, что случайно выбранный узел является либо особенным, либо смежным с особым:

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