Spectra of "real-world" graphs: beyond the semicircle law

Origin and implications of zero degeneracy in networks spectra

The spectra of many real world networks exhibit properties which are different from those of random networks generated using various models. One such property is the existence of a very high degeneracy at the zero eigenvalue. In this work, we provide all the possible reasons behind the occurrence of the zero degeneracy in the network spectra, namely, the complete and partial duplications, as well as their implications. The power-law degree sequence and the preferential attachment are the properties which enhances the occurrence of such duplications and hence leading to the zero degeneracy. A comparison of the zero degeneracy in protein-protein interaction networks of six different species and in their corresponding model networks indicates importance of the degree sequences and the power-law exponent for the occurrence of zero degeneracy.

Finding communities in sparse networks

Spectral algorithms based on matrix representations of networks are often used to detect communities, but classic spectral methods based on the adjacency matrix and its variants fail in sparse networks. New spectral methods based on non-backtracking random walks have recently been introduced that successfully detect communities in many sparse networks. However, the spectrum of non-backtracking random walks ignores hanging trees in networks that can contain information about their community structure. We introduce the reluctant backtracking operators that explicitly account for hanging trees as they admit a small probability of returning to the immediately previous node, unlike the non-backtracking operators that forbid an immediate return. We show that the reluctant backtracking operators can detect communities in certain sparse networks where the non-backtracking operators cannot, while performing comparably on benchmark stochastic block model networks and real world networks. We also show that the spectrum of the reluctant backtracking operator approximately optimises the standard modularity function. Interestingly, for this family of non- and reluctant-backtracking operators the main determinant of performance on real-world networks is whether or not they are normalised to conserve probability at each node.

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.

Toward link predictability of complex networks

The organization of real networks usually embodies both regularities and irregularities, and, in principle, the former can be modeled. The extent to which the formation of a network can be explained coincides with our ability to predict missing links. To understand network organization, we should be able to estimate link predictability. We assume that the regularity of a network is reflected in the consistency of structural features before and after a random removal of a small set of links. Based on the perturbation of the adjacency matrix, we propose a universal structural consistency index that is free of prior knowledge of network organization. Extensive experiments on disparate real-world networks demonstrate that (i) structural consistency is a good estimation of link predictability and (ii) a derivative algorithm outperforms state-of-the-art link prediction methods in both accuracy and robustness. This analysis has further applications in evaluating link prediction algorithms and monitoring sudden changes in evolving network mechanisms. It will provide unique fundamental insights into the above-mentioned academic research fields, and will foster the development of advanced information filtering technologies of interest to information technology practitioners.

Assortative and disassortative mixing investigated using the spectra of graphs

We investigate the impact of degree-degree correlations on the spectra of networks. Even though density distributions exhibit drastic changes depending on the (dis)assortative mixing and the network architecture, the short-range correlations in eigenvalues exhibit universal random matrix theory predictions. The long-range correlations turn out to be a measure of randomness in (dis)assortative networks. The analysis further provides insight into the origin of high degeneracy at the zero eigenvalue displayed by a majority of biological networks.

Localization and centrality in networks

Eigenvector centrality is a common measure of the importance of nodes in a network. Here we show that under common conditions the eigenvector centrality displays a localization transition that causes most of the weight of the centrality to concentrate on a small number of nodes in the network. In this regime the measure is no longer useful for distinguishing among the remaining nodes and its efficacy as a network metric is impaired. As a remedy, we propose an alternative centrality measure based on the nonbacktracking matrix, which gives results closely similar to the standard eigenvector centrality in dense networks where the latter is well behaved but avoids localization and gives useful results in regimes where the standard centrality fails.

Heterogeneity in ecological mutualistic networks dominantly determines community stability

