Universality in complex networks: random matrix analysis

Abnormal suppression of thermal transport by long-range interactions in networks

Heat and electricity are two fundamental forms of energy widely utilized in our daily lives. Recently, in the study of complex networks, there is growing evidence that they behave significantly different at the micro-nanoscale. Here, we use a small-world network model to investigate the effects of reconnection probability p and decay exponent α on thermal and electrical transport within the network. Our results demonstrate that the electrical transport efficiency increases by nearly one order of magnitude, while the thermal transport efficiency falls off a cliff by three to four orders of magnitude, breaking the traditional rule that shortcuts enhance energy transport in small-world networks. Furthermore, we elucidate that phonon localization is a crucial factor in the weakening of thermal transport efficiency in small-world networks by characterizing the density of states, phonon participation ratio, and nearest-neighbor spacing distribution. These insights will pave new ways for designing thermoelectric materials with high electrical conductance and low thermal conductance.

Eigenvalue ratio statistics of complex networks: Disorder versus randomness

The distribution of the ratios of consecutive eigenvalue spacings of random matrices has emerged as an important tool to study spectral properties of many-body systems. This article numerically investigates the eigenvalue ratios distribution of various model networks, namely, small-world, Erdős-Rényi random, and (dis)assortative random having a diagonal disorder in the corresponding adjacency matrices. Without any diagonal disorder, the eigenvalues ratio distribution of these model networks depict Gaussian orthogonal ensemble (GOE) statistics. Upon adding diagonal disorder, there exists a gradual transition from the GOE to Poisson statistics depending upon the strength of the disorder. The critical disorder (w_{c}) required to procure the Poisson statistics increases with the randomness in the network architecture. We relate w_{c} with the time taken by maximum entropy random walker to reach the steady state. These analyses will be helpful to understand the role of eigenvalues other than the principal one for various network dynamics such as transient behavior.

Disordered beta thinned ensemble with applications

It recently has been found that methods of the statistical theories of spectra can be a useful tool in the analysis of spectra far from levels of Hamiltonian systems. The purpose of the present study is to deepen this kind of approach by performing a more comprehensive spectral analysis that measures both the local- and long-range statistics. We have found that, as a common feature, spectra of this kind can exhibit a situation in which local statistics are relatively quenched while the long-range ones show large fluctuations. By combining three extensions of the standard random matrix theory (RMT) and considering long spectra, we demonstrate that this phenomenon occurs when disorder and level incompleteness are introduced in an RMT spectrum. Consequently, the long-range statistics follow Taylor's law, suggesting the presence of a fluctuation scaling (FS) mechanism in this kind of spectra. Applications of the combined ensemble are then presented for spectra originate from several very diverse areas, including complex networks, COVID-19 time series, and quantitative linguistics, which demonstrate that short- and long-range statistics reflect the rigid and elastic characteristics of a given spectrum, respectively. These observations may shed some light on spectral data classification.

Structural and spectral properties of generative models for synthetic multilayer air transportation networks

To understand airline transportation networks (ATN) systems we can effectively represent them as multilayer networks, where layers capture different airline companies, the nodes correspond to the airports and the edges to the routes between the airports. We focus our study on the importance of leveraging synthetic generative multilayer models to support the analysis of meaningful patterns in these routes, capturing an ATN’s evolution with an emphasis on measuring its resilience to random or targeted attacks and considering deliberate locations of airports. By resorting to the European ATN and the United States ATN as exemplary references, in this work, we provide a systematic analysis of major existing synthetic generation models for ATNs, specifically ANGEL, STARGEN and BINBALL. Besides a thorough study of the topological aspects of the ATNs created by the three models, our major contribution lays on an unprecedented investigation of their spectral characteristics based on Random Matrix Theory and on their resilience analysis based on both site and bond percolation approaches. Results have shown that ANGEL outperforms STARGEN and BINBALL to better capture the complexity of real-world ATNs by featuring the unique properties of building a multiplex ATN layer by layer and of replicating layers with point-to-point structures alongside hub-spoke formations.

Random matrix theory for analysing the brain functional network in lower limb motor imagery

