# Automatic Detection of Multilevel Communities: Scalable, Selective and Resolution-Limit-Free +
## Appendix A Relevant Range of the Resolution Parameter \(\alpha\)
### Upper Bound of \(\alpha\): Splitting a Random Graph  
With fixed \(\beta\), since large values of \(\alpha\) deliver small communities, the upper bound of \(\alpha\) can be estimated by the limit at which the fitness function \(F_{\alpha}^{\beta}\) starts to split a graph inappropriately into smaller parts. For such an estimation, one useful reference is the random graph: since a random graph is believed to have no communities, by any algorithm it should not be split into smaller pieces [42]. Suppose we have a random graph consisting of \(N\) nodes, with probability \(p\), each pair of nodes shares an edge between them. Consider splitting the graph into two parts: subgraph \(\mathcal{M}\) contains \(m\) nodes (\(0\leq m\leq N\)), while subgraph \(\mathcal{N}\) contains \(N-m\) nodes. Both \(\mathcal{M}\) and \(\mathcal{N}\) are random graphs with identical connection probability \(p\). Subgraph \(\mathcal{M}\) (containing \(m\) nodes) is expected to have \(\frac{m(m-1)}{2}p\) intra-connections, thus it has a total in-degree \(k_{in}^{\mathcal{M}}=m(m-1)p\). Each node of \(\mathcal{M}\) shares with each node of \(\mathcal{N}\) a connection with probability \(p\), thus the out-degrees \(k_{out}^{\mathcal{M}}=k_{out}^{\mathcal{N}}=m(N-m)p\). Then, the fitness of community \(\mathcal{M}\) can be calculated as  
\[\left(F_{\alpha}^{\beta}\right)^{\mathcal{M}}=\frac{\left[m(m-1)p\right]^{ \beta}}{\left[m(m-1)p+m(N-m)p\right]^{\alpha}}=\frac{m^{\beta-\alpha}(m-1)^{ \beta}p^{\beta-\alpha}}{\left(N-1\right)^{\alpha}} \tag{1}\]Similarly, the fitness of community \(\mathcal{N}\) can be calculated as  
\[\left(F_{\alpha}^{\beta}\right)^{\mathcal{N}}=\frac{(N-m)^{\beta-\alpha}(N-m-1)^ {\beta}p^{\beta-\alpha}}{(N-1)^{\alpha}} \tag{10}\]  
Then, the fitness of the whole network (with respect to a division to \(\mathcal{M}\) and \(\mathcal{N}\)) is  
\[\left(F_{\alpha}^{\beta}\right)^{\mathcal{M}}+\left(F_{\alpha}^{\beta}\right)^ {\mathcal{N}}=[m^{\beta-\alpha}(m-1)^{\beta}+(N-m)^{\beta-\alpha}(N-m-1)^{ \beta}]p^{\beta-\alpha}(N-1)^{-\alpha} \tag{11}\]  
In comparison, if the whole network is recognized as one community (indicated by \(\mathcal{M}+\mathcal{N}\)), its fitness can be calculated as  
\[\left(F_{\alpha}^{\beta}\right)^{\mathcal{M}+\mathcal{N}}=N^{\beta-\alpha}(N -1)^{\beta}p^{\beta-\alpha}(N-1)^{-\alpha} \tag{12}\]  
We do not hope the random graph \(\mathcal{M}+\mathcal{N}\) be split into subgraphs \(\mathcal{M}\) and \(\mathcal{N}\), which requires  
\[\left(F_{\alpha}^{\beta}\right)^{\mathcal{M}+\mathcal{N}}>\left(F_{\alpha}^{ \beta}\right)^{\mathcal{M}}+\left(F_{\alpha}^{\beta}\right)^{\mathcal{N}} \tag{13}\]  
Substitute (11) and (12) into (13), we obtain  
\[N^{\beta-\alpha}(N-1)^{\beta}>m^{\beta-\alpha}(m-1)^{\beta}+(N-m)^{\beta- \alpha}(N-m-1)^{\beta},\text{ for any }0\ <\ m<\ N \tag{14}\]  
Inequality (14) is equivalent to the following statement, i.e., the maximum of the function  
\[f_{\alpha}^{\beta}(m)=m^{\beta-\alpha}(m-1)^{\beta}+(N-m)^{\beta-\alpha}(N-m- 1)^{\beta} \tag{15}\]  
should be reached at \(m=0\) or \(m=N\). Equation (10) is a \((2\beta-\alpha)\)-order polynomial on variable \(m\); a full set of its extrema (either maxima or minima) is difficult to solve. Here, we simply make a very rough estimation on the solution of (14): we notice that due to symmetry, \(f_{\alpha}^{\beta}(m)\) has an extremum at \(m=N/2\) (we do not care it's a maximum or a minimum). As a necessary condition, (14) at least requires  
\[f_{\alpha}^{\beta}(0)=f_{\alpha}^{\beta}(N)>f_{\alpha}^{\beta}(\frac{N}{2}) \tag{16}\]  
Substitute (15) into (16) we obtain  
\[N^{\beta-\alpha}(N-1)^{\beta}>2^{\alpha-2\beta+1}N^{\beta-\alpha}(N-2)^{\beta} \tag{17}\]  
\[2^{\alpha-2\beta+1}<(1+\frac{1}{N-2})^{\beta} \tag{18}\]  
Obviously, when \(\alpha\leq 2\beta-1\), (18) can be always satisfied. In other words, when \(\alpha\leq 2\beta-1\), at least a random graph would not be split into two subgraphs of the same size.