Estimating the resolution limit of the map equation in community detection

A community detection algorithm is considered to have a resolution limit if the scale of the smallest modules that can be resolved depends on the size of the analyzed subnetwork. The resolution limit is known to prevent some community detection algorithms from accurately identifying the modular structure of a network. In fact, any global objective function for measuring the quality of a two-level assignment of nodes into modules must have some sort of resolution limit or an external resolution parameter. However, it is yet unknown how the resolution limit affects the so-called map equation, which is known to be an efficient objective function for community detection. We derive an analytical estimate and conclude that the resolution limit of the map equation is set by the total number of links between modules instead of the total number of links in the full network as for modularity. This mechanism makes the resolution limit much less restrictive for the map equation than for modularity; in practice, it is orders of magnitudes smaller. Furthermore, we argue that the effect of the resolution limit often results from shoehorning multilevel modular structures into two-level descriptions. As we show, the hierarchical map equation effectively eliminates the resolution limit for networks with nested multilevel modular structures.

Figure 1

A schematic picture for the greedy update of two modules ${\mathcal{M}}_1$ and ${\mathcal{M}}_2$. Note that ${\mathcal{M}}_3$ may consist of many modules.

Figure 2

Detectable region of $m$ modules, each forming a clique with $n$ nodes. In the inset network, $n=5$ and $m=8$. The solid line is the resolution limits of the map equation according to Eq. (14), while the dashed line is the resolution limit of modularity, $m=n(n-1)+2$ [16].

Figure 3

Detected sizes of modules for each Sierpinski triangle of different size $l$ with the two-level method (circular points) and the multilevel method (cross points). For example, the two-level method detects modules of 3 links and 12 links when the hierarchy of the Sierpinski triangle is three. The Sierpinski triangles up to three levels are illustrated at the top. The boundary of the shaded region shows the resolution limit of the module size obtained with Eq. (14).

Figure 4

Module size distributions of (a) the collaboration network of authors of scientific papers from DBLP computer science bibliography [29, 33], (b) the copurchasing network of products in Amazon.com [29, 33], (c) the network of citations in arXiv's High Energy Physics-Theory (hep-th) section [34], (d) the friendship network on Facebook [35], (e) the road network of California [36] in the USA, and (f) the bipartite rating network of products in Amazon.com [37] in the log-log scale with partial-logarithmic binning. The circular points represent the result of the two-level method and the cross points represent the result in the finest level of the multilevel method. Note that the size of a module here does not indicate the number of internal links, but the number of nodes within the module.

Figure 5

Effective network sizes (the region encircled with the dashed line) for the evaluation of partitioning of the nine nodes at the top of the Sierpinski triangle (the nodes of open circles) in the two-level method and in the finest level of the multilevel method. While the effective network size is the size of the whole network in the two-level method, in the finest level of the multilevel method, it is of the supermodule plus the links lying between the supermodule and the rest of the network.

Figure 6

(a) An example of a hierarchical community structure in a network. (b) Phase diagram of the accepted and rejected regions for the generation of a higher level. The shaded region (A28) of the upper-right corner is invalid.

Figure 7

The plot $y=f\left(x\right)$ in Eq. (A35).