Statistics of Changes in Lead Node in Connectivity-Driven Networks

We study statistical properties of the highest degree, or most popular, nodes in growing networks. We show that the number of lead changes increases logarithmically with network size $N$, independent of the details of the growth mechanism. The probability that the first node retains the lead approaches a finite constant for popularity-driven growth, and decays as $N^{-\varphi }(\ln N{)}^{-1/2}$, with $\varphi =0.08607\dots$, for growth with no popularity bias.

Figure 1

Average index of the leader $J_{\mathrm{l}\mathrm{e}\mathrm{a}\mathrm{d}}(N)$ as a function of the total number of nodes $N$ for ${10}^5$ realizations of a growing network of ${10}^5$ nodes. Shown are the cases of attachment rates $A_k=1$ and $A_k=k$.

Figure 2

Average number of lead changes $L(N)$ as a function of network size $N$ for ${10}^5$ realizations of the network for $A_k=1$ and $A_k=k$.

Figure 3

Degree distribution of the first node for the dimer, trimer (2 links to the initial node), and pentamer (4 links) initial conditions based on ${10}^5$ realizations of a network with ${10}^5$ links. The curve is the prediction of Eq. (7).

Figure 4

Probability that the first node leads throughout the evolution for ${10}^5$ realizations of up to size $N={10}^7$ for $A_k=k$ (upper), and up to $N={10}^8$ for $A_k=1$ (lower).