Source-linked AI summary
Finding overlapping communities in networks by label propagation
Steve Gregory
TL;DR
The paper addresses scalable detection of overlapping communities in large networks, extending label propagation so vertices can retain multiple community memberships. COPRA supports up to v memberships per vertex and is reported as highly effective and fast, though bipartite solutions can have lower modularity than projections.
Problem
Large networks require community detection that can represent overlapping memberships while remaining practical at scale.
Method
COPRA extends RAK label propagation by retaining multiple community identifiers using belonging coefficients, with v setting the maximum memberships per vertex.
Results
COPRA is well-suited to large real-world networks because its execution time grows slightly more than linearly with vertices and less than linearly with average degree.
Takeaways & Limitations
COPRA detects greater overlap as v increases, while retaining the ability to detect smaller overlap or disjoint communities when v is higher.
Takeaways & Limitations
Bipartite communities can have lower modularity than projected communities, partly because optimizing each mode conflicts with maintaining consistency between modes.
Abstract
from arXiv · showhide
We propose an algorithm for finding overlapping community structure in very large networks. The algorithm is based on the label propagation technique of Raghavan, Albert, and Kumara, but is able to detect communities that overlap. Like the original algorithm, vertices have labels that propagate between neighbouring vertices so that members of a community reach a consensus on their community membership. Our main contribution is to extend the label and propagation step to include information about more than one community: each vertex can now belong to up to v communities, where v is the parameter of the algorithm. Our algorithm can also handle weighted and bipartite networks. Tests on an independently designed set of benchmarks, and on real networks, show the algorithm to be highly effective in recovering overlapping communities. It is also very fast and can process very large and dense networks in a short time.
1. Introduction
Community detection reveals network structure, but many existing methods assume disjoint communities and practical algorithms must also scale to very large networks. The paper extends fast label propagation to detect overlapping communities.
- Community structure groups vertices densely internally and sparsely across communities, helping infer vertex attributes and coarse network organization.
- Most community detection algorithms target unipartite networks with undirected, unweighted edges and use varied techniques with different performance and speed.
- Many algorithms assume disjoint communities, although overlapping communities can better represent vertices belonging to multiple groups.
- Practical community detection algorithms must have very low time complexity to handle networks with millions of vertices in reasonable time.
- COPRA generalizes the near-linear-time RAK label propagation algorithm to overlapping communities using parameter v, with RAK recovered when v=1.
2. Detecting communities by label propagation
RAK detects communities by propagating vertex labels toward local neighbor majorities, then grouping shared labels and splitting disconnected groups. Asynchronous updates help ensure termination, while the method remains almost linear in network size.
- RAK initializes every vertex with a unique label, then repeatedly adopts the most frequent neighboring label, breaking ties randomly.
- Asynchronous updating mixes old and updated neighbor labels to ensure the propagation phase terminates when each vertex has a locally maximal label.
- After propagation, vertices sharing a label form a community, but disconnected groups are split into connected communities.
- The algorithm has almost linear time complexity: initialization is O(n), each iteration is O(m), and disconnected-community processing is O(m+n).
- Synchronous updating is more stable but requires more iterations than asynchronous updating, according to analysis by Leung et al.
3. Overlapping communities
COPRA extends label propagation to overlapping communities by storing weighted community identifiers, pruning labels with a threshold controlled by v, and using synchronous updates. It includes termination and postprocessing steps, supports weighted networks, and has essentially linear per-iteration complexity for sparse networks when v is small.
- 3.1. Extending to overlapping communities: Each vertex label stores community identifiers with belonging coefficients that sum to 1, allowing propagation to represent overlapping membership.Each update unions neighbors’ labels, sums coefficients, and normalizes.
- 3.1. Extending to overlapping communities: COPRA retains identifiers with belonging coefficient at least 1/v, so v bounds the maximum number of communities per vertex.If all coefficients fall below the threshold, only the greatest is retained; ties are resolved randomly, followed by renormalization.
- 3.1. Extending to overlapping communities: For v<2, COPRA is essentially the RAK algorithm, retaining only the identifier used by the greatest number of neighbors.The paper’s v=2 example produces two overlapping communities, {a,b,c,d} and {a,e,f,g}.
- 3.2. Design alternatives: Several alternatives were rejected: degree-dependent thresholds and alternative handling of below-threshold identifiers performed less successfully, while limiting propagation improved worst results but harmed best results.The propagation-limiting method sometimes restricted community sizes more than appropriate.
- 3.3. Termination: COPRA uses a new termination condition because complex labels and synchronous updating make the RAK criterion unsuitable; the condition is inexpensive and works well in practice, but lacks a proof of selecting the best iteration.The number of identifiers decreases monotonically until it reaches a minimum.
- 3.4. Postprocessing: After termination, vertices are assigned to communities by their retained identifiers, and subset communities are deleted during construction in linear time.The implementation’s overall per-iteration cost is O(vm log (vm/n)); for sparse networks it is O(v3n) plus O(vn log(v)) per iteration, essentially linear when v is small.
4. Experiments
COPRA was evaluated on synthetic and real networks using overlap modularity, NMI, stability, speed, and comparisons with other community-detection algorithms. Results show that its parameter v strongly affects quality, while COPRA remains effective and fast on large networks.
- Methodology: COPRA’s overlap modularity was evaluated on real networks, with results averaged over 100 runs because the algorithm can be nondeterministic.The experiments used overlap modularity Qov, which accounts for each vertex’s number of communities and equal membership strengths.
- Properties of the algorithm: Termination occurred soon after maximum modularity on the PGP network, supporting the effectiveness of COPRA’s termination criterion there.Modularity increased with iterations, reached a maximum, and then fluctuated slightly.
- Properties of the algorithm: On overlapping synthetic networks, solution quality improved with v and became almost perfect at v=7 or 8, whereas v=1 performed poorly.For disjoint networks, v=1 was near-perfect and increasing v to 9 caused no adverse effect; the best solutions used v=4–9.
- Properties of the algorithm: The synthetic-network results reflect accurate recovery of both community count and overlap: for overlapping networks, v=6,…,9 produced overlap values of 1.46–1.51 versus the correct 1.5.For the overlapping network, the number of detected communities increased from 275 to 285 as v rose from 1 to 7, compared with the correct count of 305.
- Properties of the algorithm: COPRA’s runtime scaled favorably: time per iteration increased sublinearly with v, while increasing edges generally increased time per iteration linearly and iterations sublinearly or decreasingly.The predicted worst-case time per iteration was O(vm log (vm/n)), but observed growth was better than predicted.
5. Bipartite networks
COPRA extends overlapping community detection to bipartite networks by coordinating label propagation across the two vertex modes. Experiments on Southern Women and Autism networks show useful solutions, while bipartite modularity can trail projection-based results because the method balances both modes.
- Motivation: Projection-based detection can lose information and produce communities that are inconsistent across the two modes.
- Method: COPRA modifies propagation so labels pass between the larger and smaller vertex sets in a coordinated sequence.Labels are propagated first from the larger mode using updated labels, then from the smaller mode using the previous labels.
- Autism: The Autism network contains 4084 papers, 8498 authors, and 20099 edges, with projections containing 59935 and 51433 edges.
- Autism: For Autism, v=9 produced 372 bipartite communities with modularities 0.615 for papers and 0.720 for authors, below the projection results.The paper attributes this reduction partly to a compromise between maximizing each mode’s modularity and maintaining cross-mode consistency.
- Method: COPRA can also process almost-bipartite networks when vertex modes are known, even if intramode edges are present.
6. Conclusions
COPRA extends label propagation to detect overlapping communities while supporting weighted and bipartite networks. Experiments show strong performance and scalability, though it inherits nondeterminism and other theoretical drawbacks from RAK.
- 6.1. Contributions: COPRA extends RAK label propagation with multiple community identifiers, synchronous updating, and a termination condition that permits overlapping communities.It also handles weighted and bipartite networks.
- 6.1. Contributions: COPRA inherits RAK’s theoretical drawbacks, including the tendency to find one of many suboptimal partitions, which the paper does not address.The authors suggest that recent RAK improvements may also apply to COPRA.
- 6.2. Discussion: Synthetic-network results are excellent and stable with relatively little mixing or overlap, but performance suddenly declines when either increases too far.An incorrect random choice can let a community identifier flood the network; LFM behaves similarly, while CFinder and CONGO deteriorate more gradually.
- 6.2. Discussion: COPRA performs well on larger networks and slightly better on smaller communities, whereas CFinder is biased toward smaller communities but unaffected by network size.These results distinguish COPRA’s scaling behavior from CFinder’s community-size bias.
- 6.2. Discussion: Increasing v permits greater detectable overlap without impairing detection of smaller overlap or disjoint communities, but excessive v causes identifiers to propagate too far.The authors therefore limit plotted values of v because higher values give worse results, especially for smaller networks.
- 6.2. Discussion: Users are advised to try the largest v producing a good, high-modularity solution, since COPRA’s speed often makes repeated runs feasible.The recommendation addresses parameter selection for real networks.
- 6.2. Discussion: Allowing v greater than one reduces the number of iterations required, despite increasing execution time per iteration, and often makes COPRA less nondeterministic than RAK.COPRA can retain several community identifiers instead of choosing randomly between them.
- 6.2. Discussion: COPRA’s strongest practical advantage is speed: runtime grows slightly more than linearly with vertices and less than linearly with average degree.This makes it suitable for large real-world networks where CFinder, LFM, and CONGO are impractically slow.