Although the hypothesis that nestedness determines mutualistic ecosystem dynamics is accepted in general, results of some recent data analyses and theoretical studies have begun to cast doubt on the impact of nestedness on ecosystem stability. However, definite conclusions have not yet been reached because previous studies are mainly based on numerical simulations. Therefore, we reveal a mathematical architecture in the relationship between ecological mutualistic networks and local stability based on spectral graph analysis. In particular, we propose a theoretical method for estimating the dominant eigenvalue (i.e., spectral radius) of quantitative (or weighted) bipartite networks by extending spectral graph theory, and provide a theoretical prediction that the heterogeneity of node degrees and link weights primarily determines the local stability; on the other hand, nestedness additionally affects it. Numerical simulations demonstrate the validity of our theory and prediction. This study emphasizes the importance of ecological network heterogeneity in ecosystem dynamics, and it enhances our understanding of structure–stability relationships.

Full eigenvalues of the Markov matrix for scale-free polymer networks

Much important information about the structural and dynamical properties of complex systems can be extracted from the eigenvalues and eigenvectors of a Markov matrix associated with random walks performed on these systems, and spectral methods have become an indispensable tool in the complex system analysis. In this paper, we study the Markov matrix of a class of scale-free polymer networks. We present an exact analytical expression for all the eigenvalues and determine explicitly their multiplicities. We then use the obtained eigenvalues to derive an explicit formula for the random target access time for random walks on the studied networks. Furthermore, based on the link between the eigenvalues of the Markov matrix and the number of spanning trees, we confirm the validity of the obtained eigenvalues and their corresponding degeneracies.

Spectra of random graphs with community structure and arbitrary degrees

Using methods from random matrix theory researchers have recently calculated the full spectra of random networks with arbitrary degrees and with community structure. Both reveal interesting spectral features, including deviations from the Wigner semicircle distribution and phase transitions in the spectra of community structured networks. In this paper we generalize both calculations, giving a prescription for calculating the spectrum of a network with both community structure and an arbitrary degree distribution. In general the spectrum has two parts, a continuous spectral band, which can depart strongly from the classic semicircle form, and a set of outlying eigenvalues that indicate the presence of communities.

Structure and Overlaps of Ground-Truth Communities in Networks

One of the main organizing principles in real-world networks is that of network communities , where sets of nodes organize into densely linked clusters. Even though detection of such communities is of great interest, understanding the structure communities in large networks remains relatively limited. In particular, due to the unavailability of labeled ground-truth data, it was traditionally very hard to develop accurate models of network community structure.

Here we use six large social, collaboration, and information networks where nodes explicitly state their ground-truth community memberships. For example, nodes in social networks join into explicitly defined interest based groups, and we use such groups as explicitly labeled ground-truth communities. We use such ground-truth communities to study their structural signatures by analyzing how ground-truth communities emerge in networks and how they overlap. We observe some surprising phenomena. First, ground-truth communities contain high-degree hub nodes that reside in community overlaps and link to most of the members of the community. Second, the overlaps of communities are more densely connected than the non-overlapping parts of communities. We show that this in contrast to the conventional wisdom that community overlaps are more sparsely connected than the non-overlapping parts themselves. We then show that many existing models of network communities do not capture dense community overlaps. This in turn means that most present models and community detection methods confuse overlaps as separate communities. In contrast, we present the community-affiliation graph model (AGM), a conceptual model of network community structure. We demonstrate that AGM reliably captures the overall structure of networks as well as the overlapping and hierarchical nature of network communities.

Topological analyses and small-world patterns of hydrogen bond networks in water + t-butanol, water + n-butanol and water + ammonia mixtures

H-bond networks in aqueous mixtures obtained by Monte Carlo simulations and analyzed by statistical mechanics based tools revealed small-word patterns.

Spectral Characterization of Hierarchical Modularity in Product Architectures

Despite the importance of the architectural modularity of products and systems, existing modularity metrics or algorithms do not account for overlapping and hierarchically embedded modules. This paper presents a graph theoretic spectral approach to characterize the degree of modular hierarchical-overlapping organization in the architecture of products and complex engineered systems. It is shown that the eigenvalues of the adjacency matrix of a product architecture graph can reveal layers of hidden modular or hierarchical modular organization that are not immediately visible in the predefined architectural description. We use the approach to analyze and discuss several design, management, and system resilience implications for complex engineered systems.

