Finding community structure in networks using the eigenvectors of matrices.
By Mark Newman. Physical review. E, Statistical, nonlinear, and soft matter physics, 2006
4,786 citations recorded by the source corpus.
We consider the problem of detecting communities or modules in networks, groups of vertices with a higher-than-average density of edges connecting them. Previous work indicates that a robust approach to this problem is the maximization of the benefit function known as "modularity" over possible divisions of a network. Here we show that this maximization process can be written in terms of the eigenspectrum of a matrix we call the modularity matrix, which plays a role in community detection similar to that played by the graph Laplacian in graph partitioning calculations. This result leads us to a number of possible algorithms for detecting community structure, as well as several other results, including a spectral measure of bipartite structure in networks and a centrality measure that identifies vertices that occupy central positions within the communities to which they belong. The algorithms and measures proposed are illustrated with applications to a variety of real-world complex networks.
Subfields: Geometry and Topology, Statistical and Nonlinear Physics
View Paper: https://www.semanticscholar.org/paper/0250b5c0f7a414dec8c7a0aa7be20c9637eeb6ec
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Geometry and Topology
In Statistical and Nonlinear Physics
- Santo Fortunato
- Jure Leskovec
- M. A. Porter
- Mark Newman
- Olaf Sporns
- Ludo Waltman
- Bryan Perozzi
- Nees Jan van Eck
Citations in the corpus
- Random Walks, Markov Processes and the Multiscale Modular Organization of Complex Networks (2008, methodology): “We have shown that spectral clustering methods provide exact procedures for the optimization of Markov Stability at long times.”
- Graph Clustering with Graph Neural Networks (2020, methodology): “Maximizing the modularity is proven to be NP-hard [5], however, a spectral relaxation of the problem can be solved efficiently [37].”
- Random walks and diffusion on networks (2016, background): “, a type of spectral partitioning) if the corresponding eigenvalue is not degenerate [338].”
- MGAE: Marginalized Graph Autoencoder for Graph Clustering (2017, positive): “Early clustering methods on graphs mainly focus on graph structure only. either capture the betweenness of edges [7], compute eigenvectors of the graph Laplacian [20, 21], or employ belief propagation [10] to exploit the graph structure.”
- Large-Scale Community Detection on YouTube for Topic Discovery and Exploration (2011, neutral): “Figure 1: Framework of community detection”
- Consistency of community detection in networks under degree-corrected stochastic block models (2011, background): “Computationally, modularity type criteria can be approximately optimized by solving an eigenvalue problem [24], whereas likelihood type criteria have no such approximations and thus have to be optimized by slower heuristic search algorithms, as was done in [5] and [20].”
- Predicting the Political Alignment of Twitter Users (2011, methodology): “48, a high value indicating well-separated communities [34].”
- Scalable learning of collective behavior based on sparse social dimensions (2009, methodology): “In the instantiation of the framework SocDim , modularity maximization [15] is adopted to extract social dimensions.”
- The Physics of Communicability in Complex Networks (2011, background): “The detection of communities in complex networks has become one of the most intensive areas of interdisciplinary research in this field (Fortunato, 2010; Fortunato and Barthélemy, 2007; Newman, 2004; 2006a; b; von Luxburg, 2007).”
- Adaptive Graph Encoder for Attributed Graph Embedding (2020, methodology): “Early graph embedding approaches are based on Laplacian eigenmaps [21], matrix factorization [3, 19, 34, 36], and random walks [10, 25].”
- The responses and adaptations of microbial communities to salinity in farmland soils: a molecular ecological network analysis. (2017, methodology): “The network modules were generated by fast greedy modularity optimization (Newman, 2006).”
- Scalable detection of statistically significant communities and hierarchies, using message passing for modularity (2014, neutral): “e* = ffiffi c p − 1 ffiffi c p − 1+ q : [2]”