On Finding Graph Clusterings with Maximum Modularity
Lecture notes in computer sciencePublished 6 December 2007Open access
Ulrik Brandes, Daniel Delling, Marco Gaertler, Robert Görke, Martin Hoefer, Zoran Nikoloski
Citations183
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
It is proved the conjectured hardness of maximizing modularity both in the general case and with the restriction to cuts, and an Integer Linear Programming formulation is given.
Abstract
Modularity is a recently introduced quality measure for graph clusterings. It has immediately received considerable attention in several disciplines, and in particular in the complex systems literature, although its properties are not well understood. We study the problem of finding clusterings with maximum modularity, thus providing theoretical foundations for past and present work based on this measure. More precisely, we prove the conjectured hardness of maximizing modularity both in the general case and with the restriction to cuts, and give an Integer Linear Programming formulation. This is complemented by first insights into the behavior and performance of the commonly applied greedy agglomaration approach.
Keywords
MathematicsPhysics and Astronomy
Reviews of Modern PhysicsStatistical mechanics of complex networks
20,607 Citations2002Réka Albert, Albert-Ĺaszló Barabási
A simple model based on these two principles was able to reproduce the power-law degree distribution of real networks, indicating a heterogeneous topology in which the majority of the nodes have a small degree, but there is a significant fraction of highly connected nodes that play an important role in the connectivity of the network.
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.
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.
Journal of Anthropological ResearchAn Information Flow Model for Conflict and Fission in Small Groups
4,661 Citations1977Wayne Zachary
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.
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.
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 ECommunity detection in complex networks using extremal optimization
1,573 Citations2005Jordi Duch, Àlex Arenas
The method outperforms the optimal modularity found by the existing algorithms in the literature and is feasible to be used for the accurate identification of community structure in large complex networks.
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.
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.
Network Analysis: Methodological Foundations
646 Citations2010Ulrik Brandes, Thomas Erlebach
IntegrationRecent directions in netlist partitioning: a survey
638 Citations1995Charles J. Alpert, Andrew B. Kahng
This survey describes research directions in netlist partitioning during the past two decades in terms of both problem formulations and solution approaches, and discusses methods which combine clustering with existing algorithms (e.g., two-phase partitioning).
Information Processing LettersA clustering algorithm based on graph connectivity
487 Citations2000Erez Hartuv, Ron Shamir
A novel algorithm for cluster analysis that is based on graph theoretic techniques and produces a solution with some provably good properties and performs well on simulated and real data.
A Spectral Clustering Approach To Finding Communities in Graphs
399 Citations2005Scott R. White, Padhraic Smyth
This paper shows how optimizing the Q function can be reformulated as a spectral relaxation problem and proposes two new spectral clustering algorithms that seek to maximize Q and indicates that the new algorithms are efficient and effective at finding both good clusterings and the appropriate number of clusters across a variety of real-world graph data sets.
On clusterings-good, bad and spectral
380 Citations2002Ramachandran Kannan, S. Vempala +1 more
Two results regarding the quality of the clustering found by a popular spectral algorithm are presented, one proffers worst case guarantees whilst the other shows that if there exists a "good" clustering then the spectral algorithm will find one close to it.
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.
Lecture notes in computer scienceExperiments on Graph Clustering Algorithms
303 Citations2003Ulrik Brandes, Marco Gaertler +1 more
An experimental evaluation of graph clustering approaches is conducted and by combining proven techniques from graph partitioning and geometric clustering, a new approach is introduced that compares favorably.
Lecture notes in computer scienceAlgorithms - ESA 2003
198 Citations2003Anders Dessmark, Pierre Fraigniaud
A blizzard of recent results in property testing, streaming, and sublinear approximation algorithms have shown that, for a large class of problems, all but a vanishing fraction of the input data is essentially unnecessary.
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.
Physical Review EInformation-theoretic approach to network modularity
105 Citations2005Etay Ziv, Manuel Middendorf +1 more
The network information bottleneck (NIB) algorithm is applied to a number of real world networks, including the "social" network of co-authors at the 2004 APS March Meeting.
Theory of Computing
105 Citations2006Ioannis Giotis, Venkatesan Guruswami
This paper focuses on the situation when the number of clusters is stipulated to be a small constant k, and finds that for every k, there is a polynomial time approximation scheme for both maximizing agreements and minimizing disagreements.
Repository KITopen (Karlsruhe Institute of Technology)On Modularity - NP-Completeness and Beyond
65 Citations2006Ulrik Brandes, Daniel Delling +5 more
The complexity status of modularity maximization is resolved showing that the corresponding decision version is NP-complete in the strong sense and the formulation as an Integer Linear Program (ILP) to facilitate exact optimization.
Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06Correlation clustering with a fixed number of clusters
50 Citations2006Ioannis Giotis, Venkatesan Guruswami
Lecture notes in computer scienceSignificance-Driven Graph Clustering
22 Citations2007Marco Gaertler, Robert Görke +1 more
A first systematic analysis of the behavior of realizations of the founding paradigm based on the trade-off between the achieved quality and the expected quality of a clustering with respect to networks with similar intrinsic structure arrives at remarkably good results of community detection.
Lecture notes in computer scienceSpatially Constrained Networks and the Evolution of Modular Control Systems
13 Citations2006Peter Fine, Ezequiel A. Di Paolo +1 more
This paper investigates the relationship between spatially embedded neural network models and modularity and concludes that a bias towards modularity is perhaps not always a desirable property for a control system paradigm to possess.