Source-linked AI summary
Detecting highly overlapping community structure by greedy clique expansion
Conrad Lee, Fergal Reid, Aaron McDaid, Neil Hurley
TL;DR
Existing community-assignment algorithms are difficult to assess realistically and often perform poorly when many nodes belong to multiple communities. The paper introduces Greedy Clique Expansion, which expands maximal cliques through greedy local fitness optimization, and evaluates it across synthetic and empirical networks. GCE accurately recovers highly overlapping synthetic communities and performs competitively or best in the reported comparisons.
Problem
Community-assignment algorithms lack realistic benchmarks and often perform poorly when community overlap is substantial.
Method
Greedy Clique Expansion uses maximal cliques as seeds and greedily expands each seed using a local community fitness function.
Results
GCE accurately recovers communities when nodes belong to multiple communities, performs competitively on non-overlapping LFR graphs, and gives the best results among compared overlapping methods.
Takeaways & Limitations
GCE provides a community-assignment approach that remains effective on highly overlapping synthetic networks and is competitive across the paper’s broader evaluations.
Takeaways & Limitations
On four larger collegiate Facebook networks, no algorithm achieved an NMI value greater than 0.01, with dorm labels and social structure potentially limiting the benchmark.
Abstract
from arXiv · showhide
In complex networks it is common for each node to belong to several communities, implying a highly overlapping community structure. Recent advances in benchmarking indicate that existing community assignment algorithms that are capable of detecting overlapping communities perform well only when the extent of community overlap is kept to modest levels. To overcome this limitation, we introduce a new community assignment algorithm called Greedy Clique Expansion (GCE). The algorithm identifies distinct cliques as seeds and expands these seeds by greedily optimizing a local fitness function. We perform extensive benchmarks on synthetic data to demonstrate that GCE's good performance is robust across diverse graph topologies. Significantly, GCE is the only algorithm to perform well on these synthetic graphs, in which every node belongs to multiple communities. Furthermore, when put to the task of identifying functional modules in protein interaction data, and college dorm assignments in Facebook friendship data, we find that GCE performs competitively.
1. INTRODUCTION
Community-assignment algorithms are difficult to evaluate realistically, especially for highly overlapping communities. The paper introduces GCE and benchmarks it on high-overlap synthetic and empirical networks.
- Benchmarking gap: Realistic benchmarking is hindered by scarce ground-truth datasets and simplistic synthetic graphs with unrealistic topology and non-overlapping memberships.Popular GN benchmarks lack heterogeneous degree distributions, varied community sizes, triadic closure, and overlapping communities.
- Benchmarking gap: Benchmarking research has received too little attention to establish which graph-clustering methods are most reliable in applications.The paper frames this as a serious limitation of the field.
- Overlapping communities: LFR benchmarks revealed that many community-assignment algorithms perform poorly even on moderately overlapping community structure.This matters because social networks such as Facebook commonly contain users connected to multiple distinct social groups.
- Overlapping communities: Facebook ego networks illustrate the challenge: users may belong to several groups formed across high-school, college, professional, and family settings.Algorithms that assign each node to only one community cannot represent all of these memberships.
- Paper response: The paper introduces Greedy Clique Expansion and benchmarks it against leading overlapping-community methods on highly overlapping synthetic graphs and two empirical datasets.The empirical benchmarks use protein-protein interaction data and Caltech’s Facebook friendship network.
2. METHOD
GCE detects communities by expanding clique-based seeds through greedy local optimization, while filtering near-duplicate results. Its design targets networks with highly overlapping community structure and uses clique size and fitness parameters to balance false positives against false negatives.
- GCE workflow: GCE detects seeds, expands them serially by greedily maximizing a local community fitness function, and accepts only communities that are not near-duplicates.This workflow combines seed selection, local expansion, and duplicate filtering.
- Fitness function: The local fitness function formalizes community quality through internal and external connectivity, but its suitability depends on the type of network data.The paper reports that the Lancichinetti et al. function performed well across diverse synthetic and empirical data.
- Fitness function: The parameter α controls fitness behavior: lower α values make larger communities fitter, with α values from 0.9 −1.5 providing the best results.The reported range follows the experience of Lancichinetti et al.
- Greedy expansion: A seed expands by evaluating each frontier node, adding the node with largest fitness when that fitness is positive, and stopping otherwise.The procedure repeats frontier-fitness calculations after each accepted addition.
- Seed selection: GCE uses maximal cliques as seeds because they are characteristic structures within communities and, after filtering smaller embedded cliques, are rare.The paper distinguishes this clique-seeded strategy from prior greedy expansion algorithms.
- Parameter choices: The minimum clique size k must be large enough to avoid false-positive seeds but small enough to include every target community, with k values of 3 or 4 generally satisfying these requirements.Communities detectable by GCE must contain a clique with k or more nodes; the paper notes that LFR results indicate this requirement is not overly restrictive.
3. OPTIMIZATIONS
GCE combines clique-based seeding, greedy local expansion, duplicate-community filtering, and the CCH heuristic to improve computational performance. Its runtime scales favorably with graph size but is sensitive to node degree, while CCH can substantially reduce redundant processing.
- Seed selection: GCE finds maximal cliques as expansion seeds using Bron–Kerbosch, which is efficient for sufficiently sparse graphs.The implementation uses Bron–Kerbosch to enumerate maximal cliques in the analyzed synthetic and empirical networks.
- Greedy expansion: Initial frontier identification has complexity O(|E| × M), where M is the number of cliques expanded.Frontiers are identified through symmetric differences between endpoint seed sets.
- Greedy expansion: During greedy expansion, GCE adds the fittest frontier node and updates the frontier using that node’s neighbors and degree information.The update requires at most θ insertions, where θ is the graph’s maximum degree, and fitness depends on internal and external degrees.
- Clique Coverage Heuristic: CCH orders maximal cliques largest first and rejects a clique when too many of its nodes are already covered by accepted larger cliques.The threshold is controlled by the proportion φ of nodes contained in at least two previously accepted larger cliques.
- Clique Coverage Heuristic: On the Oklahoma State Facebook subnetwork, CCH reduced cliques from over 46 million to around 5000 while producing almost identical results to GCE without CCH.CCH is intended as a computational speedup and was found not to significantly alter benchmark results.
- Performance characteristics: GCE scales favorably as graph size increases, but on 5000-node graphs its runtime rises rapidly with average degree; CCH improves scalability.Figure 3 reports operation on over ten million edges in two minutes under constant degree and community size.
4. SYNTHETIC BENCHMARKS
The paper benchmarks community assignment algorithms on LFR graphs with increasingly overlapping communities and finds that GCE remains effective where other methods often fail. It also compares GCE with established algorithms on standard disjoint-community benchmarks.
- Overlapping benchmarks: The benchmarks test CAAs on synthetic graphs where nodes belong to up to five communities, extending beyond previously studied moderate overlap.The fifth graph assigns every node to five communities; successive graphs increase both overlap and average degree.
- Benchmark limitations: The high-overlap benchmark parameters were chosen by the authors because comparable benchmarks had not previously been carried out.This parameter-selection constraint is stated as a limitation of the synthetic evaluation.
- Benchmark design: LFR graphs provide scale-free degree and community-size distributions, while NMI compares planted ground-truth communities with algorithmically found communities.The benchmark procedure constructs a graph, runs a CAA, and compares the resulting communities with the planted structure.
- Overlapping benchmarks: GCE shows robust accuracy as overlap increases, whereas existing algorithms perform poorly even at moderate overlap.Figure 5 evaluates nine CAAs on LFR graphs with increasing community overlap; the authors describe GCE’s robustness as unprecedented.
- Overlapping benchmarks: LFM and GCE use the same fitness function and similar greedy heuristics, yet their results differ substantially; the authors speculate that LFM’s random seeds prematurely abandon unexplored regions.The comparison highlights seed selection as a possible explanation for the performance gap.
- Disjoint benchmarks: On standard disjoint-community benchmarks, GCE clearly outperforms several classic methods and performs competitively with leading community-partitioning algorithms.GCE outperforms GN, Radicchi, EM, MCL, an information-theoretic method, and a spectral method; results against other methods are mixed.
5. EMPIRICAL BENCHMARKS
The paper evaluates GCE on empirical protein-interaction and Facebook friendship networks with available ground truths. GCE achieves the highest reported NMI for the protein-complex benchmark among the compared methods.
- Empirical evaluation: The empirical evaluation targets meaningful communities in non-trivial networks for which ground-truth information is available.The authors use protein complexes and college dorm assignments as two empirical datasets.
- Protein interaction benchmark: The protein–protein interaction network contains 1622 proteins and 9070 interactions, with known protein complexes used as approximate ground truth.Complexes with fewer than four proteins were removed because they were not recognizable as network communities.
- Protein interaction benchmark: GCE’s found communities have the highest NMI with the protein-complex ground truth, followed closely by abchampions and clique percolation.The result is reported for the compared methods in the protein-interaction benchmark.
4 Available at http://wodaklab.org/cyc2008/
The evaluation applies GCE and other community assignment algorithms to protein-interaction and Facebook friendship networks, using NMI and F1-based analyses. GCE has the strongest overlapping-algorithm results for protein complexes, while larger collegiate Facebook networks yield uniformly low NMI.
- Protein-interaction data: F1-score analysis selects each known complex’s best-matching found community, with 1.0 denoting perfect recovery.The resulting best F1-scores are shown as a histogram.
- Protein-interaction data: Among overlapping algorithms, GCE finds the most perfectly recovered communities and the fewest poor matches, although non-overlapping MCL performs slightly better.The comparison uses the F1-score histograms of the highest-performing algorithms.
- Facebook friendship data: CalTech Facebook evaluation compares algorithm communities with dorm assignments using NMI, excluding nodes with unknown dorm assignments.Dorm assignment is treated as an approximate ground truth for this network.
- Facebook friendship data: On four larger collegiate Facebook networks, no algorithm achieves NMI above 0.01.The authors cite weaker dorm-based social organization, a large off-campus category, and more unknown assignments as possible factors.
6. CONCLUSION
GCE combines clique finding with greedy expansion and is evaluated on highly overlapping synthetic graphs, LFR graphs, protein-interaction data, and social graphs. It performs especially well when nodes belong to multiple communities, while the authors identify benchmarking and heuristic limitations for future work.
- Conclusion: GCE combines a graph-structure-based clique-finding approach with the greedy expansion strategy used by other algorithms.The algorithm is designed for community structures with substantial overlap.
- Conclusion: GCE accurately recovers communities on synthetic networks in which every node belongs to four communities.No other algorithm performs nearly as well on synthetic graphs where every node belongs to two or more communities.
- Conclusion: Across LFR graphs with non-overlapping communities, GCE performs competitively, supporting robustness beyond the highly overlapping benchmark setting.The authors also apply GCE to biological and social networks with ground-truth attributes.
- Conclusion: Compared with other overlapping community assignment algorithms, GCE gives the best results on the evaluated protein-interaction and social-graph applications.The applications recover biological communities and infer nonnetwork attributes, respectively.
- Further work: GCE currently uses only a simple greedy expansion heuristic, and a parallel implementation could improve scalability.The paper proposes investigating more sophisticated local heuristics and parallelization.
- Further work: Future work should improve benchmarking with systematic tests of topology-dependent breakdowns and better empirical networks with known communities.The authors note that synthetic and empirical benchmarks address complementary evaluation needs.