ID: 1509.06484

Detectability of the spectral method for sparse graph partitioning

September 22, 2015

View on ArXiv
Tatsuro Kawamoto, Yoshiyuki Kabashima
Computer Science
Condensed Matter
Physics
Social and Information Netwo...
Statistical Mechanics
Physics and Society

We show that modularity maximization with the resolution parameter offers a unifying framework of graph partitioning. In this framework, we demonstrate that the spectral method exhibits universal detectability, irrespective of the value of the resolution parameter, as long as the graph is partitioned. Furthermore, we show that when the resolution parameter is sufficiently small, a first-order phase transition occurs, resulting in the graph being unpartitioned.

Similar papers 1

Spectral methods for network community detection and graph partitioning

July 29, 2013

89% Match
M. E. J. Newman
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...

Find SimilarView on arXiv

Graph spectra and the detectability of community structure in networks

May 8, 2012

89% Match
Raj Rao Nadakuditi, M. E. J. Newman
Social and Information Netwo...
Statistical Mechanics
Physics and Society

We study networks that display community structure -- groups of nodes within which connections are unusually dense. Using methods from random matrix theory, we calculate the spectra of such networks in the limit of large size, and hence demonstrate the presence of a phase transition in matrix methods for community detection, such as the popular modularity maximization method. The transition separates a regime in which such methods successfully detect the community structure f...

Find SimilarView on arXiv

Limitations in the spectral method for graph partitioning: detectability threshold and localization of eigenvectors

February 24, 2015

89% Match
Tatsuro Kawamoto, Yoshiyuki Kabashima
Social and Information Netwo...
Statistical Mechanics
Physics and Society

Investigating the performance of different methods is a fundamental problem in graph partitioning. In this paper, we estimate the so-called detectability threshold for the spectral method with both unnormalized and normalized Laplacians in sparse graphs. The detectability threshold is the critical point at which the result of the spectral method is completely uncorrelated to the planted partition. We also analyze whether the localization of eigenvectors affects the partitioni...

Find SimilarView on arXiv

An upper bound on community size in scalable community detection

March 29, 2011

87% Match
Gautier Krings, Vincent D. Blondel
Physics and Society
Social and Information Netwo...

It is well-known that community detection methods based on modularity optimization often fails to discover small communities. Several objective functions used for community detection therefore involve a resolution parameter that allows the detection of communities at different scales. We provide an explicit upper bound on the community size of communities resulting from the optimization of several of these functions. We also show with a simple example that the use of the reso...

Find SimilarView on arXiv

Limits of modularity maximization in community detection

July 6, 2011

87% Match
Andrea Lancichinetti, Santo Fortunato
Physics and Society
Social and Information Netwo...

Modularity maximization is the most popular technique for the detection of community structure in graphs. The resolution limit of the method is supposedly solvable with the introduction of modified versions of the measure, with tunable resolution parameters. We show that multiresolution modularity suffers from two opposite coexisting problems: the tendency to merge small subgraphs, which dominates when the resolution is low; the tendency to split large subgraphs, which domina...

Find SimilarView on arXiv

Community detection and graph partitioning

May 21, 2013

87% 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

Counting the number of metastable states in the modularity landscape: Algorithmic detectability limit of greedy algorithms in community detection

August 23, 2018

86% Match
Tatsuro Kawamoto, Yoshiyuki Kabashima
Physics and Society
Social and Information Netwo...

Modularity maximization using greedy algorithms continues to be a popular approach toward community detection in graphs, even after various better forming algorithms have been proposed. Apart from its clear mechanism and ease of implementation, this approach is persistently popular because, presumably, its risk of algorithmic failure is not well understood. This Rapid Communication provides insight into this issue by estimating the algorithmic performance limit of modularity ...

Find SimilarView on arXiv

Fast and accurate determination of modularity and its effect size

December 29, 2014

86% 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
Paolo Barucca
Social and Information Netwo...
Physics and Society

Graph partitioning problems emerge in a wide variety of complex systems, ranging from biology to finance, but can be rigorously analyzed and solved only for a few graph ensembles. Here, an ensemble of equitable graphs, i.e. random graphs with a block-regular structure, is studied, for which analytical results can be obtained. In particular, the spectral density of this ensemble is computed exactly for a modular and bipartite structure. Kesten-McKay's law for random regular gr...

Resolution limit in community detection

July 11, 2006

86% Match
Santo Fortunato, Marc Barthelemy
Physics and Society
Disordered Systems and Neura...

Detecting community structure is fundamental to clarify the link between structure and function in complex networks and is used for practical applications in many disciplines. A successful method relies on the optimization of a quantity called modularity [Newman and Girvan, Phys. Rev. E 69, 026113 (2004)], which is a quality index of a partition of a network into communities. We find that modularity optimization may fail to identify modules smaller than a scale which depends ...

Find SimilarView on arXiv