# Local Community Detection Based on Small Cliques
## 4 Experiments
### Unweighted Graphs  
For the first experiment, we run the algorithms on the parameter set Unweighted in Table 1, which are the large (5000 node) variants used by [PERSON] et al. [11]. This parameter set consists of two different community size ranges [10; 50] and [20; 100]. Therefore, we generate two different sets of graphs for which we vary \(\mu_{t}\), the topological mixing parameter. We generate 20 instances of each graph and let the algorithms run from 20 randomly picked seed nodes per graph. Figure 1 shows the average \(F_{1}\)-scores both for the variants starting from a single seed node (left column) as well as when starting from the maximum clique (right column). The \"Cl\" algorithm in the left column is just the maximum clique of the seed node, i.e., the starting point of the algorithms in the right column. \begin{table}
\begin{tabular}{c c c c c} \hline \hline
**Name** & **Description** & **Unweighted** & **Overlapping** & **Weighted** \\ \hline \(n\) & number of nodes & 5000 & 2000 & 5000 \\ \(k\) & average degree & 20 & 39.5, 61.5, 78.1, 91.8, 103.5 & 20 \\ \(k_{\max}\) & maximum degree & 50 & 120 & 50 \\ \(\tau_{1}\) & degree exponent & \(-2\) & \(-2\) & \(-2\) \\ \(C_{\min}\) & minimum community size & \(10,20\) & 60 & 20 \\ \(C_{\max}\) & maximum community size & \(50,100\) & 120 & 100 \\ \(\tau_{2}\) & community size exponent & \(-1\) & \(-2\) & \(-1\) \\ \(\mu_{t}\) & topological mixing & \(0.1,\ldots,0.9\) & 0.2 & \(0.3,0.5,0.8\) \\ \(\beta\) & weight exponent & & & \(-1.5\) \\ \(\mu_{w}\) & weight mixing & & & \(0.1,\ldots,0.9\) \\ \(O_{m}\) & communities per node & 1 & \(1,\ldots,5\) & 1 \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Parameters of the LFR benchmark that we use in our experiments. The performance of the plain Local T algorithm is well below the performance of the baseline BFS, with clique initialization it performs slightly better but still worse than all other algorithms. Even the simple clique algorithm outperforms it in terms of \(F_{1}\) score. The density-based simple greedy expansion algorithms GCE M, GCE L and LFM all perform very similar, which is not unexpected as they are based on very similar quality functions. With a clique as initialization their performance is significantly improved, in particular on the smaller communities they return almost perfect communities even past \(\mu=0.5\). The original L-based community detection algorithm, Two-Phase L, performs worse than these simple expansion algorithms. One explanation for this behavior is that if the seed node is no longer part of the detected community, the algorithm simply returns an empty community, giving a score of 0. Only the triangle-based algorithms LTE and TCE perform well when initialized with a single seed node. They also profit from the initialization with a clique, though. In particular on the smaller communities their performance is not far from the Infomap algorithm, which is able to perfectly recover the community structure till \(\mu=0.7\). The PageRank-Nibble algorithm (PRN) performs only well on the graphs with low values of \(\mu\), for higher values its performance degrades very quickly. To explore the performance of the different algorithms in more detail and get some explanations for their behavior, we show more detailed results in Figure 2. In Figure 1(a),b, we see the conductance of the detected communities. Due to the definition of conductance and the ground truth communities in LFR, \(\mu\) corresponds exactly to the conductance of the ground truth communities. We can see here that the triangle-based algorithms which almost perfectly recover the community structure (TCE and LTE) also yield good, though not perfect conductance values. For the methods based on density and simple greedy expansion, GCE M, GCE L, LFMLocal, we can see that the conductance of the detected communities is improved by starting from a clique. Figure 1: Avg.