Spectral Measures of Bipartivity in Complex Networks

Abstract

We introduce a quantitative measure of network bipartivity as a proportion of even to total number of closed walks in the network. Spectral graph theory is used to quantify how close to bipartite a network is and the extent to which individual nodes and edges contribute to the global network bipartivity. It is shown that the bipartivity characterizes the network structure and can be related to the efficiency of semantic or communication networks, trophic interactions in food webs, construction principles in metabolic networks, or communities in social networks.

arXiv comment16 pages, 1 figure, 1 table

References in corpus (8)

• Statistical mechanics of complex networks
• The structure and function of complex networks
• Cooperative Game Theory Approaches for Network Partitioning
• The large-scale organization of metabolic networks
• Evolution of networks
• Subgraph Centrality in Complex Networks
• Global Organization of the Lexicon
• On network bipartivity

Cited by in corpus (43)

• Finding community structure in networks using the eigenvectors of matrices
• Characterization of complex networks: A survey of measurements
• Vital nodes identification in complex networks
• How to project a bipartite network?
• Communicability in complex networks
• Mixture models and exploratory analysis in networks
• The Physics of Communicability in Complex Networks
• Network Analysis of Particles and Grains
• Statistical-mechanical approach to subgraph centrality in complex networks
• Network models of financial systemic risk: A review
• Spectral centrality measures in complex networks
• Overlapping stochastic block models with application to the French political blogosphere
• Graph Vulnerability and Robustness: A Survey
• Spectral Scaling in Complex Networks
• Empirical analysis of web-based user-object bipartite networks
• Resolving Structure in Human Brain Organization: Identifying Mesoscale Organization in Weighted Network Representations
• Balance and Frustration in Signed Networks
• Random Walks Along the Streets and Canals in Compact Cities: Spectral analysis, Dynamical Modularity, Information, and Statistical Mechanics
• Communicability and multipartite structures in complex networks at negative absolute temperatures
• Detecting Core-Periphery Structures by Surprise
• On sum of powers of Laplacian eigenvalues and Laplacian Estrada index of graphs
• Functional centrality in graphs
• Exploiting the Structure of Bipartite Graphs for Algebraic and Spectral Graph Theory Applications
• Social dynamics of financial networks
• Maximum Estrada Index of Bicyclic Graphs
• Structural measures of similarity and complementarity in complex networks
• Detecting mesoscale structures by surprise
• Graph animals, subgraph sampling and motif search in large networks
• Understanding how both the partitions of a bipartite network affect its one-mode projection
• Functional structure in production networks
• Model selection and clustering in stochastic block models with the exact integrated complete data likelihood
• Approximating the Spectral Sums of Large-scale Matrices using Chebyshev Approximations
• Subgraphs and motifs in a dynamic airline network
• Robustness of Regular Graphs Based on Natural Connectivity
• Emergence of (bi)multi-partiteness in networks having inhibitory and excitatory couplings
• Collaborative similarity analysis of multilayer developer-project bipartite network
• Modular Representation of Layered Neural Networks
• Metrics for Community Analysis: A Survey
• Spectral properties of unimodular lattice triangulations
• Detection of network inhomogeneity by total neighbor degree
• More on the normalized Laplacian Estrada index
• Model Selection in Overlapping Stochastic Block Models
• On maximum Estrada indices of bipartite graphs with some given parameters