Spectral methods for community detection and graph partitioning

M. E. J. Newman

Phys. Rev. E 88, 042822 – Published 30 October 2013

Abstract

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.

Received 13 August 2013

DOI:https://doi.org/10.1103/PhysRevE.88.042822

Authors & Affiliations

M. E. J. Newman

Department of Physics and Center for the Study of Complex Systems, University of Michigan, Ann Arbor, Michigan 48109, USA

Article Text (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand

Issue

Vol. 88, Iss. 4 — October 2013

Reuse & Permissions

Access Options

Author publication services for translation and copyediting assistance advertisement

Images

Figure 1
Geometric representation of the relaxation method employed here. The true optimization is over values of the vector $s$ falling at the corners of a hypercube centered on the origin. The most common relaxation involves generalizing to values that lie anywhere on the bounding hypersphere that touches the cube at the corners (blue). In this paper, however, we generalize instead to a bounding hyperellipsoid, which also touches the cube at its corners (green).Reuse & Permissions
Figure 2
Results from the application of the algorithm described here to networks generated using the stochastic block model with two communities. (a) Each curve shows the values, plotted in increasing order, of the elements of the second eigenvector of Eq. (15) for single networks with $n = 10 000$ vertices and within-group and between-group edge probabilities $ω_{in} = 75 / n$ and $ω_{out} = 25 / n$ respectively. The curves are, from left to right, for networks in which group 1 has size 1000, 2000, 3000, $...$ ,9000. (b) Similar curves for networks of $10 000$ vertices and equally sized groups, but with varying edge probabilities. The edge probabilities are given by $n ω_{in} = 60$ , 65, 70, 75, 80, 85, and 90 and $n ω_{out} = 100 - n ω_{in}$ .Reuse & Permissions
Figure 3
The fraction of vertices classified into the correct groups by the algorithm described in this paper (blue circles) and by a standard spectral algorithm based on the leading eigenvector of the modularity matrix (red stars) for networks of $n = 10 000$ vertices generated from a stochastic block model with two equally sized groups and mean degree 50. The vertical dashed line represents the position of the detectability threshold below which all community detection algorithms must fail this test [28, 37, 38, 39, 40].Reuse & Permissions
Figure 4
Left: results of applying the algorithm to a network of frequent association among a group of bottlenose dolphins studied by Lusseau et al. [43], which is believed to divide into two clear communities. The top panel shows the values of the eigenvector elements in increasing order. The bottom panel shows the resulting division of the network. Right: equivalent plots for a copurchasing network of books about US politics in which vertices represent books and edges connect books frequently purchased by the same purchaser. This network is thought to split strongly along lines of political ideology.Reuse & Permissions
Figure 5
Eigenvector elements and community division found by application of the algorithm described in this paper to a network of weblogs about US politics, and the web hyperlinks between them, compiled by Adamic and Glance [44]. Again the algorithm finds clear two-way community structure that corresponds closely to the acknowledged division of the network, but in this case the community structure was obtained from the third, not the second, eigenvector of the normalized Laplacian.Reuse & Permissions

Physical Review E

covering statistical, nonlinear, biological, and soft matter physics