Covariance, correlation matrix and the multi-scale community structure of networks

Abstract

Empirical studies show that real world networks often exhibit multiple scales of topological descriptions. However, it is still an open problem how to identify the intrinsic multiple scales of networks. In this article, we consider detecting the multi-scale community structure of network from the perspective of dimension reduction. According to this perspective, a covariance matrix of network is defined to uncover the multi-scale community structure through the translation and rotation transformations. It is proved that the covariance matrix is the unbiased version of the well-known modularity matrix. We then point out that the translation and rotation transformations fail to deal with the heterogeneous network, which is very common in nature and society. To address this problem, a correlation matrix is proposed through introducing the rescaling transformation into the covariance matrix. Extensive tests on real world and artificial networks demonstrate that the correlation matrix significantly outperforms the covariance matrix, identically the modularity matrix, as regards identifying the multi-scale community structure of network. This work provides a novel perspective to the identification of community structure and thus various dimension reduction methods might be used for the identification of community structure. Through introducing the correlation matrix, we further conclude that the rescaling transformation is crucial to identify the multi-scale community structure of network, as well as the translation and rotation transformations.

10 pages, 7 figures

References in corpus (33)

• The structure and function of complex networks
• Community structure in social and biological networks
• Finding and evaluating community structure in networks
• Modularity and community structure in networks
• Community detection in graphs
• Finding community structure in very large networks
• Uncovering the overlapping community structure of complex networks in nature and society
• Assortative mixing in networks
• Finding community structure in networks using the eigenvectors of matrices
• Cooperative Game Theory Approaches for Network Partitioning
• Functional cartography of complex metabolic networks
• Mixing patterns in networks
• Benchmark graphs for testing community detection algorithms
• Resolution limit in community detection
• Comparing community structure identification
• Defining and identifying communities in networks
• Community Structure in Time-Dependent, Multiscale, and Multiplex Networks
• Community detection in complex networks using Extremal Optimization
• Self-similar community structure in organisations
• Community Structure in Jazz
• Synchronization reveals topological scales in complex networks
• An information-theoretic framework for resolving community structure in complex networks
• Detect overlapping and hierarchical community structure in networks
• Analysis of the structure of complex networks at different resolution levels
• Detecting communities in large networks
• Multiresolution community detection for megascale networks by information-based replica correlations
• Modularity and Extreme Edges of the Internet
• Evaluating Local Community Methods in Networks
• Quantifying and identifying the overlapping community structure in networks
• Uncovering the community structure associated with the diffusion dynamics of networks
• Optimal map of the modular structure of complex networks
• Triangular clustering in document networks
• Partition of Networks into Basins of Attraction

Cited by in corpus (12)

• Community landscapes: an integrative approach to determine overlapping network module hierarchy, identify key nodes and predict network dynamics
• Spectral methods for the detection of network community structure: a comparative analysis
• Bridgeness: A Local Index on Edge Significance in Maintaining Global Connectivity
• Exploring the structural regularities in networks
• Distinguishing manipulated stocks via trading network analysis
• A divisive spectral method for network community detection
• Characterization of multiple topological scales in multiplex networks through supra-Laplacian eigengaps
• Detecting Communities in Tripartite Hypergraphs
• Structured networks and coarse-grained descriptions: a dynamical perspective
• Local multiresolution order in community detection
• Link power coordination for energy conservation in complex communication networks
• Correlation-Based Community Detection