Random(graphs) Networks ° Average degree(k)=p(N-1)≈pN Clustering coefficient: C=P=(k)/N<< Average path length: L oc In N/In pN Degree distribution: Binomial E(XN Poisson h)=∠ k
Random (Graphs) Networks • Average degree: • Clustering coefficient: • Average path length: • Degree distribution: Binomial ~Poisson k p(N 1) pN C p k / N 1 e k P k k ! ( ) L ln N / ln pN
Classroom Question QUIZ In the class of Erdos-Renyi random graphs gp(300)with 300 nodes and unit link weights, compute the following: (a)What is ProbIgp(n) is connected], the probability that Gp(n)is connected, as a function of p? Make also a drawing as a function of the link density p. What is the connectivity threshold pc? (b) The link density p=3pc, what is the probability P(k= 299)of an arbitrary node with degree 299? What is the k that can make P(k)maximum? (c)what is the average link number e[L] of the graph Gp(300)? (d) Calculate the average clustering coefficient E CGp(300) of the random graph Gp(300)
In the class of Erdős-Rényi random graphs Gp(300) with 300 nodes and unit link weights, compute the following: (a) What is Prob[Gp(N) is connected], the probability that Gp(N) is connected, as a function of p? Make also a drawing as a function of the link density p. What is the connectivity threshold pc? (b) The link density p=3pc, what is the probability of an arbitrary node with degree 299? What is the k that can make maximum? (c) What is the average link number E[L] of the graph Gp(300)? (d) Calculate the average clustering coefficient E[CGp(300)] of the random graph Gp(300). P( 299) k P( ) k Classroom Question
O&A In the class of Erdos-Renyi random graphs g, 300)with 300 nodes and unit link weights (a)Pr[G (N)is connected]=P(kmin 21)=(P(krg 21) (1-P(k=0) (1-p)-) 0 if p The connectivity PrIGP (N) is connected] threshold N logN log 300 300 0.019 0 ClogN/N When p>pc the graphs are connected with high probability, but some still are disconneted, when the size n of the graph is not large enough
In the class of Erdős-Rényi random graphs Gp (300) with 300 nodes and unit link weights (a) Pr[Gp (N) is connected] pc~logN/N Pr[ Gp (N) is connected] 1 O N 1 0 min 1 P( 1) P( 1) 1 P( 0) (1 (1 ) ) N rg N N N k k k p log log300 300 0.019 c N p N The connectivity threshold: log 0 Pr[ ( ) ] log 1 p N if p N G N is connected N if p N When p>pc , the graphs are connected with high probability, but some still are disconneted, when the size N of the graph is not large enough. Q&A
Random graph gooo8(300 Connected cluster size 255 nodes Isolated node Node with degree≤9 Node with degree >9
Random Graph G0.008(300) Connected cluster size = 255 nodes Isolated node Node with degree ≤ 9 Node with degree > 9
Random graph goog( 300) Connected graph Connected threshold p=0.019 But, generate 10000 '0. 300)graphs. 62% graphs are disconnected Isolated node Node with degree≤9 Node with degree >9
Random Graph G0.019(300) Connected graph! Connected threshold pc=0.019 But, generate 10000 G0.019(300) graphs, 62% graphs are disconnected. Isolated node Node with degree ≤ 9 Node with degree > 9