Extracting connectivity from dynamics of networks with uniform bidirectional coupling

In the study of networked systems, a method that can extract information about how the individual nodes are connected with one another would be valuable. In this paper, we present a method that can yield such information of network connectivity using measurements of the dynamics of the nodes as the only input data. Our method is built upon a noise-induced relation between the Laplacian matrix of the network and the dynamical covariance matrix of the nodes, and applies to networked dynamical systems in which the coupling between nodes is uniform and bidirectional. Using examples of different networks and dynamics, we demonstrate that the method can give accurate connectivity information for a wide range of noise amplitude and coupling strength. Moreover, we can calculate a parameter Δ using again only the input of time-series data, and assess the accuracy of the extracted connectivity information based on the value of Δ.

Topological Strata of Weighted Complex Networks

The statistical mechanical approach to complex networks is the dominant paradigm in describing natural and societal complex systems. The study of network properties, and their implications on dynamical processes, mostly focus on locally defined quantities of nodes and edges, such as node degrees, edge weights and -more recently- correlations between neighboring nodes. However, statistical methods quickly become cumbersome when dealing with many-body properties and do not capture the precise mesoscopic structure of complex networks. Here we introduce a novel method, based on persistent homology, to detect particular non-local structures, akin to weighted holes within the link-weight network fabric, which are invisible to existing methods. Their properties divide weighted networks in two broad classes: one is characterized by small hierarchically nested holes, while the second displays larger and longer living inhomogeneities. These classes cannot be reduced to known local or quasilocal network properties, because of the intrinsic non-locality of homological properties, and thus yield a new classification built on high order coordination patterns. Our results show that topology can provide novel insights relevant for many-body interactions in social and spatial networks. Moreover, this new method creates the first bridge between network theory and algebraic topology, which will allow to import the toolset of algebraic methods to complex systems.

Linking human brain local activity fluctuations to structural and functional network architectures

Activity of cortical local neuronal populations fluctuates continuously, and a large proportion of these fluctuations are shared across populations of neurons. Here we seek organizational rules that link these two phenomena. Using neuronal activity, as identified by functional MRI (fMRI) and for a given voxel or brain region, we derive a single measure of full bandwidth brain-oxygenation-level-dependent (BOLD) fluctuations by calculating the slope, α, for the log-linear power spectrum. For the same voxel or region, we also measure the temporal coherence of its fluctuations to other voxels or regions, based on exceeding a given threshold, Θ, for zero lag correlation, establishing functional connectivity between pairs of neuronal populations. From resting state fMRI, we calculated whole-brain group-averaged maps for α and for functional connectivity. Both maps showed similar spatial organization, with a correlation coefficient of 0.75 between the two parameters across all brain voxels, as well as variability with hodology. A computational model replicated the main results, suggesting that synaptic low-pass filtering can account for these interrelationships. We also investigated the relationship between α and structural connectivity, as determined by diffusion tensor imaging-based tractography. We observe that the correlation between α and connectivity depends on attentional state; specifically, α correlated more highly to structural connectivity during rest than while attending to a task. Overall, these results provide global rules for the dynamics between frequency characteristics of local brain activity and the architecture of underlying brain networks.

Spectral characterization of hierarchical network modularity and limits of modularity detection

