[]Katharina<EMAIL_ADDRESS>
# LazyFox: Fast and parallelized overlapping community detection in large
graphs

Tim Garrels  Hasso Plattner Institute, Digital Engineering Faculty, University
of Potsdam, Prof.-Dr.-Helmert Str. 2-3, 14482 Potsdam, Germany  Athar
Khodabakhsh  Hasso Plattner Institute, Digital Engineering Faculty, University
of Potsdam, Prof.-Dr.-Helmert Str. 2-3, 14482 Potsdam, Germany  Bernhard Y.
Renard  Hasso Plattner Institute, Digital Engineering Faculty, University of
Potsdam, Prof.-Dr.-Helmert Str. 2-3, 14482 Potsdam, Germany  Department of
Mathematics and Computer Science, Free University Berlin, Takustraße 9, 14195
Berlin, Germany  Katharina Baum  Hasso Plattner Institute, Digital Engineering
Faculty, University of Potsdam, Prof.-Dr.-Helmert Str. 2-3, 14482 Potsdam,
Germany

###### Abstract

The detection of communities in graph datasets provides insight about a
graph’s underlying structure and is an important tool for various domains such
as social sciences, marketing, traffic forecast, and drug discovery. While
most existing algorithms provide fast approaches for community detection,
their results usually contain strictly separated communities. However, most
datasets would semantically allow for or even require overlapping communities
that can only be determined at much higher computational cost. We build on an
efficient algorithm, Fox, that detects such overlapping communities. Fox
measures the closeness of a node to a community by approximating the count of
triangles which that node forms with that community. We propose LazyFox, a
multi-threaded version of the Fox algorithm, which provides even faster
detection without an impact on community quality. This allows for the analyses
of significantly larger and more complex datasets. LazyFox enables overlapping
community detection on complex graph datasets with millions of nodes and
billions of edges in days instead of weeks. As part of this work, LazyFox’s
implementation was published and is available as a tool under an MIT licence
at https://github.com/TimGarrels/LazyFox.

## Introduction & Related Work

Graphs, also called networks, are present in many fields as they capture the
interaction of entities as edges between nodes representing those entities.
Communities (or clusters, or modules) are considered to be important network
structures as they describe functionally similar groups within networks. The
identification of such groups is relevant in various domains such as biology
(Barabasi and Oltvai,, 2004; Regan et al.,, 2002; Boccaletti et al.,, 2006;
Guimerà and Amaral,, 2005; Ahn et al.,, 2010), medicine (Barabasi et al.,,
2011; Gavin et al.,, 2006) and technical infrastructure (Regan and Barabasi,,
2003; Guimerà et al.,, 2005). In social networks, communities can identify
common interest groups or friend circles (Mcauley and Leskovec,, 2014). In
drug research, new, targetable proteins can be discovered by clustering
proteins into functionality groups (Ma et al.,, 2019). Similar products of an
online shop can be grouped together to derive product recommendations
(Basuchowdhuri et al.,, 2014).

While community itself is a term whose precise definition is highly context
dependent (Kelley et al.,, 2012), various algorithms have been developed to
detect such structures (Fortunato,, 2010). In this work, we focus on
communities of bond. These are communities where the membership of a community
is based on the relation to other members – their connectivity in the network
– rather than an affinity to the identity of that group as a whole. This
naturally leads to more interconnections between group members (Ren et al.,,
2007). Algorithms detecting such communities typically exploit this property
by optimizing communities so that nodes of one group are more densely
connected with each other than with nodes outside of that group.

### Disjoint Community Detection

Disjoint communities capture structural node clusters within a network where
each node belongs to exactly one community. While algorithms based on label
propagation (Raghavan et al.,, 2007), stochastic blockmodels (Hofman and
Wiggins,, 2008; Wang and Wong,, 1987) and game theory (Bu et al.,, 2017) for
disjoint community detection exist, the most common approach is to define a
metric that measures desired structural properties of a community
(Lancichinetti et al.,, 2011; Yang and Leskovec,, 2012; Newman,, 2006; Prat-
Pérez et al.,, 2012). By choosing communities that increase the metric over
communities that decrease it, the communities are optimized to display that
structural property. This way a clear community definition (groups of nodes
that result in the highest value of the metric) is created and detected
communities are to some degree controllable in their structure.

### Overlapping Community Detection

Most approaches identify communities in such a way that each node can belong
to only one community. While disjoint communities yield valuable information,
most real world datasets contain functional groups that are overlapping (Reid
et al.,, 2011; Lancichinetti et al.,, 2009). People can belong to multiple
social circles, proteins can have various biological functions or be target of
multiple drugs, and products rarely fall into exactly one category. Therefore,
traditional community detection algorithms have been adapted and new
algorithms have been proposed to detect overlapping communities (Fortunato,,
2010). However, overlapping community detection is a computationally more
expensive problem than regular (disjoint) community detection. Long runtimes
of days or even weeks make community detection unfeasible in large datasets,
which is especially true for overlapping community detection (Lancichinetti
and Fortunato,, 2009; Danon et al.,, 2005). This limits the usability of most
algorithms to smaller sized networks with edge counts in the lower millions.

Algorithms which detect overlapping communities can use other approaches than
disjoint community detection algorithms such as clique expansion (Lee et al.,,
2010; Palla et al.,, 2005), matrix factorization (Yang and Leskovec,, 2013;
Psorakis et al.,, 2011) and link clustering (Shi et al.,, 2013; Ahn et al.,,
2010; Evans and Lambiotte,, 2009). Some approaches also propose post-
processing steps to create overlapping communities from pre-existing disjoint
communities (Chakraborty,, 2015).

Moreover, approaches that have been proposed to detect disjoint communities
can also be adjusted to directly yield overlapping communities. Label
propagation based algorithms can allow nodes to hold multiple labels at the
same time, thereby creating overlapping communities (Xie and Szymanski,, 2012;
Gregory,, 2009). Stochastic blockmodels can support mixed memberships (Airoldi
et al.,, 2007; Gopalan and Blei,, 2013). And if an algorithm is based on the
optimization of a metric measuring structural properties, allowing nodes to
join multiple communities during the optimization can also change the result
from disjoint to overlapping communities (Lancichinetti et al.,, 2009).

### Enabling Large Scale Community Detection

Large scale datasets pose a challenge for many community detection algorithms
as their runtime increases drastically (Lancichinetti and Fortunato,, 2009;
Danon et al.,, 2005). Various approaches can be used to improve runtime and
enable the use of community detection algorithms on large datasets.
Parallelization can leverage modern multi-core CPUs, and algorithms with
independent computation steps can profit from parallelization directly (Liu
and Chamberlain,, 2018). Other algorithms cannot be parallelized without
logical changes, however, small alterations often do not influence the results
substantially (Prat-Pérez et al.,, 2014). Such parallelized approaches can
also be distributed to a multi-machine computing cluster, enabling the use of
even more computational resources (Saltz et al.,, 2015). Finally, algorithms
relying on metric optimization can also be improved in runtime by replacing
the metric with an estimator. This reduces computational effort and speeds up
the community detection.

##### Weighted Community Clustering Score

The Weighted Community Clustering ($WCC$) score (Prat-Pérez et al.,, 2012) is
a metric that has been successfully used to detect communities (Saltz et al.,,
2015; Song et al.,, 2015; Prat-Pérez et al.,, 2014). It measures structural
closeness by counting the number of triangles a node forms with a community to
determine the membership of that node to that community. Thereby, it is
closely related to the general concept of clustering coefficients. In Methods
we explain this metric in more detail. Community detection algorithms based on
this metric optimize communities to maximize the global $WCC$ score by
allowing nodes to individually join or leave communities. Such algorithms can
yield disjoint or overlapping communities depending on whether nodes are
allowed to join multiple communities.

