# Automatic Detection of Multilevel Communities: Scalable, Selective and Resolution-Limit-Free +
## 2 Method
### On the Heterogeneous Lancichinetti-Fortunato-Radicchi (LFR) Benchmark Networks  
Benchmark networks with implanted communities generated by early methods, including the traditional stochastic block model (SBM) [25; 26], and the GN benchmark [2], differ substantially from their real-world counterparts: real-world networks typically have heterogeneous distributions of node degree and community size [51]. The LFR benchmark network was proposed to address the issue. Its node degrees and community sizes follow different power-law distributions, and may both span more than one order of magnitude. Each node is planted into a community: it shares a fraction of \(1-\mu\) of its connections with the other nodes of the same community, and the rest fraction \(\mu\) with nodes in other communities; \(\mu\) is called a mixing parameter [52]. Large values of \(\mu\) weaken the validity of the implanted communities. Especially, when \(\mu\geq 0.5\), the implanted communities violate the customary definitions of community in both a strong sense and a weak sense, which, respectively, require \(k_{\text{in}}>k_{\text{out}}\) for every node, or \(\Sigma k_{\text{in}}>\Sigma k_{\text{out}}\) for every community [50]. However, many community detection methods keep recovering the implanted communities perfectly even when \(\mu\) is near 0.8; the reasonability is based on the fact that most nodes in the network still retain more connections within its own community than sharing connections with any other communities, as suggested by [53]. In previous literature, it is typical to employ a normalized mutual information (NMI) [54] to evaluate the consistency between the detected communities and the implanted ones. Formula (5) displays the definition of NMI between two divisions (\(A\) and \(B\)) of a given network; NMI equals to 1 indicates that divisions \(A\) and \(B\) agree with each other perfectly. \[NMI(A,B)=\frac{-2\sum_{i=1}^{k_{A}}\sum_{j=1}^{k_{B}}n_{ij}^{AB}\log\left(\frac {n_{ij}^{AB},N}{n_{i}^{A},n_{j}^{B}}\right)}{\sum_{i=1}^{k_{A}}n_{i}^{A}\log \left(\frac{n_{i}^{A}}{N}\right)+\sum_{j=1}^{k_{B}}n_{j}^{B}\log\left(\frac{n_ {ij}^{B}}{N}\right)} \tag{5}\]  
where \(N\) is the size of the network, \(k^{A}\) and \(k^{B}\) are the numbers of communities contained in divisions \(A\) and \(B\). \(n_{i}^{A}\) and \(n_{j}^{B}\) denote the sizes of the \(i\)-th community of division \(A\) and the \(j\)-th community of division \(B\), while \(n_{ij}^{AB}\) represents the number of nodes shared between these two communities (see [54] for more details). In [42], the authors argued on an LFR network, when the community sizes vary enormously, all previous multiresolution methods lose their effectiveness. Multiresolution methods are reported to outperform other methods only because the community sizes used in their tests were too close to one another. In larger networks with more heterogeneous community sizes, multiresolution methods all fail to detect the expected communities even when \(\mu\) is far below 0.5. In contrast, Infomap, having a lack of a tunable resolution parameter, performs much better (see Figures 6-9 in [42]). We test the effectiveness of our method under the same conditions: on LFR networks built with exactly the same parameters as those in Figures 6-9 of [42], we exhibit in Figures 4 and 5 the NMIs between the implanted communities and the communities detected by our strongest (shown in red squares) and second strongest (shown in blue circles) plateaus with different values of \(\mu\). Networks in Figure 4 are relatively small and contain communities of similar sizes, while networks in Figure 5 are larger and more heterogeneous. Since the LFR networks contain no multilevel structure, for each network we only run 1000 realizations of the Louvain algorithm with \(\beta=1\); \(\beta\geq 2\) simply yields the same results. For comparison, we show in the same figures the NMIs for communities detected by Infomap (shown in black triangles).