Network evolution based on centrality

We study the evolution of networks when the creation and decay of links are based on the position of nodes in the network measured by their centrality. We show that the same network dynamics arise under various centrality measures, and solve analytically the network evolution. During the complete evolution, the network is characterized by nestedness: the neighborhood of a node is contained in the neighborhood of the nodes with larger degree. We find a discontinuous transition in the network density between hierarchical and homogeneous networks, depending on the rate of link decay. We also show that this evolution mechanism leads to double power-law degree distributions, with interrelated exponents.

Figure 1

Representation of a nested network and the associated stepwise adjacency matrix with $N=10$ nodes. A nested network can be partitioned into subsets of nodes with the same degree (each subset is represented by circle, next to which the degree $d$ of the nodes in the subset is indicated). A line connecting two subsets indicates that there exists a link between each node in one set to all nodes in the other set. The union of the sets represented by the circles to the left of the dashed line induce a dominating set, while to the right the circles indicate independent sets. In the matrix $\mathbf{A}$ to the right, the zero-entries are separated from the one-entries by a step-function, $h\left(r\right)$, of the rank degree of the nodes.

Figure 2

(a) Eigenvector centralization ${\mathcal{C}}_v$ in stationary networks as a function of the link formation probability $\alpha$ for different system sizes $N=100$ ($\circ$), $N=1000$ ($red\square$), and $N=5000$ ($green\diamond$). Results of numerical simulations are superimposed with lines representing the analytical prediction. (b) Degree distributions of stationary networks for different values of $\alpha =0.45$ ($\circ$), $0.48$ ($red\square$), $0.49$ ($green\diamond$), $0.495$ ($blue▵$), and system size $N=5000$. The figure reveals that the leading part of the distribution is exponential, while a logarithmic binning shows a power-law tail with exponent $-1$.

Figure 3

(a) Degree distribution for different exponents in the head of the distribution $\eta =1.2$ ($black\nabla$), $1.5$ ($red▵$), 2 ($green\diamond$), $2.5$ ($blue\square$), 3 ($magenta\circ$). If a nested network exhibits a power-law in the head (tail) of the degree distribution then the distribution will also exhibit a power-law behavior in the tail (head), with an exponent that can be completely determined by the head (tail). (b) Power-law exponents for the tail of the degree distribution, i.e. $k\to \infty$ ($red\square$), and the head of the distribution, i.e. $k\to 0$ ($\circ$), as a function of the power-law exponent of the head. The symbols correspond to networks of $N={10}^5$ nodes, and the lines represent the numerical simulations.