Faster unfolding of communities: speeding up the Louvain algorithm.
V.A. Traag1, 2, ∗
1

arXiv:1503.01322v2 [physics.soc-ph] 9 Sep 2015

2

Royal Netherlands Institute of Southeast Asian and Caribbean Studies
e-Humanities Group, Royal Netherlands Academy of Arts and Sciences

Many complex networks exhibit a modular structure of densely connected groups of nodes. Usually, such a modular structure is uncovered by the optimization of some quality function. Although
flawed, modularity remains one of the most popular quality functions. The Louvain algorithm was
originally developed for optimizing modularity, but has been applied to a variety of methods. As
such, speeding up the Louvain algorithm, enables the analysis of larger graphs in a shorter time
for various methods. We here suggest to consider moving nodes to a random neighbor community,
instead of the best neighbor community. Although incredibly simple, it reduces the theoretical
runtime complexity from O(m) to O(n loghki) in networks with a clear community structure. In
benchmark networks, it speeds up the algorithm roughly 2–3 times, while in some real networks
it even reaches 10 times faster runtimes. This improvement is due to two factors: (1) a random
neighbor is likely to be in a “good” community; and (2) random neighbors are likely to be hubs,
helping the convergence. Finally, the performance gain only slightly diminishes the quality, especially for modularity, thus providing a good quality-performance ratio. However, these gains are less
pronounced, or even disappear, for some other measures such as significance or surprise.

I.

INTRODUCTION

Complex networks have gained attention the past
decade [1]. Especially with the rise of social media, social
networks of unprecedented size became available, which
contributed to the establishment of the computational
social sciences [2, 3]. But networks are also common in
disciplines such as biology [4] and neurology [5]. Many
of these networks share various common characteristics.
They often have skewed degree distributions [6], show a
high clustering and a low average path length [7]. Nodes
often cluster together in dense groups, usually called
communities. Nodes in a community often share other
characteristics: metabolites show related functions [8]
and people have a similar background [9]. Revealing the
community structure can thus help to understand the
network [10].
Modularity [11] remains one of the most popular measures in community detection, even though it is flawed.
There have been many algorithms suggested for optimizing modularity. The original algorithm [11] created a full
dendrogram and used modularity to decide on a cutting
point. It was quite slow, running in O(n2 m), where n is
the number of nodes and m the number of links. Many
algorithms were quickly introduced to optimize modularity, such as extremal optimization [12], simulated annealing [13, 14], spectral methods [15], greedy methods [16],
and many other methods [10]. One of the fastest and
most effective algorithms is the Louvain algorithm [17],
believed to be running in O(m). It has been shown to
perform very well in comparative benchmark tests [18].
The algorithm is largely independent of the objective
function to optimize, and as such has been used for different methods [19–24]

∗

traag@kitlv.nl

We first briefly describe the algorithm, and introduce
the terminology. We then describe our simple improvement, which we call the random neighbor Louvain, and
argue why we expect it to function well. We derive estimates of the runtime complexity, and obtain O(m) for
the original Louvain algorithm, in line with earlier results, and O(n loghki) for our improvement, where hki
is the average degree. This makes it one of the fastest
algorithms for community detection to optimize an objective function. Whereas the original algorithm runs in
linear time with respect to the number of edges, the random neighbor algorithm is nearly linear with respect to
the number of nodes. Finally, we show on benchmark
tests and some real networks that this minor adjustment
indeed leads to reductions in running time, without losing much quality. These gains are especially visible for
modularity, but less clear for other measures such as significance and surprise.

II.

LOUVAIN ALGORITHM

Community detection tries to find a “good” partition
for a certain graph. In other words, the input is some
graph G = (V, E) with n = |V | nodes and m = |E|
edges. Each node has ki neighbors, which is called the
degree, which on average is hki = 2m
n . The output is
some partition V = {V1 , V2 , . . . , Vr }, where each Vc ⊆ V
is a set of nodes we call a community. We work with nonoverlapping nodes, such that Vc ∩ Vd = ∅ for all c 6= d
and
S all nodes will have to be in a community, so that
Vc = V . Alternatively, we denote by σi the community
of node i, such that σi = c if (and only if) i ∈ Vc . Both
σ and V may be used interchangeably to refer to the
partition. If the distinction is essential, we will explicitly
state this.
The Louvain algorithm is suited for optimizing a single
objective function that specifies some quality of a par-

2
function Louvain(Graph G)
σi ← i.
. Initial partition
σ 0 ← MoveNodes(G)
. Initial move nodes
while H(σ 0 ) > H(σ) do
σ ← σ0
G ← Aggregate(G, σ)
Σ ← MoveNodes(G)
. Move nodes
σi0 ← Σσi0 for all i
. Correct σ 0 according to Σ
end while
return σ 0
end function

