Distributed Graph Clustering using Modularity
and Map Equation ?

arXiv:1710.09605v2 [cs.DS] 22 Mar 2018

Michael Hamann, Ben Strasser, Dorothea Wagner, and Tim Zeitz
Institute of Theoretical Informatics, Karlsruhe Institute of Technology, Karlsruhe,
Germany; michael.hamann@kit.edu, academia@ben-strasser.net,
dorothea.wagner@kit.edu, and tim.zeitz@kit.edu

Abstract. We study large-scale, distributed graph clustering. Given an
undirected graph, our objective is to partition the nodes into disjoint sets
called clusters. A cluster should contain many internal edges while being
sparsely connected to other clusters. In the context of a social network, a
cluster could be a group of friends. Modularity and map equation are established formalizations of this internally-dense-externally-sparse principle. We present two versions of a simple distributed algorithm to optimize
both measures. They are based on Thrill, a distributed big data processing framework that implements an extended MapReduce model. The algorithms for the two measures, DSLM-Mod and DSLM-Map, differ only
slightly. Adapting them for similar quality measures is straight-forward.
We conduct an extensive experimental study on real-world graphs and on
synthetic graph clustering benchmark graphs with up to 68 billion edges.
Our algorithms are fast while detecting clusterings similar to those detected by other sequential, parallel and distributed clustering algorithms.
Compared to the distributed GossipMap algorithm, DSLM-Map needs
less memory and is up to an order of magnitude faster.

1

Introduction

Graph clustering is a well researched topic [8,10] and has many applications, such
as community detection in social networks where users can be modeled as nodes
and friendships as edges between them. These graphs can be huge and may not
fit into the main memory of a single machine. We therefore study distributed
extensions of established single machine clustering algorithms. This enables us
to efficiently compute clusterings in huge graphs.
We consider the problem of clustering a graph into disjoint clusters. While
there is no universally accepted definition of a good clustering, it is commonly
accepted that clusters should be internally densely and externally sparsely connected. Our algorithms optimize two established quality measures that formalize
this concept: modularity [19] and map equation [21]. Other community detection formalizations have been considered. For example, EgoLP [7] is a distributed
algorithm to find overlapping clusters.
?

This work was partially supported by the DFG under grants WA654/19-2 and
WA654/22-2. The authors acknowledge support by the state of Baden-Württemberg
through bwHPC.

1.1

Related Work

Existing distributed approaches follow one of two approaches.
The first is to partition the graph into a subgraph per machine. Each subgraph is then clustered independently on one machine. Then, all clusters are
contracted and the resulting coarser graph is clustered on a single machine. This
assumes it fits in the memory of a single machine. In [25], for the partitioning, the
input node ID range is chunked into equally sized parts. This can work well, but
is problematic if input node IDs do not reflect the graph structure. In [23], the
input graph is partitioned using the non-distributed, parallel graph partitioning
algorithm ParMETIS [14]. While this is independent of node IDs, it requires
that the graph fits into the memory of one machine for the partitioning.
The second approach consists of distributing the clustering algorithm itself.
Using MPI, [20] have introduced a distributed extension of the Louvain algorithm [5]. Similarly, [18] have presented an algorithm that uses the GraphX
framework. Another algorithm named GossipMap is presented in [3] which uses
the GraphLab framework. Our algorithms also use this second approach.
All of these related algorithms heuristically optimize modularity except GossipMap, which optimizes the map equation.
1.2

Contribution

