Finding community structure in networks using the eigenvectors of matrices
Author:
Preprint
Abstract
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 new centrality measure that identifies those 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.Keywords
All Related Versions
This publication has 46 references indexed in Scilit:
- Currency and commodity metabolites: their identification and relation to the modularity of metabolic networksIET Systems Biology, 2007
- Comparison and validation of community structures in complex networksPhysica A: Statistical Mechanics and its Applications, 2006
- Uncovering the overlapping community structure of complex networks in nature and societyNature, 2005
- Functional cartography of complex metabolic networksNature, 2005
- Defining and identifying communities in networksProceedings of the National Academy of Sciences, 2004
- Compartments revealed in food-web structureNature, 2003
- Connected Components in Random Graphs with Given Expected Degree SequencesAnnals of Combinatorics, 2002
- Exploring complex networksNature, 2001
- Collective dynamics of ‘small-world’ networksNature, 1998
- An Efficient Heuristic Procedure for Partitioning GraphsBell System Technical Journal, 1970