Many real world networks are reported to have hierarchically modular organization. However, there exists no algorithm-independent metric to characterize hierarchical modularity in a complex system. The main results of the paper are a set of methods to address this problem. First, classical results from random matrix theory are used to derive the spectrum of a typical stochastic block model hierarchical modular network form. Second, it is shown that hierarchical modularity can be fingerprinted using the spectrum of its largest eigenvalues and gaps between clusters of closely spaced eigenvalues that are well separated from the bulk distribution of eigenvalues around the origin. Third, some well-known results on fingerprinting non-hierarchical modularity in networks automatically follow as special cases, threreby unifying these previously fragmented results. Finally, using these spectral results, it is found that the limits of detection of modularity can be empirically established by studying the mean values of the largest eigenvalues and the limits of the bulk distribution of eigenvalues for an ensemble of networks. It is shown that even when modularity and hierarchical modularity are present in a weak form in the network, they are impossible to detect, because some of the leading eigenvalues fall within the bulk distribution. This provides a threshold for the detection of modularity. Eigenvalue distributions of some technological, social, and biological networks are studied, and the implications of detecting hierarchical modularity in real world networks are discussed.

Spectra of random graphs with arbitrary expected degrees

We study random graphs with arbitrary distributions of expected degree and derive expressions for the spectra of their adjacency and modularity matrices. We give a complete prescription for calculating the spectra that is exact in the limit of large network size and large vertex degrees. We also study the effect on the spectra of hubs in the network, vertices of unusually high degree, and show that these produce isolated eigenvalues outside the main spectral band, akin to impurity states in condensed matter systems, with accompanying eigenvectors that are strongly localized around the hubs. We give numerical results that confirm our analytic expressions.

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.

Weighting for sex acts to understand the spread of STI on networks

Human sexual networks exhibit a heterogeneous structure where few individuals have many partners and many individuals have few partners. Network theory predicts that the spread of sexually transmitted infections (STI) on such networks should exhibit striking properties (e.g. rapid spread). However, these properties cannot be found in epidemiological data. Current network models typically assume a constant STI transmission risk per partnership, which is unrealistic because it implies that sexual activity is proportional to the number of partners and that individuals have the same activity with each partner. We develop a framework that allows us to weight any sexual network based on biological assumptions. Our results indicate that STI spreading on the resulting weighted networks do not have heterogeneous-related properties, which is consistent with data and earlier studies.

Small-world network spectra in mean-field theory

Collective dynamics on small-world networks emerge in a broad range of systems with their spectra characterizing fundamental asymptotic features. Here we derive analytic mean-field predictions for the spectra of small-world models that systematically interpolate between regular and random topologies by varying their randomness. These theoretical predictions agree well with the actual spectra (obtained by numerical diagonalization) for undirected and directed networks and from fully regular to strongly random topologies. These results may provide analytical insights to empirically found features of dynamics on small-world networks from various research fields, including biology, physics, engineering, and social science.

Network extreme eigenvalue: from mutimodal to scale-free networks

The extreme eigenvalues of adjacency matrices are important indicators on the influence of topological structures to the collective dynamical behavior of complex networks. Recent findings on the ensemble averageability of the extreme eigenvalue have further authenticated its applicability to the study of network dynamics. However, the ensemble average of extreme eigenvalue has only been solved analytically up to the second order correction. Here, we determine the ensemble average of the extreme eigenvalue and characterize its deviation across the ensemble through the discrete form of random scale-free network. Remarkably, the analytical approximation derived from the discrete form shows significant improvement over previous results, which implies a more accurate prediction of the epidemic threshold. In addition, we show that bimodal networks, which are more robust against both random and targeted removal of nodes, are more vulnerable to the spreading of diseases.

Spectra of sparse regular graphs with loops

We derive exact equations that determine the spectra of undirected and directed sparsely connected regular graphs containing loops of arbitrary lengths. The implications of our results for the structural and dynamical properties of network models are discussed by showing how loops influence the size of the spectral gap and the propensity for synchronization. Analytical formulas for the spectrum are obtained for specific lengths of the loops.

Localization transition in symmetric random matrices

We study the behavior of the inverse participation ratio and the localization transition in infinitely large random matrices through the cavity method. Results are shown for two ensembles of random matrices: Laplacian matrices on sparse random graphs and fully connected Lévy matrices. We derive a critical line separating localized from extended states in the case of Lévy matrices. Comparison between theoretical results and diagonalization of finite random matrices is shown.

Phase-space networks of the six-vertex model under different boundary conditions

