Improving the performance of algorithms to find communities in networks

Richard K. Darst, Zohar Nussinov, and Santo Fortunato

Phys. Rev. E 89, 032809 – Published 20 March 2014

Abstract

Most algorithms to detect communities in networks typically work without any information on the cluster structure to be found, as one has no a priori knowledge of it, in general. Not surprisingly, knowing some features of the unknown partition could help its identification, yielding an improvement of the performance of the method. Here we show that, if the number of clusters was known beforehand, standard methods, like modularity optimization, would considerably gain in accuracy, mitigating the severe resolution bias that undermines the reliability of the results of the original unconstrained version. The number of clusters can be inferred from the spectra of the recently introduced nonbacktracking and flow matrices, even in benchmark graphs with realistic community structure. The limit of such a two-step procedure is the overhead of the computation of the spectra.

Received 15 November 2013
Revised 20 January 2014

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

Authors & Affiliations

Richard K. Darst¹, Zohar Nussinov², and Santo Fortunato¹

¹Department of Biomedical Engineering and Computational Science, Aalto University School of Science, P.O. Box 12200, FI-00076, Finland
²Physics Department, Washington University in St. Louis, CB 1105, One Brookings Drive, St. Louis, Missouri 63130-4899, USA

Article Text (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand

Issue

Vol. 89, Iss. 3 — March 2014

Reuse & Permissions

Access Options

Author publication services for translation and copyediting assistance advertisement

Images

Figure 1
Fraction of correctly detected nodes for the planted partition model with $q = 2$ clusters, average internal degree $μ_{in} = 10$ , and four values for the size of the clusters: (a) $n = 50$ , (b) $n = 200$ , (c) $n = 500$ , and (d) $n = 1000$ . Symbols indicate the performance curves of different popular methods of community detection. For modularity optimization (Mod) and the absolute Potts model (APM) we show two curves, referring to the results of the method in the absence of any information on the number of clusters of the planted partition, and when such information is fed into the model as initial input. In both cases, knowing the number of clusters beforehand leads to a much better performance. Modularity's limit performance (dot-dashed curve), as estimated by Nadakuditi and Newman [13], is attained only when the number of clusters is known. Otherwise modularity optimization performs rather poorly, as expected. The detectability limit is shown as a vertical line at $μ_{out} = 6$ .
Reuse & Permissions
Figure 2
Fraction of correctly detected nodes for the planted partition model with $n = 200$ nodes per cluster, average internal degree $μ_{in} = 10$ , and four values for the number of clusters: (a) $q = 4$ , (b) $q = 6$ , (c) $q = 8$ , and (d) $q = 10$ . Symbols indicate the performance curves of different popular methods of community detection. For modularity optimization (Mod) and the absolute Potts model (APM) we show two curves, referring to the results of the method in the absence of any information on the number of clusters of the planted partition, and when such information is fed into the model as initial input. In both cases, knowing the number of clusters beforehand leads to a much better performance. The detectability limit is shown as a vertical line which varies as a function of $q$ , according to Eq. (1). The horizontal dashed line indicates the fraction $1 / q$ of nodes correctly detected by a random partition of the graph in $q$ equal-sized clusters.
Reuse & Permissions
Figure 3
Accuracy of the prediction of the number of clusters by various methods as a function of the average external degree $μ_{out}$ for the model graphs of Fig. 1. All graphs have $q = 2$ clusters, average internal degree $μ_{in} = 10$ , and the size varies: (a) $n = 50$ , (b) $n = 200$ , (c) $n = 500$ , and (d) $n = 1000$ . Appreciable deviations are found already at fairly low values of $μ_{out}$ , when the planted partition is pronounced. The predictions from the spectra of the nonbacktracking and flow matrices are more accurate and the results are better the larger the graph size. In the limit of infinite graphs it has been conjectured that the number of clusters inferred through the nonbacktracking matrix matches the right one all the way to the detectability limit [3]. The detectability limit is indicated as a vertical dashed line.
Reuse & Permissions
Figure 4
Accuracy of the prediction of the number of clusters by various methods as a function of the mixing parameter $μ$ for LFR benchmark graphs of different sizes [(a), (b) 1000 and (c), (d) 5000 nodes] and cluster size ranges [(a), (c) [10:50] and (b), (d) [20:100]]. Infomap is the best predictor on these graphs, though the accuracy of the spectral methods seems to improve if the system gets larger.
Reuse & Permissions
Figure 5
Same as Fig. 4, but on LFR benchmark graphs with (a) $N = 10 000$ (50 averaging runs per point) and (b) $N = 20 000$ nodes (20 averaging runs per point). The range of community sizes is [10:1000]. On these graphs the nonbacktracking and flow matrices, which give very similar results, outperform Infomap.
Reuse & Permissions
Figure 6
Modularity optimization on the LFR benchmark. The graphs are generated using the same parameters as for those in Figs. 4–4, respectively. Hexagons indicate modularity optimization via simulated annealing, without any constraint on the number of clusters. The green triangles show the performance of our two-step procedure, where the number of clusters, $q$ , is inferred by the flow matrix and modularity is optimized with a greedy procedure over the set of partitions with $q$ clusters. The improvement of the performance is manifest, especially on the larger graphs.
Reuse & Permissions

Physical Review E

covering statistical, nonlinear, biological, and soft matter physics