Detecting communities using asymptotical surprise

Nodes in real-world networks are repeatedly observed to form dense clusters, often referred to as communities. Methods to detect these groups of nodes usually maximize an objective function, which implicitly contains the definition of a community. We here analyze a recently proposed measure called surprise, which assesses the quality of the partition of a network into communities. In its current form, the formulation of surprise is rather difficult to analyze. We here therefore develop an accurate asymptotic approximation. This allows for the development of an efficient algorithm for optimizing surprise. Incidentally, this leads to a straightforward extension of surprise to weighted graphs. Additionally, the approximation makes it possible to analyze surprise more closely and compare it to other methods, especially modularity. We show that surprise is (nearly) unaffected by the well-known resolution limit, a particular problem for modularity. However, surprise may tend to overestimate the number of communities, whereas they may be underestimated by modularity. In short, surprise works well in the limit of many small communities, whereas modularity works better in the limit of few large communities. In this sense, surprise is more discriminative than modularity and may find communities where modularity fails to discern any structure.

Figure 1

Comparison of bounds. We show the quality of partitions of a lattice in $r$ communities. ER modularity quickly reaches a maximum for few communities (we show $2m{Q}_{\text{ER}}^2$ rather than $Q_{\text{ER}}$ for comparison). Both significance and surprise reach a maximum for many more communities. This illustrates that ER modularity is simply unable to discern partitions with such a high number of communities. The inset shows the same data, but on a logarithmic $x$ axis.

Figure 2

Approximation of surprise. The asymptotic formulation of surprise, using the KL divergence, approximates well both the binomial and the hypergeometric surprise. The inset shows the approximation ratio ${\mathcal{S}}_{\text{asym}}/{\mathcal{S}}_{\text{hyper}}$ and ${\mathcal{S}}_{\text{asym}}/{\mathcal{S}}_{\text{binom}}$, both going to 1 for large graphs.

Figure 3

Limitations on community detection. We construct graphs with a planted partition, with a probability of an edge between communities of $\mu =0.1$. We show the quality ratio $\frac{\mathcal{S}}{{\mathcal{S}}_{\text{plt}}}$ between the quality of the partition found by optimization $\mathcal{S}$ and the quality of the planted partition ${\mathcal{S}}_{\text{plt}}$ (and similarly for ER modularity). Hence, if the quality ratio $\frac{\mathcal{S}}{{\mathcal{S}}_{\text{plt}}}>1$, the planted partition is no longer optimal. In the figure on the left we consider the case for fixed community size $n_c=10$, but increase the number of communities $r$. The results show that in this case surprise finds the planted partitions, whereas ER modularity has more difficulties, in line with our analysis. This is mostly due to the resolution limit in modularity, which underestimates the number of communities. In the figure on the right we consider the case of a fixed number of communities $r=2$ but an increasing community size $n_c$. In this case, surprise quickly finds other partitions than the planted partition, whereas modularity remains closer to the planted partition, consistent with our analysis. This is mostly because surprise tends to find substructure in the rather large communities arising from random fluctuations, which thus overestimates the number of communities. However, modularity also has some difficulty in finding the planted partition. This figure shows the average over five replications for each setting, and the error bars show the standard deviation.

Figure 4

Inequalities. In most cases significance is more discriminative than surprise, which is more discriminative than the ER modularity, so that $\mathcal{Z}>\mathcal{S}>{\mathcal{Q}}_{\text{ER}}$. These inequalities clearly hold over the whole range of the mixing parameter $\mu$ for LFR benchmarks ($n={10}^4$). For ER modularity we display $2m{\mathcal{Q}}_{\text{ER}}^2$, as used in Eq. (14).

Figure 5

Benchmark results. The first row shows results for “small” communities, which range from 10 to 50, while the second row contains results for “large” communities, ranging from 20 to 100. The community sizes are power-law distributed with exponent 1. We set the average degree $\langle k\rangle =20$ and the maximum degree is 50, which follows a power-law degree distribution with exponent 2. Both surprise and significance perform very well, especially for relatively large graphs, where ER and CM modularity fail. This difference is more notable for smaller communities, for which both ER and CM modularity have difficulties. This is, in part, due to the well-known resolution limit and in line with our earlier analysis.