^{1}, Dong-Hee Kim

^{2}and Adilson E. Motter

^{3}

### Abstract

Networkmodeling based on ensemble averages tacitly assumes that the networks meant to be modeled are typical in the ensemble. Previous research on networkeigenvalues, which govern a range of dynamical phenomena, has shown that this is indeed the case for uncorrelated networks with minimum degree ≥ 3. Here, we focus on real networks, which generally have both structural correlations and low-degree nodes. We show that: (i) the ensemble distribution of the dynamically most important eigenvalues can be not only broad and far apart from the real eigenvalue but also highly structured, often with a multimodal rather than a bell-shaped form; (ii) these interesting properties are found to be due to low-degree nodes, mainly those with degree ≤ 3, and network communities, which is a common form of structural correlation found in real networks. In addition to having implications for ensemble-based approaches, this shows that low-degree nodes may have a stronger influence on collective dynamics than previously anticipated from the study of computer-generated networks.

In the networkmodeling of collective behavior, while one can analyze each network individually, the ideal is to draw general conclusions that can apply to an entire class of networks. However, one must ascertain under what conditions such results apply. These can be determined by considering ensembles, and many results have already been established for ensembles of random networks. It remains to be addressed, though, the extent to which random ensembles are representative of real networks. Given a real network, one can define an associated ensemble as the set of all possible realizations of the network in which one or more parameters, represented by

*p*

_{1},…,

*p*

_{ n }, are preserved. In one extreme there is , where one only fixes the number

*N*of nodes, so that the real network could be very dissimilar from most ensemble elements. In the opposite extreme there is , where all possible parameters are fixed, but this is equivalent to studying the original network. An important goal is to restrict as few of the parameters as possible while still capturing the essential features of the real network. This is fundamental for the study of collective dynamics because in many network processes, including diffusion, consensus phenomena, and synchronization, the influence of the network structure is determined by the eigenvalues of a coupling matrix, which exhibit a rather convoluted dependence on simple networkproperties. Focusing primarily on the ensemble , which preserves the number of nodes and the degree sequence {

*k*

_{ i }}, we study the ensemble distribution of individual eigenvalues and the conditions under which the ensemble networks are representative of the real network.

The authors thank Jie Sun for providing feedback on the manuscript. This study was supported by the U.S. National Science Foundation under Grants No. DMS-0709212 and No. DMS-1057128 and the Academy of Finland under Grant No. 139514.

I. INTRODUCTION

II. EIGENVALUES AND EMPIRICAL NETWORKS

III. EIGENVALUE ENSEMBLE DISTRIBUTIONS

IV. ROLE OF LOW DEGREES AND ADDITIONAL NETWORK STRUCTURE

V. FINAL REMARKS

### Key Topics

- Eigenvalues
- 74.0
- Networks
- 21.0
- Statistical properties
- 8.0
- Diffusion
- 3.0
- Internet
- 2.0

## Figures

(Color online) Ensemble distributions of the extreme eigenvalues for a selection of real networks: the protein interaction network, the coauthorship network, and the power grid (Table I). The eigenvalues are (a) the smallest nonzero eigenvalue of the Laplacian, (b) the largest eigenvalue of the Laplacian, (c) the largest eigenvalue of the adjacency matrix, (d) the smallest nonzero eigenvalue of the normalized Laplacian, and (e) the largest eigenvalue of the normalized Laplacian. Tilde is used to indicate that the distributions are rescaled as to have zero averages and unit variances, where is the average and *σ* _{ x } is the standard deviation of the original distribution *P*(*x*) of an eigenvalue *x*. The arrows (top) indicate the positions of the real extreme eigenvalues that lie within the range of the plot, clearly showing that in most cases the real network is not “typical” within the random ensemble.

(Color online) Ensemble distributions of the extreme eigenvalues for a selection of real networks: the protein interaction network, the coauthorship network, and the power grid (Table I). The eigenvalues are (a) the smallest nonzero eigenvalue of the Laplacian, (b) the largest eigenvalue of the Laplacian, (c) the largest eigenvalue of the adjacency matrix, (d) the smallest nonzero eigenvalue of the normalized Laplacian, and (e) the largest eigenvalue of the normalized Laplacian. Tilde is used to indicate that the distributions are rescaled as to have zero averages and unit variances, where is the average and *σ* _{ x } is the standard deviation of the original distribution *P*(*x*) of an eigenvalue *x*. The arrows (top) indicate the positions of the real extreme eigenvalues that lie within the range of the plot, clearly showing that in most cases the real network is not “typical” within the random ensemble.

