Link-space formalism for network analysis

We introduce the link-space formalism for analyzing network models with degree-degree correlations. The formalism is based on a statistical description of the fraction of links $l_{i,j}$ connecting nodes of degrees $i$ and $j$. To demonstrate its use, we apply the framework to some pedagogical network models, namely, random attachment, Barabási-Albert preferential attachment, and the classical Erdős and Rényi random graph. For these three models the link-space matrix can be solved analytically. We apply the formalism to a simple one-parameter growing network model whose numerical solution exemplifies the effect of degree-degree correlations for the resulting degree distribution. We also employ the formalism to derive the degree distributions of two very simple network decay models, more specifically, that of random link deletion and random node deletion. The formalism allows detailed analysis of the correlations within networks and we also employ it to derive the form of a perfectly nonassortative network for arbitrary degree distribution.

Figure 1

(Color online) Top: the analytically derived, normalized link-space matrix for the random attachment growth algorithm. This could be filled to arbitrary size but is truncated to maximum degree of 40 here. Bottom: comparison of the cumulative link-space matrices for the analytic solution and a simulation of the algorithm. The simulation comprises an ensemble average of 100 networks grown to ${10}^8$ nodes. The maximum degree obtained was 37. The first 30 rows ($i$ values) of the cumulative link-space are illustrated and finite-size effects are noticable at high $j$.

Figure 2

(Color online) Top: the analytically derived, normalized link-space matrix for the preferential attachment growth algorithm. This could be filled to arbitrary size but is here truncated to maximum degree of approximately ${10}^5$. Bottom: comparison of the cumulative link-space matrices for the analytic solution and a simulation of the algorithm. The simulation comprises an ensemble average of 1000 networks each grown to ${10}^7$ nodes. The maximum degree obtained was 17 609. Various rows ($i$ values) from 1 to 3500 of the cumulative link-space are illustrated and the effects of the finite nature of the simulation are apparent.

Figure 3

(Color online) Top: the analytically derived, normalized link-space matrix for the Erdős and Rényi (ER) random graph with mean degree equal to 5. This could be filled to arbitrary size but is here truncated to a maximum degree of 30. Bottom: comparison of the cumulative link-space matrices for the analytic solution and a simulation of the algorithm. The simulation comprises an ensemble average of 500 networks each consisting of ${10}^7$ nodes. The probability that a link exists between any pair of nodes is $\alpha =5\times {10}^{-7}$ and the maximum degree obtained was 25. The first 20 rows ($i$ values) of the cumulative link-space are illustrated and, again, the finite nature of the simulation is apparent for high $j$.

Figure 4

(Color online) The mean degree of the nearest neighbors ${⟨k_{nn}⟩}_i$ of nodes of degree $i$ as a function of $i$ for the analytic solutions to the random attachment algorithm (Sec. 2A), the BA model (Sec. 2B), and the ER random graph (Sec. 2C).

Figure 5

(Color online) The conditional probability $P(j\mid i)$ that one end of a randomly selected link has degree $j$ given that the other end is of degree $i$ over the range $i=\{1,6,11,16,\dots ,51\}$. The top plot is for the random attachment algorithm and the bottom is preferential attachment. The criterion of nonassortativity of Eq. (23) is denoted with red circles.

Figure 6

(Color online) Top: Networks generated using the one-parameter, local information growth algorithm with $a=1$ (left), $a=0.2$ (center), and $a=0$ (right). Initial network seed comprised of two nodes and one link. Networks drawn with PAJEK [50]. Bottom: Cumulative degree distributions for the same networks grown to ${10}^5$ nodes and ensemble-averaged over 100 networks per $a$ value.

Figure 7

(Color online) Degree distributions generated using the link-space analysis of our one-step algorithm. Dashed line: results for the Barabási-Albert (BA) [8] preferential-attachment algorithm. Our one-step algorithm closely resembles the BA results with a parameter value $a=0.25$ (see inset).

Figure 8

The paths of probability flux from $c_{x-1}$ influencing element $l_{i,j}$. Each arrow (step) represents a further factor of $\frac{1}{3}$.

Figure 9

(Color online) Comparison of the numerically derived link-space matrix (markers) and the analytic solution (solid lines) for random node attachment for the first 20 rows ($i$ values) of the link-space matrix. The numerical implementation populates the link-space matrix directly from the degree distribution and the steady-state link-space recurrence relations.

Figure 10

The components of flux of probability around the link-space matrix. This is general to any attachment kernel. An element within the link-space matrix can be built up from contributing elements and the appropriate factors.

Figure 11

A binomial process over seven steps. The number of paths between $A$ and $B$ can be expressed as the sum of the paths $A\to W$, $A\to X$, $A\to Y$, and $A\to Z$.

Figure 12

(Color online) Comparison of the numerically derived link-space matrix (markers) and the analytic solution (solid lines) for preferential attachment. The numerical implementation populates the matrix from the solution of the degree distribution and the link-space recurrence equations.