tition. We denote such an objective function with H,
which should be maximized. We use H(σ) and H(V)
to mean the same thing. There are various choices for
such an objective function, such as modularity [11], Potts
models [13, 19, 22], significance [25], surprise [26], infomap [21] and many more. We will not specify any of
the objective functions here, nor shall we discuss their
(dis)advantages, as we focus on the Louvain algorithm
as a general optimization scheme.
Briefly, the Louvain algorithm works as follows. The
algorithm initially starts out with a partition where each
node is in its own community (i.e. σi = i), which is
the initial partition. So, initially, there are as many
communities as there are nodes. The algorithm moves
around nodes from one community to another, to try to
improve H(σ). We denote by ∆H(σi 7→ c) the difference
in moving node i to another community c. In particular, ∆H(σi 7→ c) = H(σ 0 ) − H(σ) where σj0 = σj for all
j 6= i and σi0 = c, implying that if ∆H(σi 7→ c) > 0, the
objective function H is improved. At some point, the
algorithm can no longer improve H by moving around
individual nodes, at which point it aggregates the graph,
and reiterates on the aggregated graph. We repeat this
procedure as long as we can improve H(σ). The outline
of the algorithm is displayed in Algorithm 1.
There are two key procedures: MoveNodes and Aggregate. The MoveNodes procedure displayed in Algorithm 1 loops over all nodes (in random order), and
considers moving them to an alternative community.
This procedure relies on SelectCommunity to select a
(possibly) better community c. Only if the improvement
∆H(σv 7→ c) > 0, we will actually move the node to
community c. The Aggregate procedure may depend
on the exact quality function H used. In particular, the
aggregate graph G0 should be constructed according to
σ, such that H(G0 , σ 0 ) = H(G, σ), where σi0 = i is the
initial partition. That is, the quality of the initial partition σ 0 of the aggregated graph G0 should be equal to
the quality of the partition σ of the original graph G.
In Algorithm 1 a version is displayed which is suited for
modularity. Other methods may require additional variables to be used when aggregating the graph (e.g. [19]).
The only procedure that remains to be specified is SelectCommunity. In the original Louvain algorithm,
this procedure commonly considers all possible neighboring communities, and then greedily selects the best
community. It is summarized in Algorithm 2.
We created a new flexible and fast implementation of
the Louvain algorithm in C++ for use in python using
igraph. The implementation of the algorithm itself is
quite detached from the objective function to optimize.
In particular, all that is required to implement a new objective function is the difference when moving a node ∆H
and the quality function H itself (although the latter is
not strictly necessary). This implementation is available

function MoveNodes(Graph G)
σi ← i for i = 1, . . . , |V (G)|.
q ← −∞
while H(σ) > q do
q = H(σ)
for random v ∈ V (G) do
c ← SelectCommunity(v)
if ∆H(σv 7→ c) > 0 then
σv ← c.
end if
end for
end while
end function

. Initial partition

function Aggregate(Graph G, Partition σ)
A ← Adjacency(G)
P
A0cd ← ij Aij δ(σi , c)δ(σj , d)
return A0
end function
ALGORITHM 1. Louvain method. The algorithm loops over
all nodes and moves nodes to alternative communities. When
no more improvement can be made, it aggregates the graph
and reiterates the procedure.

open source from GitHub1 and PyPi2 .
III.

IMPROVEMENT

Not surprisingly, the Louvain algorithm generally
spends most of its time contemplating alternative communities. While profiling our implementation, we found
that it spends roughly 95% of the time calculating the
difference ∆H(σv 7→ c) in Algorithm 2. Much of this
time is spent moving around nodes for the first time.
With an initial partition where each node is in its own
community, almost any neighboring community would
be an improvement. Moreover, when the algorithm has
progressed a bit, many neighbors likely belong to the
same community. We therefore suggest that instead of
considering all neighboring communities, we simply select a random neighbor, and consider that community
(as stated in Algorithm 2), which we call the random

1
2

https://github.com/vtraag/louvain-igraph
https://pypi.python.org/pypi/louvain

3
All comms.

102

a

Time (s)

1012
109

3

100
100

b

ER modularity

c

10−1

102

10

CM modularity

10−4

106

Time (s)

E (t)

Rand. neigh. comm.

101

102

103
nc

104

105

106

Simulation

Significance

d

Surprise

e

10−1

10−4
101

102
nc

101

102
nc

Actual runtime

FIG. 1. Clique. The original Louvain algorithm considers all communities, which leads to E(t) = O(n2c ) operations for
putting all nc nodes of a clique in a single community. The improvement considers only random neighbors, which takes only
E(t) = O(nc log nc ) operations to identify the whole clique as a community. In (a) we show the number of operations in
a simulation, with the markers indicating the simulated number of operations, and the solid lines the analytically derived
estimates. In (b)–(e) we show the actual time used when optimizing the indicated quality functions for a clique for the different
objective functions. The solid lines in (b)–(e) denote best fits to n2c and nc log nc in log-space.
Select best neighbor community
function SelectCommunity(Node v)
δ ← −∞.
c ← σv .
C ← {σu | (uv) ∈ E(G)}
. Neighbor communities.
for Community c0 ∈ C do
if ∆H(σv 7→ c0 ) > δ then
δ ← ∆H(σv 7→ c0 )
c ← c0
end if
end for
return c
end function
Select random neighbor community
function SelectCommunity(Node v)
return random σ ∈ {σu | (uv) ∈ E(G)}.
end function
ALGORITHM 2. Select the best or a random neighbor community.

neighbor Louvain. Notice that the selection of a random neighbor makes the greedy Louvain algorithm less
greedy and thus more explorative. Indeed, when also accepting moves with some probability depending on the
improvement (possibly also accepting degrading moves),
the algorithm comes close to resemble simulated anneal-

