A large company's internal email network grows by one new employee joining per time step

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

Many Parts, One Behaviour, Ch Growing networks: preferential attachment and scale-free degree distributions

Problem

A large company's internal email network grows by one new employee joining per time step, time tt counted in employees who have joined so far. Each new employee creates m=3m=3 introductory email links to employees already at the company. Two rules for choosing the m=3m=3 contacts are compared.Model U (uniform): the contacts are chosen independently and uniformly at random among existing employees, regardless of how many links each already has. Its stationary degree distribution is pk(U)=1m+1(mm+1)k−m,k≥m.p_k^{(\mathrm{U})}=\frac{1}{m+1}\left(\frac{m}{m+1}\right)^{k-m},\qquad k\ge m.Model P (preferential): the contacts are chosen with probability proportional to the number of links the existing employee already has (the Barabási-Albert rule). Its stationary degree distribution is pk(P)=2m(m+1)k(k+1)(k+2),k≥m.p_k^{(\mathrm{P})}=\frac{2m(m+1)}{k(k+1)(k+2)},\qquad k\ge m. (a) Show that the cumulative tail (the probability that a randomly chosen employee has degree at least kk) is exactly P(U)(k)=(mm+1)k−mandP(P)(k)=m(m+1)k(k+1),P^{(\mathrm{U})}(k)=\left(\frac{m}{m+1}\right)^{k-m}\quad\text{and}\quad P^{(\mathrm{P})}(k)=\frac{m(m+1)}{k(k+1)}, using the geometric series sum for model U and the partial-fraction telescoping sum for model P. (b) Estimate the largest degree expected among N=5×105N=5\times10^5 employees under each model, using NP(kmax⁡)≈1NP(k_{\max})\approx1. (c) State in one sentence what the comparison shows about the claim that growth alone, with no preference for high-degree employees, is enough to create a genuine hub.

Browse the problem library