(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) 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.
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...