We propose two distributed graph clustering algorithms, DSLM-Mod and DSLMMap, that optimize modularity and map equation, respectively. Our algorithms
are the first graph clustering algorithms based on Thrill [4], a distributed big data
processing framework written in C++ that implements an extended MapReduce
model. Our algorithms are easy to extend for optimizing different density-based
quality measures. To evaluate the clustering quality, we compare against ground
truth communities on synthetic LFR [16] graph clustering benchmark graphs
with up to 68 billion edges. Even for these graphs, 32 hosts of a compute cluster
are enough. Our results show that our algorithms scale well and DSLM-Map is
better at recovering the ground truth than the sequential Infomap algorithm [21].
On real-world graphs, we show that our algorithms find clusterings similar to
those found by sequential algorithms. We evaluate the actual similarity and not
just quality scores, where a very small change of the score can result in very
different clusterings [11].
Similar to most related work, we make implicit assumptions on the structure
of the graph. We assume that all edges incident to nodes in a single cluster fit
into the memory of a single compute node. In practice, this is only a limitation
when a network has huge clusters. In many scenarios like social networks or web
graphs, this is no limitation as cluster sizes are not that huge. Our algorithms can
be modified to avoid these restrictions, but this would increase running times.
Outline. In the following we introduce our notation and present the quality
measures we optimize. We also give a brief introduction to Thrill. In Section 3,
we present our algorithms. In Section 4 we present our experimental results. We
conclude in Section 5.

2

Preliminaries

Conceptually, our algorithms work on undirected graphs. However, we represent
all graphs G = (V, E, ω) as symmetric, directed, weighted graphs of |V | = n
nodes and |E| = m edges. The pair (u, v) ∈ E represents the edge from u to v.
Unless stated otherwise, there are no multi-edges. We describe our algorithms
for weighted graphs. As our input graphs are unweighted, we set ω(u, v) = 1 for
every edge (u, v) ∈ E.
A cluster C is a node subset. A clustering C is a set of clusters such that each
node is part of exactly one cluster.
The weighted degree deg(x) of a node x is the sum over the weights of all
outgoing edges (x, y) of x. The weight of the loop edge is counted twice. The
volume vol(C) of a set of nodes C is the sum of their weighted degrees. The cut
cut(C, D) between two sets of nodes C, D is the sum of the weights of all edges
(x, y) such that x ∈ C and y ∈ D. As a simplification, we write cut(v, C) for
cut({v}, C), cut(C) := cut(C, V \ C) for the cut of C with the rest of the graph.
Many approaches exist to formalize the quality of a clustering. In this work,
we study two popular ones: modularity [19] and map equation [21]. Higher modularity and lower map equation values indicate better clusterings. However, sometimes higher modularity values can also be achieved by merging small but actually clearly distinct clusters. This effect is called resolution limit [9]. For the map
equation, this effect is much weaker [15]. Optimizing modularity is NP-hard [6]
but it can be optimized heuristically in practice [5]. Only heuristic map equation
optimization algorithms are known to us [21].
To compare clusterings, either with ground truth communities or with a
clustering calculated using a different algorithm, we use the adjusted rand index
(ARI) [13]. The maximum value of 1 indicates that both clusterings are equal.
ARI is normalized such that when one of the two clusterings is random, its
expected value is 0. It can also be negative.
2.1

Thrill

Thrill [4] is a distributed C++ big data processing framework. It can distribute
the program execution over multiple machines and threads within a machine.
Each thread is called worker. Every worker executes the same program.
If there is not enough main memory available, Thrill can use local storage
such as an SSD as external memory (EM) to store parts of the processed data.
Data is maintained in distributed immutable arrays (DIA). Distributed Thrill
operations are applied to the DIAs. For example, Thrill contains a sort operation,
whose input is a DIA and whose output is a new sorted DIA. Similarly, the
zip operation combines two DIAs of the same length into one DIA where each
element is a pair of the two original elements.
Thrill also supports DIAs with elements of non-uniform size, as long as each
element fits into the memory of a worker. This allows elements to be arrays.
Apart from zip and sort, we use the following operations: The map operation
applies a function to each element of a DIA. The return values are the elements

of the new DIA. Flatmap is similar, but the function may emit 0, 1, or more
elements. This is similar to the map operation in the original MapReduce model.
A DIA can be aggregated by a key component. All elements with the same
key are combined and put into an array. This is similar to the reduce operation
in the original MapReduce model. An aggregation is much more efficient if the
keys are consecutive integers. In that case, the result is also automatically sorted
by the keys. We use this optimized variant for all aggregations that are based
on node IDs.

3

Algorithm

