# Link Pruning for Community Detection in Social Networks
## 4 Experiments
### Verification of Efficiency  
We applied various algorithms to the community detection algorithm \(A\) to verify the efficiency of the proposed algorithm. The computational complexity of the proposed algorithm depends on the numbers of nodes \(V\) and the number of links \(|E|\) in a given graph \(G=(V,E)\). An approximation algorithm can be performed to reduce the computational complexity in calculating link attributes in a large-scale graph. For example, it is known that locality sensitive hashing (LSH) can be applied to Jaccard's index to approximately calculate link attributes or link weights in a graph [32]. The computational complexity is linear to the number of hash functions under this condition, and approximate calculations can be performed to reduce the calculation time.  
The results obtained from analyzing the efficiency of the proposed algorithm according to the five popular community detection algorithms are presented as follows. Community detection algorithms used for the comparison include the Louvain method, the label propagation algorithm (LPA) [33], Infomap [34], Fastgreedy [6] and Walktrap [35]. We note that the computational complexities are \(O(|V|\log|V|)\), \(O(|E|)\), \(O(|E|)\), \(O(|V|\log^{2}|V|)\) and \(O(|V|^{2}\log|V|)\) based on the Louvain method, LPA. Infomap, Fastgreedy and Walktrap, respectively [36].  
In addition, we measured the amount of time required for the operation of Algorithm 1 by increasing \(\alpha\) from 0 to 0.3, and pruning links when the Amazon network was used and Jaccard's index was performed as link attributes. Table 3 presents the results obtained from measuring the total operation time of Algorithm 1. Table 4 illustrates the modularity values in the same set of experiments. The LPA frequently combined the entire graphs as a single community due to its unstable performance in identifying communities based on randomness when label information was not provided prior to the algorithm. Infomap and Walktrap required a longer operation time than other algorithms and showed low modularity values. Regarding the Louvain method and Fastgreedy, the Louvain method required a shorter operation time and performed high modularity. As a result, in our algorithm, it was verified that the Louvain method showed the best performance with the highest efficiency.  
\begin{table}
\begin{tabular}{c c c c c c} \hline \hline
**Pruning Rate (\(\alpha\))** & **Louvain** & **LPA** & **Infomap** & **Fastgreedy** & **Walktrap** \\ \hline
0 & **4.94** & 28.31 & 1681.35 & 308.87 & 1495.25 \\ \hline
0.1 & **4.59** & 22.49 & 1332.08 & 137.12 & 1398.27 \\ \hline
0.2 & **4.42** & 14.81 & 903.47 & 32.16 & 1392.60 \\ \hline
0.3 & **4.32** & 12.19 & 10504.02 & 63.47 & 1199.82 \\ \hline \hline \end{tabular}
\end{table}
Table 3: Running times of clustering algorithms with various link pruning rates.  
The experimental results based on a change in the link pruning rate are presented as follows. As presented in Table 3, Infomap and Fastgreedy implied a rapidly increasing operation time where the link pruning rate changed from 0.2 to 0.3. Except for these cases, community detection algorithms tended to require a shorter operation time as the pruning rate increased. In addition, as shown in Table 4, the entire community detection algorithms show low modularity values as the pruning rate increases. We use another community detection evaluation which is conductance. Well-separated communities lower the conductance. As shown in Table 5, the entire community detection algorithms always show low conductance values regardless of the pruning rate. Based on this result, it was verified that our proposed algorithm performed excellent performance, regardless of the choice of the community detection algorithm \(A\).