In einer zufälligen Grafik: Wie groß ist die Wahrscheinlichkeit, dass ein Knoten eine Verbindung zu einem beliebigen Knoten in einer Liste hat? X definierte spezielle Knoten?

Question

Ich habe dieses Problem für eine Berechnung, die ich auf einem beobachteten Netzwerk mache.

wir uns vor, einen zufälligen Graphen G (n, p) wo N ist die Anzahl der Knoten und p ist die Wahrscheinlichkeit einer Kante zwischen jedem Knoten n _i und n gebildet ist, _j. Die Grafik ist ungerichtet.

Lassen Sie uns dann eine Menge von x Knoten, sagen 5, als speziell markieren. Was ist dann die Wahrscheinlichkeit ( p _s) eines Knotens, eine Kante zu einem dieser speziellen Knoten zu haben.

Ich habe beunruhigend wenig Ideen, wie ich selbst darüber gehen soll. Ich nehme an, dass die Antwort wird in zwei Schritten sein:

Erstens, weil ich mir vorstellen, dass ich alle möglichen Graphen von N Knoten, um Ereignisse für meine Wahrscheinlichkeitsrechnung machen müssen. Ich denke, es könnte S (S-1)/2 möglichen Grafiken wenn S = N (N-1)/2, aber diese sind nicht gleich wahrscheinlich, so dass ich ratlos bin. Zweitens verstehe ich, dass die Wahrscheinlichkeit von Links zu speziellem Knoten 1 als die Anzahl von speziellen Knoten nähern muß ( x) Ansatz N, und dass p _s = p wenn x = 1.

Vielen Dank für Hinweise. Danke

Answer 1

Für einen nicht-speziellen Knoten gibt es x potenzielle Kanten von diesem Knoten zu einem speziellen Knoten. Für jede solche potentielle Kante ist die Wahrscheinlichkeit, dass die Kante nicht in der Grafik ist, 1-p. Unter der Annahme der Unabhängigkeit ist die Wahrscheinlichkeit, dass alle spezielle Knoten vermieden werden, (1-p)^x. Die komplementäre Wahrscheinlichkeit ist, was Sie suchen, ist es

1 - (1-p)^x 

Für spezielle Knoten, die Wahrscheinlichkeit, dass ein spezieller gegebenen Knoten zu einem der anderen speziellen Knoten verbunden ist,

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

Sie diese Antworten kombinieren auf verschiedene Arten. Wählen Sie einen Knoten zufällig aus. Die Wahrscheinlichkeit, daß sie entweder speziell oder nur einen Rand um es zu einem speziellen Knoten verbindet, ist:

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

die Wahrscheinlichkeit, dass es um eine Kante zu einem speziellen Knoten verbinden muss, ist:

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

in allen Fällen - diese tendieren zu 1, da x zu N neigt.

Da dies Stack Overflow ist, ist ein bisschen Programmierung in Ordnung.Hier ist eine Python 3 Monte-Carlo-Simulation, die die Genauigkeit der Formel für die Wahrscheinlichkeit scheint darauf hinzudeuten, dass ein zufällig ausgewählten Knoten entweder spezielle oder angrenzend an eine besondere ist:

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 müssten anpassen zB x/N zu floaten (x)/N).

Beispielausgabe:

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