The basis of our algorithm is the Louvain algorithm [5], a fast algorithm for
modularity optimization that delivers high-quality results. The original Infomap
algorithm proposed for optimizing the map equation [21] is based on the same
scheme, but introduces additional steps to improve the quality.
Initially, every node is in its own cluster. This is called a singleton clustering.
In the local moving phase, the Louvain algorithm works in rounds. In each
round, it iterates in a random order over all nodes v. For every v, it considers v’s
current cluster and all clusters C such that there is an edge from v to a node of
C. For all these clusters, the difference in quality score ∆v,C is computed. If the
clustering quality can be improved, v is moved into a cluster that maximizes it,
resolving ties uniformly at random. The local moving phase stops when no node
is moved in a round or a maximum number of rounds is reached.
After the local moving phase, the contraction phase starts. All nodes inside
a cluster are merged into a single node. The weights of all edges from a cluster
C to D are summed up and added as an edge from the node representing C to
the node representing D. All edge weights within a cluster are summed up and
added as a loop edge. The contraction does not change the quality score. On the
contracted graph, the algorithm is applied recursively. It terminates when the
contraction phase is entered and the clustering is still the singleton clustering.
3.1

Distributed Synchronous Local Moving (DSLM)

In local moving, the i-th move depends on the clustering after the first i − 1
moves are executed. This data dependency makes the parallelization difficult.
We therefore split a round into sub-rounds. Every node picks a random subround in which it is active. In the i-th sub-round, all active nodes are moved
synchronously and in parallel with respect to the clustering after the (i − 1)-th
sub-round. For the first sub-round, this is with respect to the initial clustering.
We call this scheme synchronous local moving. For our distributed synchronous
local moving, a global hash function h maps a tuple of a node ID v, the number
of completed rounds and a global seed onto the sub-round rv in which v is active.
We represent a graph and its clustering as two DIAs. They have length n
and are stored sorted by their first item, the node ID v. The graph DIA stores
triples (v, hui i, hwi i), where hui i and hwi i are equally-sized arrays. For every i,

there is an edge (v, ui ) with weight wi . The clustering DIA of pairs (v, C) stores
for every node v its cluster ID C.
In DSLM, a sub-round is composed of a bidding and a compare step. In the
bidding step, the clusters place bids for active nodes. In the compare step, every
active node compares its bids and becomes part of the cluster with the best bid.
To allow a node v to compute the change in modularity or map equation
when joining the neighboring cluster C, each bid contains: (a) volume vol(C \ v),
(b) cut weight cut(v, C \ v) between C \ v and v, and (c) cut weight cut(C)
between C and the remaining graph.
The bidding step starts by zipping the clustering DIA and graph DIA and
aggregating this zipped DIA by cluster ID. The result is a DIA with one large
element per cluster C. Each element contains all nodes in the cluster C and
the neighborhoods of these nodes. This allows us to compute the measures (a),
(b), and (c) using a non-distributed algorithm inside a worker. Using a flatmap,
our algorithm emits for every cluster C bids for all active nodes inside C and
adjacent to C. It can determine which nodes are active as the hash function h is
globally known. The generated bid DIA consists of quintuples (C, v, vol(C \ v),
cut(v, C \ v), cut(C \ v)). Each quintuple is a bid of cluster C for active node v.
The compare step aggregates the bid DIA by node v. After the aggregation,
the result is zipped with the graph DIA to obtain the nodes’ degree and loop
edge weight. In a map operation, we use this information to compute for every
active node the best bid and return the according cluster. We retrieve the old
cluster ID for non-active nodes by zipping with the original clustering DIA. This
yields the updated clustering DIA, which is the input of the next sub-round.
Implementation Details and Optimizations. If modularity is optimized,
our algorithm can be improved in two ways. First, we can omit the cut weight
as it is only needed for the map equation. Second, we can compare bids without
knowing the current cluster. This allows us to use a pairwise reduction instead
of one that first waits for all elements. As we still need the node’s degree, each
worker stores the degree of the nodes that are reduced on that worker in a plain
array. This is possible because we know on which worker each node will end up.
3.2

Distributed Contraction and Unpacking

