Source-linked AI summary
Fast unfolding of communities in large networks
Vincent D. Blondel, Jean-Loup Guillaume, Renaud Lambiotte, Etienne Lefebvre
TL;DR
Community detection in large networks needs fast approximations because exact modularity optimization is computationally hard. This paper introduces a hierarchical modularity-optimization algorithm that analyzes networks exceeding 100 million nodes while achieving excellent accuracy compared with slower methods.
Problem
Community detection in large networks requires fast approximate partitioning because exact modularity optimization is computationally hard and existing methods face scale limits.
Method
The paper introduces a heuristic modularity-optimization algorithm that repeatedly moves nodes and aggregates communities to unfold a hierarchy.
Results
The algorithm analyzed networks exceeding 100 million nodes and showed excellent accuracy compared with slower community-detection methods.
Takeaways & Limitations
The method makes modular analysis of networks at whole-country or huge-Internet scales computationally accessible.
Takeaways & Limitations
Only the final partition’s accuracy was verified; the accuracy of intermediate hierarchical partitions remains untested.
Abstract
from arXiv · showhide
We propose a simple method to extract the community structure of large networks. Our method is a heuristic method that is based on modularity optimization. It is shown to outperform all other known community detection method in terms of computation time. Moreover, the quality of the communities detected is very good, as measured by the so-called modularity. This is shown first by identifying language communities in a Belgian mobile phone network of 2.6 million customers and by analyzing a web graph of 118 million nodes and more than one billion links. The accuracy of our algorithm is also verified on ad-hoc modular networks. .
1. Introduction
Community detection partitions large networks into densely connected groups, but exact modularity optimization is computationally hard. Existing methods therefore trade speed and partition quality, motivating improved approaches for increasingly large networks.
- Motivation: Large social, technological, and information networks can contain millions or billions of nodes, creating a need for methods that retrieve structural information at scale.Examples include social network services, mobile phone networks, and the web.
- Problem formulation: Community detection seeks partitions with dense within-community connections and sparse between-community connections, but precise optimization formulations are computationally intractable.Algorithms therefore aim to find reasonably good partitions reasonably quickly.
- Modularity: Modularity compares partition quality and can serve as an optimization objective, but exact modularity optimization is computationally hard for large networks.Approximation algorithms are consequently necessary.
- Limitations of prior work: The fastest prior large-network modularity algorithm produced significantly lower modularity than simulated annealing and could generate oversized super-communities.This artifact slowed the algorithm and made it inapplicable to networks of more than a million nodes.
- Motivation: 30739 nodes, about 400000 items, and about 5.5 million users were the largest network scales previously addressed, leaving substantial room for improvement.The passage contrasts these scales with Facebook’s about 64 million active users and larger contemporary systems.
2. Method
The algorithm alternates modularity-improving node moves with community aggregation to produce high-modularity partitions quickly and reveal community structure at multiple resolutions. Its efficiency comes from easily computed modularity gains and rapidly decreasing numbers of communities across passes.
- Hierarchy: Each pass decreases the number of meta-communities, enabling a complete hierarchical community structure with multiple detection resolutions.Intermediate partitions can preserve smaller communities that are merged in later passes.
- First phase: The first phase moves isolated nodes between neighboring communities when this increases modularity, using an easily computed gain ΔQ.The gain is evaluated by removing a node from its current community and considering its movement into a neighboring community.
- Second phase: The second phase aggregates each detected community into a node, preserving inter-community link weights and representing internal links as self-loops.The two phases are combined into repeated passes on progressively coarser weighted networks.
- Efficiency: The algorithm is unsupervised, intuitive, easy to implement, and suggested by simulations to have linear complexity on typical sparse modular networks.The reported efficiency is attributed to simple modularity-gain calculations and drastic community reduction after a few passes.
3. Application to large networks
The algorithm is evaluated on benchmark, web, synthetic, and Belgian mobile-phone networks, where it combines rapid computation with high modularity and identifies linguistically coherent communities. Tests also examine scalability, sensitivity to known structures, and language concentration across a detected hierarchy.
- Benchmark comparison: Across benchmark networks, the algorithm outperforms three compared community-detection methods in computation time and modularity.Table 1 compares the methods of Clauset, Newman and Moore, Pons and Latapy, Wakita and Tsurumi, and the proposed algorithm; empty cells indicate computation times over 24 hours.
- Large web networks: 39 million nodes and 783 million links were analyzed in a .uk web sub-network, alongside a separate 118-million-node web network.These were described as web networks of unprecedented sizes.
- Synthetic-network validation: The method was tested on 128-node synthetic networks divided into four 32-node communities to assess sensitivity to known community structure.Within-community and between-community links were generated with probabilities pin and pout, respectively.
- Language structure: More than 60% of German-speaking customers were concentrated in one community, whereas English-speaking customers were dispersed relatively evenly across communities.The operator’s customers could declare French, Dutch, English, or German.
4. Conclusion and discussion
The algorithm optimizes modularity on networks exceeding 100 million nodes, with main-memory storage—not computation time—the limiting factor in the experiments. It also produces complete hierarchical community structures, although the paper verifies only their top levels and leaves multi-resolution accuracy for further study.
- 4. Conclusion and discussion: The algorithm enables modularity optimization on networks of more than 100 million nodes, compared with around 5 million for previous methods.In the reported experiments, main-memory storage was the limitation rather than computation time.
- 4. Conclusion and discussion: By construction, each pass yields an intermediate partition, producing a complete hierarchical community structure for the network.The hierarchy consists of the partitions found at successive levels.
- 4. Conclusion and discussion: The paper verifies only the hierarchy’s top-level accuracy, so its qualitative multi-resolution behavior remains to be confirmed on networks with known or absent hierarchical structure and against tunable-resolution methods.The proposed checks include ad-hoc networks with known hierarchical structure, Erdős-Rényi random graphs, and comparisons with methods incorporating tunable resolution.