Exploring the solution landscape enables more reliable network community detection

To understand how a complex system is organized and functions, researchers often identify communities in the system's network of interactions. Because it is practically impossible to explore all solutions to guarantee the best one, many community-detection algorithms rely on multiple stochastic searches. But for a given combination of network and stochastic algorithms, how many searches are sufficient to find a solution that is good enough? The standard approach is to pick a reasonably large number of searches and select the network partition with the highest quality or derive a consensus solution based on all network partitions. However, if different partitions have similar qualities such that the solution landscape is degenerate, the single best partition may miss relevant information, and a consensus solution may blur complementary communities. Here we address this degeneracy problem with coarse-grained descriptions of the solution landscape. We cluster network partitions based on their similarity and suggest an approach to determine the minimum number of searches required to describe the solution landscape adequately. To make good use of all partitions, we also propose different ways to explore the solution landscape, including a significance clustering procedure. We test these approaches on synthetic networks and a real-world network using two contrasting community-detection algorithms: The algorithm that can identify more general structures requires more searches, and networks with clearer community structures require fewer searches. We also find that exploring the coarse-grained solution landscape can reveal complementary solutions and enable more reliable community detection.

Figure 1

A schematic solution landscape projected into a two-dimensional space with isolines for quality score. White squares and black circles represent two network partition clusters, with partitions distributed based on their partition distances. Large symbols represent cluster centers. A consensus solution biased toward the numerous partitions marked with a black circle may have a lower quality score than any of the detected partitions.

Figure 2

Distance from Infomap and BSBM partitions to planted partitions obtained with the LFR benchmark. Dark colors are medians and light bars are between the 25th and 75th percentiles over 500 partitions for each intercommunity link probability $\mu$.

Figure 3

The number of clusters describing (a,c) Infomap and (b,d) BSBM solution landscapes for synthetic networks generated with four intercommunity link probabilities $\mu$. Solid lines are medians and shaded regions are between the 25th and 75th percentiles for 50–500 partitions with partition distance thresholds (a,b) $d_{\text{max}}=0.025$ and (c,d) $d_{\text{max}}=0.05$. The more variable BSBM partitions require more clusters.

Figure 4

(a,c) Infomap and (b,d) BSBM solution landscape completeness for synthetic networks generated with four intercommunity link probabilities $\mu$. The validation scores $\sigma$ are represented with solid medians, and shaded regions are between the 25th and 75th percentiles for different numbers of partitions with partition distance thresholds (a,b) $d_{\text{max}}=0.025$ and (c,d) $d_{\text{max}}=0.05$. Infomap requires fewer partitions than the BSBM for complete solution landscapes. Both methods require more partitions for less pronounced communities.

Figure 5

Validation score $\sigma$ for landscape completeness of the terrestrial mammal occurrence network under four partition distance threshold values $d_{\text{max}}$ (0.2, 0.1, 0.05, 0.025) using Infomap. 1000 partitions are enough for a median validation score above 0.9.

Figure 6

World bioregions from communities in the two best partition cluster centers. (a) Alluvial diagram showing the differences between the two partitions at the highest hierarchical level. (b) Geographic projection of nodes representing grid cells. In all cases, we obtained three hierarchical levels. The differences show the rich information contained in separate partitions, even when they have similar quality.

Figure 7

(a) The fraction of partitions having a community no more distant than $\tau =0.2$ to the reference community. (b) The fraction of partitions where a node belongs to the most similar community. We see, for example, that the weakly supported African Euro-Asiatic region in the first level appears to hold a significant core of nodes coinciding with the north of Eurasia, while less significant nodes tend to be placed along bioregional borders. The striped areas correspond to regions that were not further subdivided in the third hierarchical level.