##### Efficient $WCC$-based large scale overlapping community detection

$WCC$-based overlapping community detection approaches also suffer from
computational complexity issues when dealing with large scale datasets. Thus,
parallelized (Prat-Pérez et al.,, 2014) and distributed (Saltz et al.,, 2015)
$WCC$ versions have been proposed that allow multiple nodes at the same time
to decide for changes to the community partition, so those decisions can be
computed on separate threads or machines. Furthermore, computationally less
expensive estimations of the $WCC$ score have been suggested (Prat-Pérez et
al.,, 2014; Lyu et al.,, 2020) to further improve runtime. Thereby, Lyu and
colleagues have found that approximating triangle counts with their metric,
$\widehat{WCC}$, in an algorithm they call Fox yields very similar results as
calculating the exact count. While their proposed estimation allows Fox to
compute overlapping communities on large networks with millions of edges, the
implementation of Fox was not published making it hard to reproduce the
results or to use them for further applications.

#####  LazyFox\- Parallelized Large Scale Overlapping Community Detection

We here propose our tool for overlapping community detection, LazyFox, that
contains an implementation of the Fox algorithm. In addition, we extend the
work of Lyu and colleagues and combine it with ideas from (Prat-Pérez et al.,,
2014) by introducing parallelism to leverage the advantage of modern
multiprocessor systems to even further accelerate the algorithm.

We show that LazyFox produces extremely similar results to Fox in a fraction
of Fox’s runtime, making it more efficient to work with. This also enables the
usage of the approach on large scale graphs like the social media network
Friendster with millions of nodes and billions of edges (Leskovec and Krevl,,
2014). We analyse the impact of hyperparameters of the Fox and LazyFox
algorithm on real-world examples. The C++ implementation of LazyFox (which
also includes a Fox implementation) is published as open-source under MIT
licence.

In the following sections we introduce the datasets, the algorithmic details
of Fox and LazyFox and the methods used to evaluate them. We describe the
impact of our LazyFox contribution on the runtime and community quality of
three datasets. We include the analysis of a fourth dataset to illustrate the
ability of LazyFox to handle large scale datasets in contrast to Fox. Finally,
we summarize and discuss our results.

## Methods

We introduce LazyFox, with its required input data and preprocessing, the
employed metric $\widehat{WCC}$, and the performed steps in the algorithm. We
describe the parallelization that sets LazyFox apart from Fox (Lyu et al.,,
2020) and allows LazyFox to scale across multiple CPU cores, and finally the
performance measures employed here.

### Input Data

Our algorithm LazyFox takes the edge list of an undirected, unweighted graph
$G(V,E)$ as input, $V$ denoting the nodes and $E$ the edges of the graph. We
assume this graph to be connected for the theoretical discussions, however,
LazyFox will still work on a graph with multiple connected components.

### Preprocessing

LazyFox performs the following preprocessing steps on the input edge list of
$G$:

##### Remove Multi-Edges

In graphs a pair of nodes can be connected via multiple edges. Since our
research on Fox and LazyFox works on “by-bond” communities, we regard multiple
connections between two entities as one. Therefore, we remove such duplicated
edges, turning any input multi-graph into a simple graph.

##### Dense Node Labels

The node identifiers (IDs) in edge lists are not necessarily consecutive due
to preprocessing (this is the case in most datasets introduced in the
’Datasets’ section). We apply a shift to the node IDs to restore their
consecutive nature. This allows both Fox and LazyFox to use the node IDs
directly as data-structure indices which speeds up computation.

##### Node Order

As LazyFox computes communities by gradually improving node memberships, there
needs to be a well defined order in which the nodes are being processed. We
define this order by sorting them by decreasing clustering coefficient (CC):

$CC(i)=\begin{cases}\frac{k_{i}}{d_{i}\cdot(d_{i}-1)/2},&\text{if }d_{i}>1,\\\
0,&\text{else}\end{cases}$

$k_{i}$ denotes the number of triangles containing node $i$ (equal to the
number of edges between two neighbors of node $i$), while $d_{i}$ denotes the
degree of node $i$. A higher CC indicates that a node is central in its
neighborhood, and we process more central nodes first. Ties are resolved by
node degrees in decreasing order. This order ensures that nodes with less
connectivity and thus less influence can adapt to changes in memberships of
more important, connected nodes resulting in a more coherent community
structure at the end of one iteration.

##### Initial Clustering

To initiate the clustering process LazyFox computes a greedy, non-overlapping
community decomposition using the above node order. A node that is not yet
part of a community is assigned to a new community. Then all its not yet
assigned neighbors join this community.

This process allows for self-initialization on any given network. LazyFox
derives the initial community count and the initial clustering from the
structure of the underlying network. On the other hand, LazyFox is, just like
Fox (Lyu et al.,, 2020), also able to improve upon an existing division into
communities by replacing the initial clustering step by inserting those
existing divisions. Therefore, known structural properties can be taken into
account. This way LazyFox can be used to generate overlapping community
structure from partitions, i.e. from non-overlapping community structure. See
Lyu et al., (2020) for a discussion and examples.

###  $\widehat{WCC}$– A Metric to Optimize for

Lyu and colleagues introduced $\widehat{WCC}$ as an advanced metric to assess
the quality of a partition into communities. This metric forms the core of
both the Fox and the LazyFox algorithm as they use $\widehat{WCC}$ to decide
on the necessary local optimization steps. To provide a better understanding
of $\widehat{WCC}$ we will first describe $WCC$.

##### WCC

The weighted clustering coefficient $WCC$ as introduced by Prat-Pérez et al.,
(2012) is a score that rates a community decomposition as the sum of its
community ratings. We denote such a rating of a community decomposition
$P=\\{C_{1},\dots,C_{k}\\}$ as

$WCC(P)=\sum_{i=1}^{k}WCC(C_{i})$

This rating of an individual community $C_{i}$ can be again decomposed into
how well the individual nodes of that community fit into the community:

$WCC(C_{i})=\sum_{x\in C_{i}}WCC(x,C_{i})$

Such a fit of a node $x$ into its community $C$ is assessed by the ratio of
$t(x,C)$ to $t(x,V)$: The number of triangles that the node forms within its
community to the number of triangles that it forms within the whole graph. The
assessment also uses $vt(x,C)$, the number of nodes in the community $C$ that
form triangles with node $x$. Furthermore, $vt(x,V\setminus C)$, the number of
nodes outside of the community $C$ that form triangles with node $x$,
influences this assessment:

$WCC(x,C)=\begin{cases}\frac{t(x,C)}{t(x,V)}\cdot\frac{vt(x,V)}{\mid
C\setminus\\{x\\}\mid+vt(x,V\setminus C)},&\text{if }t(x,V)>0,\\\
0&\text{else}\end{cases}$

##### Heuristic Counting of Triangles

The counting of triangles for the $WCC$ computation is expensive. To
accelerate the evaluation of a new community decomposition, the exact count
can be replaced by a heuristic. Rather than counting the triangles a node
forms with the nodes of a community $C$ and all other nodes, $\widehat{WCC}$
(Lyu et al.,, 2020) approximates this by using the number of edges instead.

Assuming that the edges inside a community are homogeneously distributed
between the nodes, a mean-field approximation can be performed. This delivers
the expected triangle count depending on the density $p$ of the community and
the degree $deg(x,C)$, which is the count of edges between node $x$ and all
nodes within community $C$:

$\mathbb{E}[t(x,C)]=\binom{deg(x,C)}{2}\cdot p$

Analogously, one can also define an estimator for the average number of
triangles in the whole graph. It uses the global clustering coefficient $cc$
(Watts and Strogatz,, 1998), the average of all local clustering coefficients
(CC):

$\mathbb{E}[t(x,V)]=\binom{deg(x,V)}{2}\cdot cc$

The exact values of $vt(x,V)$ and $vt(x,V\setminus C)$ are harder to estimate.
However, both have an upper bound. If all neighbours of $x$ form a triangle
with $x$, the upper bound of $vt(x,V)$ is reached – it is exactly $deg(x,V)$.
The same holds for all neighbors of the vertices $V\setminus C$, so that the
upper bound of $vt(x,V\setminus C)$ is $deg(x,V\setminus C)$.

Using $\mathbb{E}[t(x,C)]$, $\mathbb{E}[t(x,V)]$ and these upper bounds, an
estimator $\widehat{WCC}$ for the weighted clustering coefficient WCC can be
derived:

$\widehat{WCC}(x,C)=\begin{cases}\frac{\mathbb{E}[t(x,C)]}{\mathbb{E}[t(x,V)]}\frac{deg(x,V)}{\mid
C\setminus\\{x\\}\mid+deg(x,V\setminus C)},&\text{if }\mathbb{E}[t(x,V)]>0,\\\
0,&\text{else}\end{cases}$

This can be then used to define the $\widehat{WCC}$ for whole communities
$C_{i}$ and community decompositions $P=\\{C_{1},\dots,C_{k}\\}$,
respectively:

$\widehat{WCC}(C_{i})=\sum_{x\in C_{i}}\widehat{WCC}(x,C_{i})$
$\widehat{WCC}(P)=\sum_{i=1}^{k}\widehat{WCC}(C_{i})$

Both Fox (Lyu et al.,, 2020) and LazyFox use this estimate to compute the
optimization steps, as it is faster than the WCC metric.

### Node Changes

Starting with the initial, non-overlapping community decomposition obtained by
the preprocessing step, Fox and LazyFox process the nodes of our graph in
multiple iterations. One iteration here is equivalent to computing and
applying changes for each node once, described in Algorithm 1 and Algorithm 2.
Before deciding on changes, LazyFox gathers $\widehat{WCC}(P)$, the quality
rating of the current decomposition $P$. The LazyFox algorithm then computes
for the node a potential _join_ \- and a potential _leave_ -action.

##### Joining a Community

For the current node $x$, LazyFox finds all communities that $x$ is currently
not part of but any of $x$’s neighbors are. Each of these communities $C_{k}$
is then evaluated by creating a decomposition $P^{\prime}$ that differs from
the current one by adding $x$ to $C_{k}$ and then computing the, potentially
negative, improvement in $\widehat{WCC}(P^{\prime})$ compared to
$\widehat{WCC}(P)$. If any of these changes yields a positive improvement, we
choose the community with the highest increase in $\widehat{WCC}$ as the
current _join_ -action. This is described in lines two to six in Algorithm 1.

##### Leaving a Community

Similarly LazyFox checks all communities $C_{k}$ of the current node $x$ and
evaluates the gain in $\widehat{WCC}$ if $x$ leaves that community. Therefore,
we again form a $P^{\prime}$ per community by removing $x$ from $C_{k}$ and
gather the improvement in $\widehat{WCC}$ compared to the old decomposition.
If any of these improvements is positive, we again choose the community with
the highest increase in $\widehat{WCC}$ as the current _leave_ -action. This
is described in lines seven to eleven in Algorithm 1.

After determining the best _join_ -action and _leave_ -action for a node,
these are executed yielding a new decomposition as the new $P$ before
calculating change actions for the next node. This is described in line
twelve.

In Fox, the steps of one iteration are sequential and executed on one single
thread, visualized in 1(a).

Algorithm 1 Fox (Lyu et al.,, 2020)

1:for node $x$ $\in$ Graph do

2: bestJoin = undefined

3: for community $c$ that does not contain $x$ and is a neighbor of $x$ do

4: join = partition if $x$ joined $c$

5: update bestJoin if the join partition has a higher $\widehat{WCC}$ score

6: end for

7: bestLeave = undefined

8: for community $c$ that contains $x$ do

9: leave = partition if $x$ left $c$

10: update bestLeave if the leave partition has a higher $\widehat{WCC}$ score

11: end for

12: apply bestLeave and bestJoin to the partitioning

13:end for

(a) Fox iteration

(b) LazyFox iteration

Figure 1: Program Control Flows

Each color denotes a separate thread. While Fox (1(a)) is computed
sequentially on one thread, LazyFox (1(b)) can leverage up to queue size many
threads that are synchronized by applying their respective node changes. Queue
size is denoted as $q$. Note that each Find-Apply-Block in LazyFox contains
$q$ nodes, except for the last one, as the total number of nodes of the graph,
$n$, might not be a multiple of $q$.

### Parallelism on Node Change Computations

To leverage the advantage of modern multi-core computer systems, LazyFox is
capable of parallelizing the computations for the _join_ and _leave_ -actions
by doing this in parallel for a queue of nodes. 1(b) visualizes the parallel
nature of a LazyFox iteration. Every compute thread fetches a node from the
node queue and computes the best actions independently. After the queue is
emptied, LazyFox gathers all the computed _join_ -actions and _leave_ -actions
and applies all of them before re-filling the queue by the next set of nodes
of the current iteration.

The core process for calculating node changes in LazyFox is the same as in Fox
(see Algorithm 2): The lines seven to 16 of Algorithm 2 are the same as the
lines three to eleven of Algorithm 1. The difference is the parallel
computation of $queueSize$ many nodes in LazyFox (lines one to six) and the
bulk apply of node changes in lines 19 to 21.

The parallel computation introduces the first hyper-parameter of LazyFox– the
queue size. The parallelization is what sets apart LazyFox from Fox.

Algorithm 2 LazyFox

1:nodeQueue = EmptyList()

2:for node x $\in$ Graph do

3: nodeQueue.insert(x)

4: if nodeQueue.size == queueSize or x is last node then

5: for node q $\in$ nodeQueue do

6: run on separate thread

7: bestJoin = undefined

8: for community $c$ that does not contain $x$ and is a neighbor of $x$ do

9: join = partition if $x$ joined $c$

10: update bestJoin if the join partition has a higher $\widehat{WCC}$ score

11: end for

12: bestLeave = undefined

13: for community $c$ that contains $x$ do

14: leave = partition if $x$ left $c$

15: update bestLeave if the leave partition has a higher $\widehat{WCC}$ score

16: end for

17: end run

18: end for

19: collect bestLeaves and bestJoins as nodeChanges from threads

20: apply nodeChanges to the partitioning

21: nodeQueue = EmptyList()

22: end if

23:end for

### Stopping Criteria

While computing and applying the _join_ -actions and _leave_ -actions, LazyFox
updates the $\widehat{WCC}$ of the partition. At the end of each iteration,
the current $\widehat{WCC}$ is compared to the $\widehat{WCC}$ of the
partition an iteration earlier. If the total relative improvement of
$\widehat{WCC}$ is below a $\widehat{WCC}$-threshold – a second hyperparameter
– LazyFox stops and switches over to the post-processing phase. The first
iteration of LazyFox is compared to the $\widehat{WCC}$ of the initial node
clustering described in the Preprocessing paragraph.

