Reverse engineering of linking preferences from network restructuring

We provide a method to deduce the preferences governing the restructuring dynamics of a network from the observed rewiring of the edges. Our approach is applicable for systems in which the preferences can be formulated in terms of a single-vertex energy function with $f\left(k\right)$ being the contribution of a node of degree $k$ to the total energy, and the dynamics obeys the detailed balance. The method is first tested by Monte Carlo simulations of restructuring graphs with known energies; then it is used to study variations of real network systems ranging from the coauthorship network of scientific publications to the asset graphs of the New York Stock Exchange. The empirical energies obtained from the restructuring can be described by a universal function $f\left(k\right)\sim -k\ln k$, which is consistent with and justifies the validity of the preferential attachment rule proposed for growing networks.

Figure 1

We illustrate the measurement of the currents $I_{k\to k+1}$ and $I_{k\to k-1}$ in the data set by comparing two subsequent states of vertex 0 in a hypothetical simple graph with 17 vertices. (Only edges connected to vertex 0 are shown.) In the initial state (left side), the central vertex is connected to vertices 1,2,4,5 with one edge and to vertex 3 with two edges; hence its degree is $k=6$. In the second state (right side), the link to vertex 2 and one of the links to vertex 3 disappeared giving a contribution $I_{6\to 5}=2$ to the currents. Similarly, new links to vertices 6, 12, and 13 appeared; thus $I_{6\to 7}=3$.

Figure 2

$\varphi \left(k\right)$ obtained from the restructuring data of the MC simulation with $C_{1}k$ subtracted, together with fits. For the case of $E=0$ (random rewiring, circles), the system converges to a classical random graph, which results in a narrow degree distribution. In the system with $E=-k\ln \left(k\right)$ (crosses), the interval in which $\varphi \left(k\right)$ can be obtained is wider. Thus the results from reverse engineering are in good agreement with the initial MC energies.

Figure 3

The empirical $\varphi \left(k\right)$ obtained for the neuroscience publication network (diamonds) for $\tau =3$. In order to make the nonlinear part of $\varphi \left(k\right)$ more apparent, the linear part of the fit, $C_{1}k$, was subtracted from the data. The actual values obtained for the fitting parameters were $C_0=-6.7$, $C_1=12.6$, $\tilde{\alpha }=0.96$. A relatively large gap between $\varphi \left(k\right)$ at $k=0$ and $k=1$ can be observed. The inset shows the corresponding $\gamma \left(k\right)$ with $C_0∕k+C_1$ subtracted from the data (boxes) together with $-\tilde{\alpha }\ln \left(k\right)$ (dashed line).

Figure 4

The empirical $\varphi \left(k\right)$ of the Astrophysics archive for $\tau =3\mathrm{yr}$ with $C_{1}k$ subtracted (diamonds) plotted together with $-\tilde{\alpha }k\ln \left(k\right)+C_0$ (solid line). The values of the fitting parameters read $C_0=-4.8$, $C_1=8.4$, $\tilde{\alpha }=0.59$. The $\varphi (k=0)$ is separated from the $k⩾1$ part by a gap, similarly to the case shown in Fig. 3. In the inset the corresponding $\gamma \left(k\right)-C_0∕k-C_1$ is shown together with $-0.59\ln \left(k\right)$.

Figure 5

$\varphi \left(k\right)$ obtained in case of the U.S. movie actor network for $\tau =3$ with $C_{1}k$ subtracted from the data (diamonds). The resulting functions can be fitted with $-\tilde{\alpha }k\ln \left(k\right)+C_0$ similarly to previously studied collaboration networks. The actual values of the fitting parameters are $C_0=-14$, $C_1=10.4$, $\tilde{\alpha }=0.74$. The gap separating $\varphi (k=0)$ from the $k⩾1$ part characteristic of the other collaboration networks can be seen in this case as well. The $\gamma \left(k\right)$ corresponding to this $\varphi \left(k\right)$ is shown in the inset with $C_0∕k+C_1$ subtracted from the data, plotted together with $-\tilde{\alpha }\ln \left(k\right)$.

Figure 6

The empirical $\varphi \left(k\right)$ of the asset graphs of the New York Stock Exchange with $C_{1}k$ subtracted from the data (diamonds), plotted together with $-\tilde{\alpha }k\ln \left(k\right)$ (solid line). The fitting parameters were $C_0=0$, $C_1=8.5$, $\tilde{\alpha }=1.7$. The inset shows $\gamma \left(k\right)-C_1$ plotted together with $-\tilde{\alpha }\ln \left(k\right)$.