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 cluster of N=5000 database servers, each linked to others by data-mirroring connections, is examined through three separate idealised pictures, one for each result below.
((a)) Treat the cluster as an Erdos-Renyi random graph with mean degree c=3.2. Starting from the binomial degree distribution and taking the sparse limit N→∞ at fixed c, obtain the Poisson degree distribution, and use it to find the expected number of servers with no mirroring links at all.
((b)) To picture the local clustering this random graph ignores, imagine instead that every server mirrors only its k=8 nearest neighbours on a fixed reference ring (a Watts-Strogatz ring with no rewiring). By counting the triangles formed by a node and its neighbours, derive C(0)=3(k−2)/[4(k−1)] and evaluate it for k=8.
((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) and evaluate it for c=3.2. Compare with the square-lattice site threshold 0.5927.