The contraction is performed in three steps: (a) obtain consecutive cluster IDs,
(b) replace all node IDs by the cluster IDs, and (c) combine multi-edges.
We first zip the graph and clustering DIAs and aggregate them by cluster
ID. To get consecutive cluster IDs, we replace them by the element positions.
From the result, which contains tuples (C, hvi , huj i, hwj ii), we derive two DIAs.
The first DIA is a new clustering DIA with consecutive cluster IDs. To obtain
it, we first drop the neighborhood information. We store this intermediate DIA
(C, hvi i) for the unpacking phase. Then, we expand it into pairs (vi , C) of node
and cluster ID using a flatmap operation and sort by node IDs.
The second DIA is the contracted graph DIA. To obtain it, we first emit a
triple (Cu , v, w) for every node v that is a neighbor of a node in Cu in a flatmap
operation. The weight w is the sum of all edge weights from nodes in Cu to v. We

aggregate this DIA by v, zip it with the new clustering DIA and replace v by v’s
cluster ID Cv . We then aggregate by Cv to obtain pairs (Cv , hCu,i , wi i) containing
the neighboring clusters Cu,i for every Cv . Finally, we sum up the weights wi for
the same neighboring cluster for every cluster Cv in a map operation.
To unpack the clustering calculated in a level, we zip the clustering DIA
(v, Cv ) with the intermediate clustering DIA (v, hvi i) of a cluster v and its nodes
hvi i from the previous contraction phase. A flatmap operation assigns the cluster
ID Cv of the contracted node to all original nodes u ∈ hvi i, resulting in a
clustering DIA (u, Cu ). After sorting it by node, it is returned to the next level.

4

Experiments

In this section, we present an experimental evaluation of our algorithm DSLM1 .
The source code of our implementation is publicly available on GitHub2 . We first
describe our experimental setup. Then, we present weak scaling experiments to
evaluate the running time, compare the quality on LFR benchmark graphs [16]
and evaluate the performance on established real-world benchmark data.
All running time experiments were performed on a compute cluster. Each
compute node has two 14-core Intel Xeon E5-2660 v4 processors (Broadwell)
with a default frequency of 2 GHz, 128 GiB RAM and 480 GiB SSD. They are
connected by an InfiniBand 4X FDR Interconnect. We use the TCP back-end of
Thrill due to problems with the combination of multithreading and OpenMPI.
We use Thrill’s default parameters, except for the block size, which determines
the size of data packages sent between the hosts. Preliminary experiments found
that a block size of 128 KiB instead of the default 2 MiB yields the best results.
For our algorithms, we use four sub-rounds as in a preliminary study [24].
Using less results in problems with the convergence. Using more does not significantly improve quality but increases running time. In each local moving phase, we
perform at most eight rounds. All experiments were performed with 16 threads
per host.
Apart from DSLM-Mod and DSLM-Map that optimize modularity and map
equation, we also evaluate a variant DSLM-Mod w/o Cont. that stops after
the first local moving phase. This significantly decreases the running time and
surprisingly also improves the quality on synthetic instances. We evaluate this
behavior in more detail in Section 4.2.
For modularity, we compare against our own implementation of the sequential Louvain algorithm [5] and the shared-memory parallel PLM [22]. For map
equation, we compare against the sequential Infomap [21], the shared-memory
parallel RelaxMap [2] and the distributed GossipMap [3] implementations.
In a preprocessing step, we remove degree zero nodes, make the ID space
consecutive and randomize the node order. This ensures that our algorithms are
independent of input order and improves load balancing.
1

2

This paper only covers parts of our experiments. Under https://github.com/kit-algo/
distributed clustering thrill evaluation you can find additional analyses, links to our
raw data and information on how to explore our data on your own.
https://github.com/kit-algo/distributed clustering thrill

DSLM-Mod
DSLM-Mod w/o Cont.
DSLM-Map

1.0

ARI

0.8
0.6
0.4
0.2

Hosts / Graph size factor

32

16

8

4

2

0.0
1

Running time [s]

3500
3000
2500
2000
1500
1000
500
0

106