ing [13, 14]. However, simulated annealing is rather slow
for community detection [18], so we don’t explore that
direction further, since we are interested in speeding up
the algorithm.
There are several advantages to the selection of a random neighbor. First of all, it is likely to choose a relatively “good” community. In general, a node should be
in a community to which relatively many of its neighbors belong as well (although this of course depends on
the exact quality function). By selecting a community
from among its neighbors, there is a good chance that
a relatively good community is picked. In particular, if
node i has ki (c) neighbors in community c, the probability that community c will be considered for moving
is ki (c)/ki . The probability for selecting a community
is thus proportional to the number of neighbors in that
community. Bad communities (with relatively few neighbors) are less frequently sampled, so that the algorithm
focuses more on the promising communities (those with
relatively many neighbors).
Moreover, when considering the initial partition of each
node in its own community, almost any move would improve the quality function H. The difference between
alternative communities in this early stage is likely to
be marginal. Any move that puts two nodes in the same
community is probably better than a node in its own community. Such moves quickly reduce the number of com-

4
CM Modularity
Significance

ER Modularity
Surprise

CM modularity
Significance

ER modularity
Surprise

Community size

Quality Ratio

a

6

b

4

4

2

2

0
2

0
2

c

d

1.5

1.5

1

1

0.5
0
104

0.5
105

106

No. Nodes (n)

107

µ = 0.1

105

106

0
107

10

µ = 0.8

a

8

Speedup ratio

Speedup Ratio

6

µ = 0.8

b

10
8

6

6

4

4

2

2

0
104
Found hnc i

µ = 0.1

c

d

102

0
104

102

100
101

102

No. Nodes (n)

104 101

103

102

Planted hnc i

103

104

100

Planted hnc i

Community size inequality

munities from roughly n to n/2. But instead of considering every neighboring community as in the original Louvain algorithm, which takes roughly O(hki), our random
neighbor Louvain algorithm only considers a single random neighbor, which takes constant time O(1). So, for
the first few iterations, Louvain runs in O(nhki) = O(m),
whereas selecting a random neighbor runs in O(n).
Notice there is a big difference between (1) selecting a
random neighbor and then its community and (2) selecting a random community from among the neighboring
communities. The first method selects a community proportional to the number of neighbors that are in that
community, while the second method selects a community uniformly from the set of neighboring communities.
Consider for example a node that is connected to two
communities, and has ki −1 neighbors in the first community and only 1 in the other community. When selecting
a community of a random neighbor, the probability the
good community is considered is 1 − k1i , while the prob-

µ = 0.1
6
Speedup ratio

FIG. 2. Network size. We here show the ratio of the time
and of the quality (i.e. H) of the uncovered partitions by the
original Louvain algorithm and the random neighbor Louvain.
The random neighbor Louvain algorithm is 2–3 times faster
than the original Louvain algorithm and at some points event
faster for clear communities in (a) when using µ = 0.1. However, for less clear communities at µ = 0.8 as displayed in
(b), the optimization of significance and surprise is not faster
by using the random neighbor Louvain. The random neighbor Louvain uncovers almost the same quality as the original
version for a large part, as shown in (c) and (d). However,
especially for surprise, the quality is adversely affected by the
random neighbor Louvain for µ = 0.1, shown in (c). The results are based on benchmark graph with communities of size
nc = 1 000 and an average degree of hki = 15.

µ = 0.8

e

6

f

4

4

2

2

0

2

4

6

8

Community size ratio

2

4

6

8

0

Community size ratio

FIG. 3. Effect of community size. Results in (a) show
that the speedup ratio increases with the community size for
µ = 0.1. Surprise and significance find smaller substructures
within large communities as seen in (c). This is also when the
improvement starts to deteriorate. The results for large communities in (a) and (c) are very similar to the situation when
µ = 0.8 in (b) and (d), which resembles a random graph more
closely. The speedup ratio in (b) corresponds to this: the
speedup is rather large for modularity, while it is much lower
for surprise and significance. In (e) and (f) we show that
heterogeneity in the community sizes nearly do not impact
the speedup ratio. In that case we generate LFR benchmark
graphs with smallest community size nc = 10 and the maximum community size varies from 2 to 10 times as large. We
use n = 105 and hki = 10 for both benchmarks.

ability is only 12 when selecting a random community.
Secondly, random selection of a neighbor increases the
likelihood of quick convergence. The probability that
node i is selected as a random neighbor is roughly ki /2m,
resembling preferential attachment [27] in a certain sense.
Hubs are thus more likely to be chosen as a candidate
community. Since, hubs connect many vertices, there is
a considerable probability that two nodes consider the

