Detecting highly overlapping community structure by greedy clique expansion
By Conrad Lee, Fergal Reid, Aaron F. McDaid, Neil J. Hurley. Knowledge Discovery and Data Mining, 2010
312 citations recorded by the source corpus.
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 the 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.
Subfields: Artificial Intelligence, Molecular Biology, Statistical and Nonlinear Physics
View Paper: https://www.semanticscholar.org/paper/261cf358dc9d5fe5ddeea8ad14e5b3c63077a2a6
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Jure Leskovec
- Jaewon Yang
- Boleslaw K. Szymanski
- Punam Bedi
- Chhavi Sharma
- Jierui Xie
- William L. Hamilton
- Stephan Günnemann
In Molecular Biology
- Jure Leskovec
- Jaewon Yang
- Boleslaw K. Szymanski
- Punam Bedi
- Chhavi Sharma
- Jierui Xie
- William L. Hamilton
- Stephan Günnemann
In Statistical and Nonlinear Physics
- Jure Leskovec
- Jaewon Yang
- Punam Bedi
- Chhavi Sharma
- Boleslaw K. Szymanski
- Jierui Xie
- Santo Fortunato
- Darko Hric
Citations in the corpus
- Community detection in social networks (2016, background): “Greedy clique expansion (GCE) 81 fi rst identi fi es cliques in a network.”
- Towards Linear Time Overlapping Community Detection in Social Networks (2012, background): “On a desktop with 2.80GHz CPU, SLPA took about six minutes to run over a two million nodes Amazon co-purchasing, which is ten times faster than GCE running over the same network.”
- Overlapping Communities Explain Core–Periphery Organization of Networks (2014, methodology): “(Refer to the extended version of the paper [35] for details.”