107
108
Graph size (# Nodes)

Fig. 1. Weak scaling: running time of our distributed algorithms and ARI with ground
truth. The DSLM-Mod w/o Cont. ARI line is hidden by the DSLM-Map line.

All experiments were repeated 10 times with different random seeds. We
report averaged results and standard deviation where possible as error bars.
During the experiments, the meltdown and spectre vulnerabilities became
public and performance impacting patches were applied to the machines. Rerunning some experiments showed a slowdown of up to 1.6 for runs with 32 hosts
but no significant slowdown for runs with a single host. We did not have the resources to rerun all experiments. At this point, most distributed algorithm runs
were already done. About half of the GossipMap runs on the real world graphs
were performed afterwards and are excluded from the running time reports. All
runs for non-distributed algorithms were performed with patches applied.
Synthetic Instance Generation. Our synthetic test data is generated using the established LFR benchmark generation scheme [16]. To generate graphs
of up to 512 million nodes and 67.6 billion (undirected) edges in a reasonable
time, we use the external memory LFR generator implementation of [12].
LFR benchmark graphs feature a ground truth clustering. Node degrees and
cluster sizes are drawn from power law distributions. The mixing parameter µ
determines the fraction of edges that are between different clusters. For details,
we refer the reader to the original description [16]. We set a minimum degree of
50 and a maximum degree of 10 000 with a power law exponent of 2. This leads
to an average degree of approximately 264. For the communities, we set 50 as
minimum and 12 000 as maximum size with a power law exponent of 1. Unless
otherwise noted, we set the mixing parameter µ to 0.4.
4.1

Weak Scaling

For the weak scaling experiments, we use LFR graphs with 16, 32, 64, 128, 256
and 512 million nodes. We cluster them on 1, 2, 4, 8, 16, and 32 hosts respectively. The left part of Figure 1 shows the running time of our algorithms. Our
algorithms utilize almost the entire available RAM. GossipMap is less memoryefficient and was unable to cluster the graphs in these configurations and crashed.
With a linear time algorithm and perfect scaling, we would expect that the
running time remains constant as we increase graph size and the number of

1.0

0.8

0.8

0.6

0.6
ARI

ARI

1.0

0.4
0.2
0.0
0.1

Seq. Louvain
PLM
DSLM-Mod
DSLM-Mod w/o Cont.
0.2

0.3

0.4

0.5
mu

0.4
0.2
0.0

0.6

0.7

0.8

0.9

0.1

Seq. Infomap
RelaxMap
GossipMap
DSLM-Map
0.2

0.3

0.4

0.5
mu

0.6

0.7

0.8

0.9

Fig. 2. Adjusted rand index with ground truth for µ ∈ [0.1, 0.9].

nodes. For the variant of DSLM-Mod w/o Cont., the running time actually does
not increase much. The running time of the full DSLM-Mod and DSLM-Map
algorithms increases approximately linearly though as the number of hosts is
scaled exponentially. The reason for this is that LFR graphs get very dense
during contraction and thus in particular larger graphs still have a significant
amount of edges after the contraction. Also, DSLM-Map is approximately a
factor of two slower than DSLM-Mod. This is expected as the optimizations
described at the end of Section 3.1 are not applicable to DSLM-Map.
4.2

Quality

First, we evaluate the quality of the clusterings obtained in the weak scaling
experiment. The right part of Figure 1 depicts the similarities of the clusterings found by our algorithms and the ground truth. From the plot, we observe
that DSLM-Map finds a clustering very close to the ground truth. DSLM-Mod
w/o Cont. achieves similar results. Unfortunately, DSLM-Mod fails to find a
clustering similar to the ground truth on the larger instances. This shows that
after the contraction, clusters are merged that should not be merged. To verify
if the worse results of DSLM-Mod are due to the resolution limit, we started a
sequential Louvain algorithm on a graph where we contracted the ground truth.
This algorithm indeed merges clusters, showing that the resolution limit is relevant here. However, the thereby detected clusters are much more similar to the
ground truth than those detected by DSLM-Mod and even the ground truth
alone has higher modularity scores than those found by DSLM-Mod.
We also use smaller LFR graphs with 1M nodes and varying mixing parameter to compare the quality of the communities found by all compared algorithms.
Figure 2 shows the adjusted rand index of the detected clusterings with the
ground truth. DSLM-Mod w/o Cont. and DSLM-Map outperform all other algorithms by a significant margin. On average, DSLM-Mod still outperforms the
other modularity-optimizing algorithms. For all values of µ, the ground truth
has a higher modularity score than the clustering found by the modularityoptimizing algorithms. Merging clusters of the ground truth again improves the
modularity score but leads to clusterings that still have an ARI of above 0.99

LiveJournal
4M
34M 8
99
25
31
Orkut
3M 117M 8 170
53
47
uk-2002
18M 261M 8 572 142
46
Friendster
66M 1806M 16 6002 1755 1047
uk-2007-05 105M 3302M 16 7993 2520 151

14
34
22
742
106

DSLM-Map

GossipMap

RelaxMap

Infomap

DSLM-Mod
DSLM-Mod
w/o Cont.

PLM

Louvain

# Hosts

# Edges

# Nodes

Table 1. Running time in seconds of the different algorithms on the real-world graphs.

1329 163
372
49
2405 415
700
84
6656 240
682
52
oom oom 13743 1161
oom oom 4211 214

for µ < 0.9. With the algorithms optimizing map equation, the situation is similar. For µ < 0.8, the ground truth, which DSLM-Map consistently finds, has a
better map equation score than the clusterings found by all other algorithms.
For µ ≥ 0.8, a singleton clustering yields a better map equation score than the
ground truth clustering. GossipMap finds neither good map equation scores nor
the ground truth for µ > 0.4.
Overall, for these LFR benchmark graphs, DSLM seems to be superior to
sequential local moving. Examining sequential local moving algorithms, we noticed that high-degree nodes attract many nodes in the first local moving round.
After a few nodes join their cluster, many others follow. In contrast to that, with
DLSM, 25% of the nodes can join the cluster of another node before any cluster
sizes come into play. Apparently, this avoids such accumulation effects.
4.3

Real-World Graphs

To assess whether our results on LFR benchmark graphs are also true for realworld graphs, we perform experiments on a set of different real-world graphs.
From the Stanford Large Network Dataset Collection [17], we include three social networks (com-LiveJournal, com-Orkut and com-Friendster). From the 10th
DIMACS Implementation challenge [1], we include two web graphs where nodes
represent URLs and edges links between them (uk-2002 and uk-2007-05).
We clustered these graphs both with the sequential baseline algorithms and
our distributed algorithms. Table 1 depicts the sizes of the graphs, the number of
hosts we used for the distributed algorithms and the running times in seconds.
RelaxMap and GossipMap use the directed version of the map equation that
includes a PageRank approximation as preprocessing step. To allow for a fair
comparison, we only report the running time of the actual clustering step after
this preprocessing. As three GossipMap runs on uk-2007-05 crashed, there are
less samples. Unfortunately, both the original Infomap implementation and RelaxMap were not able to cluster all instances. On the two largest graphs, 128 GB
of RAM were not enough memory (oom).
With 8 or 16 hosts, our distributed algorithms are almost always faster than
the sequential and shared-memory parallel algorithms. Note that due to the

DSLM-Map

GossipMap

RelaxMap

0.500
0.555
0.663
0.575
0.823

Directed
Infomap

0.570
0.600
0.712
0.619
0.882

Infomap

DSLM-Mod

0.568
0.592
0.717
0.609
0.875

DSLM-Mod
w/o Cont.

PLM

LiveJournal
Orkut
uk-2002
Friendster
uk-2007-05

Louvain

Table 2. Similarities in terms of adjusted rand index with baseline clusterings calculated by the respective sequential algorithm.

0.170 0.977 0.974 0.373 0.780 0.767
0.212 0.930 0.935 0.819 0.498 0.828
0.047 0.984 0.984 0.928 0.698 0.968
0.365 oom oom oom
0.012
0.281 oom oom oom
0.131

randomized node order, PLM is slower in our experiments than reported in [22].
DSLM-Map with 8 hosts is more than a factor of 5, for uk-2002 even a factor of
20 faster than RelaxMap and also a factor of 10 faster than GossipMap. DSLMMod is faster than DSLM-Map, but the difference is less pronounced than in the
weak scaling experiments. This shows the advantage of our algorithmic scheme
in combination with the efficient Thrill framework.
In Table 2, we compare the detected clusterings to 5 different baseline clusterings found by Louvain for algorithms optimizing modularity and Infomap for
algorithms optimizing the map equation. For the latter, only GossipMap and
DSLM-Map were able to cluster the two largest graphs, so we compare them directly. The columns “Louvain” and “Infomap” compare runs with different seeds
to the baseline clusterings. We observe that the baseline algorithms do not consistently find the same clustering. Especially, the Louvain algorithm finds vastly
different clusterings depending on the random seed. Further, on social networks
the adjusted rand indices are smaller than on web graphs. This is probably due
to web graphs having a more pronounced community structure. PLM produces
relatively stable clusterings due to less randomization. Therefore, on Friendster
and uk-2007-05, it finds clusterings that match the baseline clusterings even better than Louvain. DSLM-Mod produces clusterings that are less similar, but still
much more similar than DSLM-Mod w/o Cont., which produces vastly different
clusterings. This shows that DSLM-Mod w/o Cont., which performed really well
on the LFR benchmark graphs, is unsuited for real-world graphs.
Infomap is in general much more stable than Louvain with an adjusted rand
index close to 1. DSLM-Map produces very similar clusterings on uk-2002. On
the LiveJournal and Orkut graphs, the clusterings are slightly less similar. Quite
interestingly, the parallel RelaxMap and the distributed GossipMap algorithms
produce significantly different clusterings in particular for the two social networks. To understand if this is the case because they optimize the map equation
for directed networks, we also run Infomap with the directed version. But, as the
column “Directed Infomap” shows, the results are very similar to the undirected
Infomap algorithm. We conclude that RelaxMap and GossipMap indeed fail to
find similar clusterings reliably.

5

Conclusion

We have introduced two distributed graph clustering algorithms, DSLM-Mod
and DSLM-Map, that optimize modularity and map equation, respectively. They
are based on the Thrill framework. In an extensive experimental evaluation, we
have shown that on LFR benchmark graphs, DSLM-Map achieves excellent results, even better than the sequential Infomap algorithm. For DSLM-Mod, we
also evaluate a variant without contraction which has great performance on LFR
benchmark graphs. The full DSLM-Mod algorithm with contraction fails to recover the ground truth on LFR benchmark graphs – similar to the sequential
Louvain algorithm – but significantly outperforms the variant without contraction on real-world graphs. On real-world graphs, both distributed algorithms find
slightly different clusterings than the sequential algorithms. Compared to GossipMap, the state-of-the-art distributed algorithm for optimizing map equation,
DSLM-Map is up to an order of magnitude faster while detecting clusterings
that are more similar to the results of the sequential implementation.
In the first local moving phase, synchronous local moving seems to be superior to sequential local moving. Further research is needed to see if this is a
phenomenon particular to the LFR graphs we studied or if synchronous local
moving could be a way to avoid local maxima when optimizing such quality
functions. After the contraction, more careful local moving strategies should be
developed though to avoid the problems we see in particular on LFR graphs.
Therefore, further research on different local moving strategies seems to be a
promising direction.

References
1. Bader, D.A., Meyerhenke, H., Sanders, P., Schulz, C., Kappes, A., Wagner, D.:
Benchmarking for graph clustering and partitioning. In: Rokne, J., Alhajj, R. (eds.)
Encyclopedia of Social Network Analysis and Mining, pp. 73–82. Springer (2013)
2. Bae, S., Halperin, D., West, J.D., Rosvall, M., Howe, B.: Scalable and Efficient
Flow-Based Community Detection for Large-Scale Graph Analysis. ACM Transactions on Knowledge Discovery from Data 11(3), 32:1–32:30 (2017)
3. Bae, S., Howe, B.: GossipMap: a distributed community detection algorithm for
billion-edge directed graphs. In: Proceedings of the International Conference for
High Performance Computing, Networking, Storage and Analysis. pp. 27:1–27:12.
ACM Press (2015)
4. Bingmann, T., Axtmann, M., Jöbstel, E., Lamm, S., Nguyen, H.C., Noe, A.,
Schlag, S., Stumpp, M., Sturm, T., Sanders, P.: Thrill: High-Performance Algorithmic Distributed Batch Data Processing with C++. Tech. rep., arXiv (2016),
arXiv:1608.05634
5. Blondel, V., Guillaume, J.L., Lambiotte, R., Lefebvre, E.: Fast unfolding of communities in large networks. Journal of Statistical Mechanics: Theory and Experiment
2008(10) (2008)
6. Brandes, U., Delling, D., Gaertler, M., Görke, R., Höfer, M., Nikoloski, Z., Wagner, D.: On Modularity Clustering. IEEE Transactions on Knowledge and Data
Engineering 20(2), 172–188 (February 2008)

7. Buzun, N., Korshunov, A., Avanesov, V., Filonenko, I., Kozlov, I., Turdakov, D.,
Kim, H.: EgoLP: Fast and Distributed Community Detection in Billion-Node Social
Networks. In: Proceedings of the 2014 IEEE International Conference on Data
Mining Workshops. pp. 533–540. IEEE Computer Society (2014)
8. Fortunato, S.: Community detection in graphs. Physics Reports 486(3–5) (2010)
9. Fortunato, S., Barthélemy, M.: Resolution limit in community detection. Proceedings of the National Academy of Science of the United States of America 104(1),
36–41 (2007)
10. Fortunato, S., Hric, D.: Community detection in networks: A user guide. Physics
Reports 659, 1–44 (2016)
11. Good, B.H., de Montjoye, Y.A., Clauset, A.: Performance of modularity maximization in practical contexts. Physical Review E 81(046106) (2010)
12. Hamann, M., Meyer, U., Penschuck, M., Wagner, D.: I/O-efficient Generation of
Massive Graphs Following the LFR Benchmark. In: Proceedings of the 19th Meeting on Algorithm Engineering and Experiments (ALENEX’17). SIAM (2017)
13. Hubert, L., Arabie, P.: Comparing partitions. Journal of Classification 2(1), 193–
218 (December 1985)
14. Karypis, G., Kumar, V.: A Parallel Algorithm for Multilevel Graph Partitioning
and Sparse Matrix Ordering. Journal of Parallel and Distributed Computing 48,
71–95 (January 1998)
15. Kawamoto, T., Rosvall, M.: Estimating the resolution limit of the map equation
in community detection. Physical Review E 91, 012809 (2015)
16. Lancichinetti, A., Fortunato, S., Radicchi, F.: Benchmark graphs for testing community detection algorithms. Physical Review E 78(4), 046110 (October 2008)
17. Leskovec, J., Krevl, A.: SNAP Datasets: Stanford Large Network Dataset Collection (June 2014), http://snap.stanford.edu/data
18. Ling, X., Yang, J., Wang, D., Chen, J., Li, L.: Fast Community Detection in
Large Weighted Networks Using GraphX in the Cloud. In: 18th IEEE International
Conference on High Performance Computing and Communications. pp. 1–8. IEEE
(2016)
19. Newman, M.E.J., Girvan, M.: Finding and evaluating community structure in networks. Physical Review E 69(026113), 1–16 (2004)
20. Que, X., Checconi, F., Petrini, F., Wang, T., Yu, W.: Lightning-fast community
detection in social media: A scalable implementation of the louvain algorithm.
Tech. rep., Department of Computer Science and Software Engineering, Auburn
University (2013), tech. Rep. AU-CSSE-PASL/13-TR01
21. Rosvall, M., Axelsson, D., Bergstrom, C.T.: The map equation. The European
Physical Journal Special Topics 178(1), 13–23 (2009)
22. Staudt, C., Meyerhenke, H.: Engineering Parallel Algorithms for Community Detection in Massive Networks. IEEE Transactions on Parallel and Distributed Systems 27(1), 171–184 (2016)
23. Wickramaarachchi, C., Frincu, M., Small, P., Prasanna, V.K.: Fast parallel algorithm for unfolding of communities in large graphs. In: Proceedings of the 2014
IEEE High Performance Extreme Computing Conference. pp. 1–6. IEEE (2014)
24. Zeitz, T.: Engineering Distributed Graph Clustering using MapReduce. Master’s
thesis, Karlsruhe Institute of Technology (2017)
25. Zeng, J., Yu, H.: A study of graph partitioning schemes for parallel graph community detection. Parallel Computing 58, 131–139 (2016)

