Source-linked AI summary
Identifying network communities with a high resolution
Jianhua Ruan, Weixiong Zhang
TL;DR
Community discovery requires methods that are computationally practical while resolving small or hierarchical communities missed by modularity optimization. The paper introduces Qcut and recursive HQcut, showing improved modularity, scalability, accuracy, and finer-scale detection, with applications to yeast protein interactions.
Problem
Modularity-based community discovery is NP-hard and may miss communities below a certain scale, limiting efficient and fine-resolution network analysis.
Method
Qcut combines spectral graph partitioning with local search, while HQcut recursively reapplies Qcut and uses statistical tests to assess subcommunities and community associations.
Results
Qcut finds higher modularities and is more scalable, while HQcut detects finer-scale communities with higher accuracy than modularity optimization alone.
Takeaways & Limitations
Combining HQcut with significance testing can reveal high-resolution and hierarchically related communities, including functionally related pairs in yeast protein-interaction networks.
Takeaways & Limitations
Modularity optimization can merge small communities or communities with relatively high inter-community connectivity into a single community.
Abstract
from arXiv · showhide
Community structure is an important property of complex networks. An automatic discovery of such structure is a fundamental task in many disciplines, including sociology, biology, engineering, and computer science. Recently, several community discovery algorithms have been proposed based on the optimization of a quantity called modularity (Q). However, the problem of modularity optimization is NP-hard, and the existing approaches often suffer from prohibitively long running time or poor quality. Furthermore, it has been recently pointed out that algorithms based on optimizing Q will have a resolution limit, i.e., communities below a certain scale may not be detected. In this research, we first propose an efficient heuristic algorithm, Qcut, which combines spectral graph partitioning and local search to optimize Q. Using both synthetic and real networks, we show that Qcut can find higher modularities and is more scalable than the existing algorithms. Furthermore, using Qcut as an essential component, we propose a recursive algorithm, HQcut, to solve the resolution limit problem. We show that HQcut can successfully detect communities at a much finer scale and with a higher accuracy than the existing algorithms. Finally, we apply Qcut and HQcut to study a protein-protein interaction network, and show that the combination of the two algorithms can reveal interesting biological results that may be otherwise undetectable.
1 Introduction
Community structure divides network vertices into densely connected groups with fewer external links, offering a functional view of complex systems. The paper addresses modularity optimization’s computational and resolution-limit problems with Qcut and HQcut.
- Motivation: Community structure groups vertices with many within-group connections and relatively fewer links to other groups.Such communities may correspond to functional units, including similarly functioning genes or similarly themed web pages.
- Motivation: Community discovery must determine both what constitutes a community and how to find communities without prior structural knowledge.No universally accepted community definition exists, and algorithms should distinguish meaningful structure from essentially random networks.
- Challenges: Modularity optimization is NP-hard, while existing approaches can suffer from long running times or poor quality.The paper uses modularity Q as a quantitative measure for assessing community structures.
- Challenges: Modularity optimization may merge communities below a certain scale or with relatively high inter-community connectivity.This resolution limit casts doubt on modularity optimization as a complete solution for community discovery.
- Contributions: Qcut combines spectral graph partitioning with local search to find higher Q values, improve scalability, and recover known communities more accurately on suitable synthetic networks.The paper evaluates Qcut on synthetic and real networks.
- Contributions: HQcut recursively applies Qcut to subcommunities and uses a statistical test to avoid over-partitioning, detecting finer-scale communities with higher accuracy than modularity-only algorithms.The paper also discusses small communities, noisy interconnections, and hierarchical structure as practical sources of the resolution limit.
- Application: Combining Qcut and HQcut in a budding-yeast protein-protein interaction network revealed biological results that might otherwise remain undetected.The study analyzes the biological significance of the resulting communities.
2 Community identification by modularity optimization
The paper formulates community discovery as modularity optimization and uses a two-stage Qcut procedure to obtain and refine approximate solutions. Spectral partitioning supplies an initial division, while local search applies improving vertex migrations, merges, and splits.
- Modularity formulation: Modularity Q measures within-community edge fraction minus the fraction expected under random edge placement.A larger Q indicates stronger community structure; Q ≤0 indicates no excess intra-community edges, while a single-cluster partition has Q = 0.
- Qcut procedure: Because optimizing Q is NP-hard, Qcut uses recursive spectral graph partitioning followed by local refinement.The partitioning stage stops dividing when no Q improvement is achieved.
- Qcut procedure: Local refinement considers vertex migration, community merging, and community splitting, always selecting the operation with the highest Q improvement.Splitting is considered only after migration and merging cannot improve Q, because it is more expensive to search.
- Qcut procedure: Migration is favored toward a relatively smaller community where the vertex has more connections.The paper interprets this condition using community sizes and the vertex’s connections to candidate communities.
- Qcut procedure: The migration change table records each potential Q change for moving a vertex between communities, with sparse-network structure allowing many entries to be zero.The table has N×K potential entries, where N is the number of vertices and K is the number of communities.
- Qcut procedure: The merge-change table S stores the potential Q change for combining each pair of communities.For communities i and j, s_ij represents the potential modularity change from merging them.
- Qcut procedure: Qcut repeatedly chooses the operation with the greatest positive improvement and avoids recomputing unchanged entries in its cached tables.The procedure terminates when no positive entry remains; its stated worst-case bound is at most M^2 iterations.
- Comparison: Compared with Newman’s spectral approach, Qcut uses a typically sparse Laplacian matrix instead of an almost-complete modularity matrix, reducing memory needs and improving scalability.Both spectral methods can approximately optimize Q, but their matrix structures differ substantially.
3 Limitation of modularity optimization and a solution
Modularity optimization can merge small or hierarchically embedded communities because its expected-edge criterion depends on network scale and assumes a flat structure. HQcut addresses this by recursively applying Qcut and using modularity and statistical-significance tests, while a Monte Carlo procedure distinguishes community relationships.
- Limitation of modularity optimization: Qcut merges communities i and j when their connecting edges exceed the expected count a_i a_j/2M, improving modularity.This criterion treats higher-than-expected connectivity as evidence that the sub-networks should not remain separate.
- Limitation of modularity optimization: When two cliques connect to a large network, modularity can merge them despite their single connecting edge once M exceeds a_i a_j/2.The expected inter-clique edge count then falls below one, producing the resolution limit problem.
- Limitation of modularity optimization: Small communities connected by erroneous edges may become non-separable, because modularity optimization assumes that all network edges are reliable.This is especially relevant to social and biological networks constructed from survey or experimental data.
- Limitation of modularity optimization: Modularity also assumes a non-hierarchical community structure and unrestricted vertex connectivity, although communities may depend on the analysis granularity.The paper distinguishes statistically chance-linked affiliated communities from statistically closely associated communities, while noting no clear boundary between them.
- HQcut solution: HQcut recursively applies Qcut to sub-networks while ignoring inter-community edges, then tests whether further partitioning is warranted.This recursive strategy is designed to expose sub-community structure that coarse modularity optimization does not separate.
- HQcut solution: HQcut uses a modularity threshold and Monte Carlo Z-score test to reject weak or chance-level sub-community partitions.The default settings are minq = 0.3 and minz ≥ 2, corresponding to p = 0.05; results are generally insensitive across a wide parameter range.
- Relationship classification: Community pairs are called associated when random rewiring gives probability < 0.01 and affiliated when that probability exceeds 0.1; intermediate cases are ignored.The classification is applied only to candidate pairs whose merge would increase the entire network’s modularity.
4 Results
Experiments on synthetic and real networks show that Qcut improves modularity optimization, while HQcut recovers finer-scale and hierarchical communities, including biologically meaningful protein complexes.
- Computer-generated networks: Qcut and simulated annealing outperformed Newman in modularity optimization on the first synthetic network set.
- Computer-generated networks: HQcut achieved the highest accuracy across the second synthetic network set despite slightly lower modularities.
- Computer-generated networks: Qcut and Newman reached 100% accuracy on coarse communities but could not separate sub-communities, whereas HQcut achieved 99.9% sub-community accuracy.
- Real-world networks: On real networks, Qcut consistently obtained higher modularities than Newman and scaled better than Newman beyond approximately 1500 vertices.
- Real-world networks: HQcut usually returned fewer sub-communities than SA-2, indicating that SA-2 probably over-partitioned the tested networks.
- Biological network: HQcut matched 216 communities to known protein complexes with a weighted average matching score of 0.70, including 43 perfect matches.
- Biological network: The protein network contained 195 associated versus 83 affiliated communities, and examples such as RNA polymerases were separated into biologically related HQcut sub-communities.
5 Conclusions and discussion
The paper presents Qcut for efficient modularity optimization and HQcut for overcoming modularity’s resolution limit through recursive subdivision and statistical testing. The resulting framework improves fine-scale accuracy and identifies biologically meaningful hierarchical communities.
- Qcut combines spectral graph partitioning with local search to optimize modularity efficiently.
- Modularity can miss small or hierarchical communities, even when it identifies coarse community structure accurately.
- HQcut recursively applies Qcut and uses a statistical significance test to increase resolution without introducing spurious communities.
- HQcut recovered protein communities corresponding well to known complexes, whereas modularity-only communities may contain several complexes.
- HQcut’s success depends on Qcut effectively optimizing modularity, because merged communities can be recursively separated more readily than incorrectly split ones.
- The statistical test distinguishes resolution-limit cases caused by small communities from those caused by hierarchical communities.