(Color online) Effect of low-degree nodes on ensemble distributions for the Internet and the network of political blogs. The distributions correspond to (a, c) the smallest nonzero eigenvalue of the Laplacian and (b, d) the smallest nonzero eigenvalue of the normalized Laplacian. The distribution for the largest eigenvalue of the normalized Laplacian is essentially undistinguishable from the latter and is not shown. Dotted lines indicate the distributions associated with the original real networks, and continuous lines indicate the distributions for the corresponding 3-cores of the networks. All distributions are rescaled as in Fig. 1. In most cases, the ensemble distributions for the 3-cores are significantly smoother than for the original networks, indicating that at least part of the observed structures is due to low-degree nodes.

(Color online) Effect of low-degree nodes on ensemble distributions for the Internet and the network of political blogs. The distributions correspond to (a, c) the smallest nonzero eigenvalue of the Laplacian and (b, d) the smallest nonzero eigenvalue of the normalized Laplacian. The distribution for the largest eigenvalue of the normalized Laplacian is essentially undistinguishable from the latter and is not shown. Dotted lines indicate the distributions associated with the original real networks, and continuous lines indicate the distributions for the corresponding 3-cores of the networks. All distributions are rescaled as in Fig. 1. In most cases, the ensemble distributions for the 3-cores are significantly smoother than for the original networks, indicating that at least part of the observed structures is due to low-degree nodes.

(Color online) Example of the network structure contributing to the fluctuations in the distribution *P*(*λ* _{2}) associated with the network of political blogs. The subgraph shown highlights the relevant part of an ensemble network at the second peak (left to right) of the 3-core random ensemble in Fig. 2(c). The positions of the peaks in the distribution can be estimated by considering only the submatrix of the Laplacian that includes the links between the two low-degree nodes (*α* and *β*) and their neighbors (solid lines).

(Color online) Example of the network structure contributing to the fluctuations in the distribution *P*(*λ* _{2}) associated with the network of political blogs. The subgraph shown highlights the relevant part of an ensemble network at the second peak (left to right) of the 3-core random ensemble in Fig. 2(c). The positions of the peaks in the distribution can be estimated by considering only the submatrix of the Laplacian that includes the links between the two low-degree nodes (*α* and *β*) and their neighbors (solid lines).

(Color online) Network structure effecting the extreme eigenvalues *λ* _{2} and *μ* _{2}. (a) Community structure found in the word network. (b) Model network with 50 nodes, consisting of two clusters connected to each other by a single link. The randomization of the whole network without preserving the clusters tends to increase the smallest nonzero eigenvalues of the Laplacian and normalized Laplacian.

(Color online) Network structure effecting the extreme eigenvalues *λ* _{2} and *μ* _{2}. (a) Community structure found in the word network. (b) Model network with 50 nodes, consisting of two clusters connected to each other by a single link. The randomization of the whole network without preserving the clusters tends to increase the smallest nonzero eigenvalues of the Laplacian and normalized Laplacian.

## Tables

Real networks considered in this study. The columns show basic properties of the real networks as well as the extreme eigenvalues, the corresponding spectral positions Δ_{ x }, and the standard deviations *σ* _{ x } of the random ensembles (see Sec. III). The basic properties are the number of nodes *N*, the average degree , and the maximum degree *k* _{ N }. The minimum degree *k* _{1} is one for all networks. In each case, we focus on the largest connected component of the real network. In the *k*-core test with *k* = 2 and *k* = 3, the percentage of remaining nodes is *q* _{2} and *q* _{3}, respectively. A summary of the 3-core tests is given as superscripted symbols, where † indicates an originally structured eigenvalue distribution that becomes unimodal in the 3-core networks, while those with * are still structured in the 3-core networks. No symbol is specified for non-structured distributions in the original random ensemble.

Real networks considered in this study. The columns show basic properties of the real networks as well as the extreme eigenvalues, the corresponding spectral positions Δ_{ x }, and the standard deviations *σ* _{ x } of the random ensembles (see Sec. III). The basic properties are the number of nodes *N*, the average degree , and the maximum degree *k* _{ N }. The minimum degree *k* _{1} is one for all networks. In each case, we focus on the largest connected component of the real network. In the *k*-core test with *k* = 2 and *k* = 3, the percentage of remaining nodes is *q* _{2} and *q* _{3}, respectively. A summary of the 3-core tests is given as superscripted symbols, where † indicates an originally structured eigenvalue distribution that becomes unimodal in the 3-core networks, while those with * are still structured in the 3-core networks. No symbol is specified for non-structured distributions in the original random ensemble.

Article metrics loading...

Full text loading...

Commenting has been disabled for this content