We use random matrix theory (RMT) to investigate the statistical properties of brain functional networks in lower limb motor imagery. Functional connectivity was calculated by Pearson correlation coefficient (PCC), mutual information (MTI) and phase locking value (PLV) extracted from EEG signals. We found that when the measured subjects imagined the movements of their lower limbs the spectral density as well as the level spacings displayed deviations from the random matrix prediction. In particular, a significant difference between the left and right foot imaginary movements was observed in the maximum eigenvalue from the PCC, which can provide a theoretical basis for further study on the classification of unilateral movement of lower limbs.

Geometrical and spectral study of β-skeleton graphs

We perform an extensive numerical analysis of β-skeleton graphs, a particular type of proximity graphs. In a β-skeleton graph (BSG) two vertices are connected if a proximity rule, that depends of the parameter β∈(0,∞), is satisfied. Moreover, for β>1 there exist two different proximity rules, leading to lune-based and circle-based BSGs. First, by computing the average degree of large ensembles of BSGs we detect differences, which increase with the increase of β, between lune-based and circle-based BSGs. Then, within a random matrix theory (RMT) approach, we explore spectral and eigenvector properties of random BSGs by the use of the nearest-neighbor energy-level spacing distribution and the entropic eigenvector localization length, respectively. The RMT analysis allows us to conclude that a localization transition occurs at β=1.

Inferring pathogen-host interactions between Leptospira interrogans and Homo sapiens using network theory

Leptospirosis is the most emerging zoonotic disease of epidemic potential caused by pathogenic species of Leptospira. The bacterium invades the host system and causes the disease by interacting with the host proteins. Analyzing these pathogen-host protein interactions (PHPIs) may provide deeper insight into the disease pathogenesis. For this analysis, inter-species as well as intra-species protein interactions networks of Leptospira interrogans and human were constructed and investigated. The topological analyses of these networks showed lesser connectivity in inter-species network than intra-species, indicating the perturbed nature of the inter-species network. Hence, it can be one of the reasons behind the disease development. A total of 35 out of 586 PHPIs were identified as key interactions based on their sub-cellular localization. Two outer membrane proteins (GpsA and MetXA) and two periplasmic proteins (Flab and GlyA) participating in PHPIs were found conserved in all pathogenic, intermediate and saprophytic spp. of Leptospira. Furthermore, the bacterial membrane proteins involved in PHPIs were found playing major roles in disruption of the immune systems and metabolic processes within host and thereby causing infectious disease. Thus, the present results signify that the membrane proteins participating in such interactions hold potential to serve as effective immunotherapeutic candidates for vaccine development.

Network spectra for drug-target identification in complex diseases: new guns against old foes

The fundamental understanding of altered complex molecular interactions in a diseased condition is the key to its cure. The overall functioning of these molecules is kind of jugglers play in the cell orchestra and to anticipate these relationships among the molecules is one of the greatest challenges in modern biology and medicine. Network science turned out to be providing a successful and simple platform to understand complex interactions among healthy and diseased tissues. Furthermore, much information about the structure and dynamics of a network is concealed in the eigenvalues of its adjacency matrix. In this review, we illustrate rapid advancements in the field of network science in combination with spectral graph theory that enables us to uncover the complexities of various diseases. Interpretations laid by network science approach have solicited insights into molecular relationships and have reported novel drug targets and biomarkers in various complex diseases.

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.

Comment on "Spectral analysis of deformed random networks"

We comment on the findings presented in [Phys. Rev. E 80, 046101 (2009)10.1103/PhysRevE.80.046101] concerning the spacing distribution of the spectrum of sparsely connected random networks. We point out that for clustered networks without any connection among them the spacing distribution is not described by Poisson but rather by a superposition of multiple Gaussian orthogonal ensemble (GOE) statistics. Therefore, the spacing distribution for a network having two dense subnetworks with few connections between the two subnetworks follows a transition from two-GOE to a GOE statistics and not as the article suggests a transition from Poisson statistics to the GOE.

Scaling properties of multilayer random networks

Multilayer networks are widespread in natural and manmade systems. Key properties of these networks are their spectral and eigenfunction characteristics, as they determine the critical properties of many dynamics occurring on top of them. Here, we numerically demonstrate that the normalized localization length β of the eigenfunctions of multilayer random networks follows a simple scaling law given by β=x^{*}/(1+x^{*}), with x^{*}=γ(b_{eff}^{2}/L)^{δ}, δ∼1, and b_{eff} being the effective bandwidth of the adjacency matrix of the network, whose size is L. The scaling law for β, that we validate on real-world networks, might help to better understand criticality in multilayer networks and to predict the eigenfunction localization properties of them.

