Detecting Network Communities: a new systematic and efficient algorithm
arXiv:cond-mat/0404652 · doi:10.1088/1742-5468/2004/10/P10012
Abstract
An efficient and relatively fast algorithm for the detection of communities in complex networks is introduced. The method exploits spectral properties of the graph Laplacian-matrix combined with hierarchical-clustering techniques, and includes a procedure to maximize the ``modularity'' of the output. Its performance is compared with that of other existing methods, as applied to different well-known instances of complex networks with a community-structure: both computer-generated and from the real-world. Our results are in all the tested cases, at least, as good as the best ones obtained with any other methods, and faster in most of the cases than methods providing similar-quality results. This converts the algorithm in a valuable computational tool for detecting and analyzing communities and modular structures in complex networks.
8 pages, 6 figures. minor changes and some references added, to be published in JSTAT
References in corpus (6)
- The structure and function of complex networks
- Finding and evaluating community structure in networks
- Fast algorithm for detecting community structure in networks
- Cooperative Game Theory Approaches for Network Partitioning
- Defining and identifying communities in networks
- Finding Communities in Linear Time: A Physics Approach
Cited by in corpus (55)
- Functional cartography of complex metabolic networks
- Comparing community structure identification
- Community detection algorithms: a comparative analysis
- Community detection in complex networks using Extremal Optimization
- Vertex similarity in networks
- Synchronization reveals topological scales in complex networks
- Unfolding communities in large complex networks: Combining defensive and offensive label propagation for core extraction
- Synchronization processes in complex networks
- Mixing local and global information for community detection in large networks
- Spectral coarse-graining of complex networks
- Statistical significance of communities in networks
- Laplacian Spectra as a Diagnostic Tool for Network Structure and Dynamics
- Spectral and Dynamical Properties in Classes of Sparse Networks with Mesoscopic Inhomogeneities
- Emergent Complex Network Geometry
- Surprise maximization reveals the community structure of complex networks
- Optimal network topologies: Expanders, Cages, Ramanujan graphs, Entangled networks and all that
- Community Detecting By Signaling on Complex Networks
- Spectral tripartitioning of networks
- Exploring the limits of community detection strategies in complex networks
- Topologically biased random walk with application for community finding in networks
- Accuracy and Precision of Methods for Community Identification in Weighted Networks
- Post-Processing Hierarchical Community Structures: Quality Improvements and Multi-scale View
- Detecting communities of triangles in complex networks using spectral optimization
- Detection of node group membership in networks with group overlap
- Limitation of multi-resolution methods in community detection
- Analysis of Nonlinear Synchronization Dynamics of Oscillator Networks by Laplacian Spectral Methods
- Diffusion and networks: A powerful combination!
- The critical point of k-clique percolation in the Erdos-Renyi graph
- The role of modularity in self-organisation dynamics in biological networks
- Maximal entropy random walk in community finding
- Scaling laws for diffusion on (trans)fractal scale-free networks
- A divisive spectral method for network community detection
- Graph Comparison via the Non-backtracking Spectrum
- Network synchronization: Optimal and Pessimal Scale-Free Topologies
- Enhancing community detection by local structural information
- Effect of size heterogeneity on community identification in complex networks
- Quantum walks on complex networks with connection instabilities and community structure
- Discovering Network Structure Beyond Communities
- Jamming and Correlation Patterns in Traffic of Information on Sparse Modular Networks
- Community detection based on significance optimization in complex networks
- Networks with many structural scales: a Renormalization Group perspective
- Communities and classes in symmetric fractals
- Community detection based on "clumpiness" matrix in complex networks
- Detecting the optimal number of communities in complex networks
- Multi-scale Laplacian community detection in heterogeneous networks
- Criterions for locally dense subgraphs
- Enhance the Efficiency of Heuristic Algorithm for Maximizing Modularity Q
- Network Community Detection on Metric Space
- Strange Attractors in Complex Networks
- Comprehensive spectral approach for community structure analysis on complex networks
- Membership in social networks and the application in information filtering
- Transforming complex network to the acyclic one
- Dynamic Ising Model: Reconstruction of Evolutionary Trees
- Network theory approach for data evaluation in the dynamic force spectroscopy of biomolecular interactions
- Ground state energy of -state Potts model: the minimum modularity