Constrained randomization of weighted networks

We propose a Markov chain method to efficiently generate surrogate networks that are random under the constraint of given vertex strengths. With these strength-preserving surrogates and with edge-weight-preserving surrogates we investigate the clustering coefficient and the average shortest path length of functional networks of the human brain as well as of the International Trade Networks. We demonstrate that surrogate networks can provide additional information about network-specific characteristics and thus help interpreting empirical weighted networks.

Figure 1

“Tetragon transformation” of the network $P^{h-1}$ to $P^h$. In a randomly selected tetragon ($i$, $j$, $k$, $l$), a random number $\zeta$ is added to the weights of two opposing edges ($P_{ij}^{h-1}$, $P_{kl}^{h-1}$) and subtracted from the weights of the others ($P_{jk}^{h-1}$, $P_{li}^{h-1}$). Other edge weights remain unaltered. Edge weights are encoded as line thickness.

Figure 2

Scheme used to generate surrogates $\mathcal{P}=\{P_1,...,P_{4096}\}$ from an original network $O$. Short arrows represent a “step” consisting of $t$ tetragon transformations, long arrows represent 10 such steps, and $A_1,...,A_{14}$ are auxiliary networks. (Superscripts are omitted for better readability.)

Figure 3

Number of sufficient transformations $t_{\mathit{suf}}$ per step for the generation of 4096 surrogate networks from four toy networks with $n$ vertices. For comparison, the solid line displays twice the number of edges.

Figure 4

Temporal evolutions of clustering coefficients $\overline{C}$ (first row) and $\overline{K}$ (fifth row) and average shortest path length $\overline{L}$ (third row) of functional brain networks [solid (black) lines] and of weight-preserving surrogates [dotted (red) lines] and strength-preserving surrogates [dashed (green) lines] for these networks. For $\overline{L}$ we show the margins of standard deviation over 4096 weight-preserving surrogates [dotted (red) lines]. The original networks and the weight-preserving surrogates differed in $\overline{C}$ by $0.0015$ on average. Standard deviations of $\overline{C}$ and $\overline{K}$ over the weight-preserving surrogates were too small to be displayed; the maximum standard deviation of $\overline{C}$, $\overline{K}$, and $\overline{L}$ over the 4096 strength-preserving surrogates was $0.02$ each. For comparison, for the original networks we show the temporal evolutions of the inverse of the maximum weight $\frac{1}{\mathit{max}\left(\mathcal{W}\right)}$ (second row) and of the standard deviation $\sigma \left(\mathcal{W}\right)$ of the edge weights (fourth row).

Figure 5

(top) Temporal evolutions of clustering coefficient $\overline{K}$ (right) and average shortest path length $\overline{L}$ (left) of the International Trade Networks for the years 1948 to 2000 [solid (black) lines]. Also shown are the margins of standard deviation for 4096 weight-preserving surrogates [dotted (red) lines] and 4096 strength-preserving surrogates [dashed (green) lines] for these networks; (bottom left) the same for the clustering coefficient $\overline{C}$ and (bottom right) the inverse of the number of vertices, $\frac{1}{n}$, for comparison.