Spectral methods for the detection of network community structure: a comparative analysis

Abstract

Spectral analysis has been successfully applied at the detection of community structure of networks, respectively being based on the adjacency matrix, the standard Laplacian matrix, the normalized Laplacian matrix, the modularity matrix, the correlation matrix and several other variants of these matrices. However, the comparison between these spectral methods is less reported. More importantly, it is still unclear which matrix is more appropriate for the detection of community structure. This paper answers the question through evaluating the effectiveness of these five matrices against the benchmark networks with heterogeneous distributions of node degree and community size. Test results demonstrate that the normalized Laplacian matrix and the correlation matrix significantly outperform the other three matrices at identifying the community structure of networks. This indicates that it is crucial to take into account the heterogeneous distribution of node degree when using spectral analysis for the detection of community structure. In addition, to our surprise, the modularity matrix exhibits very similar performance to the adjacency matrix, which indicates that the modularity matrix does not gain desired benefits from using the configuration model as reference network with the consideration of the node degree heterogeneity.

13 pages, 9 figures

References in corpus (38)

• 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
• Error and attack tolerance of complex networks
• Uncovering the overlapping community structure of complex networks in nature and society
• Finding community structure in networks using the eigenvectors of matrices
• Cooperative Game Theory Approaches for Network Partitioning
• Functional cartography of complex metabolic networks
• Benchmark graphs for testing community detection algorithms
• Resolution limit in community detection
• Comparing community structure identification
• Defining and identifying communities in networks
• Community detection algorithms: a comparative analysis
• Link communities reveal multiscale complexity in networks
• Community detection in complex networks using Extremal Optimization
• Synchronization reveals topological scales in complex networks
• An information-theoretic framework for resolving community structure in complex networks
• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• Detect overlapping and hierarchical community structure in networks
• Analysis of the structure of complex networks at different resolution levels
• Phase transition in the detection of modules in sparse networks
• Detecting communities in large networks
• A Bayesian Approach to Network Modularity
• Multiresolution community detection for megascale networks by information-based replica correlations
• Community Detection as an Inference Problem
• Evaluating Local Community Methods in Networks
• Quantifying and identifying the overlapping community structure in networks
• Bridgeness: A Local Index on Edge Significance in Maintaining Global Connectivity
• (Un)detectable cluster structure in sparse networks
• Protein-Interaction-Networks: More than mere modules
• Uncovering the community structure associated with the diffusion dynamics of networks
• Covariance, correlation matrix and the multi-scale community structure of networks
• The interplay of microscopic and mesoscopic structure in complex networks
• Triangular clustering in document networks
• Phase Changes in the Evolution of the IPv4 and IPv6 AS-Level Internet Topologies

Cited by in corpus (14)

• Diffusion on networked systems is a question of time or structure
• Exploring the structural regularities in networks
• Community Structure Detection in Complex Networks with Partial Background Information
• A divisive spectral method for network community detection
• Community detection in networks via nonlinear modularity eigenvectors
• Detecting Communities in Tripartite Hypergraphs
• Global disorder transition in the community structure of large-q Potts systems
• The stability to instability transition in the structure of large scale networks
• Total variation based community detection using a nonlinear optimization approach
• A Modular Multiscale Approach to Overlapping Community Detection
• Community Detection Using Revised Medoid-Shift Based on KNN
• A graph model for the clustering of dark matter halos
• Non-backtracking walks reveal compartments in sparse chromatin interaction networks
• Unified Statistical Theory of Spectral Graph Analysis