Community detection in graphs
By Santo Fortunato. 2009
11,570 citations recorded by the source corpus.
The modern science of networks has brought significant advances to our understanding of complex systems. One of the most relevant features of graphs representing real systems is community structure, or clustering, i.e. the organization of vertices in clusters, with many edges joining vertices of the same cluster and comparatively few edges joining vertices of different clusters. Such clusters, or communities, can be considered as fairly independent compartments of a graph, playing a similar role like, e.g., the tissues or the organs in the human body. Detecting communities is of great importance in sociology, biology and computer science, disciplines where systems are often represented as graphs. This problem is very hard and not yet satisfactorily solved, despite the huge effort of a large interdisciplinary community of scientists working on it over the past few years. We will attempt a thorough exposition of the topic, from the definition of the main elements of the problem, to the presentation of most methods developed, with a special focus on techniques designed by statistical physicists, from the discussion of crucial issues like the significance of clustering and how methods should be tested and compared against each other, to the description of applications to real networks.
Subfields: Molecular Biology, Statistical and Nonlinear Physics, Graph Learning, Algorithms & Complexity
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Molecular Biology
- Jure Leskovec
- Santo Fortunato
- Olaf Sporns
- Jaewon Yang
- Ludo Waltman
- Nees Jan van Eck
- Tiago P. Peixoto
- William L. Hamilton
In Statistical and Nonlinear Physics
- Jure Leskovec
- Santo Fortunato
- Olaf Sporns
- Mark Newman
- M. A. Porter
- Darko Hric
- Jaewon Yang
- Renaud Lambiotte
In Graph Learning
- Jure Leskovec
- William L. Hamilton
- Bryan Perozzi
- Michael M. Bronstein
- Stephan Günnemann
- Rex Ying
- Marinka Zitnik
- Philip S. Yu
In Algorithms & Complexity
- Mark Newman
- Jure Leskovec
- Olaf Sporns
- Marc Barthelemy
- Ludo Waltman
- Nees Jan van Eck
- E. Bullmore
- Jaewon Yang
Citations in the corpus
- Prioritizing network communities (2018, background): “(4) takes computational time linear in the size of the network, which is impractical for large networks with many detected communities.”
- Representation Learning on Graphs: Methods and Applications (2017, background): “In a similar vein as visualization, node embeddings are a powerful tool for clustering related nodes, a task that has countless applications from computational biology ( e.g. , discovering related drugs) to marketing ( e.g. , discovering related products) [23].”
- Graphite: Iterative Generative Modeling of Graphs (2018, background): “Graphs arise in a wide variety of domains in physical sciences, information sciences, and social sciences, and consequently algorithms for unsupervised representation learning of such data have several downstream applications, including node classification, link prediction, and community detection [”
- Geometric Deep Learning: Going beyond Euclidean data (2016, background): “In network analysis applications such as computational sociology, the topological structure of the social graph representing the social relations between people carries important insights allowing, for example, to classify the vertices and detect communities [48].”
- Regularizing Text Categorization with Clusters of Words (2016, methodology): “Having constructed the collection-level graph-ofwords, we can now apply community detection algorithms (Fortunato, 2010).”
- A Review of Relational Machine Learning for Knowledge Graphs (2015, background): “In social network analysis, link-based clustering is also known as community detection [54].”
- Optimal randomized classification trees (2021, neutral): “Extracting knowledge from data is a crucial task in Statistics and Machine Learning, which has applications in areas such as Biomedicine [1, 2], Criminal Justice [3, 4, 5], Fraud Detection [6], Privacy Protection [7], Health Care [8, 9, 10, 11], Risk Management [12, 13], Social Networks [14], and Co”
- Scalable Learning of Collective Behavior (2012, background): “Please refer to [30] for a comprehensive survey.”
- Hierarchical block structures and high-resolution model selection in large networks (2013, background): “[2] Santo Fortunato, “Community detection in graphs,” Physics Reports 486, 75–174 (2010).”
- A smart local moving algorithm for large-scale modularity-based community detection (2013, methodology): “ the highest values found in the literature. PACS: 89.75.Hc, 02.10.Ox 1. Introduction The problem of community detection in networks has received a lot of attention in the network science literature (Fortunato, 2010). Communities are clusters of closely connected nodes within a network. A popular ap”
- Exact controllability of complex networks (2013, methodology): “(5) and (6), respectively, S denotes the exact controllability of sparse networks from equation (5) and, LSB denotes the structural controllability from the”
- How semantic memory structure and intelligence contribute to creative thought: a network science approach (2017, background): “Finally, a network’s modularity, (Q), examines how a complex system comprised of many nodes and edges, breaks apart (or partitions) into smaller sub-networks (Fortunato, 2010; Newman, 2006).”
- Redrawing the Map of Great Britain from a Network of Human Interactions (2010, methodology): “However, multi-resolutions methods could be used to detect smaller robust communities (see [17]).”
- Statistical Inference on Random Dot Product Graphs: a Survey (2017, methodology): “Fortunato [36] provides an overview of partitioning techniques for graphs in general, and consistent partitioning of stochastic block models for two blocks was accomplished by Snijders and Nowicki [87] and for equal-sized blocks by Condon and Karp in 2001.”
- The relation between semantic memory structure, associative abilities, and verbal and figural creativity (2020, background): “Finally, Q measures the extent to which a network partitions into modules, or subcommunities (Fortunato, 2010; Newman, 2006).”
- Detecting cohesive and 2-mode communities indirected and undirected networks (2014, methodology): “Traditional methods aim to find network communities, which are defined as groups of nodes with many connections among the group’s members, but few to the rest of the network [2, 11, 14, 34].”