Understanding cancer complexome using networks, spectral graph theory and multilayer framework

Cancer complexome comprises a heterogeneous and multifactorial milieu that varies in cytology, physiology, signaling mechanisms and response to therapy. The combined framework of network theory and spectral graph theory along with the multilayer analysis provides a comprehensive approach to analyze the proteomic data of seven different cancers, namely, breast, oral, ovarian, cervical, lung, colon and prostate. Our analysis demonstrates that the protein-protein interaction networks of the normal and the cancerous tissues associated with the seven cancers have overall similar structural and spectral properties. However, few of these properties implicate unsystematic changes from the normal to the disease networks depicting difference in the interactions and highlighting changes in the complexity of different cancers. Importantly, analysis of common proteins of all the cancer networks reveals few proteins namely the sensors, which not only occupy significant position in all the layers but also have direct involvement in causing cancer. The prediction and analysis of miRNAs targeting these sensor proteins hint towards the possible role of these proteins in tumorigenesis. This novel approach helps in understanding cancer at the fundamental level and provides a clue to develop promising and nascent concept of single drug therapy for multiple diseases as well as personalized medicine.

Anderson Transition for Classical Transport in Composite Materials

The Anderson transition in solids and optics is a wave phenomenon where disorder induces localization of the wave functions. We find here that the hallmarks of the Anderson transition are exhibited by classical transport at a percolation threshold-without wave interference or scattering effects. As long range order or connectedness develops, the eigenvalue statistics of a key random matrix governing transport cross over toward universal statistics of the Gaussian orthogonal ensemble, and the field eigenvectors delocalize. The transition is examined in resistor networks, human bone, and sea ice structures.

Random matrix theory for analyzing the brain functional network in attention deficit hyperactivity disorder

Attention deficit hyperactivity disorder (ADHD) is the most common childhood neuropsychiatric disorder and affects approximately 6-7% of children worldwide. Here, we investigate the statistical properties of undirected and directed brain functional networks in ADHD patients based on random matrix theory (RMT), in which the undirected functional connectivity is constructed based on correlation coefficient and the directed functional connectivity is measured based on cross-correlation coefficient and mutual information. We first analyze the functional connectivity and the eigenvalues of the brain functional network. We find that ADHD patients have increased undirected functional connectivity, reflecting a higher degree of linear dependence between regions, and increased directed functional connectivity, indicating stronger causality and more transmission of information among brain regions. More importantly, we explore the randomness of the undirected and directed functional networks using RMT. We find that for ADHD patients, the undirected functional network is more orderly than that for normal subjects, which indicates an abnormal increase in undirected functional connectivity. In addition, we find that the directed functional networks are more random, which reveals greater disorder in causality and more chaotic information flow among brain regions in ADHD patients. Our results not only further confirm the efficacy of RMT in characterizing the intrinsic properties of brain functional networks but also provide insights into the possibilities RMT offers for improving clinical diagnoses and treatment evaluations for ADHD patients.

Spectral properties of the temporal evolution of brain network structure

The temporal evolution properties of the brain network are crucial for complex brain processes. In this paper, we investigate the differences in the dynamic brain network during resting and visual stimulation states in a task-positive subnetwork, task-negative subnetwork, and whole-brain network. The dynamic brain network is first constructed from human functional magnetic resonance imaging data based on the sliding window method, and then the eigenvalues corresponding to the network are calculated. We use eigenvalue analysis to analyze the global properties of eigenvalues and the random matrix theory (RMT) method to measure the local properties. For global properties, the shifting of the eigenvalue distribution and the decrease in the largest eigenvalue are linked to visual stimulation in all networks. For local properties, the short-range correlation in eigenvalues as measured by the nearest neighbor spacing distribution is not always sensitive to visual stimulation. However, the long-range correlation in eigenvalues as evaluated by spectral rigidity and number variance not only predicts the universal behavior of the dynamic brain network but also suggests non-consistent changes in different networks. These results demonstrate that the dynamic brain network is more random for the task-positive subnetwork and whole-brain network under visual stimulation but is more regular for the task-negative subnetwork. Our findings provide deeper insight into the importance of spectral properties in the functional brain network, especially the incomparable role of RMT in revealing the intrinsic properties of complex systems.

