An online discussion forum links its registered users by an edge whenever two of them…

PHYSICS · Subjective · Fermi University Physics · Thermal, Statistical & Complex Systems · Complex and collective systems · Complex and collective systems

Many Parts, One Behaviour, Ch Random graphs, the giant component and percolation on networks

Problem

An online discussion forum links its

N = 2000

registered users by an edge whenever two of them have replied in the same thread at least once; counting these edges gives

M = 5000

in total. Model the resulting social graph as an Erdos-Renyi random graph

G(N,p)

, in which every pair of the

N

users is joined independently with the same probability

p

, and take the mean degree to be

c = 2M/N

. (a) Starting from the exact binomial degree distribution of

G(N,p)

, derive the Poisson form

p_k = e^{-c}c^k/k!

that holds in the sparse limit

N \to \infty

at fixed

c

. State explicitly which limit turns the binomial into the Poisson distribution. (b) Derive the clustering coefficient of

G(N,p)

from its definition as the probability that two neighbours of a given node are themselves joined by an edge, and show that

C = p

. (c) Evaluate

c

p

and

C

for the forum network described. An independent audit of the same platform's reply data gives a measured clustering coefficient of

C_{\rm real} = 0.15

. By what factor does the Erdos-Renyi prediction fall short of this measured value?

Browse the problem library