ID: 1307.7729

Spectral methods for network community detection and graph partitioning

July 29, 2013

View on ArXiv
M. E. J. Newman
Physics
Condensed Matter
Computer Science
Physics and Society
Statistical Mechanics
Social and Information Netwo...
Data Analysis, Statistics an...

We consider three distinct and well studied problems concerning network structure: community detection by modularity maximization, community detection by statistical inference, and normalized-cut graph partitioning. Each of these problems can be tackled using spectral algorithms that make use of the eigenvectors of matrix representations of the network. We show that with certain choices of the free parameters appearing in these spectral algorithms the algorithms for all three problems are, in fact, identical, and hence that, at least within the spectral approximations used here, there is no difference between the modularity- and inference-based community detection methods, or between either and graph partitioning.

Similar papers 1

Community detection and graph partitioning

May 21, 2013

96% Match
M. E. J. Newman
Social and Information Netwo...
Data Analysis, Statistics an...
Physics and Society

Many methods have been proposed for community detection in networks. Some of the most promising are methods based on statistical inference, which rest on solid mathematical foundations and return excellent results in practice. In this paper we show that two of the most widely used inference methods can be mapped directly onto versions of the standard minimum-cut graph partitioning problem, which allows us to apply any of the many well-understood partitioning algorithms to the...

Find SimilarView on arXiv

Modularity and community structure in networks

February 17, 2006

95% Match
M. E. J. Newman
Data Analysis, Statistics an...
Statistical Mechanics
Physics and Society

Many networks of interest in the sciences, including a variety of social and biological networks, are found to divide naturally into communities or modules. The problem of detecting and characterizing this community structure has attracted considerable recent attention. One of the most sensitive detection methods is optimization of the quality function known as "modularity" over the possible divisions of a network, but direct application of this method using, for instance, si...

Find SimilarView on arXiv

Finding community structure in networks using the eigenvectors of matrices

May 10, 2006

95% Match
M. E. J. Newman
Data Analysis, Statistics an...
Statistical Mechanics
Physics and Society

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 commun...

Find SimilarView on arXiv

Improved spectral algorithm for the detection of network communities

April 8, 2005

94% Match
L. Donetti, M. A. Munoz
Physics and Society
Statistical Mechanics

We review and improve a recently introduced method for the detection of communities in complex networks. This method combines spectral properties of some matrices encoding the network topology, with well known hierarchical clustering techniques, and the use of the modularity parameter to quantify the goodness of any possible community subdivision. This provides one of the best available methods for the detection of community structures in complex systems.

Find SimilarView on arXiv

Detecting Network Communities: a new systematic and efficient algorithm

April 27, 2004

94% Match
Luca Donetti, Miguel A. Munoz
Statistical Mechanics
Other Condensed Matter

An efficient and relatively fast algorithm for the detection of communities in complex networks is introduced. The method exploits spectral properties of the graph Laplacian-matrix combined with hierarchical-clustering techniques, and includes a procedure to maximize the ``modularity'' of the output. Its performance is compared with that of other existing methods, as applied to different well-known instances of complex networks with a community-structure: both computer-genera...

Find SimilarView on arXiv

Multiway spectral community detection in networks

June 22, 2015

94% Match
Xiao Zhang, M. E. J. Newman
Physics and Society
Statistical Mechanics
Social and Information Netwo...

One of the most widely used methods for community detection in networks is the maximization of the quality function known as modularity. Of the many maximization techniques that have been used in this context, some of the most conceptually attractive are the spectral methods, which are based on the eigenvectors of the modularity matrix. Spectral algorithms have, however, been limited by and large to the division of networks into only two or three communities, with divisions i...

Find SimilarView on arXiv

Community detection in graphs

June 3, 2009

93% Match
Santo Fortunato
physics.soc-ph
cond-mat.stat-mech
cs.IR
physics.bio-ph
physics.comp-ph
q-bio.QM

The modern science of networks has brought significant advances to our understanding of complex systems. One of the most relevant features of graphs representing real systems is community structure, or clustering, i. e. the organization of vertices in clusters, with many edges joining vertices of the same cluster and comparatively few edges joining vertices of different clusters. Such clusters, or communities, can be considered as fairly independent compartments of a graph, p...

Find SimilarView on arXiv

Fast and accurate determination of modularity and its effect size

December 29, 2014

92% Match
Santiago III Treviño, Amy Nyberg, ... , Bassler Kevin E.
Physics and Society
Social and Information Netwo...

We present a fast spectral algorithm for community detection in complex networks. Our method searches for the partition with the maximum value of the modularity via the interplay of several refinement steps that include both agglomeration and division. We validate the accuracy of the algorithm by applying it to several real-world benchmark networks. On all these, our algorithm performs as well or better than any other known polynomial scheme. This allows us to extensively stu...

Find SimilarView on arXiv

Spectral methods for the detection of network community structure: a comparative analysis

October 20, 2010

92% Match
Hua-Wei Shen, Xue-Qi Cheng
Physics and Society
Statistical Mechanics
Social and Information Netwo...

Spectral analysis has been successfully applied at the detection of community structure of networks, respectively being based on the adjacency matrix, the standard Laplacian matrix, the normalized Laplacian matrix, the modularity matrix, the correlation matrix and several other variants of these matrices. However, the comparison between these spectral methods is less reported. More importantly, it is still unclear which matrix is more appropriate for the detection of communit...

Find SimilarView on arXiv

Optimization via Low-rank Approximation for Community Detection in Networks

May 31, 2014

92% Match
Can M. Le, Elizaveta Levina, Roman Vershynin
Machine Learning
Social and Information Netwo...
Statistics Theory
Physics and Society
Statistics Theory

Community detection is one of the fundamental problems of network analysis, for which a number of methods have been proposed. Most model-based or criteria-based methods have to solve an optimization problem over a discrete set of labels to find communities, which is computationally infeasible. Some fast spectral algorithms have been proposed for specific methods or models, but only on a case-by-case basis. Here we propose a general approach for maximizing a function of a netw...

Find SimilarView on arXiv