Eigenvalue spectra of complex networks

Path-integral approach to sparse non-Hermitian random matrices

The theory of large random matrices has proved an invaluable tool for the study of systems with disordered interactions in many quite disparate research areas. Widely applicable results, such as the celebrated elliptic law for dense random matrices, allow one to deduce the statistical properties of the interactions in a complex dynamical system that permit stability. However, such simple and universal results have so far proved difficult to come by in the case of sparse random matrices. Here, we perform an expansion in the inverse connectivity, and thus derive general modified versions of the classic elliptic and semicircle laws, taking into account the sparse correction. This is accomplished using a dynamical approach, which maps the hermitized resolvent of a random matrix onto the response functions of a linear dynamical system. The response functions are then evaluated using a path integral formalism, enabling one to construct Feynman diagrams, which facilitate the perturbative analysis. Additionally, in order to demonstrate the broad utility of the path integral framework, we derive a generic non-Hermitian generalization of the Marchenko-Pastur law, and we also show how one can handle non-negligible higher-order statistics (i.e., non-Gaussian statistics) in dense ensembles.

Effects of clustering heterogeneity on the spectral density of sparse networks

We derive exact equations for the spectral density of sparse networks with an arbitrary distribution of the number of single edges and triangles per node. These equations enable a systematic investigation of the effects of clustering on the spectral properties of the network adjacency matrix. In the case of heterogeneous networks, we demonstrate that the spectral density becomes more symmetric as the fluctuations in the triangle-degree sequence increase. This phenomenon is explained by the small clustering coefficient of networks with a large variance of the triangle-degree distribution. In the homogeneous case of regular clustered networks, we find that both perturbative and nonperturbative approximations fail to predict the spectral density in the high-connectivity limit. This suggests that traditional large-degree approximations may be ineffective in studying the spectral properties of networks with more complex motifs. Our theoretical results are fully confirmed by numerical diagonalizations of finite adjacency matrices.

Eigenvalue spectra and stability of directed complex networks

Quantifying the eigenvalue spectra of large random matrices allows one to understand the factors that contribute to the stability of dynamical systems with many interacting components. This work explores the effect that the interaction network between components has on the eigenvalue spectrum. We build on previous results, which usually only take into account the mean degree of the network, by allowing for nontrivial network degree heterogeneity. We derive closed-form expressions for the eigenvalue spectrum of the adjacency matrix of a general weighted and directed network. Using these results, which are valid for any large well-connected complex network, we then derive compact formulas for the corrections (due to nonzero network heterogeneity) to well-known results in random matrix theory. Specifically, we derive modified versions of the Wigner semicircle law, the Girko circle law, and the elliptic law and any outlier eigenvalues. We also derive a surprisingly neat analytical expression for the eigenvalue density of a directed Barabási-Albert network. We are thus able to deduce that network heterogeneity is mostly a destabilizing influence in complex dynamical systems.

Spectral properties of complex networks

This review presents an account of the major works done on spectra of adjacency matrices drawn on networks and the basic understanding attained so far. We have divided the review under three sections: (a) extremal eigenvalues, (b) bulk part of the spectrum, and (c) degenerate eigenvalues, based on the intrinsic properties of eigenvalues and the phenomena they capture. We have reviewed the works done for spectra of various popular model networks, such as the Erdős-Rényi random networks, scale-free networks, 1-d lattice, small-world networks, and various different real-world networks. Additionally, potential applications of spectral properties for natural processes have been reviewed.

Localization in random bipartite graphs: Numerical and empirical study

We investigate adjacency matrices of bipartite graphs with a power-law degree distribution. Motivation for this study is twofold: first, vibrational states in granular matter and jammed sphere packings; second, graphs encoding social interaction, especially electronic commerce. We establish the position of the mobility edge and show that it strongly depends on the power in the degree distribution and on the ratio of the sizes of the two parts of the bipartite graph. At the jamming threshold, where the two parts have the same size, localization vanishes. We found that the multifractal spectrum is nontrivial in the delocalized phase, but still near the mobility edge. We also study an empirical bipartite graph, namely, the Amazon reviewer-item network. We found that in this specific graph the mobility edge disappears, and we draw a conclusion from this fact regarding earlier empirical studies of the Amazon network.

Collective relaxation dynamics of small-world networks

