Phys. Rev. E 96, 032310 (2017) - Efficient method for estimating the number of communities in a network

Go Mobile »
Access by University of Bath

Efficient method for estimating the number of communities in a network

Maria A. Riolo, George T. Cantwell, Gesine Reinert, and M. E. J. Newman

Phys. Rev. E 96, 032310 – Published 14 September 2017

Abstract

While there exist a wide range of effective methods for community detection in networks, most of them require one to know in advance how many communities one is looking for. Here we present a method for estimating the number of communities in a network using a combination of Bayesian inference with a novel prior and an efficient Monte Carlo sampling scheme. We test the method extensively on both real and computer-generated networks, showing that it performs accurately and consistently, even in cases where groups are widely varying in size or structure.

Received 16 June 2017

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

©2017 American Physical Society

Physics Subject Headings (PhySH)

Clustering Community structure

Networks

Authors & Affiliations

Maria A. Riolo¹, George T. Cantwell², Gesine Reinert³, and M. E. J. Newman^1,2

¹Center for the Study of Complex Systems, University of Michigan, Ann Arbor, Michigan 48109, USA
²Department of Physics, University of Michigan, Ann Arbor, Michigan 48109, USA
³Department of Statistics, University of Oxford, 24–29 St. Giles, Oxford OX1 3LB, United Kingdom

Article Text

Click to Expand

References

Click to Expand

Issue

Vol. 96, Iss. 3 — September 2017

Reuse & Permissions

Access Options

Article part of CHORUS

Announcement

Physical Review E Scope Description to Include Biological Physics

January 14, 2016

The editors of Physical Review E are pleased to announce that the journal’s stated scope has been expanded to explicitly include the term “Biological Physics.”

Images

Figure 1
Tests of the method on synthetic networks. In each panel, circles represent results derived from Monte Carlo runs with random initial assignments of nodes to groups, while triangles represent runs started with the known correct assignments (the “ground truth”). (a) Networks generated using the stochastic block model with $n = 1000$ $n = 1000$ nodes, mean degree 30, and equally sized groups with 90% of connections within groups and 10% between groups. (b) Networks generated using the stochastic block model with groups of fixed size 250 nodes (so that network size varies with the number of groups $k$ $k$ ), and each node having an average of 16 in-group connections and 8 out-group connections. (c) Networks generated using the same stochastic block model as in (a) but with the rows and columns of the matrix of edge probabilities permuted to produce a mixed assortative-disassortative structure. (d) Networks generated using the LFR benchmark model of [19], which is parametrized by its maximum and minimum group sizes. In these tests we used minimum group sizes between 10 and 80 nodes, and maximum group size equal to five times the minimum. Ten Monte Carlo runs were performed for each network of 2000 steps per node each, with the distribution over $k$ $k$ being calculated from the final 1000 only.
Reuse & Permissions
Figure 2
Fraction of runs on which the algorithm correctly estimates the number of groups $k$ $k$ in tests on networks generated using the stochastic block model, as a function of the normalized mixing parameter $(c_{in} - c_{out}) / \sqrt{c}$ $(c_{in} - c_{out}) / \sqrt{c}$ . Networks have $n = 1000$ $n = 1000$ nodes, average degree $c = 30$ $c = 30$ and $k = 2$ $k = 2$ , 4, 8, 16, 32, with mixing varying from perfect assortativity (right-hand side of the plot) to perfect disassortativity (left-hand side). The dashed gray lines at $\pm 1$ $\pm 1$ denote the theoretical detectability thresholds. Fifty Monte Carlo runs were performed for each network of 2000 steps per node each, with the distribution over $k$ $k$ calculated from the final 1000 only.
Reuse & Permissions
Figure 3
Results for four real-world networks. Each column shows results for one network, as indicated. From top to bottom the results shown are the posterior probability distribution of the number of groups, the distribution of the effective number of groups calculated using the entropy measure of Eq. (34), the maximum likelihood community structure, the adjacency matrix, and the “meta-network” representation of the communities and their pattern of connectivity.
Reuse & Permissions
Figure 4
A plot of the matrix $ω_{g_{i} g_{j}}$ $ω_{g_{i} g_{j}}$ of connection parameters for a large network of copurchased products on Amazon.com. In this network nodes represents products and edges join pairs of products frequently purchased by the same buyer. In this calculation we performed ten runs of $10000$ $10 000$ Monte Carlo steps per node each and we display results from the run with the highest average likelihood during the last 1000. The calculation found 81 groups in total. Color is on a log scale for clarity.
Reuse & Permissions

1 of 4

Sign up to receive regular email alerts from Physical Review E