Improved community structure detection using a modified fine tuning strategy
arXiv:0901.2151 · doi:10.1209/0295-5075/86/28004
Abstract
The community structure of a complex network can be determined by finding the partitioning of its nodes that maximizes modularity. Many of the proposed algorithms for doing this work by recursively bisecting the network. We show that this unduely constrains their results, leading to a bias in the size of the communities they find and limiting their effectivness. To solve this problem, we propose adding a step to the existing algorithms that does not increase the order of their computational complexity. We show that, if this step is combined with a commonly used method, the identified constraint and resulting bias are removed, and its ability to find the optimal partitioning is improved. The effectiveness of this combined algorithm is also demonstrated by using it on real-world example networks. For a number of these examples, it achieves the best results of any known algorithm.
arXiv comment6 pages, 3 figures, 1 table
References in corpus (35)
- 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
- Finding community structure in very large networks
- Fast algorithm for detecting 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
- Cooperative Game Theory Approaches for Network Partitioning
- Maps of random walks on complex networks reveal community structure
- The large-scale organization of metabolic networks
- Resolution limit in community detection
- Defining and identifying communities in networks
- Statistical Mechanics of Community Detection
- Community detection in complex networks using Extremal Optimization
- Self-similar community structure in organisations
- Community Structure in Jazz
- An information-theoretic framework for resolving community structure in complex networks
- Detecting fuzzy community structures in complex networks with a Potts model
- Extracting the hierarchical organization of complex systems
- Finding Communities in Linear Time: A Physics Approach
- Analysis of the structure of complex networks at different resolution levels
- Modularity-Maximizing Network Communities via Mathematical Programming
- Size reduction of complex networks preserving modularity
- A Method to Find Community Structures Based on Information Centrality
- Optimal routing on complex networks
- Community Detection as an Inference Problem
- Identifying network communities with a high resolution
- Efficient modularity optimization by multistep greedy algorithm and vertex mover refinement
- Identifying "communities" within energy landscapes
- Extremal Optimization for Graph Partitioning
- An Information-Theoretic Approach to Network Modularity
- Transport optimization on complex networks
- Deterministic Modularity Optimization
- Optimal transport on wireless networks
Cited by in corpus (16)
- Community detection in graphs
- Weight-conserving characterization of complex functional brain networks
- Community landscapes: an integrative approach to determine overlapping network module hierarchy, identify key nodes and predict network dynamics
- A General Optimization Technique for High Quality Community Detection in Complex Networks
- Collectively optimal routing for congested traffic limited by link capacity
- Robust Detection of Hierarchical Communities from Escherichia coli Gene Expression Data
- Network community detection using modularity density measures
- Fast and accurate determination of modularity and its effect size
- Multi-resolution community detection based on generalized self-loop rescaling strategy
- Combinatorial approach to Modularity
- Enhancing community detection by local structural information
- Community detection based on significance optimization in complex networks
- Reduced network extremal ensemble learning (RenEEL) scheme for community detection in complex networks
- Resolution limit revisited: community detection using generalized modularity density
- Comprehensive spectral approach for community structure analysis on complex networks
- The Importance of Being Negative: A serious treatment of non-trivial edges in brain functional connectome