Source-linked AI summary
Near linear time algorithm to detect community structures in large-scale networks
Usha Nandini Raghavan, Reka Albert, Soundar Kumara
TL;DR
Community detection needs methods that can handle large networks without prior community information or expensive optimization. This paper develops label propagation, in which nodes adopt majority neighbor labels, and validates the resulting communities on known network structures while reporting multiple modular solutions and varied community sizes.
Problem
Large-scale community detection methods may require prior numbers or sizes of communities or be computationally expensive, despite the importance of identifying structure in real-world networks.
Method
The algorithm initializes each node with a unique label and asynchronously propagates majority neighbor labels until nodes sharing labels form communities.
Results
The algorithm recovered known structures in karate-club and college-football networks and produced multiple significantly modular solutions, including WWW solutions with Q between 0.857 and 0.864.
Takeaways & Limitations
The method determines community numbers and sizes from network structure alone, without external parameter settings or restrictions on community sizes.
Abstract
from arXiv · showhide
Community detection and analysis is an important methodology for understanding the organization of various real-world networks and has applications in problems as diverse as consensus formation in social communities or the identification of functional modules in biochemical networks. Currently used algorithms that identify the community structures in large-scale real-world networks require a priori information such as the number and sizes of communities or are computationally expensive. In this paper we investigate a simple label propagation algorithm that uses the network structure alone as its guide and requires neither optimization of a pre-defined objective function nor prior information about the communities. In our algorithm every node is initialized with a unique label and at every step each node adopts the label that most of its neighbors currently have. In this iterative process densely connected groups of nodes form a consensus on a unique label to form communities. We validate the algorithm by applying it to networks whose community structures are known. We also demonstrate that the algorithm takes an almost linear time and hence it is computationally less expensive than what was possible so far.
I. INTRODUCTION
Community detection seeks groups of similar, densely connected nodes in real-world networks, but existing methods may require prior community information or substantial computation. The paper proposes label propagation as a simple, structure-guided alternative that determines communities without preset numbers or sizes.
- Motivation: Community detection supports understanding complex systems represented by web, social, and biological networks.Applications include extrapolating webpage information, identifying social characteristics, and finding functional molecular modules.
- Motivation: Communities are groups of nodes that are similar internally and dissimilar from the rest of a network.They are usually densely interconnected within groups and sparsely connected across groups.
- Existing approaches: Network partitioning divides graphs into approximately equal groups, whereas community detection identifies similarity-based groups whose number and sizes are not known beforehand.This distinction makes community detection different from fixed-constant partitioning problems.
- Existing approaches: Existing community methods include hierarchical, simulation-based, spectral, and flow-maximization approaches.Hierarchical methods produce series of partitions, while other methods seek partitions using structural measures or optimization procedures.
- Proposed approach: The proposed algorithm initializes every node with a unique label and repeatedly assigns each node the most common label among its neighbors.Densely connected groups reach consensus, and nodes with the same final label form communities without optimizing a predefined measure.
II. DEFINITIONS AND PREVIOUS WORK
Community detection has no universally accepted definition, and existing methods use varied structural, hierarchical, flow-based, spectral, and label-flooding approaches. The paper motivates a structure-only algorithm designed for large networks without prior community information.
- Community definitions: A community may be defined as a clique, a chain of adjacent k-cliques, a k-clan, or a k-club.These definitions differ in strictness and whether communities may overlap.
- Community definitions: Degree-based definitions distinguish strong and weak communities using internal and external node degrees.These provide alternative criteria for judging whether a group has community structure.
- Community evaluation: Modularity compares observed within-group edge density with the density expected under a random baseline.Q = 0 indicates no excess within-group density, while values closer to 1 indicate stronger community structure.
- Previous methods: Hierarchical methods represent successive partitions in a dendrogram, while some approaches select partitions by maximizing modularity or minimizing cuts.A dendrogram records the order in which nodes are segregated or groups are successively amalgamated.
- Previous methods: Label-flooding and spectral methods have important computational or setup constraints in the cited approaches.One label-flooding method requires O(n^3) time, while the Wu–Huberman method divides a network into two communities using specified nodes from different communities.
- Paper motivation: The paper targets a simple, time-efficient algorithm using only network structure and no prior number, size, or central-node information.It also avoids optimizing a specific community-strength measure.
III. COMMUNITY DETECTION USING LABEL PROPAGATION
The algorithm propagates labels through randomly ordered node updates, allowing densely connected groups to reach consensus and define communities without an optimization objective. Asynchronous updating avoids oscillations, but random tie-breaking permits multiple valid partitions.
- Label propagation: Each node starts with a unique label and repeatedly adopts the most frequent label among its neighbors, breaking ties uniformly randomly.
- Community formation: Dense regions first reach label consensus, then expand and compete at their boundaries before final communities are formed by shared labels.
- Asynchronous updating: Asynchronous updates use already updated and not-yet-updated neighbors, avoiding oscillations that can arise in bipartite or nearly bipartite subgraphs.
- Stopping condition: The stopping condition requires every node to carry a label held by the maximum number of its neighbors, rather than maximizing an objective function.
- Solutions and scope: The process can converge to multiple partitions because ties are resolved randomly, while homogeneous random graphs yield their giant connected component as one community.
- Evaluation networks: The algorithm is evaluated on karate-club, college-football, co-authorship, and actor-collaboration networks, including a network with 374511 nodes.
A. Multiple community structures
Random tie-breaking can produce distinct community partitions from repeated runs. The paper compares these solutions using agreement measures and modularity ranges to assess their similarity and structural significance.
- Multiple solutions: The algorithm produces three karate-club solutions and two football-network solutions, demonstrating that the stopping condition does not select a unique partition.
- Similarity measures: fsame compares the percentage of nodes assigned to the same groups across two solutions, using a community-overlap matrix.
- Figure 6: Figure 6 tabulates Jaccard similarity in the lower triangle, fsame in the upper triangle, and the modularity range Q for five runs per network.
- Similarity measures: Jaccard’s index complements fsame by measuring solution similarity on a 0-to-1 scale, with higher values indicating stronger similarity.
- Interpretation: The five repeated solutions are reported as similar, while their tight, high modularity ranges suggest that they represent significant community structures.
B. Aggregate
The paper aggregates multiple community-labeling solutions by combining labels nodewise and rerunning label propagation, producing a consensus structure. This aggregation favors finer communities when one solution splits a community identified by another.
- Aggregation procedure: For each node, the aggregate solution combines its labels from two input solutions into a new label.The aggregate labels are then used to initialize another label-propagation run.
- Aggregation procedure: New solutions are incorporated sequentially by combining them with the current aggregate solution.
- Aggregation preference: When one solution splits community T into S1 and S2, aggregation favors the smaller communities S1 and S2 over T.The authors identify this as one possible aggregation method among several alternatives.
- Aggregation results: On the WWW network, aggregate-solution Jaccard similarity ranges from 0.6604 to 0.7196, versus 0.4883 to 0.5931 for individual solutions.The paper reports that aggregate solutions are consequently very similar and that five solutions can provide as much insight as a larger solution set.
IV. VALIDATION OF THE COMMUNITY DETECTION ALGORITHM
The algorithm was validated on networks with known community structures, including Zachary’s karate club and US college football. It recovered the main structures effectively, while the football network exposed a boundary caused by cross-conference connectivity.
- Known-structure validation: On Zachary’s karate club network, the algorithm effectively uncovered the underlying community structure.
- Known-structure validation: On the US college football network, the algorithm identified all conferences except Sunbelt.
- US football network: Sunbelt was difficult to recover because its teams formed two internally connected groups with only one game between them.Cross-group links from four Sunbelt teams to seven Southeastern teams further connected the conference to Southeastern.
- US football network: Across two solutions, Sunbelt either merged with Southeastern or split into two groups associated with Southeastern and another grouping.
V. TIME COMPLEXITY
The implementation is described as near-linear per iteration and reaches a stable labeling quickly. By iteration 5, at least 95% of nodes were classified correctly in the reported experiments, although disconnected groups can retain the same label.
- Per-iteration complexity: Initializing unique labels takes O(n) time, and each label-propagation iteration takes O(m) time in the number of edges.At each node, grouping neighbors by label and selecting a largest group together require time proportional to its degree.
- Convergence: 95% or more of nodes were classified correctly by iteration 5, irrespective of network size n, in the experiments.The paper defines correct classification as having the label held by the maximum number of neighbors.
- Convergence: In Erdős-Rényi graphs with n between 100 and 10000 and average degree 4, the algorithm also reached at least 95% correct classification by iteration 5.Because these graphs lack community structure, all nodes in the giant connected component were assigned to one community.
- Post-processing: After termination, disconnected groups may share a label even when connected through nodes carrying different labels.The paper proposes a breadth-first search on each label-induced subnetwork to separate such groups.
VI. DISCUSSION AND CONCLUSIONS
The label propagation algorithm uses network structure alone, requires no prior community information, and finds effective community structures with nearly linear iteration cost. Its outputs include heterogeneous and power-law-distributed community sizes, as well as multiple significantly modular solutions.
- Validation: Validation on Zachary’s karate club and US college football networks found accurate communities with significant modularity values Q.The authors use these known-structure networks to assess the detected communities.
- Computational cost: Each iteration takes O(m) time, while mathematical convergence remains difficult to prove despite substantial convergence after about five iterations.The paper compares its time scale with other methods but notes the unresolved convergence proof.
- Algorithmic scope: The algorithm requires no a priori information about community number or sizes and determines them from network structure alone.This contrasts with the Wu–Huberman method, which requires the number of communities and favors approximately equal sizes.
- Community-size distributions: Test-network community sizes approximately follow power-law distributions with exponents ranging from 0.5 to 2, indicating no characteristic community size.The WWW and co-authorship networks show cutoffs, while the actor collaboration network changes scaling at 164 nodes.
- Multiple solutions: The algorithm finds multiple significantly modular community structures rather than only one maximum-Q partition.For the WWW network, five solutions have Jaccard similarities from 0.4883 to 0.5921 while Q ranges from 0.857 to 0.864.