Random matrix ensembles involving Gaussian Wigner and Wishart matrices, and biorthogonal structure

We consider four nontrivial ensembles involving Gaussian Wigner and Wishart matrices. These are relevant to problems ranging from multiantenna communication to random supergravity. We derive the matrix probability density, as well as the eigenvalue densities for these ensembles. In all cases the joint eigenvalue density exhibits a biorthogonal structure. A determinantal representation, based on a generalization of Andréief's integration formula, is used to compactly express the r-point correlation function of eigenvalues. This representation circumvents the complications encountered in the usual approaches, and the answer is obtained immediately by examining the joint density of eigenvalues. We validate our analytical results using Monte Carlo simulations.

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.

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.

Randomness and preserved patterns in cancer network

Breast cancer has been reported to account for the maximum cases among all female cancers till date. In order to gain a deeper insight into the complexities of the disease, we analyze the breast cancer network and its normal counterpart at the proteomic level. While the short range correlations in the eigenvalues exhibiting universality provide an evidence towards the importance of random connections in the underlying networks, the long range correlations along with the localization properties reveal insightful structural patterns involving functionally important proteins. The analysis provides a benchmark for designing drugs which can target a subgraph instead of individual proteins.

Extreme-value statistics of brain networks: importance of balanced condition

Despite the key role played by inhibitory-excitatory couplings in the functioning of brain networks, the impact of a balanced condition on the stability properties of underlying networks remains largely unknown. We investigate properties of the largest eigenvalues of networks having such couplings, and find that they follow completely different statistics when in the balanced situation. Based on numerical simulations, we demonstrate that the transition from Weibull to Fréchet via the Gumbel distribution can be controlled by the variance of the column sum of the adjacency matrix, which depends monotonically on the denseness of the underlying network. As a balanced condition is imposed, the largest real part of the eigenvalue emulates a transition to the generalized extreme-value statistics, independent of the inhibitory connection probability. Furthermore, the transition to the Weibull statistics and the small-world transition occur at the same rewiring probability, reflecting a more stable system.

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 ξ.

Molecular ecological network analyses

BACKGROUND

Understanding the interaction among different species within a community and their responses to environmental changes is a central goal in ecology. However, defining the network structure in a microbial community is very challenging due to their extremely high diversity and as-yet uncultivated status. Although recent advance of metagenomic technologies, such as high throughout sequencing and functional gene arrays, provide revolutionary tools for analyzing microbial community structure, it is still difficult to examine network interactions in a microbial community based on high-throughput metagenomics data.

RESULTS

