Community detection in networks: A user guide
Physics ReportsPublished 10 October 2016Open access
Santo Fortunato, Darko Hric
Citations1,815
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A guided tour through the main aspects of community detection in networks is offered, pointing out strengths and weaknesses of popular methods, and giving directions to their use.
Abstract
Community detection in networks is one of the most popular topics of modern\nnetwork science. Communities, or clusters, are usually groups of vertices\nhaving higher probability of being connected to each other than to members of\nother groups, though other patterns are possible. Identifying communities is an\nill-defined problem. There are no universal protocols on the fundamental\ningredients, like the definition of community itself, nor on other crucial\nissues, like the validation of algorithms and the comparison of their\nperformances. This has generated a number of confusions and misconceptions,\nwhich undermine the progress in the field. We offer a guided tour through the\nmain aspects of the problem. We also point out strengths and weaknesses of\npopular methods, and give directions to their use.\n
Keywords
Computer SciencePhysics and Astronomy
Computer Networks and ISDN SystemsThe anatomy of a large-scale hypertextual Web search engine
15,828 Citations1998Sergey Brin, Lawrence M. Page
This paper provides an in-depth description of Google, a prototype of a large-scale search engine which makes heavy use of the structure present in hypertext and looks at the problem of how to effectively deal with uncontrolled hypertext collections where anyone can publish anything they want.
Proceedings of the National Academy of SciencesCommunity structure in social and biological networks
15,656 Citations2002Michelle Girvan, M. E. J. Newman
This article proposes a method for detecting communities, built around the idea of using centrality indices to find community boundaries, and tests it on computer-generated and real-world graphs whose community structure is already known and finds that the method detects this known structure with high sensitivity and reliability.
Physical Review EFinding and evaluating community structure in networks
13,892 Citations2004Michelle G. Newman, Michelle Girvan
It is demonstrated that the algorithms proposed are highly effective at discovering community structure in both computer-generated and real-world network data, and can be used to shed light on the sometimes dauntingly complex structure of networked systems.
ACM Computing SurveysData clustering
13,184 Citations1999Anil K. Jain, M. Narasimha Murty +1 more
An overview of pattern clustering methods from a statistical pattern recognition perspective is presented, with a goal of providing useful advice and references to fundamental concepts accessible to the broad community of clustering practitioners.
Proceedings of the National Academy of SciencesModularity and community structure in networks
12,281 Citations2006M. E. J. Newman
It is shown that the modularity of a network can be expressed in terms of the eigenvectors of a characteristic matrix for the network, which is called modularity matrix, and that this expression leads to a spectral algorithm for community detection that returns results of demonstrably higher quality than competing methods in shorter running times.
Physics ReportsCommunity detection in graphs
11,324 Citations2009Santo Fortunato
A thorough exposition of community structure, or clustering, is attempted, 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.
Journal of ClassificationComparing partitions
7,714 Citations1985Lawrence J. Hubert, Phipps Arabie
A measure based on the comparison of object triples having the advantage of a probabilistic interpretation in addition to being corrected for chance is proposed and bounded between ±1.5 and ±2.5.
Physical Review EFinding community structure in very large networks
7,484 Citations2004Aaron Clauset, M. E. J. Newman +1 more
A hierarchical agglomeration algorithm for detecting community structure which is faster than many competing algorithms: its running time on a network with n vertices and m edges is O (md log n) where d is the depth of the dendrogram describing the community structure.
AutomaticaModeling by shortest data description
5,944 Citations1978J. Rissanen
The number of digits it takes to write down an observed sequence x1,...,xN of a time series depends on the model with its parameters that one assumes to have generated the observed data.
Journal of the American Statistical AssociationObjective Criteria for the Evaluation of Clustering Methods
5,815 Citations1971Telmo Menezes
Physical Review EFast algorithm for detecting community structure in networks
5,491 Citations2004M. E. J. Newman
An algorithm is described which gives excellent results when tested on both computer-generated and real-world networks and is much faster, typically thousands of times faster, than previous algorithms.
NatureUncovering the overlapping community structure of complex networks in nature and society
5,435 Citations2005Gergely Palla, Imre Derényi +2 more
After defining a set of new characteristic quantities for the statistics of communities, this work applies an efficient technique for exploring overlapping communities on a large scale and finds that overlaps are significant, and the distributions introduced reveal universal features of networks.
Proceedings of the National Academy of SciencesMaps of random walks on complex networks reveal community structure
4,688 Citations2008Martin Rosvall, Carl T. Bergstrom
An information theoretic approach is introduced that reveals community structure in weighted and directed networks of large-scale biological and social systems and reveals a directional pattern of citation from the applied fields to the basic sciences.
Journal of Anthropological ResearchAn Information Flow Model for Conflict and Fission in Small Groups
4,661 Citations1977Wayne Zachary
NatureDiameter of the World-Wide Web
4,285 Citations1999Réka Albert, Hawoong Jeong +1 more
The World-Wide Web becomes a large directed graph whose vertices are documents and whose edges are links that point from one document to another, which determines the web's connectivity and consequently how effectively the authors can locate information on it.
NatureFunctional cartography of complex metabolic networks
4,013 Citations2005Roger Guimerà, Luı́s A. Nunes Amaral
A methodology is proposed that can find functional modules in complex networks, and classify nodes into universal roles according to their pattern of intra- and inter-module connections, which yields a ‘cartographic representation’ of complex networks.
Physical Review ENear linear time algorithm to detect community structures in large-scale networks
3,542 Citations2007Usha Nandini Raghavan, Réka Albert +1 more
This paper investigates a simple label propagation algorithm that uses the network structure alone as its guide and requires neither optimization of a predefined objective function nor prior information about the communities.
Journal of Complex NetworksMultilayer networks
3,109 Citations2014Mikko Kivelä, Àlex Arenas +4 more
A general framework for multilayer networks is discussed, a dictionary of terminology is constructed to relate the numerous existing concepts to each other, and a thorough discussion that compares, contrasts, and translates between related notions such as multilayers networks, multiplex networks, interdependent networks, networks of networks, and many others are provided.
Physical Review EBenchmark graphs for testing community detection algorithms
3,077 Citations2008Andrea Lancichinetti, Santo Fortunato +1 more
This work introduces a class of benchmark graphs, that account for the heterogeneity in the distributions of node degrees and of community sizes, and uses this benchmark to test two popular methods of community detection, modularity optimization, and Potts model clustering.
Proceedings of the National Academy of SciencesResolution limit in community detection
3,045 Citations2006Santo Fortunato, Marc Barthélemy
It is found that modularity optimization may fail to identify modules smaller than a scale which depends on the total size of the network and on the degree of interconnectedness of the modules, even in cases where modules are unambiguously defined.
Physics ReportsThe structure and dynamics of multilayer networks
3,014 Citations2014S. Boccaletti, G. Bianconi +7 more
This work offers a comprehensive review on both structural and dynamical organization of graphs made of diverse relationships (layers) between its constituents, and cover several relevant issues, from a full redefinition of the basic structural measures, to understanding how the multilayer nature of the network affects processes and dynamics.
Social NetworksStochastic blockmodels: First steps
2,855 Citations1983Paul W. Holland, Kathryn Blackmond Laskey +1 more
Estimation techniques are developed for the special case of a single relation social network, with blocks specified a priori, and an extension of the model allows for tendencies toward reciprocation of ties beyond those explained by the partition.
Physics ReportsTemporal networks
2,481 Citations2012Petter Holme, Jari Saramäki
This review presents the emergent field of temporal networks, and discusses methods for analyzing topological and temporal structure and models for elucidating their relation to the behavior of dynamical systems.
Proceedings of the National Academy of SciencesDefining and identifying communities in networks
2,453 Citations2004Filippo Radicchi, Claudio Castellano +3 more
This article proposes a local algorithm to detect communities which outperforms the existing algorithms with respect to computational cost, keeping the same level of reliability and applies to a network of scientific collaborations, which, for its size, cannot be attacked with the usual methods.
Physical Review EAnalysis of weighted networks
2,451 Citations2004M. E. J. Newman
It is pointed out that weighted networks can in many cases be analyzed using a simple mapping from a weighted network to an unweighted multigraph, allowing us to apply standard techniques for unweighting graphs to weighted ones as well.
Communications of the ACMAlgorithm 457: finding all cliques of an undirected graph
2,451 Citations1973Coen Bron, Joep Kerbosch
Two backtracking algorithms are presented, using a branchand-bound technique [4] to cut off branches that cannot lead to a clique, and generates cliques in a rather unpredictable order in an attempt to minimize the number of branches to be traversed.
Random Structures and AlgorithmsA critical point for random graphs with a given degree sequence
2,401 Citations1995Michael Molloy, Bruce Reed
It is shown that if Σ i(i - 2)λi > 0, then such graphs almost surely have a giant component, while if λ0, λ1… which sum to 1, then almost surely all components in such graphs are small.
Physical Review ECommunity detection algorithms: A comparative analysis
2,218 Citations2009Andrea Lancichinetti, Santo Fortunato
Three recent algorithms introduced by Rosvall and Bergstrom and Ronhovde and Nussinov have an excellent performance, with the additional advantage of low computational complexity, which enables one to analyze large systems.
ScienceCommunity Structure in Time-Dependent, Multiscale, and Multiplex Networks
2,213 Citations2010Peter J. Mucha, Thomas Richardson +3 more
A generalized framework of network quality functions was developed that allowed us to study the community structure of arbitrary multislice networks, which are combinations of individual networks coupled through links that connect each node in one network slice to itself in other slices.
Physical Review EStatistical mechanics of community detection
2,119 Citations2006Jörg Reichardt, Stefan Bornholdt
The properties of the ground state configuration are elucidated to give a concise definition of communities as cohesive subgroups in networks that is adaptive to the specific class of network under study.
Physical Review EStochastic blockmodels and community structure in networks
2,095 Citations2011Brian Karrer, M. E. J. Newman
This work demonstrates how the generalization of blockmodels to incorporate this missing element leads to an improved objective function for community detection in complex networks and proposes a heuristic algorithm forcommunity detection using this objective function or its non-degree-corrected counterpart.
The European Physical Journal BDetecting community structure in networks
2,022 Citations2004M. E. J. Newman
A number of more recent algorithms that appear to work well with real-world network data, including algorithms based on edge betweenness scores, on counts of short loops in networks and on voltage differences in resistor networks are described.
New Journal of PhysicsDetecting the overlapping and hierarchical community structure in complex networks
1,960 Citations2009Andrea Lancichinetti, Santo Fortunato +1 more
The first algorithm that finds both overlapping communities and the hierarchical structure is presented, based on the local optimization of a fitness function, enabling different hierarchical levels of organization to be investigated.
NatureLink communities reveal multiscale complexity in networks
1,941 Citations2010Yong‐Yeol Ahn, James P. Bagrow +1 more
It is implied that link communities are fundamental building blocks that reveal overlap and hierarchical organization in networks to be two aspects of the same phenomenon.
Internet MathematicsCommunity Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined Clusters
1,852 Citations2009Jure Leskovec, Kevin Lang +2 more
This paper employs approximation algorithms for the graph-partitioning problem to characterize as a function of size the statistical and structural properties of partitions of graphs that could plausibly be interpreted as communities, and defines the network community profile plot, which characterizes the "best" possible community—according to the conductance measure—over a wide range of size scales.
NatureQuantifying social group evolution
1,657 Citations2007Gergely Palla, Albert-Ĺaszló Barabási +1 more
The focus is on networks capturing the collaboration between scientists and the calls between mobile phone users, and it is found that large groups persist for longer if they are capable of dynamically altering their membership, suggesting that an ability to change the group composition results in better adaptability.
Computer Science ReviewGraph clustering
1,574 Citations2007Satu Elisa Schaeffer
This survey overviews the definitions and methods for graph clustering, that is, finding sets of ''related'' vertices in graphs, and presents global algorithms for producing a clustering for the entire vertex set of an input graph.
Journal of Multivariate AnalysisComparing clusterings—an information based distance
1,560 Citations2006Marina Meilă
This paper proposes an information theoretic criterion for comparing two partitions, or clusterings, of the same data set, called variation of information (VI), and presents it from an axiomatic point of view, showing that it is the only ''sensible'' criterion for compare partitions that is both aligned to the lattice and convexely additive.
ScienceHigher-order organization of complex networks
1,277 Citations2016Austin R. Benson, David F. Gleich +1 more
A generalized framework for clustering networks on the basis of higher-order connectivity patterns provides mathematical guarantees on the optimality of obtained clusters and scales to networks with billions of edges.
IEEE Transactions on Knowledge and Data EngineeringOn Modularity Clustering
1,221 Citations2008Ulrik Brandes, Daniel Delling +5 more
The conjectured hardness of maximizing modularity both in the general case and with the restriction to cuts is proved and an Integer Linear Programming formulation is given.
PLoS ONEFinding Statistically Significant Communities in Networks
1,198 Citations2011Andrea Lancichinetti, Filippo Radicchi +2 more
OSLOM (Order Statistics Local Optimization Method), the first method capable to detect clusters in networks accounting for edge directions, edge weights, overlapping communities, hierarchies and community dynamics, is presented.
European Journal of CombinatoricsA Probabilistic Proof of an Asymptotic Formula for the Number of Labelled Regular Graphs
1,192 Citations1980Béla Bollobás
The method determines the asymptotic distribution of the number of short cycles in graphs with a given degree sequence, and gives analogous formulae for hypergraphs.
American Sociological ReviewStructural Cohesion and Embeddedness: A Hierarchical Concept of Social Groups
1,076 Citations2003James Moody, Dougľas R. White
Physical Review EBenchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities
1,041 Citations2009Andrea Lancichinetti, Santo Fortunato
The basic ideas behind the previous benchmark are extended to generate directed and weighted networks with built-in community structure, and the possibility that nodes belong to more communities is considered, a feature occurring in real systems, such as social networks.
PsychometrikaA Method of Matrix Analysis of Group Structure
984 Citations1949R. Duncan Luce, Albert D. Perry
This paper describes a matrix method, n-chain and clique, which has simple relationships to the powers of certain matrices and applies it to the analysis of practical examples of group structure.
Physical Review EPerformance of modularity maximization in practical contexts
950 Citations2010Benjamin H. Good, Yves-Alexandre de Montjoye +1 more
It is shown that the modularity function Q exhibits extreme degeneracies: it typically admits an exponential number of distinct high-scoring solutions and typically lacks a clear global maximum, implying that the output of any modularity maximization procedure should be interpreted cautiously in scientific contexts.
ACM Computing SurveysOverlapping community detection in networks
917 Citations2013Jierui Xie, Stephen Kelley +1 more
A framework is proposed for evaluating algorithms' ability to detect overlapping nodes, which helps to assess overdetection and underdetection, and for low overlapping density networks, SLPA, OSLOM, Game, and COPRA offer better performance than the other tested algorithms.
Physical Review EModularity from fluctuations in random graphs and complex networks
905 Citations2004Roger Guimerà, Marta Sales‐Pardo +1 more
It is shown both numerically and analytically that random graphs and scale-free networks have modularity and it is argued that this fact must be taken into consideration to define statistically significant modularity in complex networks.
Proceedings of the National Academy of SciencesGeographic routing in social networks
857 Citations2005David Liben‐Nowell, Jasmine Novak +3 more
A richer model relating geography and social-network friendship is introduced, in which the probability of befriending a particular person is inversely proportional to the number of closer people.
Physical Review LettersSynchronization Reveals Topological Scales in Complex Networks
854 Citations2006Àlex Arenas, Albert Dı́az-Guilera +1 more
The analysis is based on the full dynamics towards synchronization of a system of coupled oscillators and provides a useful connection between synchronization dynamics, complex networks topology, and spectral graph analysis.
Proceedings of the Royal Society B Biological SciencesThe emergent properties of a dolphin social network
824 Citations2003David Lusseau
Despite its small size, the Doubtful Sound community of bottlenose dolphins has the same characteristics of a scale-free power-law network, and the ability for two individuals to be in contact is unaffected by the random removal of individuals.
Scientific ReportsConsensus clustering in complex networks
815 Citations2012Andrea Lancichinetti, Santo Fortunato
It is shown that consensus clustering can be combined with any existing method in a self-consistent way, enhancing considerably both the stability and the accuracy of the resulting partitions.
Proceedings of the National Academy of SciencesMissing and spurious interactions and the reconstruction of complex networks
812 Citations2009Roger Guimerà, Marta Sales‐Pardo
This work is able to reliably identify both missing and spurious interactions in noisy network observations and enables network reconstructions that yield estimates of the true network properties that are more accurate than those provided by the observations themselves.
Nature PhysicsCommunities, modules and large-scale structure in networks
809 Citations2011M. E. J. Newman
Progress towards quantifying medium- and large-scale structures within complex networks is reviewed.
Physical Review EFinding local community structure in networks
789 Citations2005Aaron Clauset
This work defines both a measure of local community structure and an algorithm that infers the hierarchy of communities that enclose a given vertex by exploring the graph one vertex at a time, and uses this algorithm to extract meaningful local clustering information in the large recommender network of an online retailer.
Physical Review EModularity and community detection in bipartite networks
751 Citations2007Michael Barber
The bipartite modularity is presented in terms of a modularity matrix B; some key properties of the eigenspectrum of B are identified and used to describe an algorithm for identifying modules in bipartites networks.
Physica A Statistical Mechanics and its ApplicationsSocial structure of Facebook networks
711 Citations2011Amanda L. Traud, Peter J. Mucha +1 more
Journal of ClassificationEstimation and Prediction for Stochastic Blockmodels for Graphs with Latent Block Structure
682 Citations1997Tom A. B. Snijders, Krzysztof Nowicki
A posteriori blockmodeling for graphs is proposed and it is shown that when the number of vertices tends to infinity while the probabilities remain constant, the block structure can be recovered correctly with probability tending to 1.
IEEE Transactions on Pattern Analysis and Machine IntelligenceClustering ensembles: models of consensus and weak partitions
657 Citations2005A. Topchy, Anil K. Jain +1 more
A unified representation for multiple clusterings is introduced and a probabilistic model of consensus is proposed using a finite mixture of multinomial distributions in a space of clusterings in order to define a new consensus function related to the classical intraclass variance criterion.
Proceedings of the National Academy of SciencesSpectral redemption in clustering sparse networks
657 Citations2013Florent Krząkała, Cristopher Moore +5 more
A way of encoding sparse data using a “nonbacktracking” matrix, and it is shown that the corresponding spectral algorithm performs optimally for some popular generative models, including the stochastic block model.
PLoS ONEMapping Change in Large Networks
650 Citations2010Martin Rosvall, Carl T. Bergstrom
It is shown that bootstrap resampling accompanied by significance clustering provides a solution to the problem of distinguishing meaningful structural changes from random fluctuations and is realized de Solla Price's vision of mapping change in science.
Physical Review ELine graphs, link partitions, and overlapping communities
617 Citations2009Tim Evans, Renaud Lambiotte
The role of the degree heterogeneity is discussed and a weighted version of the line graph is proposed in order to account for this and it is shown that any algorithm that produces a partition of nodes can be used to produce a partitions of links.
Physics ReportsClustering and community detection in directed networks: A survey
578 Citations2013Fragkiskos D. Malliaros, Michalis Vazirgiannis
An in-depth comparative review of the methods presented so far for clustering directed networks along with the relevant necessary methodological background and also related applications is offered.
Proceedings of the National Academy of SciencesMixture models and exploratory analysis in networks
567 Citations2007M. E. J. Newman, E. A. Leicht
A general technique for detecting structural features in large-scale network data that works by dividing the nodes of a network into classes such that the members of each class have similar patterns of connection to other nodes is described.
Journal of Mathematical SociologyA graph‐theoretic definition of a sociometric clique†
495 Citations1973Richard Alba
The intent of this paper is to provide a definition of a socioraetric clique in the language of graph theory, using Luce's (1950) concept of an n‐clique, but further qualifications are added.
Proceedings of the National Academy of SciencesStability of graph communities across time scales
490 Citations2010Jean‐Charles Delvenne, Sophia N. Yaliraki +1 more
The stability of a partition is introduced, a measure of its quality as a community structure based on the clustered autocovariance of a dynamic Markov process taking place on the network, and the dynamical definition provides a unifying framework for several standard partitioning measures.
Physical Review ELimits of modularity maximization in community detection
488 Citations2011Andrea Lancichinetti, Santo Fortunato
It is shown that multiresolution modularity is not capable to recover the planted community structure, not even when it is pronounced and easily detectable by other methods, for any value of the resolution parameter.
Statistics and ComputingA mixture model for random graphs
475 Citations2007Jean‐Jacques Daudin, Franck Picard +1 more
The degree distribution and the clustering coefficient associated with this model are given, a variational method to estimate its parameters and a model selection criterion to select the number of classes are selected, which allows us to deal with large networks containing thousands of vertices.
New Journal of PhysicsAnalysis of the structure of complex networks at different resolution levels
453 Citations2008A Arenas, A Fernández +1 more
The proposed method allows for multiple resolution screening of the modular structure, and its application to two real social networks allows us to find the exact splits reported in the literature, as well as the substructure beyond the actual split.
Journal of Mathematical SociologyA graph‐theoretic generalization of the clique concept
449 Citations1978Stephen B. Seidman, Brian L. Foster
A family of new clique‐like structures is proposed which captures an aspect of cliques which is seldom treated in the existing literature and provides a new means of tapping several important properties of social networks.
Physical Review ECommunity detection in networks with positive and negative links
440 Citations2009Vincent Traag, Jeroen Bruggeman
An existing Potts model is extended to incorporate negative links as well, resulting in a method similar to the clustering of signed graphs, as dealt with in social balance theory, but more general.
ACM SIGKDD Explorations NewsletterDynamic social network analysis using latent space models
440 Citations2005Purnamrita Sarkar, Andrew Moore
This paper generalizes a successful static model of relationships into a dynamic model that accounts for friendships drifting over time and shows how to make it tractable to learn such models from data, even as the number of entities n gets large.
Random Structures and AlgorithmsAlgorithms for graph partitioning on the planted partition model
433 Citations2001Anne Condon, Richard M. Karp
Physical Review EEfficient and principled method for detecting communities in networks
405 Citations2011B. Ball, Brian Karrer +1 more
This work describes a method for finding overlapping communities based on a principled statistical approach using generative network models and shows how the method can be implemented using a fast, closed-form expectation-maximization algorithm that allows us to analyze networks of millions of nodes in reasonable running times.
PLoS ONEMultilevel Compression of Random Walks on Networks Reveals Hierarchical Organization in Large Integrated Systems
403 Citations2011Martin Rosvall, Carl T. Bergstrom
With a novel search algorithm, the rich multilevel organization of several large social and biological networks are extracted and illustrated, including countries and continents, and more than 100 scientific fields organized in four major disciplines are revealed.
Nature CommunicationsStructure and inference in annotated networks
394 Citations2016M. E. J. Newman, Aaron Clauset
An approach is devised that combines a network and its metadata to detect communities more accurately than can be done with either alone and correctly uses or ignores the metadata depending on whether they contain useful information.
Physical Review LettersInference and Phase Transitions in the Detection of Modules in Sparse Networks
384 Citations2011Aurélien Decelle, Florent Krząkała +2 more
An asymptotically exact analysis of the problem of detecting communities in sparse random networks generated by stochastic block models using the cavity method of statistical physics and its relationship to belief propagation yields an optimal inference algorithm for detecting modules.
Nature CommunicationsMemory in network flows and its effects on spreading dynamics and community detection
377 Citations2014Martin Rosvall, Alcides Viamontes Esquivel +3 more
The paths taken in various systems are studied and it is suggested that accounting for higher-order memory in network flows can help to better understand how real systems are organized and function.
Physical Review ENarrow scope for resolution-limit-free community detection
366 Citations2011Vincent Traag, Paul Van Dooren +1 more
A rigorous definition is suggested and some basic properties of resolution-limit-free methods are derived, able to prove exactly which class of community detection methods are resolution- limit-free, and which methods are not.
Proceedings of the National Academy of SciencesUncovering space-independent communities in spatial networks
357 Citations2011Paul Expert, Tim Evans +2 more
This paper argues in this paper for a careful treatment of the constraints imposed by space on network topology and proposes a modularity function adapted to spatial networks for community detection and focuses on the problem of community detection.
Physical Review ERobustness of community structure in networks
350 Citations2008Brian Karrer, Elizaveta Levina +1 more
It is shown that the significance of community structure can be effectively quantified by measuring its robustness to small perturbations in network structure.
PsychometrikaConnectivity and Generalized Cliques in Sociometric Group Structure
343 Citations1950R. Duncan Luce
A generalized concept of clique, called ann-clique, is introduced and n-cliques are shown to have a very close relationship to the existence of cliques in an artificial structure defined on the same set of elements, thus permitting the determination ofn-Cliques by means of the same simple matrix procedures used to obtain the clique structures.
SIAM ReviewComparing Community Structure to Characteristics in Online Collegiate Social Networks
328 Citations2011Veronica Red, Eric D. Kelsic +2 more
This study examines the importance of common high school affiliation at large state universities and the varying degrees of influence that common major can have on the social structure at different universities, indicating that university networks typically have multiple organizing factors rather than a single dominant one.
COMBINATORICAGraph bisection algorithms with good average case behavior
327 Citations1987Thanh‐Tung Bui, S.K. Chaudhuri +2 more
A polynomial time algorithm that, for every input graph, either outputs the minimum bisection of the graph or halts without output is described, which shows that the algorithm chooses the former course with high probability for many natural classes of graphs.
Physical Review LettersGraph Spectra and the Detectability of Community Structure in Networks
323 Citations2012Raj Rao Nadakuditi, M. E. J. Newman
Using methods from random matrix theory, the spectra of networks that display community structure are calculated, and it is shown that spectral modularity maximization is an optimal detection method in the sense that no other method will succeed in the regime where the modularity method fails.
Proceedings of the National Academy of SciencesTracking evolving communities in large linked networks
304 Citations2004John E. Hopcroft, Omar Shahbaz Khan +2 more
This work examines a large real-world data set: the NEC CiteSeer database, a linked network of >250,000 papers, and identifies the subset of clusters that remain stable under multiple clustering runs that allow it to identify emerging communities and track temporal changes in the underlying structure of the network data.
Statistical Analysis and Data Mining The ASA Data Science JournalA classification for community discovery methods in complex networks
296 Citations2011Michele Coscia, Fosca Giannotti +1 more
The aim of this survey is to provide a ‘user manual’ for the community discovery problem and to organize the main categories of community discovery methods based on the definition of community they adopt.
Machine LearningAn Experimental Comparison of Model-Based Clustering Methods
284 Citations2001Marina Meilă, David Heckerman
This paper performs an experimental comparison between three batch algorithms for model-based clustering on high-dimensional discrete-variable datasets, and finds that the Expectation–Maximization (EM) algorithm significantly outperforms the other methods.
Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topicsDistance, dissimilarity index, and network community structure
271 Citations2003Haijun Zhou
This work calculates the dissimilarity index between nearest-neighboring vertices of a network and design an algorithm to partition these vertices into communities that are hierarchically organized, and identifies many clusters that have well defined biological functions.
PLoS ONECharacterizing the Community Structure of Complex Networks
269 Citations2010Andrea Lancichinetti, Mikko Kivelä +2 more
A systematic empirical analysis of the statistical properties of communities in large information, communication, technological, biological, and social networks finds that the mesoscopic organization of networks of the same category is remarkably similar.
Physical Review EMultiresolution community detection for megascale networks by information-based replica correlations
249 Citations2009Peter Ronhovde, Zohar Nussinov
A Potts model community detection algorithm is used to accurately and quantitatively evaluate the hierarchical or multiresolution structure of a graph and has an accuracy that ranks among the best of currently available methods.
Physical Review ECommunity detection in networks: Structural communities versus ground truth
240 Citations2014Darko Hric, Richard K. Darst +1 more
Network ScienceClustering attributed graphs: Models, measures and methods
240 Citations2015Cécile Bothorel, Juan David Cruz Gomez +2 more
This article characterizing the main existing clustering methods and highlighting their conceptual differences are characterized, covering the important topic of clustering evaluation and identifying current open problems.
Sociological MethodologyCategorical Data Analysis of Single Sociometric Relations
232 Citations1981Stephen E. Fienberg, Stanley Wasserman
Physical Review EDetecting complex network modularity by dynamical clustering
230 Citations2007Stefano Boccaletti, Mikhail Ivanchenko +3 more
Journal of Complex NetworksLearning latent block structure in weighted networks
225 Citations2014C. Aicher, A. Z. Jacobs +1 more
This model learns from both the presence and weight of edges, allowing it to discover structure that would otherwise be hidden when weights are discarded or thresholded, and a Bayesian variational algorithm is described for efficiently approximating this model's posterior distribution over latent block structures.
Physical Review EIdentification of core-periphery structure in networks
207 Citations2015Xiao Zhang, Travis Martin +1 more
The method is found to be efficient, scaling easily to networks with a million or more nodes, and it is demonstrated that the method is immune to the detectability transition observed in the related community detection problem, which prevents the detection of community structure when that structure is too weak.
Physical Review ELocal resolution-limit-free Potts model for community detection
205 Citations2010Peter Ronhovde, Zohar Nussinov
An exceptionally accurate spin-glass-type Potts model for community detection that is at least as accurate as the best currently available algorithms and robust to the effects of noise and competitive with the best current algorithms in terms of speed and size of solvable systems.
Physical Review ECommunity detection as an inference problem
205 Citations2006M. B. Hastings
This work expresses community detection as an inference problem of determining the most likely arrangement of communities, and applies belief propagation and mean-field theory to this problem, and shows that this leads to fast, accurate algorithms for community detection.
…