Overlapping community detection in networks: The state-of-the-art and comparative study

By Jierui Xie, Stephen Kelley, Boleslaw K. Szymanski. 2011

1,249 citations recorded by the source corpus.

This article reviews the state-of-the-art in overlapping community detection algorithms, quality measures, and benchmarks. A thorough comparison of different algorithms (a total of fourteen) is provided. In addition to community-level evaluation, we propose a framework for evaluating algorithms' ability to detect overlapping nodes, which helps to assess overdetection and underdetection. After considering community-level detection performance measured by normalized mutual information, the Omega index, and node-level detection performance measured by F-score, we reached the following conclusions. For low overlapping density networks, SLPA, OSLOM, Game, and COPRA offer better performance than the other tested algorithms. For networks with high overlapping density and high overlapping diversity, both SLPA and Game provide relatively stable performance. However, test results also suggest that the detection in such networks is still not yet fully resolved. A common feature observed by various algorithms in real-world networks is the relatively small fraction of overlapping nodes (typically less than 30%), each of which belongs to only 2 or 3 communities.

Subfields: Computer Networks and Communications, Statistical and Nonlinear Physics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

In Statistical and Nonlinear Physics

Citations in the corpus

Regularizing Text Categorization with Clusters of Words (2016, background): “As we observe that the collection-level graph-ofwords does not create well separated communities of terms, overlapping community detection algorithms, like the work of Xie et al. (2013) fail to identify “good" groups and do not offer better results.”
A Comprehensive Survey on Community Detection With Deep Learning (2021, background): “Moreover, detection techniques have been reviewed over disjoint and overlapping [6], [7] community types .”
Community Detection in Networks with Node Attributes (2013, background): “On the other hand, community detection algorithms aim to ﬁnd communities based on the network structure, e.g. , to ﬁnd groups of nodes that are densely connected [14], [39], but they typically ignore node attributes.”
Learning Community Embedding with Community Detection and Node Embedding on Graphs (2017, background): “A comprehensive survey of recent community detection algorithms can be found in [32].”
Hiding individuals and communities in a social network (2016, neutral): “Specifically, given a node vi ∈ V and an undirected network, we have: cdegr(G, vi) = |NG(vi)| n− 1 cclos(G, vi) = n− 1 ∑ vj∈V dG(vi, vj) cbetw(G, vi) = 2 (n− 1)(n− 2) ∑ vj ,vk∈V \{vi} |{p ∈ spG(vj , vk) : vi ∈ p}| |spG(vj , vk)| On the other hand, given a directed network, we have: cdegr(G, vi) = |N”
Clustering attributed graphs: Models, measures and methods (2015, background): “Other problems include how to measure the significance of overlapping nodes and how to interpret the resulting communities (Xie et al., 2013).”
Social big data: Recent achievements and new challenges (2015, background): “[58] reviewed the state of the art in overlapping comunity detection algorithms.”
Community Interaction and Conflict on the Web (2018, background): “However, analyses of intercommunity interaction and conflict are largely absent in previous work on web communities, which tend to focus on community detection [18, 80], interactions within individual communities [38, 47, 49], or how users spread their time”
Handbook of Big Data (2016, background): “• Hit s to return to the blockplot in the main window.”
A Survey of Community Detection Approaches: From Statistical Modeling to Deep Learning (2021, methodology): “ing methods by focusing on learning, a central issue of community modeling and community detection, whereas the existing reviews [37], [38] generally discuss the chronological development of the existing methods.”
Community Discovery in Dynamic Networks (2017, neutral): “; Cazabet and Amblard, 2011; Cazabet et al., 2010; Duan et al., 2012; Falkowski et al., 2008; Gorke et al., 2012; Lee et al., 2014; Ma and Huang, 2013; Nguyen et al., 2011a,b; Rossetti et al., 2017; Xie et al., 2013a; Zakrzewska and Bader, 2015) Refer to Appendix IX.B for methods description. 3. Inf”
Overlapping community detection at scale: a nonnegative matrix factorization approach (2013, background): “A large body of work in computer science, statistics, applied mathematics, and statistical physics has been devoted to identifying community structure in complex networks (see [8, 28, 32] for surveys of this area).”
Data-Driven Tree Transforms and Metrics (2017, background): “The field of community detection also addresses finding overlapping clusters in graphs [34].”
Community detection in networks: A user guide (2016, background): “More info on network clustering can be found in several review articles (Chakraborty et al., 2016; Coscia et al., 2011; Fortunato, 2010; Malliaros and Vazirgiannis, 2013; Newman, 2012; Parthasarathy et al., 2011; Porter et al., 2009; Schaeffer, 2007; Xie et al., 2013).”
Detecting cohesive and 2-mode communities indirected and undirected networks (2014, background): “Detecting communities of densely connected sets of nodes is an extensively researched area [14, 30, 35, 42] with a plethora of different algorithms and heuristics.”
Community detection in social networks (2016, methodology): “There exists another exhaustive review of methods for discovering overlapping communities conducted by Xie et al. 73 The following section discusses some of the methods used to detect overlapping communities.”