  We will present improvements to famous algorithms for community detection,
namely Newman's spectral method algorithm and the Louvain algorithm. The Newman
algorithm begins by treating the original graph as a single cluster, then
repeats the process to split each cluster into two, based on the signs of the
eigenvector corresponding to the secondlargest eigenvalue. Our improvement
involves replacing the time-consuming computation of eigenvalues with a random
walk during the splitting process. The Louvain algorithm iteratively performs
the following steps until no increase in modularity can be achieved anymore:
each step consists of two phases, phase 1 for partitioning the graph into
clusters, and phase 2 for constructing a new graph where each vertex represents
one cluster obtained from phase 1. We propose an improvement to this algorithm
by adding our random walk algorithm as an additional phase for refining
clusters obtained from phase 1. It maintains a complexity comparable to the
Louvain algorithm while exhibiting superior efficiency. To validate the
robustness and effectiveness of our proposed algorithms, we conducted
experiments using randomly generated graphs and real-world data.