5
same hub. If these two (or more) nodes (and the hub)
should in fact belong to the same community, chances
are high both nodes and the hub quickly end up in the
same community.
As an illustration of this advantage, consider a hubsand-spokes structure, with one central hub and only
neighboring spokes that are connected to each other (and
always to the hub). So, any spoke node i is connected
to nodes i − 1 and i + 1 and to the central hub, node
n. Consider for simplicity that the nodes are considered
in order and that every move will be advantageous. The
probability that the first node will move to community n
is p1 = 31 . For the second node, he will move to community n if he chooses node n immediately (which happens
with probability 13 ), or if he chooses node 1, and node
1 moved to community n, so that p2 = 13 + p1 31 . Simij
Pi
larly, for the other nodes pi = 13 + pi−1 13 = j=1 13
which goes to 12 for n → ∞. This is higher than when
just considering a random neighbor community. In that
case, the probability the first node will move to community n is still 31 . But for the second node, if node 1
moved to community n, only two communities are left:
n and 3. In that case, community n is chosen with probability 12 . If node 1 didn’t move to community n, then
node 2 will move to community n with probability 13 . In
general, node i moves to community n with probability
pi = pi−1 12 + (1 − pi−1 ) 31 = pi−1 16 + 13 . Working out
Pi−1 j
the recurrence, we obtain that pi = 13 j=0 16 , which
tends to 25 . Selecting a community of a random neighbor
thus works better than selecting a random community
from among the neighbors. Selecting a community of a
random node is even worse. In that case, the probability
is pi = n1 (1+ n1 )i−1 which tends to 0 for n → ∞. In short,
selecting the community of a random neighbor is likely
to choose a new community that will also be chosen by
other nodes.
In summary, selecting a random neighbor should work
well because of two reasons. First, it tends to focus on communities that are “good”.
Secondly, it
should help in convergence because of higher likelihood of selecting hubs. In particular, the evaluation
of SelectCommunity in the random neighbor Louvain takes a constant time O(1) whereas evaluating all
communities takes about O(hki). However, one essential
question is whether SelectCommunity will not be too
frequently evaluated in the random neighbor Louvain to
counter this benefit.
To study this question, let us consider a ring of r
cliques of nc nodes each. Thecliques (which are complete subgraphs containing n2c links) are connected to
another clique only by a single link in a circular fashion (i.e. clique i is connected only to clique i − 1 and
i + 1). Most methods tend to find the cliques (or sets
of multiple cliques due to the resolution limit [19, 28]).
Indeed, it is one of the best possible community structures: we cannot add any more internal edges, nor can
we delete any external edges without disconnecting the

Network
Health
Brightkite
Facebook
Author Collaboration
Web (Google)
Web (Berk./Stan.)

n

m

2 539
58 228
63 731
22 908
875 713
685 230

12 969
214 078
817 035
2 673 133
5 105 039
7 600 595

hki
10.22
7.35
25.64
233.38
11.66
22.18

TABLE I. Empirical network overview.

graph. However, for the runtime complexity, the external
edges will play only a marginal role. We may therefore
simply assume we will work with r disconnected cliques
of size nc . Although the actual runtime will deviate from
this, it should provide a reasonable runtime for relatively
“clear” communities, and as such provide a lower bound
for more difficult communities.
The core question is thus how quickly both the original and the random neighbor Louvain run on cliques.
We will assume the clique should become a single community, which is likely to be the case for most methods. Additionally, we assume ∆H > 0 only if a node is
moved to a larger community, which is likely to be the
case for most methods as nodes in a clique have more
links to larger communities. The complexity of the original Louvain implementation is simple to evaluate in this
case. The first node will be moved to one of its neighbors, an operation that costs nc evaluations. The second
node has only nc − 1 evaluations to make, since the community of the first node disappeared. If we continue in
this fashion, the total number of evaluations t is then
Pnc
nc (nc +1)
= O(n2c ). The analysis of
i=1 nc − i + 1 =
2
the expected runtime of the random neighbor Louvain is
more difficult (see Appendix A for more details). However, we can provide a lower bound that serves as a rough
estimate. Let us again denote by t the total number of
operations before the whole clique is identified as a single
community. We divide this in different phases of the algorithm, where each phase i runs from the time where there
are nc − i + 1 communities, until there are nc − i communities. In phase 1 we thus start out with nc communities,
and in the next phase there are only nc − 1 communities.
If we denote by ti the number
in phase i,
P of operation
P
then by linearity E(t) = E( t ti ) = t E(ti ). Notice
that we will only leave phase i whenever a community of
size 1 disappears. The probability that a community of
1 disappears is ncn−1
, since it will join any other commuc
nity (except itself). There are at most i communities of
size 1 in phase i, so that the probability a community of
size 1 is selected is bounded above by nc −i+1
. In fact,
nc
such a state is also relatively likely, as the community size
distribution tends to become more skewed than a more
uniform distribution due to the preferential attachment
on the basis of the community sizes. The number of expected operations in phase i is then bounded below by
nc
nc −i+1 , and the expected operations in total is bounded

6
CM modularity

ER modularity

Significance

Surprise
Quality

Time
15

2

a

b

Quality ratio

Speedup ratio

1.5
10

5

1

0.5

ut
A

an
.)

e)

/S
t