The six-vertex model is mapped to three-dimensional sphere stacks and different boundary conditions corresponding to different containers. The shape of the container provides a qualitative visualization of the boundary effect. Based on the sphere-stacking picture, we map the phase spaces of the six-vertex models to discrete networks. A node in the network represents a state of the system, and an edge between two nodes represents a zero-energy spin flip, which corresponds to adding or removing a sphere. The network analysis shows that the phase spaces of systems with different boundary conditions share some common features. We derived a few formulas for the number and the sizes of the disconnected phase-space subnetworks under the periodic boundary conditions. The sphere stacking provides new challenges in combinatorics and may cast light on some two-dimensional models.

Spectral properties of networks with community structure

In this paper, we discuss the eigenspectra of networks with community structure. It is shown that in many cases, the spectrum of eigenvalues of the adjacency matrix of a network with community structure gives a clear indication of the number of communities in the network. In particular, for a network with N nodes and N_(c) communities, there will typically be N_(c) eigenvalues that are significantly larger than the magnitudes of all the other (N-N_(c)) eigenvalues. We discuss this property as well as its use and limitations for determining N_(c) .

Phase-space networks of geometrically frustrated systems

We illustrate a network approach to the phase-space study by using two geometrical frustration models: antiferromagnet on triangular lattice and square ice. Their highly degenerated ground states are mapped as discrete networks such that the quantitative network analysis can be applied to phase-space studies. The resulting phase spaces share some comon features and establish a class of complex networks with unique Gaussian spectral densities. Although phase-space networks are heterogeneously connected, the systems are still ergodic due to the random Poisson processes. This network approach can be generalized to phase spaces of some other complex systems.

Models of cortical networks with long-range patchy projections

The cortex exhibits an intricate vertical and horizontal architecture, the latter often featuring spatially clustered projection patterns, so-called patches. Many network studies of cortical dynamics ignore such spatial structures and assume purely random wiring. Here, we focus on non-random network structures provided by long-range horizontal (patchy) connections that remain inside the gray matter. We investigate how the spatial arrangement of patchy projections influences global network topology and predict its impact on the activity dynamics of the network. Since neuroanatomical data on horizontal projections is rather sparse, we suggest and compare four candidate scenarios of how patchy connections may be established. To identify a set of characteristic network properties that enables us to pin down the differences between the resulting network models, we employ the framework of stochastic graph theory. We find that patchy projections provide an exceptionally efficient way of wiring, as the resulting networks tend to exhibit small-world properties with significantly reduced wiring costs. Furthermore, the eigenvalue spectra, as well as the structure of common in- and output of the networks suggest that different spatial connectivity patterns support distinct types of activity propagation.

Sick and edgy: walk-counting as a metric of epidemic spreading on networks

A network structure metric is herein suggested for the investigation of the behaviour of epidemic spreading processes in general network-structured populations. This simple measure, based on the algebraic powers of the adjacency matrix associated with the network in question, is shown to admit a heuristic interpretation as a representation of a spreading process similar to standard epidemic models. It is further shown that the values of this metric may be of use in understanding the dynamic pattern of epidemic spread on networks of greatly varying structural properties (e.g. the degree distribution, the assortativity/dissortativity and the clustering).

Spectral analysis of deformed random networks

We study spectral behavior of sparsely connected random networks under the random matrix framework. Subnetworks without any connection among them form a network having perfect community structure. As connections among the subnetworks are introduced, the spacing distribution shows a transition from the Poisson statistics to the Gaussian orthogonal ensemble statistics of random matrix theory. The eigenvalue density distribution shows a transition to the Wigner's semicircular behavior for a completely deformed network. The range for which spectral rigidity, measured by the Dyson-Mehta Delta3 statistics, follows the Gaussian orthogonal ensemble statistics depends upon the deformation of the network from the perfect community structure. The spacing distribution is particularly useful to track very slight deformations of the network from a perfect community structure, whereas the density distribution and the Delta3 statistics remain identical to the undeformed network. On the other hand the Delta3 statistics is useful for the larger deformation strengths. Finally, we analyze the spectrum of a protein-protein interaction network for Helicobacter, and compare the spectral behavior with those of the model networks.

