Mapping flows on sparse networks with missing links

Unreliable network data can cause community-detection methods to overfit and highlight spurious structures with misleading information about the organization and function of complex systems. Here we show how to detect significant flow-based communities in sparse networks with missing links using the map equation. Since the map equation builds on Shannon entropy estimation, it assumes complete data such that analyzing undersampled networks can lead to overfitting. To overcome this problem, we incorporate a Bayesian approach with assumptions about network uncertainties into the map equation framework. Results in both synthetic and real-world networks show that the Bayesian estimate of the map equation provides a principled approach to revealing significant structures in undersampled networks.

Figure 1

Illustration of the overfitting problem in a small modular network. (a) The network has three communities. (b) When observing only a fraction of the links, the identified thirteen communities misrepresent the underlying network structure.

Figure 2

Modular compression in sparse networks. (a) Modular code length for planted partitions after link removal. (b) Relative code length savings in networks for planted partitions. With standard entropy estimation, the average description length decreases as the number of missing links increases, and we cannot compare relative code length savings in networks with different densities. In contrast, Grassberger entropy estimation almost eliminates the code length's density dependency. For $r>0.7$, the code length savings are negative for the Bayesian estimate of the map equation with prior $a_{\alpha }=ln\left(V\right)$. By preferring the one-module solution over the planted partition in severely undersampled networks, the Bayesian estimate of the map equation avoids overfitting. For each $r$, we plot averages and variances over 100 network samplings of the synthetic network described in Sec. 4.

Figure 3

Mean number of communities obtained by the standard map equation, the Bayesian estimate of the map equation with different values of Dirichlet prior parameter $a$, and the degree-corrected stochastic block model (DC-SBM). The Bayesian estimate of the map equation with prior $a_{\alpha }=ln\left(V\right)$ provides the best solution: when sufficient network data are available it distinguishes significant communities from mere noise, while in the undersampled regime it detects no community structure. Results are averaged over 100 network samplings and ten algorithm searches. The standard error of the mean is never higher than 0.58.

Figure 4

Alluvial diagrams of the Jazz collaboration network show changes in community structure with missing links for (a) the standard map equation and (b) the Bayesian estimate of the map equation with prior $a_{\alpha }=ln\left(V\right)$. Compared to the standard map equation, the communities detected using the Bayesian estimate of the map equation are more robust to missing links.

Figure 5

Performance tests of the community-detection algorithms using AMI. (a) AMI scores with the planted partition of the synthetic network as reference. (b) AMI scores with a partition obtained for the complete Jazz collaboration network as reference. The Bayesian estimate of the map equation with prior $a_{\alpha }=ln\left(V\right)$ gives the most robust results when it is possible to detect significant communities. Results are averaged over 100 network samplings and ten algorithm searches. The standard error of the mean is never higher than 0.01.

Figure 6

Impact of network structure on the performance of the standard map equation and its Bayesian estimate. Prior parameter $C=0.5$ in (a) and $C=1$ in (b). For LFR networks with $V=1000$ nodes and various densities $\langle k\rangle$ and mixing parameters $\mu$, we show the critical fraction of removed links $r(\langle k\rangle ,\mu )$ where the AMI between the planted partition and the identified partition falls below 0.9. Except for weak community structures ($\mu =0.5$), where the Bayesian estimate with prior constant $C=1$ underfits for lower fraction of removed links than the standard map equation overfits, the methods are on par. Results are averaged over ten network samplings and ten algorithm searches.

Figure 7

Performance tests of the map equation with and without Bayesian estimates using cross-validation. The Bayesian estimate of the map equation with prior $a_{\alpha }=ln\left(V\right)$ prevents overfitting in the undersampled regime. Results are averaged over 100 network samplings and ten algorithm searches. The code length is measured with Grassberger entropy estimation. The standard error of the mean is never higher than 0.38.

Figure 8

Mean number of communities obtained by the Bayesian estimate of the map equation with different values of the prior constant $C$. Smaller prior constants give more communities when many links are missing. Results are averaged over 100 network samplings and ten algorithm searches.

Figure 9

Performance tests of the Bayesian estimate of the map equation with different values of the prior constant $C$ using AMI. (a) AMI scores with the planted partition of the synthetic network as reference. (b) AMI scores with a partition obtained for the complete Jazz collaboration network as reference. Smaller prior constants give communities with non-zero AMI scores when many links are missing at the cost of overall lower AMI-scores in the Jazz network. Results are averaged over 100 network samplings and ten algorithm searches.

Figure 10

Performance tests of the Bayesian estimate of the map equation with different values of the prior constant $C$ using cross-validation. Smaller prior constants give higher compression in a narrow range of missing links at the cost of lower compression for more missing links. We show relative code length savings for the test network compared to the one-community partition. The code length is measured with Grassberger entropy estimation. Results are averaged over 100 network samplings and ten algorithm searches.