oo
gl
(B

er

k.

(G
W
eb

lla
co
ho
r

do
le
A

W
eb

bo
ra
t

io
n

oo
k
Fa
c

eb

ite
rig
B

he
a
sc
e

nt

k.
/S
er
(B

ht
k

lth

.)
ta
n

gl
oo
(G
W
eb

ut
A

e)

tio
n
la

co
l
ho
r

do
A

W
eb

bo
ra

eb
Fa
c

B

rig

ht
k

oo

ite

th
al
he
t
le

sc

en

k

0

FIG. 4. Empirical network results. The random neighbor Louvain usually speeds up the optimization of the objective
function for most empirical networks. For the hyperlink network from Google it does not work for any method, while the
adolescent health dataset poses problems for optimizing CM modularity. The quality remains relatively similar compared to
the original, especially for modularity as shown in (b). For significance and surprise the difference are more pronounced.

below by
E(t) ≥ nc
= nc

nc
X
i=1
nc
X
i=1

1
nc − i + 1

(1)

1
= O(nc log nc )
i

(2)

However, this lower bound gives in fact a very accurate
estimate of the expected running time, as seen in Fig. 1.
Whereas the original Louvain algorithm runs in O(n2c ),
the random neighbor version only uses O(nc log nc ) to
put all nodes of a clique in a single community. We used
an explicit simulation of this process to validate our theoretical analysis. Running the actual algorithms on cliques
yields similar results (Fig. 1).
To get a rough idea of the overall running time, let
us translate these results back to the ring of cliques. In
that case, we have r cliques of nc nodes. The runtime for
the original Louvain method is O(n2c ) for each clique, so
that the total runtime is about O(rn2c ). One factor of n2c
comes from running over nc nodes, while the other factor
comes from running over hki ≈ nc neighbors. Since rnc =
n, and nhki = m, we thus obtain an overall running time
of Louvain of about O(rn2c ) = O(nhki) = O(m), similar
to earlier estimates [10, 17]. Following the same idea, we
obtain an estimate of roughly O(n loghki) for the runtime
of the random neighbor Louvain algorithm. So, whereas
the original algorithm runs in roughly linear time with
respect to the number of edges, the random neighbor

algorithm runs in nearly linear time with respect to the
number of nodes. Empirical networks are usually rather
sparse, so that the difference between hki and loghki is
usually not that large. Still, it is quite surprising to find
such an improvement for such a minor adjustment.

IV.

EXPERIMENTAL RESULTS

We use benchmark networks and real networks to show
that the random neighbor improvement also reduces the
runtime in practice. These benchmark networks contain
a planted partition, which we then try to uncover using both the original and the random neighbor Louvain
algorithm. An essential role is played by the probability that a link falls outside of the planted community µ.
For low µ it is thus quite easy to identify communities,
while for high µ it becomes increasingly more difficult.
We report results using the speedup ratio calculated as
T
Rspeed = Torig
, where Trn is the runtime of the random
rn
neighbor variant and Torig the runtime of the original
Louvain method. The runtime is calculated in used CPU
time, not elapsed real time. We also report the quality rarn
tio, which is calculated as Rqual = HHorig
where Hrn refers
to the quality of the partition uncovered using the random neighbor improvement and Hrn to the quality using
the original algorithm. In this way, if Rspeed > 1 the random neighbor improves upon the original and similarly
Rqual > 1 if the random neighbor is an improvement.

7
Throughout all plots, error bars indicate standard errors
of the mean. The Louvain algorithm can be applied to
many different methods, and we here show results for (1)
modularity using a configuration null model [11] (CM
modularity); (2) modularity using an Erdös-Rényi null
model [13] (ER modularity); (3) significance [25]; and
(4) surprise [29].
We first test the impact of the network size as a whole.
We construct benchmark networks ranging from n = 104
to n = 107 nodes, with equally sized communities of 1 000
nodes, with a Poissonian degree distribution. The speed
and quality of the original Louvain algorithm and the
random neighbor Louvain algorithm for all four methods
is reported in Fig. 2. For all these methods, the random
neighbor Louvain speeds up the algorithm roughly 2–3
times. At the same time, the quality of the partitions
found remains nearly the same.
However, surprise and significance seem to perform
worse than modularity. The speedup is rather limited
for higher µ (or becomes even slower than the original),
in which case communities are more difficult to detect.
Surprise and significance tend to find relatively smaller
communities than modularity [26], suggesting that the
performance gain of using the random neighbor Louvain
is especially pertinent when making a relatively coarse
partition. Revisiting the argument of the ring of cliques
makes clear that the runtime does not necessarily scale
with the degree, but rather, with the clique size, which
we may approximate as the community size. Indeed,
the runtime for merging all the nc nodes in a single
community together, should take O(n2c ) originally and
O(nc log nc ) in the random neighbor Louvain, as previously argued. However, if there are no clear communities
present in the network, the running time will not depend on the degree as much, but rather on the sizes of
the communities found. Hence, the running time should
then roughly scale as O(nnc ) for the original implementation and as O(n log nc ) for the random neighbor Louvain.
Since surprise and significance find smaller communities
than modularity (unless the communities are clearly defined), the speedup will be rather limited, whereas it will
be larger generally for modularity.
We test this by generating benchmark networks with
n = 105 nodes, hki = 10 and varying community sizes
from 10 to 20 000. Results are displayed in Fig. 3. Indeed, for larger communities, surprise and significance
have difficulties discerning such large communities, and
it tends to find substructure within these large communities. Notice that modularity also merges smaller communities (thereby uncovering artificially larger communities), part of the problem of the resolution limit [28]. This
is exactly also the point at which the speedup for surprise
and significance goes down. Moreover, when the community structure is not clear, there is no effect of community
size at all. Indeed, in that case, surprise tends to find
small communities, and modularity tends to find large
communities. The speedup follows this pattern: surprise
and significance show very small speedups, while modu-

larity shows larger speedups.
However, modularity also prefers rather balanced communities [30], so that perhaps modularity performs rather
well because of the similarity in community sizes. We
therefore also consider the impact of more heterogeneity
by constructing LFR benchmark networks [31]. In these
benchmark graphs the community sizes and the degree
both follow powerlaw distributions with exponents 1 and
2 respectively. The maximum degree was set at 2.5hki,
while the minimum community size was set at hki for
hki = 10. We varied the maximum community size from
2hki to 10hki. These results are displayed in Fig. 3, from
which we can see that the heterogeneity in community
sizes does not affect the results.
We also tested the random neighbor Louvain on six
empirical networks of varying sizes. These networks were
retrieved from the Koblenz Network Collection3 . We include (1) the adolescent health dataset, a school network
collected for health research [32]; (2) Brightkite, a social
network site [33]; (3) a Facebook friendship network [34];
(4) an author collaboration network from the High Energy topic on arXiv [35]; (5) a web hyperlink network
released by Google [36]; and (6) the complete web hyperlink network from the universities of Berkeley and Stanford [36]. An overview of the size of the networks is provided in Table I, and the results are displayed in Fig. 4.
The random neighbor Louvain is clearly faster for most
networks and methods, reaching even speedup ratios of
over 10 for the hyperlink web network from Berkeley and
Stanford. For the web network released by Google the
improvement is not faster however. The quality remains
relatively similar for most networks, especially for modularity, whereas the quality differs more for surprise and
significance.
Notice that significance is not defined for weighted networks, such that significance is not run on those networks
(health and author collaboration). But weighted networks raise an interesting point: is it possible to make
use of the weight to improve the speed even more? A
natural possibility is to sample neighbors proportional to
the weight. Neighbors in the same community are often connected with a higher weight, part of the famous
strength of weak ties [37, 38]. Sampling proportional to
the weight should thus increase the chances of drawing
a “good” community. However, this depends on the extent to which this correlation between weight and community holds. The aggregated graph is weighted also,
allowing the possibility of weighted sampling as well. On
the other hand, only little time is spent in the aggregated
iterations, making the benefit relatively small. Weighted
sampling in constant time requires preprocessing, which
takes an additional O(m) memory and O(m) time. The
question is thus whether these costs do not offset the
possible benefits.

3

http://konect.uni-koblenz.de/

8
CM modularity

ER modularity

µ = 0.1
Speedup ratio

Unweighted

15

Speedup ratio

µ = 0.8

a

15

b

10

10

5

5

0
15

Weighted

Surprise

c

0
15

d

10

10

5

5

0

0

0.2 0.4 0.6 0.8
µw

10

0.2 0.4 0.6 0.8
µw

1

0

FIG. 5. Performance weighted neighbor sampling. Instead of sampling a neighbor randomly, it is also possible to
sample neighbors proportional to the weight. We here test the
performance of the unweighted neighbor sampling in (a)–(b)
and the weighted neighbor sampling in (c)–(d). We generate weighted LFR benchmark networks, where the strength
of the nodes follows the degree si = kiβ with β = 1.5 with
hki = 10 and n = 105 . The results for the unweighted neighbor sampling in (a) and (b) are very similar to the results
for the weighted neighbor sampling in (c) and (d). Taking
into account the weight hence does not improve the random
neighbor sampling much.

We use weighted benchmark networks [39] to test
whether weighted sampling speeds up the algorithm even
further. These benchmark networks introduce an additional mixing parameter for the weight µw . Whereas the
topological mixing parameter µ controls the probability
of an edge outside of the community, the weight is distributed such that on average a proportion of about µw
lies outside of the community. The strength of the nodes
follows the degree si = kiβ with β = 1.5 with hki = 10
and n = 105 . The external weight µw si is spread over
µki external links, thereby leading to an average external
w si
= µµw kiβ−1 . If µw > µ the external weight
weight of µµk
i
is higher than the internal weight, making it difficult to
detect communities correctly. Intuitively, we would thus
expect to see an improvement in the random neighbor
selection whenever µw < µ, as in that case, the weight
correlates with the planted partition. The results for
both the unweighted and the weighted random neighbor
sampling is displayed in Fig. 5. Although the weighted
random neighbor sampling sometimes improves on the

4

http://www.ehumanities.nl/computational-humanities/
elite-network-shifts/

unweighted variant, overall the performance is comparable. The results on the unweighted benchmark networks
and the empirical networks are also very comparable (not
shown).
V.

CONCLUSION

Many networks seem to contain some community
structure. Finding such communities is important across
many different disciplines. One of the most used algorithms to optimize some quality function is the Louvain
algorithm. We here showed how a remarkably simple
adjustment leads to a clear improvement in the runtime complexity. We argue that the approximate runtime of the original Louvain algorithm should be roughly
O(m), while the improvement reduces the runtime to
O(n loghki) in a clear community structure. So, whereas
the original algorithm is linear in the number of edges,
the random neighbor algorithm is nearly linear in the
number of nodes.
We have tested the random neighbor algorithm extensively. The improvement is quite consistent across
various settings and sizes. The runtime complexity was
reduced, speeding up the algorithm roughly 2–3 times,
especially when concentrating on the coarser partitions
found by modularity. Nonetheless, some methods, such
as surprise and significance, are more sensitive to sampling a random neighbor. This seems to be mostly due to
the community size in the uncovered partition. Whereas
modularity prefers rather coarse partitions, both significance and surprise prefer more refined partitions, leading
to much smaller communities. More refined partitions offer fewer opportunities for improving the runtime, so that
sampling a random neighbor provides little improvement.
The idea could also be applied in different settings.
For example, the label propagation method is also a very
fast algorithm [40], but it doesn’t consider any objective
function. It simply puts a node in the most frequent
neighboring community. But instead of considering every neighbor, it can simply choose a random neighbor,
similar to the improvement here. We may thus expect
a similar improvement in label propagation as for the
Louvain algorithm. Similar improvements may be considered in other algorithms. The core of the idea is that
a random neighbor is likely to be in a “good” community,
which presumably also holds for other algorithms.

ACKNOWLEDGMENTS

This research is funded by the Royal Netherlands
Academy of Arts and Sciences (KNAW) through its eHumanities project 4 .

9

[1] S. Boccaletti, V. Latora, Y. Moreno, M. Chavez, and
D.-U. Hwang, Phys. Rep. 424, 175 (2006).
[2] D. J. Watts, Nature 445, 489 (2007).
[3] D. Lazer, A. Pentland, L. Adamic, S. Aral, A.-L.
Barabási, D. Brewer, N. Christakis, N. Contractor,
J. Fowler, M. Gutmann, T. Jebara, G. King, M. Macy,
D. Roy, and M. V. Alstyne, Science 323, 721 (2009).
[4] R. Guimerà, D. B. Stouffer, M. Sales-Pardo, E. A. Leicht,
M. E. J. Newman, and L. A. N. Amaral, Ecology 91,
2941 (2010).
[5] R. F. Betzel, A. Griffa, A. Avena-Koenigsberger, J. Goñi,
J.-P. Thiran, P. Hagmann, and O. Sporns, Netw. Sci. 1,
353 (2013).
[6] A.-L. Barabási, Science 325, 412 (2009).
[7] D. J. Watts and S. H. Strogatz, Nature 393, 440 (1998).
[8] E. Ravasz, A. L. Somera, D. A. Mongru, Z. N. Oltvai,
and A.-L. Barabási, Science 297, 1551 (2002).
[9] A. L. Traud, P. J. Mucha, and M. A. Porter, Physica A
391, 4165 (2012).
[10] S. Fortunato, Phys. Rep. 486, 75 (2010).
[11] M. E. J. Newman and M. Girvan, Phys. Rev. E 69,
026113 (2004).
[12] J. Duch and A. Arenas, Phys. Rev. E 72, 027104 (2005).
[13] J. Reichardt and S. Bornholdt, Phys. Rev. E 74, 016110+
(2006).
[14] R. Guimerà and L. A. Nunes Amaral, Nature 433, 895
(2005).
[15] M. E. J. Newman, Phys. Rev. E 74, 036104+ (2006).
[16] A. Clauset, M. E. J. Newman, and C. Moore, Phys. Rev.
E 70, 066111 (2004).
[17] V. D. Blondel, J.-L. Guillaume, R. Lambiotte, and
E. Lefebvre, J. Stat. Mech. 2008, P10008 (2008).
[18] A. Lancichinetti and S. Fortunato, Phys. Rev. E 80,
056117 (2009).
[19] V. A. Traag, P. Van Dooren, and Y. Nesterov, Phys.
Rev. E 84, 016114 (2011).
[20] M. Rosvall and C. T. Bergstrom, PLoS ONE 5, e8694
(2010).
[21] M. Rosvall and C. T. Bergstrom, PLoS ONE 6, e18209
(2011).
[22] P. Ronhovde and Z. Nussinov, Phys. Rev. E 81, 046114
(2010).

[23] T. S. Evans and R. Lambiotte, Phys. Rev. E 80, 016105
(2009).
[24] A. Lancichinetti, F. Radicchi, J. J. Ramasco, and S. Fortunato, PLoS ONE 6, e18961 (2011).
[25] V. A. Traag, G. Krings, and P. Van Dooren, Sci. Rep.
3, 2930 (2013).
[26] V. A. Traag, R. Aldecoa,
and J.-C. Delvenne,
arXiv:1503.00445 [physics, stat] (2015).
[27] A.-L. Barabási and R. Albert, Science 286, 509 (1999).
[28] S. Fortunato and M. Barthélemy, Proc. Natl. Acad. Sci.
USA 104, 36 (2007).
[29] R. Aldecoa and I. Marín, Sci. Rep. 3, 1060 (2013).
[30] A. Lancichinetti and S. Fortunato, Phys. Rev. E 84,
066122 (2011).
[31] A. Lancichinetti, S. Fortunato, and F. Radicchi, Phys.
Rev. E 78, 046110 (2008).
[32] J. Moody, Soc. Networks 23, 261 (2001).
[33] E. Cho, S. Myers, and J. Leskovec, in Proceedings of the
17th ACM SIGKDD . . . (ACM, 2011) pp. 1082–1090.
[34] B. Viswanath, A. Mislove, M. Cha, and K. P. Gummadi,
in Proceedings of the 2nd ACM workshop on Online social networks - WOSN ’09 (ACM Press, New York, New
York, USA, 2009) p. 37.
[35] C. F. Jure Leskovec, Jon Kleinberg, in ACM Transactions
on knowledge discovery from data (2006) pp. 1–40.
[36] J. Leskovec, K. J. Lang, A. Dasgupta, and M. W. Mahoney, in Proceeding of the 17th international conference on World Wide Web - WWW ’08 (2008) p. 695,
arXiv:arXiv:0810.1355v1.
[37] M. Granovetter, Am. J. Sociol. 78, 1360 (1973).
[38] J. Onnela, J. Saramäki, J. Hyvönen, G. Szabó, D. Lazer,
K. Kaski, J. Kertész, and A.-L. Barabási, Proc. Natl.
Acad. Sci. USA 104, 7332 (2007).
[39] A. Lancichinetti and S. Fortunato, Physical Review E
- Statistical, Nonlinear, and Soft Matter Physics 80, 1
(2009), arXiv:0904.3940.
[40] U. N. Raghavan, R. Albert, and S. Kumara, Phys. Rev.
E 76, 036106 (2007).
[41] R. P. Stanley, Enumerative Combinatorics: Volume 1,
2nd ed. (Cambridge University Press, Cambridge, NY,
2011).

10
Appendix A: Complexity in a clique

We here aim to determine the expected number of
moves in the random neighbor algorithm. We assume
it is always beneficial to move a node to a larger community. In other words, whenever we select a random node
i, and a random neighbor j, and the community σj of
the random neighbor is larger than the community σi of
node i, i.e. if |Vσj | ≥ |Vσi |, we will move the node.
Let us denote by fk the number of communities that
have size k
fk = |{c | |Vc | = k}|.

(A1)

Then gk = kfk denotes the number of nodes that belong to
Pna community of size k. Additionally, define
Fk = i=k fi the number of communities
that have size
Pn
k or larger. Similarly, define Gk = i=k gi the number of
nodes in communities that have size P
k or larger. Clearly
P
g
=
n
so
that
G
=
n.
Also,
k
1
k
k fk = r denotes
the number of communities. The probability to select
a node from a community of size k is then simply gnk .
Let us denote by Xcd the event of moving a node from a
community of size c to a community of size d. Then the
probability of Xcd is

gc gd

if c < d
n n
gc gc −c
Pr(Xcd ) = n n
(A2)
if c = d

0
if c > d
The probability
Pto move it from any community to any
other is then cd Pr(Xcd ). Alternatively, it is easy to
see that the probability to move to any other community
is Gkn−k (where we subtract k to make sure it moves to
another community, and not the same community). So,
overall, the probability we will move a node is then
Pr(move) =

n
X
gk Gk − k
n
n

(A3)

k=1

Similarly, the probability we will not move a node to
another community (i.e. we remain stuck in the same
partition) is then
n
X
gk n − Gk + k
Pr(not move) =
.
n
n

(A4)

k=1

We only reduce the number of communities if we move a
node from a community of size 1 of course. Hence, the
probability to reduce the number of communities by 1 is
then
X
g1 Gk − 1
Pr(
fk = r − 1) =
(A5)
n
n
i
Now it would be possible to construct a complete transition network from any of the partitions to other partitions. However, this becomes quickly intractable, and
rather difficult to solve.

Instead, we suggest to group partitions by the number
of communities. Then, we divide the process into different phases. The algorithm would be in phase i whenever
there are n−i+1 communities. In other words, in the first
phase there are n communities, and the next phase starts
whenever one of these nodes is put in another community.
In the penultimate phase, there are only two communities. Let us then denote by ti the number of moves during
phase i, and by t the total number of moves during the
whole process. We
Pwould like to examine E(t), which we
can write out as i E(ti ) by linearity of expectation.
The number of ways to partition a set of n nodes in
r sets can be denoted by pr (n), which is known as the
partition function in number theory [41]. This function
obeys the recursive identity
pr (n) = pr (n − r) + pr−1 (n − 1),

(A6)

since there are pr−1 (n − 1) partitions with at least one
community of size 1 and pr (n−r) partitions that all have
a community of size at least 2 (since we put r nodes in
each one of the r communities). We would then like to
know how many partitions there are that have s communities of size 1. Let us first define qk (n) to denote the
number of ways to partition n into k sets with at least one
community of size 1. Secondly, we need its counterpart
uk (n) which denotes the number of ways to partition n
into k sets without any community of size 1. Obviously
then pk (n) = qk (n) + uk (n). We can then derive the
recursion
qk (n) =

k−1
X

uk−r (n − r)

(A7)

pk−r (n − r) − qk−r (n − r)

(A8)

r=1

=

k−1
X
r=1

The reasoning is as follows. If there are r communities of
size 1, we should know how many partitions there are of
n − r nodes into k − r communities without using communities of size 1. Here q1 (1) = 1. More specifically, let
us denote by qk (n, r) the number of partitions that have
r communities of size 1 and in total k communities, using
Pk−1
n nodes. Then, obviously, qk (n) = r=1 qk (n, r). Moreover, qk (n, r) = uk−r (n − r) = pk−r (n − r) − qk−r (n − r).
The average probability to reduce the number of communities by 1 is then
X

X
Pr
fs = k − 1 |
fs = k
(A9)
=

k−1
X
r=1

=

k−1
X
r=1

qk (n, r) g1 G1 − 1
pk (n) n
n

(A10)

qk (n, r) n − r n − 1
pk (n)
n
n

(A11)

This expression is unfortunately not easy to evaluate analytically. Moreover, it incorrectly assumes that each partition is equally likely a priori, whereas we know that

11
a more uneven distribution of community sizes is more
likely due to the preferential attachment to the largest
community. However, the following upper bound is immediate
Pr

X

fs = k − 1 |

X

(A12)

In general E(ti ) can be calculated relatively straightforward as
E(ti ) =

1
Pr(reduce community by 1)

E(ti ) ≥

n
n
n−k+1n−1

(A14)

so that


fs = k ≤
n−k+1n−1
n
n

which using the bound in Eq. (A12) leads to

E(t) =

X

E(ti ) ≥

i

≈n

i=1

n
X
1
i=1

i

≈ O(n log n)
(A13)

n
X

n
n
n−i+1n−1

(A15)
(A16)
(A17)

