A university's citation database is examined through three separate idealised pictures
PHYSICS · Multi-part · 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
A university's citation database is examined through three separate idealised pictures, one for each result below.
((a)) Treat the database as an Erdos-Renyi random graph with N=2000 papers and mean degree c=4.5 citation links per paper. Starting from the binomial degree distribution and taking the sparse limit N→∞ at fixed c, obtain the Poisson degree distribution pk=e−cck/k!, and use it to find the expected number of papers with no citation links at all.
((b)) To picture the local clustering that this random graph ignores, imagine instead that every paper is linked only to its k=12 nearest neighbours in a fixed reference-order ring (a Watts-Strogatz ring with no rewiring). By counting the triangles formed by a node and its neighbours, derive the ring's clustering coefficient C(0)=3(k−2)/[4(k−1)] and evaluate it for k=12.
((c)) Return to the Erdos-Renyi picture of part (a). Using G0(x)=G1(x)=ec(x−1) for a Poisson degree distribution, derive the site-percolation threshold ϕc=1/G1′(1): the fraction of papers that must remain, after random removal, for a giant connected component to survive. Evaluate ϕc for c=4.5 and compare it with the square-lattice site threshold 0.5927.