### Post-processing

As LazyFox allows nodes to leave communities, communities can degenerate to
having less than two members. This means that no triangle can be formed with
that community anymore. Therefore, after each iteration, we remove such
degenerated communities with less than two members. In LazyFox’ final result,
individual communities can not only overlap but also contain each other. The
overlap can also lead to duplicated communities. Depending on the use-case,
such duplicated or contained communities can be unwanted and have to be
removed as part of the post-processing. While we provide an API to include
custom post-processing of the final result, LazyFox does not post-process the
communities other than removing degenerated ones.

### Evaluation Criteria

LazyFox improves the runtime of the community detection via the Fox approach.
To evaluate the quality of the results from LazyFox we utilize overlapping
normalized mutual information (ONMI) distance111OverlappingNMIDistance,
https://networkit.github.io/dev-
docs/python_api/community.html?highlight=overlappingnmi#networkit.community.OverlappingNMIDistance,
retrieved 15.09.2021 and an appropriate F1 score222CoverF1Similarity,
https://networkit.github.io/dev-
docs/python_api/community.html?highlight=coverf1similarity#networkit.community.CoverF1Similarity,
retrieved 15.09.2021, two quality measurements that are widely adopted in the
field of overlapping community detection.

##### Overlapping NMI Distance

We use a recent variation of the common Normalized Mutual Information to
enable its use for overlapping clusterings: Overlapping Normalized Mutual
Information (ONMI) (McDaid et al.,, 2011). The core idea of the ONMI score is
to compare each combination of a community from the LazyFox output with each
community in the ground truth. We then select for each output community the
closest community in the ground truth leveraging _lack of information_ as our
distance function. Then the sum over minimal distances is averaged across all
output clusters yielding one score, the ONMI distance, ranging from 0 (best)
to 1 (worst). We employ its implementation via the OverlappingNMIDistance
function in Networkit (Staudt et al.,, 2015).

##### F1-Score for Overlapping Communities

To enable the use of the common F1 score for community partitions we use the
approach proposed by (Epasto et al.,, 2017) and implemented as
CoverF1Similarity function in Networkit (Staudt et al.,, 2015). Every
community is matched to its best ground truth community, and the resulting F1
scores are then averaged to form the final F1-Score, ranging from 0 (worst) to
1 (best). A single overlapping community $C^{\prime}$ out of the detected
partition $P^{\prime}$ is compared with the regular F1-Score to all ground
truth communities $C$ out of the ground truth partition $P$. The maximum F1
score is then chosen as the F1 score for $C^{\prime}$:

$F1-Score(P^{\prime},P)=\frac{1}{|P^{\prime}|}\sum_{C^{\prime}\in
P^{\prime}}\max_{C\in P}F_{1}(C^{\prime},C)$

The F1 score for comparing a detected community $C^{\prime}$ and a ground
truth community $C$ is defined via the precision $p(C^{\prime},C)=\frac{|C\cap
C^{\prime}|}{|C^{\prime}|}$ and recall $r(C^{\prime},C)=\frac{|C\cap
C^{\prime}|}{|C|}$:

$F_{1}(C^{\prime},C)=2\cdot\frac{p(C^{\prime},C)\cdot
r(C^{\prime},C)}{p(C^{\prime},C)+r(C^{\prime},C)}$

## Datasets

To validate both our Fox and LazyFox implementation we collected a set of
well-known “by bond” (Ren et al.,, 2007) networks and ran the algorithms on
them to either benchmark their performance or test whether our implementations
are capable of dealing with the respective input sizes.

All of our datasets were obtained from the SNAP-datasets Leskovec and Krevl,
(2014) collection (see Table 1 for an overview). The networks are provided in
an edge list format. In the following subsections, we present the specific
datasets that we used with both their semantic and structural properties.

Dataset | Short Identifier | Node Count | Edge Count | Average Degree
---|---|---|---|---
Eu-core | eu | 1,005 | 25,571 | 25.4
DBLP | dblp | 317,080 | 1,049,866 | 3.3
LiveJournal | lj | 3,997,962 | 34,681,189 | 8.7
Friendster | friendster | 65,608,366 | 1,806,067,135 | 27.5
Table 1: Dataset Size Overview

### Eu-core

Eu-core333https://snap.stanford.edu/data/email-Eu-core.txt.gz, retrieved
15.09.2021 (Leskovec and Krevl,, 2014) is our first and smallest benchmarking
dataset. It consists of anonymized email data between members of a large
European research institution. An edge exists between two members if at least
one email has been sent between these members. The Eu-core graph consists of
1005 nodes and 25,571 edges. The network is very dense with a diameter of
length $7$ and a 90-percentile effective diameter of $2.9$. This can be
expected from any cooperation, as people working with each other are likely to
communicate.

### DBLP

The Digital Bibliography & Library Project (DBLP) is a computer science
publication database provided by DBLP Organisation. The Library consists of
more than 5.4 million publications from different journals and conference
articles. The DBLP
dataset444https://snap.stanford.edu/data/bigdata/communities/com-
dblp.ungraph.txt.gz, retrieved 15.09.2021 (Leskovec and Krevl,, 2014), the
second of our benchmarking datasets, is the co-authorship network calculated
for these publications. Each of the 1,049,866 edges in this dataset represents
co-authorship on a publication between two of the 317,080 authors.

### LiveJournal

The LiveJournal dataset is derived from the LiveJournal social network. In
this social network, users can assign mutual friendship and join user-defined
groups. For the
dataset555https://snap.stanford.edu/data//bigdata/communities/com-
lj.ungraph.txt.gz, retrieved 15.09.2021 (Leskovec and Krevl,, 2014) the
3,997,962 nodes represent users and the 34,681,189 edges are formed from the
friendship relations between these nodes.

### Friendster

Like the LiveJournal dataset, the Friendster
dataset666https://snap.stanford.edu/data//bigdata/communities/com-
friendster.ungraph.txt.gz, retrieved 15.09.2021 (Leskovec and Krevl,, 2014) is
also derived from the social network bearing the same name. But the Friendster
dataset is an order of magnitude larger bringing in 65,608,366 nodes and
1,806,067,135 edges and 8.7GB of compressed edges. While this scale makes it
unattractive for benchmarking Fox and LazyFox, it serves us as a feasibility
test for the algorithm and implementation on large scale.

## Results

The implementation of the LazyFox algorithm enables us to evaluate the runtime
improvements and the impact on overlapping community quality of a
multithreaded approach. Note that running LazyFox with a queue size of one is
equivalent to the original Fox algorithm.

During the evaluation, the queue size was always equal to the thread count.
The results of this section were computed with the thread counts in
$\\{1,2,4,8,16,32,64,128,256\\}$ and a fixed $\widehat{WCC}$ threshold of
0.01. The computations were made on an HPE XL225n Gen10 machine with 512 GB
RAM, and two AMD EPYC 7742 with 64 cores.

### Runtime Improvements

The main goal of any multithreaded approach is to improve the runtime. LazyFox
enables the parallel calculation of node changes, speeding up this step. The
execution of these changes, however, has to be done sequentially, which is the
main non-parallelizable part of the algorithm. The runtime measurements were
taken without saving the results of the computation to disk to remove the very
volatile I/O operation bottleneck from the benchmarks. The preprocessing steps
described in the methods section are part of the measurement.

We find significant improvements of runtime with the multithreaded approach on
the Eu-core, DBLP and LiveJournal datasets (see Figure 2). Even the use of two
threads instead of one reduces the original runtime of the Fox algorithm by
about 20%. While extra threads improve the runtime, the improvement rate does
not stay the same.

