Finding community structure in networks using the eigenvectors of
matrices
M. Newman. Physical review E, (2006)cite arxiv:physics/0605087Comment: 22 pages, 8 figures, minor corrections in this version.
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.
Description
Finding community structure in networks using the eigenvectors of
matrices
%0 Journal Article
%1 newman2006finding
%A Newman, M. E. J.
%D 2006
%J Physical review E
%K community graph structure
%N 3
%T Finding community structure in networks using the eigenvectors of
matrices
%U http://arxiv.org/abs/physics/0605087
%V 74
%X 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.
@article{newman2006finding,
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.
},
added-at = {2012-12-15T20:59:29.000+0100},
author = {Newman, M. E. J.},
biburl = {https://www.bibsonomy.org/bibtex/2d83a9dba0c7c1bd55fa4dca3ab6a3daa/kibanov},
description = {Finding community structure in networks using the eigenvectors of
matrices},
interhash = {5003bcb34d28e1e4bc301fafb9a12c72},
intrahash = {d83a9dba0c7c1bd55fa4dca3ab6a3daa},
journal = {Physical review E},
keywords = {community graph structure},
note = {cite arxiv:physics/0605087Comment: 22 pages, 8 figures, minor corrections in this version},
number = 3,
timestamp = {2012-12-15T21:01:50.000+0100},
title = {Finding community structure in networks using the eigenvectors of
matrices},
url = {http://arxiv.org/abs/physics/0605087},
volume = 74,
year = 2006
}