Local resolution-limit-free Potts model for community detection
Physical Review EPublished 27 April 2010Open access
Peter Ronhovde, Zohar Nussinov
Citations205
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
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.
Abstract
We report on an exceptionally accurate spin-glass-type Potts model for community detection. With a simple algorithm, we find that our approach is at least as accurate as the best currently available algorithms and robust to the effects of noise. It is also competitive with the best currently available algorithms in terms of speed and size of solvable systems. We find that the computational demand often exhibits superlinear scaling O(L1.3) where L is the number of edges in the system, and we have applied the algorithm to synthetic systems as large as 40 x 10(6) nodes and over 1 x 10(9) edges. A previous stumbling block encountered by popular community detection methods is the so-called "resolution limit." Being a "local" measure of community structure, our Potts model is free from this resolution-limit effect, and it further remains a local measure on weighted and directed graphs. We also address the mitigation of resolution-limit effects for two other popular Potts models.
Keywords
Physics and Astronomy
Journal of Statistical Mechanics Theory and ExperimentFast unfolding of communities in large networks
21,223 Citations2008Vincent D. Blondel, Jean‐Loup Guillaume +2 more
This work proposes a heuristic method that is shown to outperform all other known community detection methods in terms of computation time and the quality of the communities detected is very good, as measured by the so-called modularity.
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.
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.
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.
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
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.
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.
Journal of Statistical Mechanics Theory and ExperimentComparing community structure identification
2,877 Citations2005León Danon, Albert Dı́az-Guilera +2 more
It is found that the most accurate methods tend to be more computationally expensive, and that both aspects need to be considered when choosing a method for practical purposes.
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 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.
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.
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.
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.
ScienceAnalytic and Algorithmic Solution of Random Satisfiability Problems
1,092 Citations2002Marc Mézard, Giorgio Parisi +1 more
A class of optimization algorithms that can deal with the proliferation of metastable states are introduced; one such algorithm has been tested successfully on the largest existing benchmark of K-satisfiability.
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.
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 LettersDetecting Fuzzy Community Structures in Complex Networks with a Potts Model
599 Citations2004Jörg Reichardt, Stefan Bornholdt
A fast community detection algorithm based on a q-state Potts model that allows for the detection of overlapping ("fuzzy") communities and quantifying the association of nodes with multiple communities as well as the robustness of a community.
Physical Review LettersSuperparamagnetic Clustering of Data
544 Citations1996Marcelo Blatt, Shai Wiseman +1 more
This work presents a new approach for clustering, based on the physical properties of an inhomogeneous ferromagnetic model, which outperforms other algorithms for toy problems as well as for real data.
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.
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.
Physical Review EDetecting network communities by propagating labels under constraints
353 Citations2009Michael Barber, J. W. Clark
This work reformulates the recently proposed label-propagation algorithm (LPA) as an equivalent optimization problem, giving an objective function whose maxima correspond to community solutions, and produces a variety of algorithms that propagate labels subject to constraints.
New Journal of PhysicsSize reduction of complex networks preserving modularity
332 Citations2007Àlex Arenas, Jordi Duch +2 more
This work proposes an exact method for reducing the size of weighted (directed and undirected) complex networks while maintaining their modularity and compares the modularity obtained by using the extremal optimization algorithm, before and after the size reduction.
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.
ACM Transactions on Information SystemsCrimeNet explorer: a framework for criminal network knowledge discovery
246 Citations2005Jennifer Xu, Hsinchun Chen
A framework for automated network analysis and visualization was proposed that incorporates several advanced techniques: a concept space approach, hierarchical clustering, social network analysis methods, and multidimensional scaling, which demonstrated that the system could achieve higher clustering recall and precision than did untrained subjects when detecting subgroups from criminal networks.
Physical Review EDetecting complex network modularity by dynamical clustering
230 Citations2007Stefano Boccaletti, Mikhail Ivanchenko +3 more
Physical Review ESequential algorithm for fast clique percolation
225 Citations2008Jussi M. Kumpula, Mikko Kivelä +2 more
A sequential clique percolation algorithm (SCP) is presented to do fast community detection in weighted and unweighted networks, for cliques of a chosen size and can simultaneously produce a dendrogram representation of hierarchical community structure.
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.
The European Physical Journal BLimited resolution in complex network community detection with Potts model approach
188 Citations2007Jussi M. Kumpula, Jari Saramäki +2 more
The q-state Potts community detection method introduced by Reichardt and Bornholdt also has a resolution threshold, and the model contains a parameter by which this threshold can be tuned, but no a priori principle is known to select the proper value.
Physical Review ELocal modularity measure for network clusterizations
165 Citations2005Stefanie Muff, Francesco Rao +1 more
Optimization of and on the clusterization of two biological networks shows that the localized modularity identifies more cohesive clusters, yielding a complementary view of higher granularity.
Lecture notes in computer scienceMulti-level Algorithms for Modularity Clustering
141 Citations2009Andreas Noack, Randolf Rotta
It turns out that the most widely used criterion for merging clusters (modularity increase) is outperformed by other simple criteria, and that a recent multi-step algorithm is no improvement over simple single-step coarsening for these criteria.
Physical Review ESpectral properties of networks with community structure
137 Citations2009Sanjeev Chauhan, Michelle Girvan +1 more
It is shown that in many cases, the spectrum of eigenvalues of the adjacency matrix of a network with community structure gives a clear indication of the number of communities in the network.
New Journal of PhysicsImmunization of networks with community structure
92 Citations2009Naoki Masuda
An analytical framework for immunizing modular networks is developed on the basis of an immunization strategy based on eigenvector centrality and the contribution of each node to the connectivity in a coarse-grained network among modules is quantified.
Chaos An Interdisciplinary Journal of Nonlinear ScienceDynamic communities in multichannel data: An application to the foreign exchange market during the 2007–2008 credit crisis
70 Citations2009Daniel J. Fenn, Mason A. Porter +4 more
This work employs a node-centric approach that allows it to track the effects of the community evolution on the functional roles of individual nodes without having to track entire communities, and finds that exchange rates that are strongly attached to their community are persistently grouped with the same set of rates.
Fluctuation and Noise LettersLIMITED RESOLUTION AND MULTIRESOLUTION METHODS IN COMPLEX NETWORK COMMUNITY DETECTION
43 Citations2007Jussi M. Kumpula, Jari Saramäki +2 more
Physical Review ECommunity detection in complex networks by dynamical simplex evolution
39 Citations2008Vladimir Gudkov, Vladimir Montealegre +2 more
The dynamical simplex evolution (DSE) method is benchmarked with several of the currently available algorithms to detect communities in complex networks by comparing correctly identified nodes for different levels of "fuzziness" of random networks composed of well-defined communities.
New Journal of PhysicsSeeding the Kernels in graphs: toward multi-resolution community analysis
38 Citations2009Jie Zhang, Kai Zhang +3 more
Detecting modules in dense weighted networks with the potts method
29 Citations2008Tapio Heimo, Jussi M. Kumpula +2 more
Lecture notes in computer scienceExperimental Algorithms
29 Citations2008Catherine C. McGeoch
Bargaining with reading habit is no need and what will be given by this experimental algorithms 7th international workshop wea 2008 provincetown may 30 june 1, how can you bargain with the thing that has many benefits for you?
Journal of Statistical Mechanics Theory and ExperimentDetecting modules in dense weighted networks with the Potts method
24 Citations2008Tapio Heimo, Jussi M Kumpula +2 more
A weighted version of the q-state Potts method, which was originally introduced by Reichardt and Bornholdt, is discussed, and it is shown that the resulting modules correspond well to known structural properties of this correlation network.
Journal of Statistical Mechanics Theory and ExperimentFinding mesoscopic communities in sparse networks
14 Citations2006Yaroslav Ispolatov, Ilya Mazo +1 more
A fast method for finding possibly overlapping network communities of a desired size and link density based on ordering of the ferromagnetic Potts model based on the adjustable dependence of the antiferromagnetic term on the population of each Potts state, which interpolates between the two previously considered cases.