Local resolution-limit-free Potts model for community detection

We report on an exceptionally accurate spin-glass-type Potts model for community detection. With a simple algorithm, we find that our approach is at least as accurate as the best currently available algorithms and robust to the effects of noise. It is also competitive with the best currently available algorithms in terms of speed and size of solvable systems. We find that the computational demand often exhibits superlinear scaling $O\left(L^{1.3}\right)$ where $L$ is the number of edges in the system, and we have applied the algorithm to synthetic systems as large as $40\times {10}^6$ nodes and over $1\times {10}^9$ edges. A previous stumbling block encountered by popular community detection methods is the so-called “resolution limit.” Being a “local” measure of community structure, our Potts model is free from this resolution-limit effect, and it further remains a local measure on weighted and directed graphs. We also address the mitigation of resolution-limit effects for two other popular Potts models.

Figure 1

(Color online) Plot of the percentage of correctly identified nodes $p$ versus the average external degree $k_{out}$ [32]. The average node degree is $k=16$. The data for the APM of Eq. (2) and the RBCM of Eq. (7) both use $\gamma ={\gamma }_{RB}=1$. Both models use the algorithm in Sec. 3 with $q=4$ by constraint (see text regarding the RBCM/Symmetric data). The APM is at least as accurate as SA (error bars are for $t=10$ optimization trials), and the RBCM performs excellently also. Each point is an average over 500 runs.

Figure 2

(Color online) The figure depicts a simulated three-level heterogeneously sized hierarchy with $N=256$ nodes [22, 35]. The innermost level 3 has $q_3=16$ communities with a randomly assigned average density of ${\overline{p}}_3=0.90$. The intermediate level 2 has $q_2=5$ communities and an average density of ${\overline{p}}_2=0.47$ that is constructed by connecting the constituent level 3 subgroups at an intercommunity edge density of $p_2=0.3$. Level 1 is the completely merged system with an average density of ${\overline{p}}_1=0.18$, and it is constructed by connecting nodes in different level 2 communities with an intercommunity edge density of $p_1=0.1$.

Figure 3

(Color online) Plot of VI $V$ vs model weights $\gamma$ or ${\gamma }_{RB}$ for the APM of Eq. (2) and the RBCM (configuration null model) of Eq. (7), respectively. The plots illustrate how the model weights operate in the respective models. We use the algorithm in Sec. 3 for both models to identify the hierarchy depicted in Fig. 2 using $t=1$ and 4 trials. We calculate VI with respect to level 2 of the hierarchy in panel (a) and level 3 in panel (b). Both models exactly identify both levels of the hierarchy at $t=4$. The APM perfectly identifies both levels at $t=1$ which is slightly better on average than the RBCM, and it has a more stable solution for level 3. Each point is an average over 100 solutions.

Figure 4

(Color online) A sample graph with $N=512$ nodes for the noise test in Sec. 5B. In this sample, the node degrees are initially defined in a power-law distribution with an average ${⟨k⟩}_{\alpha }=5.4$, maximum $k_{\text{max}}=100$, and exponent $\alpha =-2$. Communities have a power-law distribution of sizes with a minimum $n_{\text{min}}=4$, maximum $n_{\text{max}}=50$, and exponent $\beta =-1$. These communities are then strongly defined by connecting all internal community edges $\left(p_{in}=1\right)$.

Figure 5

(Color online) Plot of VI $V$ between solved and known test systems in Sec. 5B as a function of the average external node degree $k_{out}$. The system sizes are $N_{\text{a},\text{b}}=512$ in panels (a) and (b) (with a sample system depicted in Fig. 4) and $N_{\text{c},\text{d}}=4096$ nodes in panels (c) and (d). The graphs are solved with the APM and the RBCM using the algorithm in Sec. 3 with $t=1$ and 4 trials. We use $\gamma =1$ for the APM on all solutions, and we subjectively select the best ${\gamma }_{RB}$ for the RBCM independently for each $k_{out}$ (see Appendix ). For comparison, we also solve the system at this best ${\gamma }_{RB}$ using SA. System noise is randomly assigned in an approximate power-law degree distribution [37] with an exponent $\alpha =-2$, an average degree ${⟨k⟩}_{\alpha }$, and maximum degrees of $k_{\text{a},\text{b}}^{\text{max}}=100$ or $k_{\text{c},\text{d}}^{\text{max}}=1000$, respectively. Constructed communities are randomly assigned in a power-law size distribution [38] specified by an exponent ${\beta }_{\text{a},\text{c}}=-1$ or ${\beta }_{\text{b},\text{d}}=-2$, minimum size $n_{\text{min}}=4$, and maximum size $n_{\text{max}}=50$. Communities are then maximally connected with $p_{in}=1$. Even with $t=1$, the APM is almost perfectly accurate for most tested parameters in this problem. See Appendix regarding the accuracy transitions in panel (d). Data are averaged over 100 graphs in panels (a) and (b) and 25 graphs in panels (c) and (d).

Figure 6