Eigenvalue spectra of spatial-dependent networks

Many real-life networks exhibit a spatial dependence; i.e., the probability to form an edge between two nodes in the network depends on the distance between them. We investigate the influence of spatial dependence on the spectral density of the network. When increasing spatial dependence in Erdös-Rényi, scale-free, and small-world networks, it is found that the spectrum changes. Due to the spatial dependence the degree of clustering and the number of triangles increase. This results in a higher asymmetry (skewness). Our results show that the spectrum can be used to detect and quantify clustering and spatial dependence in a network.

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.

Delocalization transition for the Google matrix

We study the localization properties of eigenvectors of the Google matrix, generated both from the world wide web and from the Albert-Barabási model of networks. We establish the emergence of a delocalization phase for the PageRank vector when network parameters are changed. For networks with localized PageRank, eigenvalues of the matrix in the complex plane with a modulus above a certain threshold correspond to localized eigenfunctions while eigenvalues below this threshold are associated with delocalized relaxation modes. We argue that, for networks with delocalized PageRank, the efficiency of information retrieval by Google-type search is strongly affected since the PageRank values have no clear hierarchical structure in this case.

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.

Recursive solutions for Laplacian spectra and eigenvectors of a class of growing treelike networks

The complete knowledge of Laplacian eigenvalues and eigenvectors of complex networks plays an outstanding role in understanding various dynamical processes running on them; however, determining analytically Laplacian eigenvalues and eigenvectors is a theoretical challenge. In this paper, we study the Laplacian spectra and their corresponding eigenvectors of a class of deterministically growing treelike networks. The two interesting quantities are determined through the recurrence relations derived from the structure of the networks. Beginning from the rigorous relations one can obtain the complete eigenvalues and eigenvectors for the networks of arbitrary size. The analytical method opens the way to analytically compute the eigenvalues and eigenvectors of some other deterministic networks, making it possible to accurately calculate their spectral characteristics.

Deformed Gaussian-orthogonal-ensemble description of small-world networks

The study of spectral behavior of networks has gained enthusiasm over the last few years. In particular, random matrix theory (RMT) concepts have proven to be useful. In discussing transition from regular behavior to fully chaotic behavior it has been found that an extrapolation formula of the Brody type can be used. In the present paper we analyze the regular to chaotic behavior of small world (SW) networks using an extension of the Gaussian orthogonal ensemble. This RMT ensemble, coined the deformed Gaussian orthogonal ensemble (DGOE), supplies a natural foundation of the Brody formula. SW networks follow GOE statistics until a certain range of eigenvalue correlations depending upon the strength of random connections. We show that for these regimes of SW networks where spectral correlations do not follow GOE beyond a certain range, DGOE statistics models the correlations very well. The analysis performed in this paper proves the utility of the DGOE in network physics, as much as it has been useful in other physical systems.

Optimization of synchronization in complex clustered networks

There has been mounting evidence that many types of biological or technological networks possess a clustered structure. As many system functions depend on synchronization, it is important to investigate the synchronizability of complex clustered networks. Here we focus on one fundamental question: Under what condition can the network synchronizability be optimized? In particular, since the two basic parameters characterizing a complex clustered network are the probabilities of intercluster and intracluster connections, we investigate, in the corresponding two-dimensional parameter plane, regions where the network can be best synchronized. Our study yields a quite surprising finding: a complex clustered network is most synchronizable when the two probabilities match each other approximately. Mismatch, for instance caused by an overwhelming increase in the number of intracluster links, can counterintuitively suppress or even destroy synchronization, even though such an increase tends to reduce the average network distance. This phenomenon provides possible principles for optimal synchronization on complex clustered networks. We provide extensive numerical evidence and an analytic theory to establish the generality of this phenomenon.