# Local Community Detection Based on Small Cliques
## 4 Experiments
### Summary  
In Figure 6 we summarize the experimental results concerning the quality of the found communities. For each type of LFR graph with non-overlapping communities, we show the result for \(\mu=0.5\) as this is for all graphs a value where many algorithms still find reasonable results but differences between algorithms are already visible. For LFR graphs with overlapping communities we picked 4 communities per node for the same reason. For the set of 100 Facebook graphs we report the average over the 10 graphs where LTE starting with a clique (the best-performing algorithm according to our results) found the best-matching communities. On all considered types of graphs, the algorithms not starting with a clique perform worse than those starting with a clique, though LTE and TCE still show reasonable results for many graphs. The algorithms TwoPhaseL, PageRank-Nibble and LocalT perform worse than the other algorithms on all types of graphs. On unweighted LFR graphs and on the Facebook graphs, LTE with clique initialization wins. However, with overlapping communities and with edge weights and a not so clear structure (i.e., \(\mu_{t}\geq 0.5\)), it seems its triangle-based score is more easily confused and outperformed by the simpler density-based algorithms like LFM or GCE with clique initialization. Our newly proposed TCE algorithm is between them, on weighted LFR graphs it is even among the best-performing algorithms. Compared to the global, non-overlapping Infomap algorithm the results are quite competitive, only on the weighted graphs Infomap performs significantly better. On the Facebook networks, the performance of Infomap is even inferior to some local algorithms. For the overlapping LFR networks, Infomap correctly finds that there is no good non-overlapping community structure.  
Overall, these results show that while using a clique as initialization is beneficial on all types of graphs, the choice of the expansion algorithm should always depend on the type of the graph.  
\begin{table}
\begin{tabular}{c c c c c c} \hline \hline \multicolumn{1}{c}{**(a) On the Overlapping LFR Benchmark.**} & \multicolumn{2}{c}{**(b) On the 100 Facebook Networks.**} \\ \hline  & **Size** & **Time (ms)** & & **Size** & **Time (ms)** \\ \hline Cl & 7 & 0.4 & TwoPhaseL & 38 & 1.7 \\ Cl+PRN & 419 & 2.1 & PRN & 975 & 4.2 \\ PRN & 605 & 2.9 & GCE M & 282 & 5.9 \\ Cl+GCE M & 321 & 3.5 & GCE L & 270 & 6.7 \\ GCE M & 405 & 3.7 & LFMLocal & 221 & 9.8 \\ Cl+GCE L & 333 & 4.0 & TCE & 321 & 11.4 \\ GCE L & 411 & 4.4 & CI & 14 & 13.0 \\ LFMLocal & 249 & 4.8 & Cl+TwoPhaseL & 52 & 17.5 \\ Cl+LFM & 242 & 5.1 & Cl+PRN & 1086 & 18.5 \\ Cl+TwoPhaseL & 243 & 5.3 & Cl+GCE M & 1009 & 45.1 \\ TwoPhaseL & 329 & 6.8 & Cl+TCE & 930 & 46.5 \\ TCE & 320 & 10.2 & Cl+GCE L & 919 & 48.0 \\ Cl+TCE & 320 & 10.5 & Cl+LFM & 907 & 77.4 \\ LTE & 294 & 26.4 & LTE & 257 & 107.5 \\ Cl+LTE & 436 & 28.8 & Cl+LTE & 407 & 150.5 \\ LocalT & 1618 & 49.7 & LocalT & 8066 & 1028.1 \\ Cl+LocalT & 1589 & 49.7 & Cl+LocalT & 8207 & 1054.7 \\ \hline \hline \end{tabular}
\end{table}
Table 2: Average times (ms) per seed node and average community sizes of the algorithms.  
For weighted graphs, it can be dangerous to depend too much on the structure of the graph as LTE does. For LFR graphs with a highly overlapping community structure, methods solely based on the density outperform those based on triangles which is a bit surprising as one would still expect that intra-cluster edges are structurally more embedded. This could mean that possibly scores based on triangles are not as sophisticated as those based on density and should be further improved.