The relative runtime improvements in the DBLP and the LiveJournal datasets are
roughly the same, despite the fact that the LiveJournal dataset has orders of
magnitude more nodes than the DBLP dataset. The original runtime on the Eu-
core dataset (Eu) is reduced massively. With 256 threads LazyFox takes just 4%
of the original Fox runtime. However, this extreme improvement is an exception
to the overall results, due to the small scale of the Eu-core dataset ($\sim
1000$ nodes spread on $256$ threads). Overall, we observe consistent runtime
improvements also for larger scale networks, making the improvements
independent of dataset size.

We also see that the runtime of LazyFox on the DBLP dataset gets worse
switching from 128 to 256 threads (see Figure 2). It is not caused by an
additional iteration that had to be made by LazyFox due to imprecision, as all
DBLP runs take exactly seven iterations to converge. Instead, the increase in
runtime appears before the first iteration runs, in the run preparations, such
as initializing the threads. Thus, the most likely cause for the increased
runtime is that the 128 additional thread initializations going from 128
threads in total to 256 threads in total do not yield enough runtime
improvement to account for their own initialization time. Taken together, we
see a thread count of 64 or 128 as optimal, being a trade-off between runtime
improvement and resource usage for our examined networks.

Threadcount | Eu-core | DBLP | LiveJournal
---|---|---|---
1 | 1.0 (13.8s) | 1.0 (47.2s) | 1.0 (262.0min)
2 | 0.58 | 0.87 | 0.80
4 | 0.39 | 0.60 | 0.65
8 | 0.30 | 0.41 | 0.51
16 | 0.19 | 0.32 | 0.40
32 | 0.15 | 0.25 | 0.30
64 | 0.09 | 0.21 | 0.23
128 | 0.06 | 0.17 | 0.18
256 | 0.04 | 0.19 | 0.16

Figure 2: Runtime Comparison

The runtimes of LazyFox on three different datasets EU-core, DBLP, and
LiveJournal and different threadcounts relative to the non-parallelized
runtime (threadcount $1$, Fox algorithm).

### Quality Impact

The multithreaded approach of LazyFox does alter the computations. Therefore,
the results of LazyFox on the same dataset differ for different threadcounts.
However, we find these changes to be insignificant for sufficiently large
datasets. The following sections compare quality measurements and analysis
results of the singlethreaded approach to the multithreaded approaches.

##### Ground Truth Metrics

To verify that the difference in community results of LazyFox and Fox are
negligible, we compare the results with each other (see Table 2). We use two
common metrics to measure overlapping community similarities, F1-Score and
ONMI distance (see Methods). As the computational differences between Fox and
LazyFox increase with a higher degree of parallelism, we compare LazyFox with
increasing threadcounts.

We find that on sufficiently large datasets, LazyFox results in communities
extremely similar to the Fox communities (F1-Score of .99, ONMI distance of
$\leq.01$). However, we find that for the small Eu-core dataset, a high degree
of parallelism does impact the result. While LazyFox with a threadcount of
$128$ creates results with .99 F1-Score and .05345 ONMI distance, the increase
to $256$ threads impacts the final result, reducing the F1-Score to .85 and
increasing the ONMI distance to 0.32. These results suggest that smaller
datasets such as Eu-core are more prone to changes caused by parallelization.

Threadcount | Eu-core | DBLP | LiveJournal
---|---|---|---
| F1 | ONMI-D | F1 | ONMI-D | F1 | ONMI-D
1 | 1.0 | 0.0 | 1.0 | 0.0 | 1.0 | 0.0
2 | 0.99 | 0.02386 | 0.99 | 0.00005 | 0.99 | 0.00348
4 | 0.99 | 0.03123 | 0.99 | 0.00007 | 0.99 | 0.00564
8 | 0.99 | 0.03005 | 0.99 | 0.00008 | 0.99 | 0.00684
16 | 0.99 | 0.03316 | 0.99 | 0.00014 | 0.99 | 0.00756
32 | 0.99 | 0.05028 | 0.99 | 0.00017 | 0.99 | 0.00799
64 | 0.99 | 0.04884 | 0.99 | 0.00027 | 0.99 | 0.00837
128 | 0.99 | 0.05345 | 0.99 | 0.00034 | 0.99 | 0.00874
256 | 0.85 | 0.31553 | 0.99 | 0.00055 | 0.99 | 0.00950

Table 2: Comparison of LazyFox Results to Fox Results

Note that LazyFox with a threadcount of $1$ is Fox. F1: F1-Score, ONMI-D: ONMI
distance, both calculated with the networkit library (Staudt et al.,, 2015).

##### Community Analysis

We also perform a structural analysis of the results obtained by LazyFox. In
the best case, the properties measured (such as average community size) should
stay the same, regardless of threadcount. Similar properties mean that all
threadcounts can be used to draw the same conclusions over community
structures within a specific dataset, making the degree of parallelism used in
LazyFox a hyper-parameter only relevant for run-time improvement, not for
result quality.

The most obvious property of community detection is the number of detected
communities. The threadcount used has no impact on this number, and for all
threadcounts we detected 213 communities for the Eu-core, 76,513 communities
for the DBLP and 920,534 communities for the LiveJournal dataset.

Looking at the size of the communities, the maximum and minimum sizes for DBLP
and LiveJournal communitites do not change dependent on threadcount. The
biggest community in DBLP has 115 members, LiveJournal 574. In the Eu-core
dataset the threadcount changes the original maximum size of 135 members by
maximum of plus two. However, the run with 256 threads is an exception, as the
maximum size here is decreased by 39. This is another indication that a
threadcount close to the node count of the dataset (256 is about one fourth of
the Eu-core node count) is not optimal.

Finally, we can investigate the overlap between communities. This is the
average number of communities a node belongs to. Again, this value does not
change for DBLP or LiveJournal over different threadcounts, staying at 1.19
for DBLP and 1.9 for LiveJournal. The Eu-core dataset’s overlap changes with
different threadsizes, starting with an overlap of 5.44 for threadcount equal
to one. For a threadcount up to four this stays relatively stable with changes
of less than 0.1. However, higher threadcounts change the overlap quite
drastically, up to +0.3. Threadcount 256 is the exception here again, changing
the overlap from the original 5.44 to 4.22, which is one community less per
node.

From these results we conclude that on sufficiently large datasets, the
threadcount does not impact the obtained community structure. The changes only
occur with the Eu-core dataset, and get worse with higher threadcounts. This
is caused by the small node count in Eu-core. The nodecount therefore can be
used as an indicator to determine the most favorable degree of
parallelization. As the Eu-core results already change at two threads instead
of one, we would suggest that the node count should at least be 500 times the
threadcount to avoid these complications.

### Cluster Analysis

While it is worthwhile to investigate the impact of the threadcount to the
various metrics, these metrics can also be used to analyze the semantics of
the datasets.

LazyFox optimizes triangle count. This means nodes end up in the same group if
they are strongly connected with each other. If we speak of people, this means
they are socially close. In all our datasets the nodes represent people,
connected by bond, such as common work (Eu-core, DBLP) or other social
interaction (LiveJournal, Friendster).

#### Eu-core

We find 213 communities with an average size of 11. This means that within the
research institution, there are about 213 teams with an average team size of
11 people. These teams can already be disbanded, as the data contains e-mails
of a long timespan. The high overlap of 5.44 indicates that a single person
works on average in 5.44 teams, however, because teams can already be
disbanded this is not true for any point in time. It means that an employee
works on average in 5.44 teams before leaving the institution or settling for
a final research team. This could mean that there are only 5 or 6 team changes
before reaching a leading position in a team or leaving the company, capping
off the team changes.