Complex networks exhibit a wide range of collective dynamic phenomena, including synchronization, diffusion, relaxation, and coordination processes. Their asymptotic dynamics is generically characterized by the local Jacobian, graph Laplacian, or a similar linear operator. The structure of networks with regular, small-world, and random connectivities are reasonably well understood, but their collective dynamical properties remain largely unknown. Here we present a two-stage mean-field theory to derive analytic expressions for network spectra. A single formula covers the spectrum from regular via small-world to strongly randomized topologies in Watts-Strogatz networks, explaining the simultaneous dependencies on network size N, average degree k, and topological randomness q. We present simplified analytic predictions for the second-largest and smallest eigenvalue, and numerical checks confirm our theoretical predictions for zero, small, and moderate topological randomness q, including the entire small-world regime. For large q of the order of one, we apply standard random matrix theory, thereby overarching the full range from regular to randomized network topologies. These results may contribute to our analytic and mechanistic understanding of collective relaxation phenomena of network dynamical systems.

Universality in the spectral and eigenfunction properties of random networks

By the use of extensive numerical simulations, we show that the nearest-neighbor energy-level spacing distribution P(s) and the entropic eigenfunction localization length of the adjacency matrices of Erdős-Rényi (ER) fully random networks are universal for fixed average degree ξ≡αN (α and N being the average network connectivity and the network size, respectively). We also demonstrate that the Brody distribution characterizes well P(s) in the transition from α=0, when the vertices in the network are isolated, to α=1, when the network is fully connected. Moreover, we explore the validity of our findings when relaxing the randomness of our network model and show that, in contrast to standard ER networks, ER networks with diagonal disorder also show universality. Finally, we also discuss the spectral and eigenfunction properties of small-world networks.

Scattering and transport properties of tight-binding random networks

We study numerically scattering and transport statistical properties of tight-binding random networks characterized by the number of nodes N and the average connectivity α. We use a scattering approach to electronic transport and concentrate on the case of a small number of single-channel attached leads. We observe a smooth crossover from insulating to metallic behavior in the average scattering matrix elements <|S(mn)|(2)>, the conductance probability distribution w(T), the average conductance <T>, the shot noise power P, and the elastic enhancement factor F by varying α from small (α→0) to large (α→1) values. We also show that all these quantities are invariant for fixed ξ=αN. Moreover, we proposes a heuristic and universal relation between <|S(mn)|(2)>, <T>, and P and the disorder parameter ξ.

Robustness of random graphs based on graph spectra

It has been recently proposed that the robustness of complex networks can be efficiently characterized through the natural connectivity, a spectral property of the graph which corresponds to the average Estrada index. The natural connectivity corresponds to an average eigenvalue calculated from the graph spectrum and can also be interpreted as the Helmholtz free energy of the network. In this article, we explore the use of this index to characterize the robustness of Erdős-Rényi (ER) random graphs, random regular graphs, and regular ring lattices. We show both analytically and numerically that the natural connectivity of ER random graphs increases linearly with the average degree. It is also shown that ER random graphs are more robust than the corresponding random regular graphs with the same number of vertices and edges. However, the relative robustness of ER random graphs and regular ring lattices depends on the average degree and graph size: there is a critical graph size above which regular ring lattices are more robust than random graphs. We use our analytical results to derive this critical graph size as a function of the average degree.

Predicting atrial fibrillation inducibility in a canine model by multi-threshold spectra of the recurrence complex network

The purpose of this study is to predict atrial fibrillation (AF) from epicardial signals by investigating the recurrence property of atrial activity dynamic system before AF. A novel scheme is proposed to predict AF by using multi-threshold spectra of the recurrence complex network. Firstly, epicardial signals are transformed into the recurrence complex network to quantify structural properties of the recurrence in the phase space. Spectral parameters with multi-threshold are used to characterize the global structure of the network. Then the feature sequential forward searching algorithm and mutual information based Maximum Relevance Minimum Redundancy criterion are used to find the optimal feature set. Finally, a support vector machine is used to predict the occurrence of AF. This method is assessed on the pre-AF epicardial signals of canine which includes the normal group A (no further AF will happen), the mild group B (the following AF time is less than 180s) and the severe group C (the following AF time is more than 180s). 25 optimal features are selected out of 180 features from each sample. With these features, sensitivity, specificity and accuracy are 99.40%, 99.70% and 99.60%, respectively, which are the best among the recurrence based methods. The results suggest that the proposed method can predict AF accurately and thus can be prospectively used in the postoperative evaluation.

Equivalence of replica and cavity methods for computing spectra of sparse random matrices