(Color online) Plot of VI $V$ between solved and known test systems in Sec. 5B vs the average external node degree $k_{out}$. In panels (a) through (d), system sizes are $N_{\text{a},\text{b}}=512$ and $N_{\text{c},\text{d}}=4096$ nodes, respectively. The graphs are solved with the APM and the RBCM using the algorithm in Sec. 3 with $t=4$ trials. The constructed configurations are identical to those used in Fig. 5. In this plot, we test two different initial states for the solutions: a symmetric initial state and a random power-law distribution (see text). We use $\gamma =1$ for the APM on all solutions, and we subjectively choose the best ${\gamma }_{RB}$ for the RBCM for each $k_{out}$ (see Appendix ). For comparison, the results for SA with $t=4$ are also depicted and are solved using this best value of ${\gamma }_{RB}$. The APM and SA with the RBCM show no difference in accuracy between the symmetric and random initial states. A symmetric state appears to be the favored starting configuration for the RBCM when using a greedy algorithm in this benchmark. In fact, this symmetric initial state allows the RBCM to slightly outperform SA in accuracy (see text). We average over 100 graphs in panels (a) and (b) and 25 graphs in panels (c) and (d).

Figure 7

(Color online) Each graph is a circle of cliques with $N$ total nodes and $L$ total edges. (a) A set of $q$ cliques with $m$ nodes each are connected in a circle by $q$ links. (b) $r$ consecutive cliques are each grouped together. Intuitively, one would expect that any measure should resist merging these communities on any system scale (e.g., $N$, $L$, or $q$) if $m\ge 3$.

Figure 8

(Color online) A large graph $G$ has $N$ nodes and three subdivisions depicted, one potentially large subgraph $G^{\prime }$ with $N^{\prime }$ nodes and two distinct communities $A$ and $B$ with $n$ and $m$ nodes, respectively. In panel (a), $G$ is unweighted, and communities $A$ and $B$ are joined by $l$ edges. In panel (b), $G$ is a weighted graph. For visualization purposes, solid lines depict weighted edges, dashed lines depict weighted missing links, and the link thickness depicts a relative link weight. Communities $A$ and $B$ are joined by weighted edges with a summed weight of $w$. Weighted missing links have a summed weight of $u$. All other graph features are left unspecified but are consistent with the community designations.

Figure 9

(Color online) Graph depicts the Zachary karate club [52] solved with the APM using weighted edges (relative line thickness), $\gamma =1$, and $q=2$ communities by constraint. All nodes except 10 are correctly assigned. By our analysis, this node appears frequently in both groups (see text).

Figure 10

(Color online) Plot of VI $V$ vs ${\gamma }_{RB}$ for the RBCM. In Sec. 5B, we generate a set of strongly defined communities with varying levels of intercommunity noise $k_{out}$. Using the greedy algorithm in Sec. 3, we compare the accuracy of solutions found with the RBCM to our APM. Since the models operate differently, we compare the results in Figs. 5, 6 for our APM using $\gamma =1$ to the best result for the RBCM independently determined for each $k_{out}$. To this end, we increment ${\gamma }_{RB}$ by 20 steps per decade and calculate VI for each solution using the known answer. We then select the best ${\gamma }_{RB}$ corresponding to the lowest VI average. This example is for a system with $N=512$ nodes (see Fig. 4) with an average external degree $k_{out}\simeq 10$. See the text regarding other parameters defining the distribution of initial node degrees and community sizes. Each point is an average over 100 graphs.

Figure 11

(Color online) Plot of VI $V$ vs the average external degree $k_{out}$ for the RBCM. In Sec. 5B, we generate a set of strongly defined communities with high levels of intercommunity noise. In Figs. 5, 6, we vary the initial average power-law degree ${⟨k⟩}_{\alpha }\simeq k_{out}$ and solve the networks using the greedy algorithm in Sec. 3 and SA where we use a starting temperature of $T_0=1.0\times {10}^{-4}$ for the $N=512$ node systems. The greedy algorithm initialized into a symmetric initial state $\left(q_0=N\right)$ outperforms SA in accuracy when using the best ${\gamma }_{RB}$ (see Appendix ). In these plots, we further examine SA for a range of starting temperatures. Even with significantly higher starting temperatures, SA cannot exceed the accuracy of the greedy algorithm in this problem.

Figure 12

(Color online) Plot of VI $V$ vs the average external degree $k_{out}$ for the APM and RBCM models. Similar to Sec. 5B, we generate strongly defined communities with $N=4096$ nodes and high levels of intercommunity noise. We use the greedy algorithm in Sec. 3 for both models. The system is initially assigned a random power-law degree distribution with an exponent $\alpha =-2$, maximum degree $k_{\text{max}}=1200$, and average degree ${⟨k⟩}_{\alpha }$ $\left(k_{out}\simeq {⟨k⟩}_{\alpha }\right)$. Communities are assigned in a power-law distribution with an exponent $\beta =-1$, minimum size $n_{\text{min}}=8$, maximum size $n_{\text{max}}=24$, and density $p_{in}=1$. The APM shows sharp accuracy transitions at (i) near $k_{out}\simeq 620$ (no zero energy moves) and at (iii) near $k_{out}\simeq 770$ (using zero energy moves). These roughly correspond to a similar transition for the RBCM at (ii). See the text regarding (iv). Each point is an average over 25 graphs.