#### DBLP

We find 76,513 communities in the DBLP network with an average size of 4.9
members per community. Semantically these communities represent research
groups. Scientists are the nodes, and edges are their co-authorship. Strong
connections mean that any author of the group has published at least once with
most of the other authors. The average size is reasonable for research groups,
and indicates that larger research groups have sub-groups who rarely co-author
with each other. Also, there is low overlap between groups, about 1.2, which
means each author has on average 1.2 research groups. While one would assume a
researcher stays true to his or her field, the nodes with an overlap over 1
are likely to be more senior members of the research community, having been
part of multiple research groups, or researchers who changed their fields.

#### LiveJournal

Another dataset we looked at is LiveJournal, a platform and social network for
blogging. Users can befriend each other and join common interest groups. In
this dataset we find that the average node has a degree of 17 and an overlap
of 1.9. This means that each user has on average 17 friends and belongs to
about two friendship groups. We assume these represent real life groups, as we
think a mutual friendship circle of average 8 people (community size mean) is
unlikely to form from social network interactions alone. However, this is an
assumption and verifying that would need sensitive data of LiveJournal user
accounts to the people behind them and their real life friendships, which we
do not have.

### Large Scale Analysis – Friendster

Finally, we would like to present the results of our computations on the
Friendster dataset. The enormous scale of this dataset makes an analysis with
Fox not feasible in reasonable time. However, due to the runtime improvements
achieved with LazyFox this analysis is made possible. We ran LazyFox with 256
threads on the Friendster dataset twice, once with and once without saving the
intermediate results to disk. For both runs we use the measured LazyFox
runtime to estimate the Fox runtime Figure 3. We do this by assuming a speedup
ratio similar to the speedup ratios of the DBLP and LiveJournal datasets
($0.18$), as we found that the speedup is independent of scale at datasets of
sufficient size.

Figure 3: Friendster Runtime Comparison

The runtime of LazyFox on the Friendster dataset with 256 threads compared to
estimates of Fox runtime. Estimates made assuming a speedup comparable to the
DBLP and LiveJournal datasets. LazyFox’ parallel computations make Friendster
community analysis feasible.

The disk operations of saving the computation results of such a large dataset
as Friendster are time consuming: After each iteration about 1.5 GB of
clustering results are written to disk. LazyFox converged after eight
iterations, running about 171.3 hours ($\sim$ 7.1 days) with and 71.6 hours
($\sim$ 3.0 days) without saving to disk. It is save to say that the I/O
operations and their preparations take up most of the runtime. This has to be
kept in mind when working with large datasets.

Figure 3 illustrates why LazyFox enables community analysis of large scale
networks. A runtime of 71.6 hours ($\sim$ 3.0 days) is far more feasible than
a runtime of almost 400 hours ($\sim$ 16.7 days).

After the 8th iteration, LazyFox results in 13,861,732 detected communities,
with an average size of 9 nodes per community. However, the largest community
has 4,721 members. This indicates that Friendster was mostly used for real
friend groups where a size of 9 people is reasonable, but it also contains
closely connected communities of great size. We find that about 92% of all
communities have 2 to 19 members. Communities over 100 members make up only
0.003% of all communities. We assume that these large communities are career
networks, institutions or non-human user networks (bots), where a high
interconnectedness between members is beneficial to the members, even if they
do not know each other personally. We also find that a node belongs on average
to 1.92 communities, meaning each user has about 2 groups of friends.

We find LazyFox highly viable to run analyses on such large datasets, despite
the runtime of over a week. However, computing metrics such as F1 which
compare the results to the graph itself would be challenging due to the sheer
size of the graph.

###  $\widehat{WCC}$ Threshold Impact

Another hyper-parameter apart from the threadcount for the LazyFox algorithm
is the iteration termination criterion, the $\widehat{WCC}$ threshold. Lyu and
colleagues propose a threshold of 0.01 of relative $\widehat{WCC}$ change,
meaning that if an iteration decreases the global $\widehat{WCC}$ by less than
1%, the algorithm stops. This threshold was determined by experiments
measuring community size and density (compare Lyu et al., (2020), Table 7), as
a lower threshold did not yield significant change in these properties.

Figure 4: Relative $\widehat{WCC}$ Change Development

The relative change of $\widehat{WCC}$ at different iterations on different
datasets, EU-core, DBLP, and LiveJournal. By default and also in Lyu et al.,
(2020), computations stop if the change drops below 0.01. Other possible
thresholds (0.02, 0.03, 0.04) are visualized.

However, we find that the threshold’s impact on the algorithm’s runtime is
quite extraordinary. As Figure 4 shows, a slightly higher threshold can save
multiple iterations. This has high impact on runtime, as the iterations get
slower over time. We find that even the threshold of 0.02 instead of 0.01
yields great runtime improvements for runs on a single thread. For the Eu-core
dataset, it saves five iterations, which is equivalent to 39% of the total
runtime. For DBLP, we save two, for LiveJournal three iterations, which is
equivalent to 33% and 43% of the total runtime, respectively.

These runtime improvements are due to an earlier termination and therefore can
still be seen in runs with a higher threadcount. Running LazyFox with 256
threads on the LiveJournal dataset with a $\widehat{WCC}$ threshold of 0.02
still saves 39% of the runtime, compared to the same run with a
$\widehat{WCC}$ threshold of 0.01. However, the effectiveness can be dependent
on the dataset scale, as the savings for the Eu-core and DBLP datasets at this
high threadcount are significantly smaller (3% and 10%, respectively).

Figure 5: $\widehat{WCC}$ at different threadcounts

$\widehat{WCC}$ development at different threadcounts at different iterations
on different datasets, EU-core, DBLP, and LiveJournal. Threadcount does not
influence the $\widehat{WCC}$ development at sufficiently large datasets. Note
that in DBLP and LiveJournal datasets the values for each threadcount are
exactly the same.

It is important to note that these decreased savings at higher threadcounts
are due to the overall decreased total runtime and not due to a different
$\widehat{WCC}$ development over time (see Figure 5). While a higher
threadcount can lead to different results and therefore change the
$\widehat{WCC}$ scores, this is not the case at large scale datasets. As the
community analysis results are unaffected by higher threadcounts (see ’Quality
Impact’ section), so is the $\widehat{WCC}$. The Eu-core dataset here again is
an outlier due to the threadcount being close to its nodecount.

## Discussion

Our proposed parallelization of the algorithm slightly differs in its logic
from the original version Fox (Lyu et al.,, 2020): LazyFox computes first all
node changes for a certain batch of nodes (in parallel) and then executes them
altogether to generate a new community structure. In contrast, in Fox,
computed changes for a single node are applied immediately. However, LazyFox
still generates highly similar results to Fox and therefore enables detecting
meaningful overlapping communities. These results go along the same lines as
the parallelization of e.g. the BigClam algorithm (Liu and Chamberlain,,
2018). They show once more that many analysis approaches can be parallelized
even if the resulting algorithms are not strictly equivalent to their
sequential counterparts.

With the runtime improvement provided by the parallelization LazyFox brings
overlapping community detection into new areas of application and allows for
the analyses of significantly larger and more complex datasets. It reduces the
computation time for networks with millions of nodes and billions of edges
from weeks to days. For example, LazyFox could not only be used to find
community structures in huge social media networks such as twitter, but also
to find complexes or pathways in intricately connected multi-layered molecular
network (Liu et al.,, 2020), or querying global-scale, finely resolved climate
(Steinhaeuser et al.,, 2011), or ecological networks (Bohan et al.,, 2017).
LazyFox is very flexible, the algorithm can be straightforwardly adapted to
take directed or weighted graphs into account. We would like to address these
extensions in the future, thereby opening even further application areas for
overlapping community detection.

