Spectral analysis of deformed random networks

Abstract

We study spectral behavior of sparsely connected random networks under the random matrix framework. Sub-networks without any connection among them form a network having perfect community structure. As connections among the sub-networks 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 ${\Delta }_3$ 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 ${\Delta }_3$ statistics remain identical to the undeformed network. On the other hand the ${\Delta }_3$ 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.

accepted for publication in Phys. Rev. E (replaced with the final version)

References in corpus (16)

• Modularity and community structure in networks
• Uncovering the overlapping community structure of complex networks in nature and society
• Finding community structure in networks using the eigenvectors of matrices
• Resolution limit in community detection
• Analysis of the structure of complex networks at different resolution levels
• Community Detection as an Inference Problem
• Laplacian spectra of complex networks and random walks on them: Are scale-free architectures really important?
• Laplacian Spectra as a Diagnostic Tool for Network Structure and Dynamics
• Random matrix analysis of complex networks
• Multistep greedy algorithm identifies community structure in real-world and computer-generated networks
• Localizations on Complex Networks
• How much random a random network is : a random matrix analysis
• Spectral transitions in networks
• Deformed Gaussian Orthogonal Ensemble description of Small-World networks
• Self-affine Fractals Embedded in Spectra of Complex Networks
• Spectral densities of scale-free networks

Cited by in corpus (16)

• Random matrix analysis of localization properties of Gene co-expression network
• Universality in the spectral and eigenfunction properties of random networks
• Random Matrix Spectra as a Time Series
• Spectral density of random graphs with topological constraints
• Spectral Properties of Directed Random Networks with Modular Structure
• Spectral statistics of random geometric graphs
• Quantifying randomness in protein-protein interaction networks of different species: A random matrix approach
• Spectral analysis of Gene co-expression network of Zebrafish
• Random matrix analysis for gene interaction networks in cancer cells
• Normal mode analysis of spectra of random networks
• Scattering and transport properties of tight-binding random networks
• Geometrical and spectral study of $\beta$-skeleton graphs
• Null-eigenvalue localization of quantum walks on real-world complex networks
• Evolution of correlated multiplexity through stability maximization
• Weighted random--geometric and random--rectangular graphs: Spectral and eigenfunction properties of the adjacency matrix
• Random Matrix Analysis of Multiplex Networks