A classification for community discovery methods in complex networks

By Michele Coscia, Fosca Giannotti, Dino Pedreschi. Statistical analysis and data mining, 2011

370 citations recorded by the source corpus.

Many real‐world networks are intimately organized according to a community structure. Much research effort has been devoted to develop methods and algorithms that can efficiently highlight this hidden structure of a network, yielding a vast literature on what is called today community detection. Since network representation can be very complex and can contain different variants in the traditional graph model, each algorithm in the literature focuses on some of these properties and establishes, explicitly or implicitly, its own definition of community. According to this definition, each proposed algorithm then extracts the communities, which typically reflect only part of the features of real communities. The aim of this survey is to provide a ‘user manual’ for the community discovery problem. Given a meta definition of what a community in a social network is, our aim is to organize the main categories of community discovery methods based on the definition of community they adopt. Given a desired definition of community and the features of a problem (size of network, direction of edges, multidimensionality, and so on) this review paper is designed to provide a set of approaches that researchers could focus on. The proposed classification of community discovery methods is also useful for putting into perspective the many open directions for further research. © 2011 Wiley Periodicals, Inc. Statistical Analysis and Data Mining 4: 512–546, 2011

Subfields: Artificial Intelligence, Molecular Biology, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/1e9c2ca8db52407381bf34ec02ca9fbf3b25bcea

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

In Molecular Biology

In Statistical and Nonlinear Physics

Citations in the corpus

Community detection in social networks (2016, methodology): “Other reviews available in the literature are by Coscia et al.(9) in 2011, Fortunato and Castellano(10) in 2012, Porter et al.”
Clustering attributed graphs: Models, measures and methods (2015, methodology): “Although several surveys on graph clustering have been written (Schaeffer, 2007; Fortunato, 2010; Aggarwal & Wang, 2010; Coscia et al., 2011), most of the approaches to cluster attributed graphs are more recent and have not been included in these works.”
Clustering and Community Detection in Directed Networks: A Survey (2013, methodology): “[23] present a categorization for community discovery methods according to the definition of community they adopt (e.”
Community Discovery in Dynamic Networks (2017, background): “Among them community discovery (Coscia et al. , 2011; Fortunato, 2010), link-based object ranking (Duhan et al. , 2009; Getoor and Diehl, 2005), frequent pattern mining (Alon, 2007; Milo et al. , 2002) are examples of analytical tasks originally deﬁned on networks “frozen in time” .”
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).”
Non-overlapping community detection (2018, methodology): “In (Coscia, Giannotti, and Pedreschi 2011), thirteen algorithms have been compared using a graph extracted from the ego network of one of the authors’ Facebook profiles.”
DEMON: a local-first discovery method for overlapping communities (2012, background): “In cases like this, also generic community discovery algorithms tend to return not meaningful communities, as they typically try to cluster the whole structure and return some huge communities and a long list of small branches (see [6]).”
A survey of community search over big graphs (2019, background): “In the literature, there is a highly related group of research works, called community detection (CD) [159, 45,155,157,111].”