LazyFox relies on nodes iteratively joining and leaving communities.
Therefore, it could generate empty, disconnected, or communities fully
contained in other communities. We provide an additional post-processing
function to eliminate those types of undesired results. However, note that it
can be computationally expensive to perform this post-processing on large
graphs, or graphs with many detected communities. Sometimes, communities that
are fully contained in other communities are desirable and occur in the ground
truth. In these cases, e.g. the citation network in SNAP (Yang and Leskovec,,
2012), they should not be removed. The post-processing needed is therefore
dictated by the research domain which is why detailed analyses on post-
processing is not part of our work.

We showed that the value of the $\widehat{WCC}$ threshold hyperparameter is
decisive for the runtime of the algorithm. This is expected as it constitutes
the termination criterion of this iterative algorithm, and it is comparable to
criteria applied to convergence assessment for other graph-based analyses,
such as the PageRank algorithm in NetworKit (Staudt et al.,, 2015).
Alternatively, limiting the number of performed steps is another solution for
termination of iterative algorithms that has been applied previously, e.g. in
node-centric PageRank computation in iPregel (Capelli et al.,, 2019). An
investigation of the asymptotic behavior, i.e. whether the $\widehat{WCC}$
score of LazyFox converges, might be interesting, but we have not experienced
problems in the application cases we analyzed. As heuristic solution, we
suggest to monitor the change in $\widehat{WCC}$ over the course of the
computation to discover problematic cases.

The queue size as second hyperparameter of LazyFox was set to the available
threadcount in our experiments. In principle, LazyFox allows to choose both
values independently from one another. However, increasing the threadcount
over the queue size does not yield any runtime improvements as the queue size
controls the maximum degree of parallelization. Additional threads will then
actually slow down the computation as their allocation takes time.

Moreover, the larger the queue size, the more different LazyFox becomes to Fox
in theory, and we cannot guarantee that the community detection results remain
stable. Overall, we find that the optimal queue size and thread count should
scale with the size of the dataset, but unless very small graphs are analysed,
up to 250 cores can be exploited without strong impact on the results.

## Conclusion

We provide LazyFox, an open-source implementation of an efficient,
parallelized algorithm for overlapping community detection. Our implementation
and analysis is another positive example for the idea that many graph analysis
algorithms can be parallelized, even if not being strictly equivalent to their
sequential version. The results show that the in-parallel computed
optimization of the $\widehat{WCC}$ metric yields extremely similar results to
the sequential computation. This allows the leverage of modern hardware to
significantly decrease runtime, enabling the detection of community structures
of very large graphs, without loosing community quality. The results on the
impact of the $\widehat{WCC}$ threshold allows an informed decision on the
runtime - $\widehat{WCC}$ score trade-off. With our improvements, we make
overlapping community detection achievable for very large graphs with at least
tens of million nodes and a few billion edges in a reasonable amount of time.
Thus, we enable this type of graph analysis for novel and complex application
domains that have not been previously explored with respect to overlapping
community detection.

## Acknowledgments

We would like to thank Martin Taraz for his excellent support and discussions.
KB furthermore acknowledges funding from an Add-on Fellowship for
Interdisciplinary Life Sciences of the Joachim Herz Stiftung.

