# An improvement on the Louvain algorithm using random walks

DO Duy Hieu and PHAN Thi Ha Duong

Institute of Mathematics
Vietnam Academy of Science and Technology

###### Abstract

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 second-largest 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.

Email<EMAIL_ADDRESS>(Do Duy Hieu<EMAIL_ADDRESS>(Phan Thi Ha
Duong).

##  1 Introduction

Research on community detection in networks is an essential field within
network science, with a wide array of applications in computer science and
various other scientific disciplines [4, 8, 17]. Consequently, numerous
research efforts from scientists have employed various methodological
approaches. Among these, two algorithms garnering significant attention are
Newman’s spectral method [12] and the Louvain algorithm [1]. Therefore,
numerous extensions and improvements have been made to these algorithms [2,
22, 20, 21].

Random walk is a focal point of interest in network community research, as it
helps elucidate the characteristics of vertices belonging to the same or
different communities [16, 6]. This paper will employ random walks to improve
Newman’s spectral method and the Louvain algorithm.

###  1.1 Newman’s Spectral Method

In [12], Newman proposed a spectral method for detecting network communities.
The initial algorithm constructs a normalized Laplacian matrix as follows:

$\mathbf{L}=D^{-1/2}AD^{-1/2}$

Here, the matrix $A$ is the adjacency matrix, and $D$ is the diagonal matrix
with elements equal to the vertex degrees $D_{ii}=d_{i}$.

Assuming $V=\\{1,2,\ldots,n\\}$ represents the set of graph vertices. The
algorithm then classifies the graph into two communities based on the
eigenvectors corresponding to eigenvalues greater than 1 of the matrix
$\mathbf{L}$. Typically, the second eigenvector is chosen (assuming
$v_{\beta}=(v^{1}_{\beta},v^{2}_{\beta},\ldots,v^{n}_{\beta})$), and
specifically, if $v^{i}_{\beta}\geq 0$, vertex $i$ belongs to community
$C_{1}$; otherwise, vertex $i$ belongs to community $C_{2}$.

Subsequently, the algorithm generates two subgraphs $G_{1}$ and $G_{2}$
corresponding to communities $C_{1}$ and $C_{2}$, and then repeats the
process. The algorithm stops when the partitioning of the graph into
communities $C_{1}$ and $C_{2}$ no longer increases the modularity value
(modularity will be introduced in the next section).

In this paper, we also introduce a graph partition method similar to the one
mentioned earlier. However, we employ a random walk at each step instead of
using eigenvectors, thereby reducing our algorithm’s computational complexity.
Additionally, we establish a connection with the eigenvalues and eigenvectors
of the normalized Laplacian matrix. This connection reveals that our algorithm
produces clustering results equivalent to Newman’s algorithm when the number
of random walk steps is sufficiently large.

###  1.2 Louvain Algorithm

The Louvain algorithm [1] stands out for its simplicity and elegance. It
optimizes a quality function, such as Modularity or CPM, through two primary
phases:
Phase 1: Nodes assess potential relocation to neighboring communities by
maximizing Modularity increase using the formula:

$\Delta
Q_{i,C_{j}}=\left[\frac{\Sigma_{in}+2k_{i,in}}{2m}-\left(\frac{\Sigma_{tot}+k_{i}}{2m}\right)^{2}\right]-\left[\frac{\Sigma_{in}}{2m}-\left(\frac{\Sigma_{tot}}{2m}\right)^{2}-\left(\frac{k_{i}}{2m}\right)^{2}\right]$
(1.1)

Here, $\Delta Q_{i,C_{j}}$ signifies Modularity change upon placing vertex $i$
into community $C_{j}$, $\Sigma_{in}$ is the sum of weights of links within
the transitioning community, $\Sigma_{tot}$ is the sum of weights of links to
nodes in the transitioning community, $k_{i}$ is the weighted degree of $i$,
$k_{i,in}$ is the sum of weights of links between $i$ and other nodes in the
transitioning community, and $m$ is the sum of weights of all links in the
network.
Phase 2: Consolidates nodes within the same community to form a new network.
Self-loops denote intra-community links, and weighted edges represent inter-
community connections.

The algorithm iterates these phases until Modularity ceases to increase.

###  1.3 Random walk on graphs

Before delving into the next section, let’s revisit the concept of a random
walk on a graph and some associated knowledge. Consider an undirected and
connected graph $G=(V,E)$ with sets of vertices ($V$) and edges ($E$). Let
$|V|$ be denoted as $n$, $|E|$ as $m$, and the adjacency matrix of $G$ as $A$.
In this context, $A_{ij}=1$ if vertices $i$ and $j$ are connected (linked by
an edge), and $A_{ij}=0$ otherwise. The degree $d(i)=\sum_{j}A_{ij}$ of a
vertex $i$ represents the Number of its neighbors, including itself. For
simplicity, this paper focuses on unweighted graphs. Nevertheless, it is
straightforward to extend the results to weighted graphs, where
$A_{ij}\in\mathbb{R}^{+}$ instead of $A_{ij}\in{0,1}$, showcasing the
versatility of this approach.

Now, consider a random walk $X=X_{0},X_{1},\ldots,X_{t},\ldots$ on graph $G$
(refer to [11, 18] for a comprehensive presentation). At each step $t$, the
walker moves to a vertex randomly and uniformly selected from its neighbors.
Consequently, the sequence of visited vertices forms a Markov chain, with
states representing the graph’s vertices. At each step, the transition
probability from vertex $i$ to vertex $j$ is given by
$P_{ij}=\frac{A_{ij}}{d(i)}$. This definition establishes the transition
matrix $P$ for the random walk process.

It’s evident that $P=D^{-1}A$, where $D$ is the diagonal matrix of degrees
($D_{ii}=d(i)$ and $D_{ij}=0$ for $i\neq j$). Finally, the information about
vertex $i$ encoded in $P^{t}$ resides in the $n$ probabilities
$(P^{t}_{ik}){1\leq k\leq n}$, equivalent to the $i$-th row of matrix $P^{t}$
denoted by $P^{t}_{i\bullet}$. We assume that $G$ is connected. According to
the convergence theorem for finite Markov chains, the associated transition
matrix $P$ satisfies $\lim_{k\rightarrow\infty}P=P_{\infty}$, where
$(P_{\infty})_{ij}=\phi_{j}$, the $j$-th component of the unique stationary
distribution $\phi=(\phi_{1},\phi_{2},...,\phi_{n})$, note that
$\phi_{i}=d(i)/\sum d(j)$ (see in [16]). This paper also represents
$X_{i\bullet}$ as the $i$-th row of an arbitrary matrix $X$.

###  1.4 Modularity

The modularity $Q$ introduced in [14, 15], which relies on the fraction of
edges $e_{C}$ inside community $C$ and the fraction of edges $a_{C}$ bound to
community $C$ :

$Q(\mathcal{P})=\sum_{C\in\mathcal{P}}(e_{C}-a_{C}^{2})$ (1.2)

From this, we can consider the Modularity corresponding to each clustering for
the graph as the total Modularity of each community. From there, with the $C$
community, we have the Modularity corresponding to it:

$Q(C,G)=e_{C}-a_{C}^{2}$ (1.3)

###  1.5 Our contribution

In this paper, we first employ a random walk strategy to introduce a novel
method for community detection through graph partitioning, akin to the
spectral method in [12], known as the Random Walk Graph Partition Algorithm.
This algorithm exhibits lower computational complexity and greater efficiency
than the spectral algorithm in [12].

Furthermore, considering the Random Walk Graph Partition Algorithm as the
1.5th step of the Louvain algorithm, we propose a new algorithm named the
Random Walk Graph Partition Louvain Algorithm. This algorithm maintains
computational complexity equivalent to the Louvain algorithm but achieves
higher efficiency, especially for graphs with unclear community structures.

Additionally, we conduct experiments on both randomly generated and real data
to demonstrate the reasonability and effectiveness of our proposed algorithms.

##  2 Random Walk Graph Partition Algorithm

Newman’s spectral approach is based on spectral analysis of the normalized
Laplacian matrix $\mathbf{L}$. This approach is quite good because the
Laplacian matrix is a matrix that has many properties of graphs and is the
subject of many people’s research. Furthermore, this algorithm is also quite
simple. However, we need to find eigenvalues and eigenvectors with great
computational complexity to implement the algorithm. Therefore, instead of
directly analyzing the matrix Laplacian, we will study it through a random
walk. We note that the transition matrix of the random walk $P$ is similar to
the matrix $\mathbf{L}$
($\mathbf{L}=D^{-\frac{1}{2}}AD^{-\frac{1}{2}}=D^{\frac{1}{2}}PD^{-\frac{1}{2}}$),
so they have the same eigenvalues, and the eigenvectors are related.

Now, we will analyze the relationship between the spectral approach and random
walk. First, we recalled the following lemma.

###### Lemma 2.1

([16, Lemma 1]) The eigenvalues of the matrix $P$ are real and satisfy:

$1=\lambda_{1}>\lambda_{2}\geq\ldots\geq\lambda_{n}>-1.$ (2.1)

Moreover, there exists an orthonormal family of vectors
$(s_{\alpha})_{1\leq\alpha\leq n}$ such that each vector
$v_{\alpha}=D^{-1/2}s_{\alpha}$ and $u_{\alpha}=D^{1/2}s_{\alpha}$ are
respectively a right and a left eigenvector associated to the eigenvalue
$\lambda_{\alpha}$:

$\forall\alpha,\,Pv_{\alpha}=\lambda_{\alpha}v_{\alpha}\,\,\mbox{ and
}P^{T}u_{\alpha}=\lambda_{\alpha}u_{\alpha}$
$\forall\alpha,\forall\beta,\,\,v^{T}_{\alpha}u_{\beta}=\delta_{\alpha\beta}$

This paper only considers the case $\lambda_{2}\neq\lambda_{3}$. We have the
following theorem from Lemma 2.1.

###### Theorem 2.2

Let $i$ be any vertex of the graph $G$. Then we have the $j-$th component of
vector $P^{t}_{i\bullet}-\phi$ and the $j-$th component of vector $s_{2}$ have
the same sign for all $j=1,2,...,n$ or opposite signs for all $j=1,2,...,n$,
where $s_{2}$ is the eigenvector corresponding to the second eigenvalue of the
normalized Laplacian matrix $\mathbf{L}$.

Proof  Lemma 2.1 makes it possible to write a spectral decomposition of the
matrix $P:$

$P=\sum_{\alpha=1}^{n}\lambda_{\alpha}v_{\alpha}u^{T}_{\alpha}\,\mbox{ and
}\,P^{t}=\sum_{\alpha=1}^{n}\lambda^{t}_{\alpha}v_{\alpha}u^{T}_{\alpha}.$
(2.2)

It follows that

$P^{t}_{ij}=\sum_{\alpha=1}^{n}\lambda^{t}_{\alpha}v_{\alpha}(i)u^{T}_{\alpha}(j)\,\mbox{
and
}P^{t}_{i\bullet}=\sum_{\alpha=1}^{n}\lambda^{t}_{\alpha}v_{\alpha}(i)u_{\alpha}.$
(2.3)

When $t$ tends towards infinity, all the terms $\alpha\geq 2$ vanish. It is
easy to show that the first right eigenvector $v_{1}$ is constant. By
normalizing we have $\forall i,\,v_{1}(i)=\frac{1}{\sum_{k}d_{k}}$ and
$\forall j,\,u_{1}(j)=\frac{d_{j}}{\sum_{k}d_{k}}.$ Therefore, we have

$\lim_{t\rightarrow\infty}P^{t}_{ij}=\lim_{t\rightarrow\infty}\lambda^{t}_{\alpha}v_{\alpha}(i)u^{T}_{\alpha}(j)=v_{1}(i)u^{T}_{1}(j)=\frac{d_{j}}{\sum_{k}d_{k}}=\phi_{j}.$
(2.4)

From (2.3), (2.4) and $\lambda_{1}=1$, we have

$P^{t}_{i\bullet}-\phi=\sum_{\alpha=2}^{n}\lambda^{t}_{\alpha}v_{\alpha}(i)u_{\alpha}=\lambda^{t}_{2}v_{2}(i)u_{2}+\lambda^{t}_{3}v_{3}(i)u_{3}+\ldots+\lambda^{t}_{n}v_{n}(i)u_{n},$
(2.5)

this is equivalent to

$P^{t}_{i\bullet}-\phi=\lambda^{t}_{2}\left(v_{2}(i)u_{2}+\frac{\lambda^{t}_{3}}{\lambda^{t}_{2}}v_{3}(i)u_{3}+\ldots+\frac{\lambda^{t}_{n}}{\lambda^{t}_{2}}v_{n}(i)u_{n}\right).$
(2.6)

On the other hand, from Theorem 2.2, we have $u_{\alpha}=D^{-1/2}s_{\alpha}$.
From there, it follows.

$P^{t}_{i\bullet}-\phi=\lambda^{t}_{2}D^{-1/2}\left(v_{2}(i)s_{2}+\frac{\lambda^{t}_{3}}{\lambda^{t}_{2}}v_{3}(i)s_{3}+\ldots+\frac{\lambda^{t}_{n}}{\lambda^{t}_{2}}v_{n}(i)s_{n}\right).$
(2.7)

From Theorem 2.2 and $\lambda_{2}\neq\lambda_{3}$, we have
$|\lambda_{\alpha}/\lambda_{2}|<1$ with $3\leq\alpha\leq n$. Therefore, when
$t$ tends towards infinity, all the terms in 2.6 with $\alpha\geq 3$ vanish.
From there we have the $j-$th component of vector $P^{t}_{i\bullet}-\phi$ and
the $j-$th component of vector $\lambda^{t}_{2}v_{2}(i)s_{2}$ having the same
sign for $t$ large enough and for all $j=1,2,...,n$. Hence the conclusion of
the theorem. Furthermore, from (2.7), we deduce this conclusion holds for all
$i=1,2,...,n$. $\Box$

From Theorem 2.2, we observe that clustering based on random walk and spectral
analysis is the same. Therefore, based on a random walk, we can propose a
Random Walk Graph Partition Algorithm 1 as follows.

Input: Graph $G$, $C\subset V(G)$, $Q=\emptyset$, $t$

Output: Final list of clusters $Q$

Phase 1:

$C_{1}=\emptyset$, $C_{2}=\emptyset$;

Create induced graph $G^{\prime}$ from $C$, and select any vertex $i_{0}$ in
cluster $V(G^{\prime})$;

Calculate
$P^{t}_{i_{0}\bullet}-\phi=(P^{t}_{i_{0}1}-\phi_{1},P^{t}_{i_{0}2}-\phi_{2},...,P^{t}_{i_{0}n}-\phi_{n})$
in $G^{\prime}$;

for  _each vertex $j$_ do

if  _$P^{t}_{i_{0}j}-\phi_{j}\geq 0$_ then

Add $j$ to cluster $C_{1}$;

end if

else

Add $j$ to cluster $C_{2}$;

end if

end for

Phase 2:

if  _$C_{1}$ , $C_{2}$ are non-empty and $Q(C_{1},G)+Q(C_{2},G)>Q(C,G)$_ then

Apply Phase 1 with $C=C_{1}$ and apply Phase 1 with $C=C_{2}$;

end if

else

$Q=Q\cup\\{C\\}$;

end if

Algorithm 1 Random Walk Graph Partition Algorithm 1

In Algorithm 1, in phase 1, we need to compute $P^{t}_{i_{0}\bullet}$. The
computational complexity for calculating $P^{t}_{i_{0}\bullet}$ is $O(tm)$,
where $m$ is the number of edges in the graph $G$ (see [16]). In phase 2, we
need to compute $Q(C,G)$. To calculate $Q(C,G)$, we need to count the number
of edges in $C$ ($e_{C}$) and the number of edges connected to $C$ ($a_{C}$),
so the computational complexity of phase 2 does not exceed $O(m)$. Therefore,
the computational complexity of each iteration is $O(tm)+O(m)=O(tm)$. Assuming
the number of communities in the graph $G$ is $k$, the computational
complexity of Algorithm 1 is $O(tkm)$.

Although the case $\lambda_{2}=\lambda_{3}$ rarely occurs; if it does happen
or $\lambda_{2}$ is very close to $\lambda_{3}$, our Random Walk Graph
Partition Algorithm 1 will no longer be accurate. Therefore, to improve the
effectiveness of our algorithm in these cases, after dividing cluster $C$ into
two clusters $C_{1},C_{2}$, we will add an adjustment step. Specifically, we
will review all vertices to see if they deserve to be in the current cluster
or if they should be moved to another cluster based on maximizing modularity.
From there, we propose the following algorithm. In this part, we shall use the
notation $C_{i}$ to represent the community that includes node $i$ and
$C_{\overline{i}}$ for the community that does not include node $i$.

Input: Graph $G$, $C\subset V(G)$, $Q=\emptyset$, $t$

Output: Final list of clusters $Q$

Phase 1:

$C_{1}=\emptyset$, $C_{2}=\emptyset$;

Create induced graph $G^{\prime}$ from $C$, and select any vertex $i_{0}$ in
cluster $V(G^{\prime})$;

Calculate
$P^{t}_{i_{0}\bullet}-\phi=(P^{t}_{i_{0}1}-\phi_{1},P^{t}_{i_{0}2}-\phi_{2},...,P^{t}_{i_{0}n}-\phi_{n})$
in $G^{\prime}$;

for  _each vertex $j$_ do

if  _$P^{t}_{i_{0}j}-\phi_{j}\geq 0$_ then

Add $j$ to cluster $C_{1}$;

end if

else

Add $j$ to cluster $C_{2}$;

end if

end for

Count.number.move=1

while  _Count.number.move $\neq$ 0_ do

Count.number.move=0;

for  _$i$ in $V(G^{\prime})$_ do

if  _$\Delta Q_{i,C_{i}\setminus\\{i\\}} <\Delta Q_{i,C_{\overline{i}}}$_ then

Add $i$ to $C_{\overline{i}}$;

Count.number.move = Count.number.move + 1;

end if

end for

end while

Phase 2:

if  _$C_{1}$ , $C_{2}$ are non-empty and $Q(C_{1},G)+Q(C_{2},G)>Q(C,G)$_ then

Apply Phase 1 with $C=C_{1}$ and apply Phase 1 with $C=C_{2}$;

end if

else

$Q=Q\cup\\{C\\}$;

end if

Algorithm 2 Random Walk Graph Partition Algorithm 2

The algorithm referred to as Algorithm 2 distinguishes itself from Algorithm 1
solely in the adjustment step, which involves computing $\Delta Q_{i,C}$.
Regarding the while loop, it is worth mentioning that this loop only iterates
a few times, and the computational complexity of calculating $\Delta Q_{i,C}$
does not surpass $O(m)$. Consequently, the computational complexity of
Algorithm 2 is equivalent to that of Algorithm 1.

##  3 Random Walk Graph Partition Louvain algorithm

The Louvain algorithm [1] is a very famous algorithm not only because of its
fast calculation speed but also because of its high algorithm accuracy. It
iteratively performs the following steps until no increase in modularity can
be achieved anymore. It’s crucial that 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.

However, this algorithm could be less effective when the network has an
unclear community structure. In the paper [20], Leiden proposed one of the
most prominent improvements of the Leiden algorithm - the author added a phase
of fine-tuning local communities after the first phase of the Louvain
algorithm.

The Leiden algorithm fine-tuning local communities doesn’t work effectively in
cases where the community could be more opaque. Therefore, this paper will
propose an algorithm with a more effective method of fine-tuning local
communities. More precisely, we will use the Random Walk Graph Partition
Algorithm mentioned above to perform the refinement for each cluster obtained
from Phase 1. Consequently, we propose a new algorithm named the Random Walk
Graph Partition Louvain Algorithm (or RWGP-Louvain Algorithm for short).

Input: Network $G_{ori}$, $\mathcal{P}=\emptyset$, $t$

Output: FinalCommunities - Final list of communities

$G=G_{ori}$

Phase 1:

for  _ $i$ in $V(G)$_ do

$C_{i}=\\{i\\}$, $\mathcal{P}=\mathcal{P}\cup C_{i}$;

end for

while  _some nodes are moved_ do

for  _ $i$ in $V(G)$_ do

for  _neighboring community $C_{j}$ of $i$_ do

Calculate $\Delta Q_{i,C_{j}}$ according to Formula 1.1;

Add $i$ to the community $C_{i_{0}}$ with maximizing $\Delta Q_{i,C_{j_{0}}}$;

end for

end for

end while

for  _$C_{j}$ in $\mathcal{P}$_ do

if  _$C_{j}=\emptyset$_ then

$\mathcal{P}=\mathcal{P}\setminus\\{C_{j}\\}$;

end if

end for

Phase 2:

If the clusters in $\mathcal{P}$ contain supernodes, then return the clusters
containing the nodes of the original graph $G_{ori}$.

for  _$C_{j}$ in $\mathcal{P}$_ do

Apply Random Walk Graph Partition Algorithm 1 or Random Walk Graph Partition
Algorithm 2 with $G=G_{ori},\,C=C_{j}$, $Q=\emptyset$;

$\mathcal{P}=\mathcal{P}\setminus\\{C_{j}\\}\cup Q$

end for

Phase 3:

Create a new network $G^{\prime}$ by consolidating nodes within the same
community to supernodes;

for  _each pair of nodes $u$ and $v$ in the same community_ do

Add a self-loop to the community node for $u$ and $v$;

end for

for  _each edge between nodes in different communities_ do

Add a weighted edge between the corresponding community nodes;

end for

We will repeat phases 1 to 3 until modularity no longer increases.;

Algorithm 3 Random Walk Graph Partition Louvain Algorithm

In Algorithm 3, compared to the Louvain algorithm, each iteration of the
algorithm involves applying the Random Walk Graph Partition Algorithm to
$G=G_{ori}$ and $C=C_{j}$ for each $C_{j}\in\mathcal{P}$. For each $C_{j}$,
the computational complexity is $O(tm_{C_{j}})$, where $m_{C_{j}}$ is the
number of edges in cluster $C_{j}$. Consequently, the overall computational
complexity for this part is $O(tm)$, where $m$ represents the number of edges
in the original graph $G_{ori}$.

##  4 Experiments

Evaluating a community detection algorithm is difficult because one needs some
test graphs with already known community structure. A classical approach is to
use randomly generated graphs with given communities. Here, we will use this
approach and generate the graphs as follows.
Planted l-partition model: The first generator model is the planted
l-partition model [3]. By determining the number of groups $l$, the number of
vertices in each group $g$, and two probabilities of inter-cluster $p_{in}$
and intra-cluster $p_{out}$, we obtain one random graph with some Property:

  * •

The average degree of one vertex is
$E\left[k\right]=p_{in}(g-1)+p_{out}g(l-1)$.

  * •

All communities have the same size.

  * •

All vertices have approximately the same degree because of each community. It
can be seen as one random graph proposed by Erdos and Renyi. Each pair of
vertices is connected in those random graphs with equal probability $p_{in}$
independent of other pairs.

Gaussian random partition generator: The next generator graph model is
Gaussian random partition generator [3], which overcomes the part disadvantage
of the planted $l-$ partition model above the vertex degree distribution.
Unlike the planted $l-$ partition model, the community size in the Gaussian
random partition generator is a random variable of Gaussian distribution. The
parameters What needs to be determined for the Gaussian random partition
generator are:

  * •

Number of vertices in the graph: $N$.

  * •

Mean of community’s size: $m$ and variance of community’s size: $\sigma$.

  * •

Edge probability of inter $p_{in}$ and intra-cluster $p_{out}$.

After clustering a graph, we need to evaluate its quality. Therefore, we will
present a metric to evaluate the clustering quality next.

###  4.1 Evaluating metrics

In our experiments, we will use two metrics to compare the algorithms. The
first metric is to use modularity (formula 1.2). The second metric is that we
use Normalized Mutual Information (NMI). Normalized Mutual Information [10]
quantifies the similarity between true class labels $Y$ and predicted cluster
assignments $C$. It is computed as:

$\mathrm{NMI}(Y,C)=\frac{2\times\mathrm{MI}(Y,C)}{\mathrm{H}(Y)+\mathrm{H}(C)},$
(4.1)

where:

  * •

$\mathrm{MI}(Y,C)$ is the Mutual Information between $Y$ and $C$,

  * •

$\mathrm{H}(Y)$ and $\mathrm{H}(C)$ are the entropies of $Y$ and $C$
respectively.

The NMI values range from 0 to 1, with higher values indicating better
clustering alignment with true class labels. It is a normalized measure
commonly used in cluster evaluation.

###  4.2 Experiments for Random Walk Graphs Partition Algorithm

In this section, we conduct experiments to compare the effectiveness of our
two algorithms, Random Walk Graphs Partition Algorithm 1 and Random Walk
Graphs Partition Algorithm 2, with the algorithms Louvain [1] and Newman’s
Spectral Method [12]. The experiments involve randomly generated graphs using
the Gaussian random generator and Planted-l partition models. Given that this
is not the primary focus of our paper, we will perform a limited set of
experiments.

We conduct ten trials on randomly generated graphs for each experiment using
either the Gaussian random generator or the Planted-l partition model.
Subsequently, we calculate Modularity for the clustering results obtained from
different algorithms.

Finally, we present graphical representations of the Modularity values
corresponding to Random Walk Graphs Partition Algorithm 1 (RWGP1), Random Walk
Graphs Partition Algorithm 2 (RWGP2), Louvain [1], and Newman’s Spectral
Method [12] (Newman).

####  4.2.1 Experiments for Random Walk Graphs Partition Algorithm on the
random graph generated by the Gaussian random generator model

With the Gaussian random generator model, we will experiment on graphs with
the number of vertices ranging from a few hundred to tens of thousands. For
each type of graph, we will fix $p_{in}=0.7$, and we will explore $p_{out}$
values of $0.01$, and $0.03$, corresponding to graphs with clear community
structure to graphs with unclear community structure. And we will set the
variance of the community’s size $\delta=2.5$.

#### Experiment 1: Experiment on the random graph generated by the Gaussian
random generator model.

Using the Gaussian random generator model with a number of vertices $N$, the
mean of the community’s size $m$ is taken with a uniform distribution in the
following corresponding intervals: $N\in[500;1000]$, $m\in[50;100]$. In
implementing the Random Walk Graphs Partition Algorithm 1 and Random Walk
Graphs Partition Algorithm 2, we set $t$ to $15$. We present these results in
Figure 1.

Figure 1: Modularity obtained in Experiment 1 using Gaussian random generator
model with $N\in[500;1000]$, $m\in[50;100]$.

#### Experiment 2: Experiment on the random graph generated by the Gaussian
random generator model.

We use the Gaussian random generator model with a number of vertices $N$, the
mean of the community’s size $m$ taken with a uniform distribution in the
following corresponding intervals: $N\in[1000;2000]$, $m\in[100;200]$. In
implementing the Random Walk Graphs Partition Algorithm 1 and Random Walk
Graphs Partition Algorithm 2, we set $t$ to $40$. We present these results in
Figure 2.

Figure 2: Modularity obtained in Experiment 2 using Gaussian random generator
model with $N\in[1000;2000]$, $m\in[100;200]$.

####  4.2.2 Experiments for Random Walk Graphs Partition Algorithm on the
random graph generated by the Planted-l partition model

With the Planted-l partition model, we also fix $p_{in}=0.7$ and explore
$p_{out}$ values of $0.01$, and $0.03$, corresponding to graphs with clear
community structure to graphs with unclear community structure.

#### Experiment 1: Experiment on the random graph generated by the Planted-l
partition model.

Using the Planted-l partition model with a number of communities $l$, the size
of each community $g$ is taken with a uniform distribution in the following
corresponding intervals: $g\in[3;5]$, $l\in[50;70]$. In implementing the
Random Walk Graphs Partition Algorithm 1 and Random Walk Graphs Partition
Algorithm 2, we set $t$ to $15$. We present these results in Figure 3.

Figure 3:  Modularity obtained in Experiment 1 using the Planted-l partition
model with $g\in[3;5]$, $l\in[50;70]$.

#### Experiment 2: Experiment on the random graph generated by the Planted-l
partition model.

We use the Planted-l partition model with a number of communities $l$, the
size of each community $g$ taken with a uniform distribution in the following
corresponding intervals: $g\in[5;10]$, $l\in[100;200]$. In implementing the
Random Walk Graphs Partition Algorithm 1 and Random Walk Graphs Partition
Algorithm 2, we set $t$ to $40$. We present these results in Figure 4.

Figure 4: Modularity obtained in Experiment 2 using the Planted-l partition
model with $g,l$ taken with $g\in[5;10]$, $l\in[100;200]$, and $p_{in}=0.7$.

###  4.3 Experiments for Random Walk Graphs Partition Louvain Algorithm on
graphs are randomly generate

In this section, we conduct experiments to compare the effectiveness of our
proposed Random Walk Graphs Partition Louvain Algorithm (RWGP-Louvain) with
existing algorithms, namely the original Louvain algorithm [1], the Fast
Louvain algorithm [22], and the Leiden algorithm [20]. The experiments involve
randomly generated graphs using the Gaussian random generator and Planted-l
partition models.

We perform ten trials on randomly generated graphs for each experiment
utilizing either the Gaussian random generator or the Planted-l partition
model. Subsequently, we calculate Modularity (use formula 1.2) for the
clustering results obtained from different algorithms and calculate the NMI
(use formula 4.1) between the clustering results obtained when applying the
algorithms and the original clustering generated when creating the graph.

Finally, we present the Modularity and NMI values corresponding to RWGP-
Louvain, Louvain [1], Fast Louvain [22], and Leiden [20] algorithms through
graphical representations. We note that we apply the Random Walk Graph
Partition Algorithm 2 in Phase 2 of the Random Walk Graph Partition Louvain
Algorithm.

####  4.3.1 Experiments for Random Walk Graphs Partition Louvain Algorithm on
the random graph generated by the Gaussian random generator model

With the Gaussian random generator model, we will experiment on graphs with
the number of vertices ranging from a few hundred to tens of thousands. For
each type of graph, we will fix $p_{in}=0.7$, and we will explore $p_{out}$
values of $0.01$, $0.03$, and $0.05$, corresponding to graphs with clear
community structure to graphs with unclear community structure. And we will
set the variance of the community’s size $\delta=2.5$.

#### Experiment 1: Random Graphs from the Gaussian Random Generator Model

Using the Gaussian Random Generator Model, we set the number of vertices ($N$)
and the mean community size ($m$) with a uniform distribution within
$N\in[500;1000]$ and $m\in[20;30]$. For RWGP-Louvain Algorithm, $t$ is set to
$15$. The results are depicted in Figures 5 and 6.

Figure 5: Modularity was observed in Experiment 1 using the Gaussian random
generator model with $N\in[500;1000]$ and $m\in[20;30]$. Figure 6: NMI was
observed in Experiment 1 using the Gaussian random generator model with
$N\in[500;1000]$ and $m\in[20;30]$.

#### Experiment 2: Random Graphs from the Gaussian Random Generator Model

Using the Gaussian Random Generator Model, we set the number of vertices ($N$)
and the mean community size ($m$) with a uniform distribution within
$N\in[2000;4000]$ and $m\in[50;70]$. For RWGP-Louvain Algorithm, $t$ is set to
$25$. The results are illustrated in Figures 7 and 8.

Figure 7: Modularity was observed in Experiment 2 using the Gaussian random
generator model with $N\in[2000;4000]$ and $m\in[50;70]$. Figure 8: NMI was
observed in Experiment 2 using the Gaussian random generator model with
$N\in[2000;4000]$ and $m\in[50;70]$.

#### Experiment 3: Random Graphs from the Gaussian Random Generator Model

Using the Gaussian Random Generator Model, we set the number of vertices ($N$)
and the mean community size ($m$) with a uniform distribution within
$N\in[4000;8000]$ and $m\in[100;150]$. For RWGP-Louvain Algorithm, $t$ is set
to $40$. The outcomes are presented in Figures 9 and 10.

Figure 9: Modularity was observed in Experiment 3 using the Gaussian random
generator model with $N\in[4000;8000]$ and $m\in[50;70]$. Figure 10: NMI was
observed in Experiment 3 using the Gaussian random generator model with
$N\in[4000;8000]$ and $m\in[100;120]$.

####  4.3.2 Experiments for RWGP-Louvain Algorithm on the random graph
generated by the Planted-l partition model

With the Planted-l partition model, we also fix $p_{in}=0.7$ and explore
$p_{out}$ values of $0.01$, $0.03$, and $0.05$, corresponding to graphs with
clear community structure to graphs with unclear community structure.

#### Experiment 1: Random Graphs from the Planted-l Partition Model

Using the Planted-l Partition Model, we set the number of communities ($l$)
and the size of each community ($g$) are selected with a uniform distribution
within the intervals $g\in[30;50]$ and $l\in[30;50]$. For RWGP-Louvain
Algorithm, $t$ is set to $25$. The results are depicted in Figures 11 and 12.

Figure 11:  Modularity was observed in Experiment 1 using the Planted-l
partition model with $g\in[30;50]$, $l\in[30;50]$. Figure 12: NMI was observed
in Experiment 1 using the Planted-l partition model with $g\in[30;50]$,
$l\in[30;50]$.

#### Experiment 2: Random Graphs from the Planted-l Partition Model

Using the Planted-l Partition Model, we set the number of communities ($l$)
and the size of each community ($g$) are selected with a uniform distribution
within the intervals $g\in[50;70]$ and $l\in[50;70]$. For RWGP-Louvain
Algorithm, $t$ is set to $25$. The results are illustrated in Figures 13 and
14.

Figure 13: Modularity was observed in Experiment 2 using the Planted-l
partition model with $g\in[50;70]$, $l\in[50;70]$. Figure 14: NMI was observed
in Experiment 2 using the Planted-l partition model with $g\in[50;70]$,
$l\in[50;70]$.

###  4.4 Experiments on real data

Before performing the experiments, we will introduce some famous real data
used in this section.
Zachary’s karate club:  Wayne W. Zachary examined a karate club’s social
network from 1970 to 1972, detailed in [23]. The network, featuring 34 members
and capturing interactions beyond the club, gained prominence as a community
structure example in networks following its analysis by Michelle Girvan and
Mark Newman in 2002 [5].
College football:  The college football network, examined in [5], serves as a
benchmark for community detection. It illustrates the games played by Division
I colleges in the autumn of 2000, with each node representing a football team
and each edge representing a regular season game. With 115 nodes and 616
edges, the network can be divided into 12 communities based on athletic
conferences, each comprising 8 to 12 teams.
Jazz network: Data was sourced from The Red Hot Jazz Archive digital database
[19], comprising 198 bands active between 1912 and 1940, predominantly in the
1920s. The database identifies musicians in each band, but distinguishing
their temporal involvement is challenging, hindering the study of the
collaboration network’s temporal evolution. The remaining 1275 musicians’
names are dispersed across the bands.
Metabolic network: As in [7], a metabolic network encompasses the entire
metabolic and physical processes governing a cell’s physiological and
biochemical characteristics. It includes metabolic reactions, pathways, and
the regulatory interactions orchestrating these reactions.

In addition, we will also perform experiments on the following real data:
Hamster households, hamster friendships, and Asoiaf. These data we can see in
[9].

Now, we will conduct experiments to compare the effectiveness of our proposed
Random Walk Graphs Partition Louvain Algorithm (RWGP-Louvain) with existing
algorithms, namely the original Louvain algorithm [1], the Fast Louvain
algorithm [22], and the Leiden algorithm [20] on real data. After obtaining
the clustering results, we will calculate modularity (using the formula 1.2)
and record the modularity results in the following table 1.

Graph $G=(|V|,|E|)$ |  Louvain |  RWGP Louvain |  Leiden |  Fast Louvain
---|---|---|---|---
Karate [7], $G=(,)$ |  0.2394806 |  0.2450690 |  0.2404668 |  0.2404668
Metabolic network [7] |  |  |  |
$G=(453,2025)$ |  0.2960217 |  0.3054383 |  0.2965548 |  0.29486578
College football [5] |  |  |  |
$G=(115,613)$ |  0.5357494 |  0.5400073 |  0.5357494 |  0.5316192
Jazz network [19] |  |  |  |
$G=(198,2742)$ |  0.2833862 |  0.2850413 |  0.2828381 |  0.2821492
Hamster households [9] |  |  |  |
$G=(921,4032)$ |  0.1678505 |  0.2058422 |  0.1983055 |  0.1940693
Hamsters friendships [9] |  |  |  |
$G=(1858,12534)$ |  0.3096735 |  0.3308066 |  0.3216459 |  0.3095751
Asoiaf [9] |  |  |  |
$G=(796,2823)$ |  0.5182439 |  0.5370974 |  0.5404249 |  0.5185884
Table 1: In this table, we present the values of Modularity (using the formula
1.2) corresponding to the clustering results of the algorithms.

###  4.5 Conclusion of the experiments

The above results show that our algorithms are efficient in almost all
experiments.

  * •

In the Subsection 4.2, we perform some simple experiments using two models
Gaussian random generator model and Planted-l partition model to compare our
Random Walk Graphs Partition Algorithm 1 and Random Walk Graphs Partition
Algorithm 2 with Louvain algorithm [1], Newman’s Spectral Method [12]. We see
that our algorithm works well on graphs with clear community structures. On
graphs with unclear structures, our Random Walk Graphs Partition Algorithm 2
algorithm still works more efficiently and has less computational complexity
than Newman’s Spectral Method.

  * •

In Subsection 4.3, we performed experiments comparing the effectiveness of our
proposed Random Walk Graphs Partition Louvain Algorithm and the Louvain
uciteLouvain, Fast Louvain Algorithm [22] and Leiden algorithm [20] through
graphs on randomly generated graphs using Gaussian random generator model and
Planted-l partition model. The algorithms we investigated on graphs with
apparent community structures produce good results. Our Random Walk Graphs
Partition Louvain Algorithm performs much better than the Louvain, Fast
Louvain, and Leiden algorithms for graphs with unclear community structures.

  * •

Furthermore, when performing experiments using real data, our Random Walk
Graphs Partition Louvain Algorithm is also more effective than the remaining
algorithms on some real data.

##  5 Conclusion and further work

This paper introduced a novel approach to community detection through graph
partitioning by leveraging a random walk strategy akin to the spectral method
presented in [12], referred to as the Random Walk Graph Partition Algorithm.
Our proposed algorithm demonstrates superior computational efficiency compared
to the spectral algorithm discussed in [12].

Moreover, recognizing the Random Walk Graph Partition Algorithm as a phase
within the Louvain algorithm, we introduce a new algorithm called the Random
Walk Graph Partition Louvain Algorithm. This algorithm retains computational
complexity equivalent to the Louvain algorithm while achieving enhanced
efficiency, particularly in scenarios involving graphs with ambiguous
community structures.

To validate the rationale and efficacy of our proposed algorithms, we conduct
experiments on randomly generated and real-world datasets. The results
underscore the effectiveness of our approaches, reinforcing their
applicability in practical community detection scenarios.

## Acknowledgments

This research was supported by the International Centre of Research and
Postgraduate Training in Mathematics, Institute of Mathematics, project code:
ICRTM04-2021.01, and Vingroup Innovation Foundation, project code:
VINIF.2023.STS.53.

## References

  * [1] V. D. Blondel1, J.-L. Guillaume1, R. Lambiotte1 and E. Lefebvre1, Fast unfolding of communities in large networks, Journal of Statistical Mechanics: Theory and Experiment, Volume 2008, October 2008.
  * [2] D. T. Dat, D. D. Hieu, P. T. H. Duong, Community detection in directed graphs using stationary distribution and hitting times methods, Social Network Analysis and Mining volume 13, Article number: 80 (2023).
  * [3] S. Fortunato, ”Community detection in graphs,” Physics Reports, vol. 486, pp. 75–174, 2010.
  * [4] G. W. Flake, S. Lawrence, C. L. Giles, and F. M. Coetzee. Self-organization and identification of web communities. Computer, 35(3):66-71, 2002.
  * [5] M. Girvan, M.E.J Newman, Community structure in social and biological networks, Proc. Natl. Acad. Sci. USA 99 (2002) 7821–7826
  * [6] D. D. Hieu, P. T. H. Duong, Overlapping community detection algorithms using Modularity and the cosine (preprint).
  * [7] H. Jeong , B. Tombor, R. Albert, Z. N. Oltvai, and A.-L. Barabási, The large-scale organization of metabolic networks. Nature 407, 651–654, 2000.
  * [8] J. Kleinberg and S. Lawrence. The structure of the web. Science, 294(5548):1849-1850, 2001.
  * [9] J. Kunegis. KONECT – The Koblenz Network Collection. In Proc. Int. Conf. on World Wide Web Companion, pages 1343–1350, 2013.
  * [10] T.O. Kvålseth, Entropy and correlation: Some comments. IEEE Trans. Syst. Man Cybern. 1987, SMC-17, 517–519.
  * [11] L. Lovász. Random walks on graphs: a survey. In Combinatorics, Paul Erdős is eighty, Vol. 2 (Keszthely, 1993), volume 2 of Bolyai Soc. Math. Stud., pages 353– 397\. János Bolyai Math. Soc., Budapest, 1996.
  * [12] M. E. J. Newman, Spectral methods for network community detection and graph partitioning, Phys. Rev. E, vol. 88, p. 042822, October 2013.
  * [13] M. E. J. Newman, Modularity and community structure in networks. Proceedings of the National Academy of Sciences of the United States of America. 103 (23): 8577–8696(2006).
  * [14] M. E. J. Newman. Fast algorithm for detecting community structure in networks. Physical Review E, 69(6):066133, 2004.
  * [15] M. E. J. Newman and M. Girvan. Finding and evaluating community structure in networks. Physical Review E, 69(2):026113, 2004.
  * [16] P. Pons and M. Latapy. Computing communities in large networks using random walks, Journal of Graph Algorithms and Applications, volume 10, no. 2, 2006, Pages 191–218, 2006.
  * [17] E. Ravasz, A. L. Somera, D. A. Mongru, Z. N. Oltvai, and A.-L. Barabási. Hierarchical Organization of Modularity in Metabolic Networks. Science, 297(5586):15511555, 2002.
  * [18] J-F. Rural, K. Venkatesan, T. Hao, T. Hirozane-Kishikawa, A. Dricot, et al. Towards a proteome-scale map of the human protein-protein interaction network. Nature 437: 1173. 2005.
  * [19] The Red Hot Jazz Archive, available at http://www.redhotjazz.co
  * [20] V.A. Traag, L. Waltman, and N.J. Van Eck, From Louvain to Leiden: guaranteeing well-connected communities. Sci Rep 9, 5233 (2019). https://doi.org/10.1038/s41598-019-41695-z
  * [21] L. Waltman, and N. J. van Eck, A smart local moving algorithm for large-scale modularity-based community detection. Eur. Phys. J. B 86, 471, https://doi.org/10.1140/epjb/e2013-40829-0 (2013).
  * [22] J. Zhang, J. Fei, X. Song, J. Feng, An Improved Louvain Algorithm for Community Detection, Mathematical Problems in Engineering, vol. 2021, Article ID 1485592, 14 pages, 2021. https://doi.org/10.1155/2021/1485592.
  * [23] Zachary, W. An information flow model for conflict and fission in small groups. J. Anthropol. Res. 33, 452–473, 1977.