Here, we describe a novel mathematical and bioinformatics framework to construct ecological association networks named molecular ecological networks (MENs) through Random Matrix Theory (RMT)-based methods. Compared to other network construction methods, this approach is remarkable in that the network is automatically defined and robust to noise, thus providing excellent solutions to several common issues associated with high-throughput metagenomics data. We applied it to determine the network structure of microbial communities subjected to long-term experimental warming based on pyrosequencing data of 16 S rRNA genes. We showed that the constructed MENs under both warming and unwarming conditions exhibited topological features of scale free, small world and modularity, which were consistent with previously described molecular ecological networks. Eigengene analysis indicated that the eigengenes represented the module profiles relatively well. In consistency with many other studies, several major environmental traits including temperature and soil pH were found to be important in determining network interactions in the microbial communities examined. To facilitate its application by the scientific community, all these methods and statistical tools have been integrated into a comprehensive Molecular Ecological Network Analysis Pipeline (MENAP), which is open-accessible now (http://ieg2.ou.edu/MENA).

CONCLUSIONS

The RMT-based molecular ecological network analysis provides powerful tools to elucidate network interactions in microbial communities and their responses to environmental changes, which are fundamentally important for research in microbial ecology and environmental microbiology.

Spectral properties of directed random networks with modular structure

We study spectra of directed networks with inhibitory and excitatory couplings. We investigate in particular eigenvector localization properties of various model networks for different values of correlation among their entries. Spectra of random networks with completely uncorrelated entries show a circular distribution with delocalized eigenvectors, whereas networks with correlated entries have localized eigenvectors. In order to understand the origin of localization we track the spectra as a function of connection probability and directionality. As connections are made directed, eigenstates start occurring in complex-conjugate pairs and the eigenvalue distribution combined with the localization measure shows a rich pattern. Moreover, for a very well distinguished community structure, the whole spectrum is localized except few eigenstates at the boundary of the circular distribution. As the network deviates from the community structure there is a sudden change in the localization property for a very small value of deformation from the perfect community structure. We search for this effect for the whole range of correlation strengths and for different community configurations. Furthermore, we investigate spectral properties of a metabolic network of zebrafish and compare them with those of the model networks.

Random matrix analysis of localization properties of gene coexpression network

We analyze gene coexpression network under the random matrix theory framework. The nearest-neighbor spacing distribution of the adjacency matrix of this network follows Gaussian orthogonal statistics of random matrix theory (RMT). Spectral rigidity test follows random matrix prediction for a certain range and deviates afterwards. Eigenvector analysis of the network using inverse participation ratio suggests that the statistics of bulk of the eigenvalues of network is consistent with those of the real symmetric random matrix, whereas few eigenvalues are localized. Based on these IPR calculations, we can divide eigenvalues in three sets: (a) The nondegenerate part that follows RMT. (b) The nondegenerate part, at both ends and at intermediate eigenvalues, which deviates from RMT and expected to contain information about important nodes in the network. (c) The degenerate part with zero eigenvalue, which fluctuates around RMT-predicted value. We identify nodes corresponding to the dominant modes of the corresponding eigenvectors and analyze their structural properties.

Random matrix approach to collective behavior and bulk universality in protein dynamics

Covariance matrices of amino acid displacements, commonly used to characterize the large-scale movements of proteins, are investigated through the prism of random matrix theory. Bulk universality is detected in the local spacing statistics of noise-dressed eigenmodes, which is well described by a Brody distribution with parameter beta approximately = 0.8. This finding, supported by other consistent indicators, implies a novel quantitative criterion to single out the collective degrees of freedom of the protein from the majority of high-energy, localized vibrations.

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.

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.

Localizations on complex networks

We study the structural characteristics of complex networks using the representative eigenvectors of the adjacent matrix. The probability distribution function of the components of the representative eigenvectors are proposed to describe the localization on networks where the Euclidean distance is invalid. Several quantities are used to describe the localization properties of the representative states, such as the participation ratio, the structural entropy, and the probability distribution function of the nearest neighbor level spacings for spectra of complex networks. Whole-cell networks in the real world and the Watts-Strogatz small-world and Barabasi-Albert scale-free networks are considered. The networks have nontrivial localization properties due to the nontrivial topological structures. It is found that the ascending-order-ranked series of the occurrence probabilities at the nodes behave generally multifractally. This characteristic can be used as a structural measure of complex networks.

Quantum transport on small-world networks: a continuous-time quantum walk approach

We consider the quantum mechanical transport of (coherent) excitons on small-world networks (SWNs). The SWNs are built from a one-dimensional ring of N nodes by randomly introducing B additional bonds between them. The exciton dynamics is modeled by continuous-time quantum walks, and we evaluate numerically the ensemble-averaged transition probability to reach any node of the network from the initially excited one. For sufficiently large B we find that the quantum mechanical transport through the SWNs is, first, very fast, given that the limiting value of the transition probability is reached very quickly, and second, that the transport does not lead to equipartition, given that on average the exciton is most likely to be found at the initial node.

Random matrix analysis of complex networks

We study complex networks under random matrix theory (RMT) framework. Using nearest-neighbor and next-nearest-neighbor spacing distributions we analyze the eigenvalues of the adjacency matrix of various model networks, namely, random, scale-free, and small-world networks. These distributions follow the Gaussian orthogonal ensemble statistic of RMT. To probe long-range correlations in the eigenvalues we study spectral rigidity via the Delta_{3} statistic of RMT as well. It follows RMT prediction of linear behavior in semilogarithmic scale with the slope being approximately 1pi;{2} . Random and scale-free networks follow RMT prediction for very large scale. A small-world network follows it for sufficiently large scale, but much less than the random and scale-free networks.