## References

  * Ahn et al., (2010) Ahn, Y.-Y., Bagrow, J., and Lehmann, S. (2010).  Link communities reveal multiscale complexity in networks.  Nature, 466:761–4.
  * Airoldi et al., (2007) Airoldi, E. M., Blei, D. M., Fienberg, S. E., and Xing, E. P. (2007).  Mixed membership stochastic blockmodels.
  * Barabasi et al., (2011) Barabasi, A.-L., Gulbahce, N., and Loscalzo, J. (2011).  Network medicine: A network-based approach to human disease.  Nature reviews. Genetics, 12:56–68.
  * Barabasi and Oltvai, (2004) Barabasi, A.-L. and Oltvai, Z. (2004).  Network biology: Understanding the cell’s functional organization.  Nature reviews. Genetics, 5:101–13.
  * Basuchowdhuri et al., (2014) Basuchowdhuri, P., Shekhawat, M. K., and Saha, S. K. (2014).  Analysis of product purchase patterns in a co-purchase network.  In 2014 Fourth International Conference of Emerging Applications of Information Technology, pages 355–360.
  * Boccaletti et al., (2006) Boccaletti, S., Latora, V., Moreno, Y., and Hwang, D.-U. (2006).  Complex networks: Structure and dynamics.  Physics Reports, 424:175–308.
  * Bohan et al., (2017) Bohan, D., Vacher, C., Tamaddoni-Nezhad, A., Raybould, A., Dumbrell, A., and Woodward, G. (2017).  Next-generation global biomonitoring: Large-scale, automated reconstruction of ecological networks.  Trends in Ecology & Evolution, 32:477–487.
  * Bu et al., (2017) Bu, Z., Cao, J., Li, H., Gao, G., and Tao, H. (2017).  Gleam: a graph clustering framework based on potential game optimization for large-scale social networks.  Knowledge and Information Systems, 55:741–770.
  * Capelli et al., (2019) Capelli, L. A., Hu, Z., Zakian, T. A., Brown, N., and Bull, J. M. (2019).  ipregel: Vertex-centric programmability vs memory efficiency and performance, why choose?  Parallel Computing, 86:45–56.
  * Chakraborty, (2015) Chakraborty, T. (2015).  Leveraging disjoint communities for detecting overlapping community structure.  ArXiv, abs/1504.06608.
  * Danon et al., (2005) Danon, L., Duch, J., Diaz-Guilera, A., and Arenas, A. (2005).  Comparing community structure identification.  Journal of Statistical Mechanics: Theory and Experiment, 2005.
  * Epasto et al., (2017) Epasto, A., Lattanzi, S., and Leme, R. (2017).  Ego-splitting framework: from non-overlapping to overlapping clusters.  pages 145–154.
  * Evans and Lambiotte, (2009) Evans, T. and Lambiotte, R. (2009).  Line graphs, link partitions and overlapping communities.  Physical review. E, Statistical, nonlinear, and soft matter physics, 80:016105.
  * Fortunato, (2010) Fortunato, S. (2010).  Community detection in graphs.  Physics Reports, 486(3-5):75–174.
  * Gavin et al., (2006) Gavin, A.-C., Aloy, P., Grandi, P., Krause, R., Boesche, M., Marzioch, M., Rau, C., Jensen, L., Bastuck, S., Dümpelfeld, B., Edelmann, A., Heurtier, M.-A., Hoffman, V., Hoefert, C., Klein, K., Hudak, M., Michon, A.-M., Schelder, M., Schirle, M., and Superti-Furga, G. (2006).  Proteome survey reveals modularity of the yeast cell machinery.  Nature, 440:631–6.
  * Gopalan and Blei, (2013) Gopalan, P. K. and Blei, D. M. (2013).  Efficient discovery of overlapping communities in massive networks.  Proceedings of the National Academy of Sciences, 110(36):14534–14539.
  * Gregory, (2009) Gregory, S. (2009).  Finding overlapping communities in networks by label propagation.  ArXiv, abs/0910.5516.
  * Guimerà and Amaral, (2005) Guimerà, R. and Amaral, L. (2005).  Functional cartography of complex metabolic networks.  Nature, 23:22–231.
  * Guimerà et al., (2005) Guimerà, R., Mossa, S., Turtschi, A., and Amaral, L. (2005).  The worldwide air transportation network: Anomalous centrality, community structure, and cities’ global roles.  Proceedings of the National Academy of Sciences of the United States of America, 102:7794–9.
  * Hofman and Wiggins, (2008) Hofman, J. M. and Wiggins, C. H. (2008).  Bayesian approach to network modularity.  Physical Review Letters, 100(25).
  * Kelley et al., (2012) Kelley, S., Goldberg, M. K., Magdon-Ismail, M., Mertsalov, K., and Wallace, A. (2012).  Defining and discovering communities in social networks.
  * Lancichinetti and Fortunato, (2009) Lancichinetti, A. and Fortunato, S. (2009).  Community detection algorithms: A comparative analysis.  Physical review. E, Statistical, nonlinear, and soft matter physics, 80:056117.
  * Lancichinetti et al., (2009) Lancichinetti, A., Fortunato, S., and Kertész, J. (2009).  Detecting the overlapping and hierarchical community structure in complex networks.  New Journal of Physics, 11:033015.
  * Lancichinetti et al., (2011) Lancichinetti, A., Radicchi, F., Ramasco, J. J., and Fortunato, S. (2011).  Finding statistically significant communities in networks.  PloS one, 6:e18961.
  * Lee et al., (2010) Lee, C., Reid, F., McDaid, A. F., and Hurley, N. J. (2010).  Detecting highly overlapping community structure by greedy clique expansion.  In KDD 2010.
  * Leskovec and Krevl, (2014) Leskovec, J. and Krevl, A. (2014).  SNAP Datasets: Stanford large network dataset collection, http://snap.stanford.edu/data.
  * Liu and Chamberlain, (2018) Liu, C. H. B. and Chamberlain, B. P. (2018).  Speeding up bigclam implementation on snap.  2018 Imperial College Computing Student Workshop (ICCSW 2018).
  * Liu et al., (2020) Liu, X., Maiorino, E., Halu, A., Glass, K., Prasad B, R., Loscalzo, J., Gao, J., and Sharma, A. (2020).  Robustness and lethality in multilayer biological molecular networks.  Nature Communications, 11.
  * Lyu et al., (2020) Lyu, T., Bing, L., Zhang, Z., and Zhang, Y. (2020).  Fox: Fast overlapping community detection algorithm in big weighted networks.  ACM Transactions on Social Computing, 3:1–23.
  * Ma et al., (2019) Ma, J., Wang, J., Soltan Ghoraie, L., Men, X., Haibe-Kains, B., and Dai, P. (2019).  A comparative study of cluster detection algorithms in protein–protein interaction for drug target discovery and drug repurposing.  Frontiers in Pharmacology, 10.
  * Mcauley and Leskovec, (2014) Mcauley, J. and Leskovec, J. (2014).  Discovering social circles in ego networks.  ACM Trans. Knowl. Discov. Data, 8(1).
  * McDaid et al., (2011) McDaid, A., Greene, D., and Hurley, N. (2011).  Normalized mutual information to evaluate overlapping community finding algorithms.  CoRR.
  * Newman, (2006) Newman, M. (2006).  Modularity and community structure in networks.  Proceedings of the National Academy of Sciences of the United States of America, 103:8577–82.
  * Palla et al., (2005) Palla, G., Derényi, I., Farkas, I., and Vicsek, T. (2005).  Uncovering the overlapping community structure of complex networks in nature and society.  Nature, 435:814–818.
  * Prat-Pérez et al., (2012) Prat-Pérez, A., Dominguez-Sal, D., Brunat, J. M., and Larriba-Pey, J.-L. (2012).  Shaping communities out of triangles.  In Proceedings of the 21st ACM International Conference on Information and Knowledge Management, CIKM ’12, page 1677–1681, New York, NY, USA. Association for Computing Machinery.
  * Prat-Pérez et al., (2014) Prat-Pérez, A., Dominguez-Sal, D., and Larriba-Pey, J.-L. (2014).  High quality, scalable and parallel community detection for large real graphs.  In Proceedings of the 23rd International Conference on World Wide Web, WWW ’14, page 225–236, New York, NY, USA. Association for Computing Machinery.
  * Psorakis et al., (2011) Psorakis, I., Roberts, S., Ebden, M., and Sheldon, B. C. (2011).  Overlapping community detection using bayesian non-negative matrix factorization.  Physical review. E, Statistical, nonlinear, and soft matter physics, 83 6 Pt 2:066114.
  * Raghavan et al., (2007) Raghavan, N., Albert, R., and Kumara, S. (2007).  Near linear time algorithm to detect community structures in large-scale networks.  Physical review. E, Statistical, nonlinear, and soft matter physics, 76:036106.
  * Regan and Barabasi, (2003) Regan, E. and Barabasi, A.-L. (2003).  Hierarchical organization in complex networks.  Physical Review E, 67.
  * Regan et al., (2002) Regan, E., Somera, A., Mongru, D., and Oltvai, Z. (2002).  Hierarchical organization of modularity in metabolic networks.  Science, 297.
  * Reid et al., (2011) Reid, F., McDaid, A. F., and Hurley, N. J. (2011).  Partitioning breaks communities.  In ASONAM.
  * Ren et al., (2007) Ren, Y., Kraut, R., and Kiesler, S. (2007).  Applying common identity and bond theory to design of online communities.  Organization Studies, 28(3):377–408.
  * Saltz et al., (2015) Saltz, M., Prat-Pérez, A., and Dominguez-Sal, D. (2015).  Distributed community detection with the wcc metric.  Proceedings of the 24th International Conference on World Wide Web.
  * Shi et al., (2013) Shi, C., Cai, Y., Fu, D., Dong, Y., and Wu, B. (2013).  A link clustering based overlapping community detection algorithm.  Data Knowl. Eng., 87:394–404.
  * Song et al., (2015) Song, Y., Bressan, S., and Dobbie, G. (2015).  Fast Disjoint and Overlapping Community Detection, pages 153–179.  Springer Berlin Heidelberg, Berlin, Heidelberg.
  * Staudt et al., (2015) Staudt, C., Sazonovs, A., and Meyerhenke, H. (2015).  Networkit: A tool suite for large-scale complex network analysis.
  * Steinhaeuser et al., (2011) Steinhaeuser, K., Ganguly, A., and Chawla, N. (2011).  Multivariate and multiscale dependence in the global climate system revealed through complex networks.  Climate Dynamics, doi:10.1007/s00382-011-1135-9.
  * Wang and Wong, (1987) Wang, Y. J. and Wong, G. Y. C. (1987).  Stochastic blockmodels for directed graphs.  Journal of the American Statistical Association, 82:8–19.
  * Watts and Strogatz, (1998) Watts, D. J. and Strogatz, S. H. (1998).  Collective dynamics of ‘small-world’ networks.  Nature, 393(6684):440–442.
  * Xie and Szymanski, (2012) Xie, J. and Szymanski, B. (2012).  Towards linear time overlapping community detection in social networks.  volume abs/1202.2465.
  * Yang and Leskovec, (2012) Yang, J. and Leskovec, J. (2012).  Defining and evaluating network communities based on ground-truth.  Knowledge and Information Systems, 42.
  * Yang and Leskovec, (2013) Yang, J. and Leskovec, J. (2013).  Overlapping community detection at scale: a nonnegative matrix factorization approach.  In WSDM ’13.