We show by direct calculation that the replica and cavity methods are exactly equivalent for the spectrum of an Erdős-Rényi random graph. We introduce a variational formulation based on the cavity method and use it to find approximate solutions for the density of eigenvalues. We also use this variational method for calculating spectra of sparse covariance matrices.

Spectral and dynamical properties in classes of sparse networks with mesoscopic inhomogeneities

We study structure, eigenvalue spectra, and random-walk dynamics in a wide class of networks with subgraphs (modules) at mesoscopic scale. The networks are grown within the model with three parameters controlling the number of modules, their internal structure as scale-free and correlated subgraphs, and the topology of connecting network. Within the exhaustive spectral analysis for both the adjacency matrix and the normalized Laplacian matrix we identify the spectral properties, which characterize the mesoscopic structure of sparse cyclic graphs and trees. The minimally connected nodes, the clustering, and the average connectivity affect the central part of the spectrum. The number of distinct modules leads to an extra peak at the lower part of the Laplacian spectrum in cyclic graphs. Such a peak does not occur in the case of topologically distinct tree subgraphs connected on a tree whereas the associated eigenvectors remain localized on the subgraphs both in trees and cyclic graphs. We also find a characteristic pattern of periodic localization along the chains on the tree for the eigenvector components associated with the largest eigenvalue lambda(L)=2 of the Laplacian. Further differences between the cyclic modular graphs and trees are found by the statistics of random walks return times and hitting patterns at nodes on these graphs. The distribution of first-return times averaged over all nodes exhibits a stretched exponential tail with the exponent sigma approximately 1/3 for trees and sigma approximately 2/3 for cyclic graphs, which is independent of their mesoscopic and global structure.

Spectral characteristics of network redundancy

Many real-world complex networks contain a significant amount of structural redundancy, in which multiple vertices play identical topological roles. Such redundancy arises naturally from the simple growth processes which form and shape many real-world systems. Since structurally redundant elements may be permuted without altering network structure, redundancy may be formally investigated by examining network automorphism (symmetry) groups. Here, we use a group-theoretic approach to give a complete description of spectral signatures of redundancy in undirected networks. In particular, we describe how a network's automorphism group may be used to directly associate specific eigenvalues and eigenvectors with specific network motifs.

Ensemble averageability in network spectra

The extreme eigenvalues of connectivity matrices govern the influence of the network structure on a number of network dynamical processes. A fundamental open question is whether the eigenvalues of large networks are well represented by ensemble averages. Here we investigate this question explicitly and validate the concept of ensemble averageability in random scale-free networks by showing that the ensemble distributions of extreme eigenvalues converge to peaked distributions as the system size increases. We discuss the significance of this result using synchronization and epidemic spreading as example processes.

Extreme fluctuations in noisy task-completion landscapes on scale-free networks

We study the statistics and scaling of extreme fluctuations in noisy task-completion landscapes, such as those emerging in synchronized distributed-computing networks, or generic causally constrained queuing networks, with scale-free topology. In these networks the average size of the fluctuations becomes finite (synchronized state) and the extreme fluctuations typically diverge only logarithmically in the large system-size limit ensuring synchronization in a practical sense. Provided that local fluctuations in the network are short tailed, the statistics of the extremes are governed by the Gumbel distribution. We present large-scale simulation results using the exact algorithmic rules, supported by mean-field arguments based on a coarse-grained description.

Spectral densities of scale-free networks

The spectral densities of the weighted Laplacian, random walk, and weighted adjacency matrices associated with a random complex network are studied using the replica method. The link weights are parametrized by a weight exponent beta. Explicit results are obtained for scale-free networks in the limit of large mean degree after the thermodynamic limit, for arbitrary degree exponent and beta.

Synchronization in weighted uncorrelated complex networks in a noisy environment: optimization and connections with transport efficiency

Motivated by synchronization problems in noisy environments, we study the Edwards-Wilkinson process on weighted uncorrelated scale-free networks. We consider a specific form of the weights, where the strength (and the associated cost) of a link is proportional to (kikj)beta with ki and kj being the degrees of the nodes connected by the link. Subject to the constraint that the total edge cost is fixed, we find that in the mean-field approximation on uncorrelated scale-free graphs, synchronization is optimal at beta*= -1 . Numerical results, based on exact numerical diagonalization of the corresponding network Laplacian, confirm the mean-field results, with small corrections to the optimal value of beta*. Employing our recent connections between the Edwards-Wilkinson process and resistor networks, and some well-known connections between random walks and resistor networks, we also pursue a naturally related problem of optimizing performance in queue-limited communication networks utilizing local weighted routing schemes.