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

Question

У меня есть эта проблема для расчета, которое я делаю в наблюдаемой сети.

Давайте представим случайный граф G (N, р), где N это количество узлов и р вероятность кромки образуется между любым узлом п _я и п _j. Граф неориентирован.

Давайте затем отметьте сумму x узлов, скажем 5, специальными. Тогда есть вероятность ( p _s) узла, у которого есть край для любого из этих специальных узлов.

У меня очень мало идей, как это сделать сам. Я полагаю, что ответ будет выполнен в два этапа:

Во-первых, поскольку я предполагаю, что мне придется уступить все возможные графики N узлов для проведения событий для расчета вероятности. Я думаю, что может быть S (S-1)/2 возможных графов, если S = N (N-1)/2, но это не так, вероятно, так что я в недоумении. Во-вторых Я понимаю, что вероятность ссылок на специальные узлы должны подходить к 1 в качестве числа специальных узлов ( х) подход N, и что р ы = р, если х = 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.

Поскольку это переполнение стека, требуется немного программирования.Вот 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 нужно будет корректировать, например, х/N для float (x)/N).

Пример вывода:

>>> estimateProb(100,0.25,10) 
0.9496800000000086 
>>> 
>>> exactProb(100,0.25,10) 
0.9493178367614746