Thresholding normally distributed data creates complex networks

Network data sets are often constructed by some kind of thresholding procedure. The resulting networks frequently possess properties such as heavy-tailed degree distributions, clustering, large connected components, and short average shortest path lengths. These properties are considered typical of complex networks and appear in many contexts, prompting consideration of their universality. Here we introduce a simple model for correlated relational data and study the network ensemble obtained by thresholding it. We find that some, but not all, of the properties associated with complex networks can be seen after thresholding the correlated data, even though the underlying data are not “complex.” In particular, we observe heavy-tailed degree distributions, a large numbers of triangles, and short path lengths, while we do not observe nonvanishing clustering or community structure.

Figure 1

Thresholding relational data to obtain networks. Panel (a) shows a general procedure to obtain unweighted networks from edge weights. Each edge weight is hypothesized to have been drawn from a specific distribution, generating an undirected weighted network. An unweighted network is then produced by assigning an edge whenever an edge weight $X_{ij}$ is greater than a threshold $t$. In panel (b) we show how edge weights are correlated in the model of Sec. 2 by covariance matrix $\mathit{\Sigma }$ [Eq. (5)]. Edge weights for edges that connect through a node have covariance $\mathrm{Cov}\left[X_{ij}{X}_{ik}\right]=\rho$, while edge weights not connected by a node have zero covariance.

Figure 2

Clustering $C$ and triangles per node $T$ as computed in Sec. 3b. Clustering decreases with increasing number of nodes, however the number of triangles per node increases with a growing number of nodes $n$ for large values of $\rho$. Clustering increases both with increasing mean degree $〈k〉$ and local edge weight correlation $\rho$. In panels (a) and (c) we chose $n=100000$ and in panels (b) and (d) we fixed $〈k〉=4$.

Figure 3

The variance of degree, Eq. (18), increases with $\rho$, the local edge weight correlation. With increasing mean degree $〈k〉$, even small correlations $\rho$ produce networks of significantly broader degree distribution than the random graph $G_{n,p}$.

Figure 4

We show degree distributions computed using Eq. (19) for $n=100000$ and $〈k〉=100$ for increasing local edge weight correlation $\rho$ in log-log (a) and linear scales (b). We also compare them to the asymptotic approximation Eq. (22). Note that large values of $\rho$ produce broad degree distributions, which could be easily mistaken for log-normal or power-law distributions.

Figure 5

Degree histograms for the three real-world networks introduced in Sec. 3c along with fitted distributions from the thresholded normal model. We show (a) a high school friendship network, (b) a coauthorship network between scientists, and (c) a protein-protein interaction network.

Figure 6

Simulations with $1000\le n\le 30000$, mean degree ${10}^{-3}\le 〈k〉\le 10, 0\le \rho \le 0.45$. 1000 samples were taken for each of the parameter combinations. Panel (a) shows the points of transitions for an increasing number of nodes $n$. To the left of the line, the network does not possess a giant component, while to the right it does. The transition point was computed using the mean size of the second largest component as a susceptibility parameter. Panel (b) shows an example of the susceptibility parameter for $n=10000$.

Figure 7

Panel (a) shows the scaling of the average shortest path in the largest connected component with the number of nodes, $n$. We fix the mean degree $〈k〉=5$, and each point is averaged over 200 samples. For $\rho =0$ we recover the result for the random graph $G_{n,p}$, where $〈d_{ij}〉\propto logn$. For nonzero correlation, the average shortest path length increases slower than logarithmically. In panel (b) we show the average shortest path length for different mean degrees and values of $\rho$ for networks with $n=10000$, again sampled 200 times for each parameter combination.

Figure 8

Local clustering coefficient and average neighbor degree for the three real-world networks introduced in Sec. 3c along with simulated results from the thresholded normal model. We show (a) a high school friendship network, (b) a co-authorship network between scientists, and (c) a protein–protein interaction network.

Figure 9

Simulations for the disparity filter [11] applied to $e^{X_{ij}}$. Networks with 2,000 nodes were created by first sampling matrices $\mathit{X}$ from a normal distribution and then applying the disparity filter to $e^{X_{ij}}$. Three different values for $\rho$ were used and $\alpha$ was set using Eq. (E5) so that the final network would have a mean degree of 4.