# Local Community Detection Based on Small Cliques
## 4 Experiments
### Unweighted Graphs
\(F_{1}\)-scores on the LFR benchmark with the parameter set Unweighted, which we specify in Table 1. The left column shows results when starting with a single seed node, the right column shows results for starting with the maximum clique as well as Infomap for comparison. PageRank-Nibble shows an interesting behavior here: starting with \(\mu=0.4\), the conductance stays almost the same, i.e., is better than what the other algorithms find. Looking at Figure 2c,d which show the sizes of the detected communities, we can see that PageRank-Nibble finds really large communities that, starting with \(\mu=0.5\) contain almost half of the nodes of the whole graph. The explanation for this is that if you randomly cut a graph in two parts equally-sized parts, in expectation you also split the neighbors of every node in two equally-sized parts. Therefore, for every node \(u\) in expectation about half of \(u\)'s neighbors are in the same part as \(u\) and the other half is in the other part. This yields a conductance of 0.5. Therefore, if the initial local PageRank approximation visits enough nodes, a large enough prefix of the sorted nodes will have a lower conductance than the actual community. Further, if the actual community is not perfectly detected, its conductance is higher and therefore the effect starts already around \(\mu=0.4\). The Local T algorithm consistently finds way too large communities that also have high conductance values except for some range around \(\mu=0.6\), where probably the community size is just right to get low conductance values regardless of the chosen cut. Concerning the sizes, the density-based algorithms GCE M, GCE L and LFM as well as TCE and LTE find approximately the right size, though for larger communities they tend to discover too few  
Figure 2: Different measures for the 5000 node unweighted graph with disjoint big communities. nodes. Starting with a clique improves this, the detected community sizes now rather correspond to the correct size which is always returned by the BFS baseline by design. Only LTE then tends to detect too large communities for \(\mu\geq 0.8\) where the community structure cannot be recovered anymore. For Two-Phase L we can clearly see that above \(\mu=0.5\), the algorithm finds smaller and smaller communities on average, meaning that more and more often it decides that the detected community is no community and discards it. In Figure 2e,f we report the average \(F_{1}\) score of every detected community with the best ground truth community regardless if that community contains the seed node. For GCE M, GCE L and LFM we can clearly see that they get much better scores compared to the comparison considering only the ground truth community of the seed node. This shows that these algorithms find communities in which the seed node is not strongly embedded. For the algorithms starting with a clique, this effect is much weaker, though for higher values of \(\mu\) it is visible for all algorithms. Existing work frequently ignores this e.g., by just considering the cover that is detected by iteratively applying the algorithm to nodes that do not yet belong to a community [5; 15].