# Community detection in networks: A user guide

Santo Fortunato<EMAIL_ADDRESS>Center for Complex Networks and Systems
Research, School of Informatics and Computing and Indiana University Network
Science Institute (IUNI), Indiana University, Bloomington, USA  Department of
Computer Science, Aalto University School of Science, P.O. Box 15400, FI-00076
Darko Hric  Department of Computer Science, Aalto University School of
Science, P.O. Box 15400, FI-00076

###### Abstract

Community detection in networks is one of the most popular topics of modern
network science. Communities, or clusters, are usually groups of vertices
having higher probability of being connected to each other than to members of
other groups, though other patterns are possible. Identifying communities is
an ill-defined problem. There are no universal protocols on the fundamental
ingredients, like the definition of community itself, nor on other crucial
issues, like the validation of algorithms and the comparison of their
performances. This has generated a number of confusions and misconceptions,
which undermine the progress in the field. We offer a guided tour through the
main aspects of the problem. We also point out strengths and weaknesses of
popular methods, and give directions to their use.

Networks, communities, clustering

###### pacs:

89.75.Fb, 89.75.Hc

###### Contents

  1. I Introduction
  2. II What are communities?
    1. II.1 Variables
    2. II.2 Classic view
    3. II.3 Modern view
  3. III Validation
    1. III.1 Artificial benchmarks
    2. III.2 Partition similarity measures
    3. III.3 Detectability
    4. III.4 Structure versus metadata
    5. III.5 Community structure in real networks
  4. IV Methods
    1. IV.1 How many clusters?
    2. IV.2 Consensus clustering
    3. IV.3 Spectral methods
    4. IV.4 Overlapping communities: Vertex or Edge clustering?
    5. IV.5 Methods based on statistical inference
    6. IV.6 Methods based on optimisation
    7. IV.7 Methods based on dynamics
    8. IV.8 Dynamic clustering
    9. IV.9 Significance
    10. IV.10 Which method then?
  5. V Software
  6. VI Outlook

##  I Introduction

The science of networks is a modern discipline spanning the natural, social
and computer sciences, as well as engineering Caldarelli (2007); Barrat _et
al._ (2008); Cohen and Havlin (2010); Newman (2010); Estrada (2011);
Dorogovtsev and Mendes (2013); Estrada and Knight (2015). Networks, or graphs,
consist of vertices and edges. An edge typically connects a pair of
vertices111There may be connections between three vertices or more. In this
case one speaks of hyperedges and the network is a hypergraph.. Networks occur
in an huge variety of contexts. Facebook, for instance, is a large social
network, where more than one billion people are connected via virtual
acquaintanceships. Another famous example is the Internet, the physical
network of computers, routers and modems which are linked via cables or
wireless signals (Fig. 1). Many other examples come from biology, physics,
economics, engineering, computer science, ecology, marketing, social and
political sciences, etc..

Most networks of interest display community structure, i. e., their vertices
are organised into groups, called communities, clusters or modules. In Fig. 2
we show a collaboration network of scientists working at the Santa Fe
Institute (SFI) in Santa Fe, New Mexico. Vertices are scientists, edges join
coauthors. Edges are concentrated within groups of vertices representing
scientists working on the same research topic, where collaborations are more
natural.

Figure 1: Internet network. Reprinted figure with permission from
www.opte.org. Figure 2: Collaboration network of scientists working at the
Santa Fe Institute (SFI). Edges connect scientists that have coauthored at
least one paper. Symbols indicate the research areas of the scientists.
Naturally, there are more edges between scholars working on the same area than
between scholars working in different areas. Reprinted figure with permission
from Girvan and Newman (2002). © 2002, by the National Academy of Sciences,
USA.

Likewise, communities could represent proteins with similar function in
protein-protein interaction networks, groups of friends in social networks,
websites on similar topics on the Web graph, and so on.

Identifying communities may offer insight on how the network is organised. It
allows us to focus on regions having some degree of autonomy within the graph.
It helps to classify the vertices, based on their role with respect to the
communities they belong to. For instance we can distinguish vertices totally
embedded within their clusters from vertices at the boundary of the clusters,
which may act as brokers between the modules and, in that case, could play a
major role both in holding the modules together and in the dynamics of
spreading processes across the network.

Community detection in networks, also called graph or network clustering, is
an ill-defined problem though. There is no universal definition of the objects
that one should be looking for. Consequently, there are no clear-cut
guidelines on how to assess the performance of different algorithms and how to
compare them with each other. On the one hand, such ambiguity leaves a lot of
freedom to propose diverse approaches to the problem, which often depend on
the specific research question and (or) the particular system at study. On the
other hand, it has introduced a lot of noise into the field, slowing down
progress. In particular, it has favoured the diffusion of questionable
concepts and convictions, on which a large number of methods are based.

This work presents a critical analysis of the problem of community detection,
intended to practitioners but accessible to readers with basic notions of
network science. It is not meant to be an exhaustive survey. The focus is on
the general aspects of the problem, especially in the light of recent
findings. Also, we discuss some popular classes of algorithms and give advice
on their usage. More info on network clustering can be found in several review
articles Schaeffer (2007); Porter _et al._ (2009); Fortunato (2010); Coscia
_et al._ (2011); Parthasarathy _et al._ (2011); Newman (2012); Malliaros and
Vazirgiannis (2013); Xie _et al._ (2013); Chakraborty _et al._ (2016).

The contents are organised in three main sections. Section II deals with the
concept of community, describing its evolution from the classic subgraph-based
notions to the modern statistical interpretation. Next we discuss the critical
issue of validation (Section III), emphasising the role of artificial
benchmarks, the importance of the choice of partition similarity scores, the
conditions under which clusters are detectable, the usefulness of metadata and
the structural peculiarities of communities in real networks. Section IV hosts
a critical discussion of some popular clustering approaches. It also tackles
important general methodological aspects, such as the determination of the
number of clusters, which is a necessary input for several techniques, the
possibility to generate robust solutions by combining multiple partitions, the
main approaches to discover dynamic communities, as well as the assessment of
the significance of clusterings. In Section V we indicate where to find useful
software. The concluding remarks of Section VI close the work.

##  II What are communities?

###  II.1 Variables

We start with a subgraph ${C}$ of a graph ${G}$. The number of vertices and
edges are $n$, $m$ for ${G}$ and $n_{C}$, $m_{C}$ for ${C}$, respectively. The
adjacency matrix of $G$ is $A$, its element $A_{ij}$ equals $1$ if vertices
$i$ and $j$ are neighbours, otherwise it equals $0$. We assume that the
subgraph is connected because communities usually are222The variables defined
in this section hold for any subgraph, connected or not.. Other types of group
structures do not require connectedness (Section II.3).

The subgraph is schematically illustrated in Fig. 3.

Figure 3: Schematic picture of a connected subgraph.

Its vertices are enclosed by the dashed contour. The magenta dots are the
external vertices connected to the subgraph, while the black ones are the
remaining vertices of the network. The blue lines indicate the edges
connecting the subgraph to the rest of the network.

The internal and external degree $k_{i}^{int}$ and $k_{i}^{ext}$ of a vertex
$i$ of the network with respect to subgraph ${C}$ are the number of edges
connecting $i$ to vertices of ${C}$ and to the rest of the graph,
respectively. Both definitions can be expressed in compact form via the
adjacency matrix $A$: $k^{int}_{i}=\sum_{j\in C}A_{ij}$ and
$k^{ext}_{i}=\sum_{j\notin C}A_{ij}$, where the sums run over all vertices $j$
inside and outside $C$, respectively. Naturally, the degree $k_{i}$ of $i$ is
the sum of $k_{i}^{int}$ and $k_{i}^{ext}$: $k_{i}=\sum_{j}A_{ij}$. If
$k_{i}^{ext}=0$ and $k_{i}^{int}>0$ $i$ has neighbours only within ${C}$ and
is an internal vertex of ${C}$ (dark green dots in the figure). If
$k_{i}^{ext}>0$ and $k_{i}^{int}>0$ $i$ has neighbours outside ${C}$ and is a
boundary vertex of ${C}$ (bright green dots in the figure). If
$k_{i}^{int}=0$, instead, the vertex is disjoint from ${C}$. The embeddedness
$\xi_{i}$ is the ratio between the internal degree and the degree of vertex
$i$: $\xi_{i}=k_{i}^{int}/k_{i}$. The larger $\xi_{i}$, the stronger the
relationship between the vertex and its community. The mixing parameter
$\mu_{i}$ is the ratio between the external degree and the degree of vertex
$i$: $\mu_{i}=k_{i}^{ext}/k_{i}$. By definition, $\mu_{i}=1-\xi_{i}$.

Now we present a number of variables related to the subgraph as a whole. We
distinguish them in three classes.

The first class comprises measures based on internal connectedness, i. e., on
how cohesive the subgraph is. The main variables are:

  * •

Internal degree $k^{int}_{C}$. The sum of the internal degrees of the vertices
of ${C}$. It equals twice the number $m_{C}$ of internal edges, as each edge
contributes two units of degree. In matrix form, $k^{int}_{C}=\sum_{i,j\in
C}A_{ij}$.

  * •

Average internal degree $k^{avg\mbox{-}int}_{C}$. Average degree of vertices
of ${C}$, considering only internal edges: $k^{avg-
int}_{C}=k^{int}_{C}/n_{C}$.

  * •

Internal edge density $\delta^{int}_{C}$. The ratio between the number of
internal edges of ${C}$ and the number of all possible internal edges:

$\delta^{int}_{C}=\frac{k^{int}_{C}}{n_{C}(n_{C}-1)}.$ (1)

We remark that $n_{C}(n_{C}-1)/2$ is the maximum number of internal edges that
a simple graph with $n_{C}$ vertices may have333A simple graph has at most one
edge running between any pair of vertices and no self-loops, i. e., no edges
connecting a vertex to itself..

The second class includes measures based on external connectedness, i. e., on
how embedded the subgraph is in the network or, equivalently, how separated
the subgraph is from it. The main variables are:

  * •

External degree, or cut, $k^{ext}_{C}$. The sum of the external degrees of the
vertices of ${C}$. It gives the number of external edges of the subgraph (blue
lines in Fig. 3). In matrix form, $k^{ext}_{C}=\sum_{i\in C,j\notin C}A_{ij}$.

  * •

Average external degree, or expansion, $k^{avg\mbox{-}ext}_{C}$. Average
degree of vertices of ${C}$, considering only external edges: $k^{avg-
ext}_{C}=k^{ext}_{C}/n_{C}$.

  * •

External edge density, or cut ratio, $\delta^{ext}_{C}$. The ratio between the
number of external edges of ${C}$ and the number of all possible external
edges:

$\delta^{ext}_{C}=\frac{k^{ext}_{C}}{n_{C}(n-n_{C})}.$ (2)

Unweighted networks | Weighted networks
---|---
Name | Symbol | Definition | Name | Symbol | Definition
Internal degree | $k^{int}_{i}$ | $\sum_{j\in C}A_{ij}$ | Internal strength | $w^{int}_{i}$ | $\sum_{j\in C}W_{ij}$
External degree | $k^{ext}_{i}$ | $\sum_{j\notin C}A_{ij}$ | External strength | $w^{ext}_{i}$ | $\sum_{j\notin C}W_{ij}$
Degree | $k_{i}$ | $\sum_{j}A_{ij}$ | Strength | $w_{i}$ | $\sum_{j}W_{ij}$
Embeddedness | $\xi_{i}$ | $\frac{k^{int}_{i}}{k_{i}}$ | Weighted embeddedness | $\xi^{w}_{i}$ | $\frac{w^{int}_{i}}{w_{i}}$
Mixing parameter | $\mu_{i}$ | $\frac{k^{ext}_{i}}{k_{i}}$ | Weighted mixing parameter | $\mu^{w}_{i}$ | $\frac{w^{ext}_{i}}{w_{i}}$
Table 1: Basic vertex community variables, for unweighted and weighted
networks. $A$ and $W$ are the adjacency and the weight matrix, respectively.

| Unweighted networks | Weighted networks
---|---|---
| Name | Symbol | Definition | Name | Symbol | Definition
| Internal degree | $k^{int}_{C}$ | $\sum_{i,j\in C}A_{ij}$ | Internal strength | $w^{int}_{C}$ | $\sum_{i,j\in C}W_{ij}$
| Average internal degree | $k^{avg\mbox{-}int}_{C}$ | $\frac{k^{int}_{C}}{n_{C}}$ | Average internal strength | $w^{avg\mbox{-}int}_{C}$ | $\frac{w^{int}_{C}}{n_{C}}$
Internal | Internal edge density | $\delta^{int}_{C}$ | $\frac{k^{int}_{C}}{n_{C}(n_{C}-1)}$ | Internal weight density | $\delta^{int}_{w,C}$ | $\frac{w^{int}_{C}}{\bar{w}n_{C}(n_{C}-1)}$
| External degree | $k^{ext}_{C}$ | $\sum_{i\in C,j\notin C}A_{ij}$ | External strength | $w^{ext}_{C}$ | $\sum_{i\in C,j\notin C}W_{ij}$
| Average external degree | $k^{avg\mbox{-}ext}_{C}$ | $\frac{k^{ext}_{C}}{n_{C}}$ | Average external strength | $w^{avg\mbox{-}ext}_{C}$ | $\frac{w^{ext}_{C}}{n_{C}}$
External | External edge density | $\delta^{ext}_{C}$ | $\frac{k^{ext}_{C}}{n_{C}(n-n_{C})}$ | External weight density | $\delta^{ext}_{w,C}$ | $\frac{w^{ext}_{C}}{\bar{w}n_{C}(n-n_{C})}$
| Total degree | $k_{C}$ | $\sum_{i\in C,j}A_{ij}$ | Total strength | $w_{C}$ | $\sum_{i\in C,j}W_{ij}$
| Average degree | $k^{avg}_{C}$ | $\frac{k_{C}}{n_{C}}$ | Average strength | $w^{avg}_{C}$ | $\frac{w_{C}}{n_{C}}$
Total | Conductance | $C_{C}$ | $\frac{k^{ext}_{C}}{k_{C}}$ | Weighted conductance | $C_{w,C}$ | $\frac{w^{ext}_{C}}{w_{C}}$
Table 2: Basic community variables, for unweighted and weighted networks. $A$
and $W$ are the adjacency and the weight matrix, respectively, $n_{C}$ the
number of vertices of the community, $n$ the total number of vertices of the
graph, $\bar{w}$ the average weight of the network edges.

Finally, we have hybrid measures, combining internal and external
connectedness. Notable examples are:

  * •

Total degree, or volume, $k_{C}$. The sum of the degrees of the vertices of
${C}$. Naturally, $k_{C}=k^{int}_{C}+k^{ext}_{C}$. In matrix form,
$k_{C}=\sum_{i\in C,j}A_{ij}$.

  * •

Average degree $k^{avg}_{C}$. Average degree of vertices of ${C}$:
$k^{avg}_{C}=k_{C}/n_{C}$.

  * •

Conductance $C_{C}$. The ratio between the external degree and the total
degree of ${C}$:

$C_{C}=\frac{k^{ext}_{C}}{k_{C}}.$ (3)

All definitions we have given hold for the case of undirected and unweighted
networks. The extension to weighted graphs is straightforward, as it suffices
to replace the “number of edges” with the sum of the weights carried by every
edge. For instance, the internal degree $k_{v}^{int}$ of a vertex $v$ becomes
the internal strength $w_{v}^{int}$, which is the sum of the weights of the
edges joining $v$ with the vertices of subgraph $C$. For the internal and
external edge densities of Eqs. (1) and (2) one would have to replace the
numerators with their weighted counterparts and multiply the denominators by
the average edge weight $\bar{w}=\sum_{ij}W_{ij}/2m$, where $W_{ij}$ is the
element of the weight matrix, indicating the weight of the edge joining
vertices $i$ and $j$ ($W_{ij}=0$ if $i$ and $j$ are disconnected) and $m$ the
total number of graph edges. In Tables 1 and 2 we list all variables we have
presented along with their extensions to the case of weighted networks. In
directed networks one would have to distinguish between incoming and outgoing
edges. Extensions of the metrics are fairly simple to implement, though their
usefulness is unclear.

###  II.2 Classic view

Figure 4 shows how scholars usually envision community structure. The network
has three clusters and in each cluster the density of edges is comparatively
higher than the density of edges between the clusters. This can be summarised
by saying that communities are dense subgraphs which are well separated from
each other. This view has been challenged, recently Leskovec _et al._ (2009);
Jeub _et al._ (2015), as we shall see in Section III.5. Communities may
overlap as well, sharing some of the vertices. For instance, in social
networks individuals can belong to different circles at the same time, like
family, friends, work colleagues. Figure 5 shows an example of a network with
overlapping communities. Communities are typically supposed to be overlapping
at their boundaries, as in the figure. Recent results reveal a different
picture, though Yang and Leskovec (2014) (Section III.5). A subdivision of a
network into overlapping communities is called cover and one speaks of soft
clustering, as opposed to hard clustering, which deals with divisions into
non-overlapping groups, called partitions. The generic term clustering can be
used to indicate both types of subdivisions. Covers can be crisp, when shared
vertices belong to their communities with equal strength, or fuzzy, when the
strength of their membership can be different in different clusters444In the
literature the word fuzzy is often used to describe both situations..

Figure 4: Classic view of community structure. Schematic picture of a network
with three communities. Figure 5: Overlapping communities. A network is
divided in four communities, enclosed by the dashed contours. Three of them
share boundary vertices, indicated by the blue dots.

The oldest definitions of community-like objects were proposed by social
network analysts and focused on the internal cohesion among vertices of a
subgraph Wasserman and Faust (1994); Scott (2000); Moody and White (2003). The
most popular concept is that of clique Luce and Perry (1949). A clique is a
complete graph, that is, a subgraph such that each of its vertices is
connected to all the others. It is also a maximal subgraph, meaning that it is
not included in a larger complete subgraph. In modern network science it is
common to call clique any complete graph, not necessarily maximal. Triangles
are the simplest cliques. Finding cliques is an NP-complete problem Bomze _et
al._ (1999); a popular technique is the Bron–Kerbosch method Bron and Kerbosch
(1973).

The notion of cliques, albeit useful, cannot be considered a good candidate
for a community definition. While a clique has the largest possible internal
edge density, as all internal edges are present, communities are not complete
graphs, in general. Moreover, all vertices have identical role in a clique,
while in real network communities some vertices are more important than
others, due to their heterogeneous linking patterns. Therefore, in social
network analysis the notion has been relaxed, generating the related concepts
of n-cliques Luce (1950); Alba (1973), n-clans and n-clubs Mokken (1979).
Other definitions are based on the idea that a vertex must be adjacent to some
minimum number of other vertices in the subgraph. A $k$-plex is a maximal
subgraph in which each vertex is adjacent to all other vertices of the
subgraph except at most $k$ of them Seidman and Foster (1978). Details on the
above definitions can be found in specialised books Wasserman and Faust
(1994); Scott (2000).

For a proper community definition, one should take into account both the
internal cohesion of the candidate subgraph and its separation from the rest
of the network. A simple idea that has received a great popularity is that a
community is a subgraph such that “the number of internal edges is larger than
the number of external edges”555Here we focus on the case of unweighted
graphs, extensions of all definitions to the weighted case are immediate..
This idea has inspired the following definitions. An $LS$-set Luccio and Sami
(1969), or strong community Radicchi _et al._ (2004), is a subgraph such that
the internal degree of each vertex is greater than its external degree. A
relaxed condition is that the internal degree of the subgraph exceeds its
external degree [weak community Radicchi _et al._ (2004)]666The definition of
weak community is the natural implementation of the naïve expectation that
there must be more edges inside than outside. However, for a subgraph ${C}$ to
be a weak community it is not necessary that the number of internal edges
$m_{C}$ exceeds that of external edges $k^{ext}_{C}$. Since the internal
degree $k^{int}_{C}=2m_{C}$ (Section II.1) the actual condition is
$2m_{C}>k^{ext}_{C}$.. A strong community is also a weak community, while the
converse is not generally true.

A drawback of these definitions is that one separates the subgraph at study
from the rest of the network, which is taken as a single object. But the
latter can be in turn divided into communities. If a subgraph ${C}$ is a
proper community, it makes sense that each of its vertices is more strongly
attached to the vertices of ${C}$ than to the vertices of any other subgraph.
This concept, proposed by Hu et al. Hu _et al._ (2008), is more in line
(though not entirely) with the modern idea of community that we discuss in the
following section. It has generated two alternative definitions of strong and
weak community. A subgraph ${C}$ is a strong community if the internal degree
of any vertex within ${C}$ exceeds the internal degree of the vertex within
any other subgraph, i. e., the number of edges joining the vertex to those of
the subgraph; likewise, a community is weak if its internal degree exceeds the
(total) internal degree of its vertices within every other community. A strong
(weak) community à la Radicchi et al. is a strong (weak) community also in the
sense of Hu et al.. The opposite is not true, in general (Fig. 6). In
particular, a subgraph can be a strong community in the sense of Hu et al.
even though all of its vertices have internal degree smaller than their
respective external degree.

Figure 6: Strong and weak communities. The four subgraphs enclosed in the
contours are weak communities according to the definitions of Radicchi et al.
Radicchi _et al._ (2004) and Hu et al. Hu _et al._ (2008). They are also
strong communities according to Hu et al., as the internal degree of each
vertex exceeds the number of edges joining the vertex with the vertices of
every other subgraph. However, three of the subgraphs are not strong
communities according to Radicchi et al., as some vertices (indicated in blue)
have external degree larger than their internal degree (the internal and
external edges of these vertices are coloured in yellow and magenta,
respectively).

The above definitions of communities use extensive variables: their value
tends to be the larger, the bigger the community (e. g., the internal and
external degrees). But there are also variables discounting community size. An
example is the internal cluster density $\delta_{int}({C})$ of Eq. (1). One
could assume that a subgraph ${C}$ with $k$ vertices is a cluster if
$\delta_{int}({C})$ is larger than a threshold $\xi$. Setting the size of the
subgraph is necessary because otherwise any clique would be among the best
possible communities, including trivial two-cliques (simple edges) or
triangles.

###  II.3 Modern view

As we have seen in the previous section, traditional definitions of community
rely on counting edges (internal, external), in various ways. But what one
should be really focusing on is the probability that vertices share edges with
a subgraph. The existence of communities implies that vertices interact more
strongly with the other members of their community than they do with vertices
of the other communities. Consequently, there is a preferential linking
pattern between vertices of the same group. This is the reason why edge
densities end up being higher within communities than between them. We can
formulate that by saying that vertices of the same community have a higher
probability to form edges with their partners than with the other vertices.

Let us suppose that we estimated the edge probabilities between all pairs of
vertices, somehow. We can define the groups by means of those probabilities.
It is a scenario similar to the classic one we have seen in Section II.2,
where we add and compare probabilities, instead of edges. Natural definitions
of strong and weak community are:

  * •

A strong community is a subgraph each of whose vertices has a higher
probability to be linked to every vertex of the subgraph than to any other
vertex of the graph.

  * •

A weak community is a subgraph such that the average edge probability of each
vertex with the other members of the group exceeds the average edge
probability of the vertex with the vertices of any other group777Since we are
comparing average probabilities, which come with a standard error, the
definition of weak community should not rely on the simple numeric inequality
between the averages, but on the statistical significance of their difference.
Significance will be discussed in Section IV.9..

The difference between the two definitions is that, in the concept of strong
community, the inequality between edge probabilities holds at the level of
every pair of vertices, while in the concept of weak community the inequality
holds only for averages over groups. Therefore, a strong community is also a
weak community, but the opposite is not true, in general.

Now we can see why the former definitions of strong and weak community
Radicchi _et al._ (2004); Hu _et al._ (2008) are not satisfactory. Suppose to
have a network with two subgraphs $A$ and $B$ of very different sizes, say
with $n_{A}$ and $n_{B}\gg n_{A}$ vertices (Fig. 7).

Figure 7: Problems of the classic notions of strong and weak communities. A
network is generated by the illustrated model, with two subgraphs $A$ and $B$
and edge probabilities $p_{in}$ between vertices of the subgraphs and
$p_{out}<p_{in}$ between vertices of $A$ and $B$. The red circle is a
representative vertex of subgraph $A$, the smaller blue circle represents the
rest of the vertices of $A$. The subgraphs are both strong and weak
communities in the probabilistic sense, but they may be neither strong nor
weak communities according to the classic definitions by Radicchi et al.
Radicchi _et al._ (2004) and Hu et al. Hu _et al._ (2008), if $B$ is
sufficiently larger than $A$.

The network is generated by a model where the edge probability is $p_{in}$
between vertices of the same group and $p_{out}<p_{in}$ for vertices of
different groups. The two subgraphs are communities both in the strong and in
the weak sense, according to the probability-based definitions above. The
expected internal degree of a vertex of $A$ is $k_{A}^{int}=p_{in}n_{A}$:
since there are $n_{A}$ possible internal neighbours888The number of possible
community neighbours should actually be $n_{A}-1$, but for simplicity one
allows for the formation of self-edges, from a vertex to itself. Results
obtained with and without self-edges are basically undistinguishable, when
community sizes are much larger than one. We shall stick to this setup
throughout the paper.. Likewise, the expected external degree of a vertex of
$A$ is $k_{A}^{ext}=p_{out}n_{B}$. The expected internal and external degrees
of $A$ are $K_{A}^{int}=p_{in}n^{2}_{A}$ and $K_{A}^{ext}=p_{out}n_{A}n_{B}$.
For any two values of $p_{in}$ and $p_{out}<p_{in}$ one can always choose
$n_{B}$ sufficiently larger than $n_{A}$ that $k_{A}^{int}<k_{A}^{ext}$, which
also implies that $K_{A}^{int}<K_{A}^{ext}$. In this setting the subgraphs are
neither strong nor weak communities, according to the definitions proposed by
Radicchi et al. and Hu et al..

How can we compute the edge probabilities between vertices? This is still an
ill-defined problem, unless one has a model stating how edges are formed. One
can make many hypotheses on the process of edge formation.

(a) Community structure

(b) Disassortative structure

(c) Core-periphery structure

(d) Random graph

Figure 8: Stochastic block model. We show the schematic adjacency matrices of
network realisations produced by the model for special choices of the edge
probabilities, along with one representative realisation for each case. For
simplicity we show the case of two blocks of equal size. Darker blocks
indicate higher edge probabilities and consequently a larger density of edges
inside the block. Figure 8a illustrates community (or assortative) structure:
the probabilities (link densities) are much higher inside the diagonal blocks
than elsewhere. Figure 8b shows the opposite situation (disassortative
structure). Figure 8c illustrates a core-periphery structure. Figure 8d shows
a random graph à la Erdős and Rényi: all edge probabilities are identical,
inside and between the blocks, so there are no actual groups. Adapted figure
with permission from Jeub _et al._ (2015). © 2015, by the American Physical
Society.

For instance, if we take social networks, we can assume that the probability
that two individuals know each other is a decreasing function of their
geographical distance, on average Liben-Nowell _et al._ (2005). Each set of
assumptions defines a model. For our purposes, eligible models should take
into account the possible presence of groups of vertices, that behave
similarly.

The most famous model of networks with group structure is the stochastic block
model (SBM) Fienberg and Wasserman (1981); Holland _et al._ (1983); Snijders
and Nowicki (1997). Suppose we have a network with $n$ vertices, divided in
$q$ groups. The group of vertex $i$ is indicated with the integer label
$g_{i}=1,2,\dots,q$. The idea of the model is very simple: the probability
$P(i\leftrightarrow j)$ that vertices $i$ and $j$ are connected depends
exclusively on their group memberships: $P(i\leftrightarrow
j)=p_{g_{i}g_{j}}$. Therefore, it is identical for any $i$ and $j$ in the same
groups. The probabilities $p_{g_{i}g_{j}}$ form a $q\times q$ symmetric
matrix999For directed graphs, the matrix is in general asymmetric. The
extension of the stochastic block model to directed graphs is straightforward.
Here we focus on undirected graphs., called the stochastic block matrix. The
diagonal elements $p_{kk}$ ($k=1,2,\dots,q$) of the stochastic block matrix
are the probabilities that vertices of block $k$ are neighbours, whereas the
off-diagonal elements give the edge probabilities between different
blocks101010In another definition of SBM the number of edges $e_{rs}$ between
blocks $r$ and $s$ is fixed ($r,s=1,2,\dots,q$), instead of the edge
probabilities. If $e_{rs}\gg 1,\forall\,r,s=1,2,\dots,q$ the two models are
fully equivalent if the edge probabilities $p_{rs}$ are chosen such that the
expected number of edges running between $r$ and $s$ coincides with $e_{rs}$..

For $p_{kk}>p_{lm},\forall k,l,m=1,2,\dots,q$, with $l\neq m$, we recover
community structure, as the probabilities that vertices of the same group are
connected exceed the probabilities that vertices of different groups are
joined (Fig. 8a). It is also called assortative structure, as it privileges
bonds between vertices of the same group. The model is very versatile, though,
and can generate various types of group structure. For $p_{kk}<p_{lm},\forall
k,l,m=1,2,\dots,q$, with $l\neq m$, we have disassortative structure, as edges
are more likely between the blocks than inside them (Fig. 8b). In the special
case in which $p_{kk}=0,\forall k=1,2,\dots,q$ we recover multipartite
structure, as there are edges only between the blocks. If $q=2$, $p_{11}\gg
p_{12}\gg p_{22}$, we have core-periphery structure: the vertices of the first
block (core) are relatively well-connected amongst themselves as well as to a
peripheral set of vertices that interact very little amongst themselves (Fig.
8c). If all probabilities are equal, $p_{ij}=p$, $\forall i,j$, we recover the
classic random graph à la Erdős and Rényi Erdös and Rényi (1959, 1960) (Fig.
8d). Here any two vertices have identical probability of being connected,
hence there is no group structure. This has become a fundamental axiom in
community detection, and has inspired some popular techniques like, e. g.,
modularity optimisation Newman and Girvan (2004); Newman (2004b) (Section
IV.6). Random graphs of this type are also useful in the validation of
clustering algorithms (Section III.1).

Alternative community definitions are based on the interplay between network
topology and dynamics. Diffusion is the most used dynamics. Random walks are
the simplest diffusion processes. A simple random walk is a path such that the
vertex reached at step $t$ is a random neighbour of the vertex reached at step
$t-1$. A random walker would be spending a long time within communities, due
to the supposedly low number of routes taking out of them Rosvall and
Bergstrom (2008); Delvenne _et al._ (2010); Rosvall _et al._ (2014). The
evolution of random walks does not depend solely on the number or density of
edges, in general, but also on the structure and distribution of paths formed
by consecutive edges, as paths are the routes that walkers can follow. This
means that random walk dynamics relies on higher-order structures than simple
edges, in general. Such relationship is even more pronounced when one
considers Markov dynamics of second order or higher, in which the probability
of reaching a vertex at step $t+1$ of the walk does not depend only on where
the walker sits at step $t$, but also on where it was at step $t-1$ and
possibly earlier Rosvall _et al._ (2014); Persson _et al._ (2016). Indeed, one
could formulate the network clustering problem by focusing on higher order
structures, like motifs (e. g., triangles) Arenas _et al._ (2008a); Serrour
_et al._ (2011); Benson _et al._ (2016). The advantage is that one can
preserve more complex features of the network and its communities, which
typically get lost when one uses network models solely based on edge
probabilities, like SBMs111111Since edges are usually placed independently of
each other in SBMs, higher order structures like triangles are usually
underrepresented in the model graphs with respect to the actual graph at
study.. The drawback is that calculations become more involved and lengthy.

Is a definition of community really necessary? Actually not, most techniques
to detect communities in networks do not require a precise definition of
community. The problem can be attacked from many angles. For instance, one can
remove the edges separating the clusters from each other, that can be
identified via some particular feature Girvan and Newman (2002); Radicchi _et
al._ (2004). But defining clusters beforehand is a useful starting point, that
allows one to check the reliability of the final results.

##  III Validation

In this section we will discuss the crucial issue of validation of clustering
algorithms. Validation usually means checking how precisely algorithms can
recover the communities in benchmark networks, whose community structure is
known. Benchmarks can be computer-generated, according to some model, or
actual networks, whose group structure is supposed to be known via non-
topological features (metadata). The lack of a universal definition of
communities makes the search for benchmarks rather arbitrary, in principle.
Nevertheless, the best known artificial benchmarks are based on the modern
definition of clusters presented in Section II.3.

We shall present some popular artificial benchmarks and show that partition
similarity measures have to be handled with care. We will see under which
conditions communities are detectable by methods, and expose the interplay
between topological information and metadata. We will conclude by presenting
some recent results on signatures of community structure extracted from real
networks.

###  III.1 Artificial benchmarks

Figure 9: Benchmark of Girvan and Newman. The three networks correspond to
realisations of the model for $\langle k_{out}\rangle=1$ (a), $\langle
k_{out}\rangle=5$ (b) and $\langle k_{out}\rangle=8$ (c). In (c) the four
groups are hardly distinguishable by eye and methods fail to assign many
vertices to their groups. Reprinted figure with permission from Ref. Guimerà
and Amaral (2005). © 2005, by the Nature Publishing Group.

The principle underneath stochastic block models (Section II.3) has inspired
many popular benchmark graphs with group structure. Community structure is
recovered in the case in which the probability for two vertices to be joined
is larger for vertices of the same group than for vertices of different groups
(Fig. 8a). For simplicity, let us suppose that there are only two values of
the edge probability, $p_{in}$ and $p_{out}<p_{in}$, for edges within and
between communities, respectively. Furthermore, we assume that all communities
have identical size $n_{c}$, so $qn_{c}=n$, where $q$ is the number of
communities. In this version, the model coincides with the planted l-partition
model, introduced in the context of graph partitioning121212Graph partitioning
means dividing a graph in subgraphs, such to minimise the number of edges
joining the subgraphs to each other. It is related to community detection, as
it aims at finding the minimum separation between the parts. However, it
usually does not consider how cohesive the parts are (number or density of
internal edges), except when special measures are used, like conductance [Eq.
(3)]. Bui _et al._ (1987); Dyer and Frieze (1989); Condon and Karp (2001). The
expected internal and external degrees of a vertex are $\langle
k_{in}\rangle=p_{in}n_{c}$ and $\langle k_{out}\rangle=p_{out}n_{c}(q-1)$,
respectively, yielding an expected (total) vertex degree $\langle
k\rangle=\langle k_{in}\rangle+\langle
k_{out}\rangle=p_{in}n_{c}+p_{out}n_{c}(q-1)$.

Girvan and Newman Girvan and Newman (2002) set $q=4$, $n_{c}=32$ (for a total
number of vertices $n=128$) and fixed the average total degree $\langle
k\rangle$ to $16$. This implies that $p_{in}+3p_{out}=1/2$ and $p_{in}$ and
$p_{out}$ are not independent parameters. The benchmark by Girvan and Newman
is still the most popular in the literature (Fig. 9).

Performance plots of clustering algorithms typically have, on the horizontal
axis, the expected external degree $\langle k_{out}\rangle$. For low values of
$\langle k_{out}\rangle$ communities are well separated131313They are also
more cohesive internally, since $\langle k_{in}\rangle$ is higher, to keep the
total degree constant. and most algorithms do a good job at detecting them. By
increasing $\langle k_{out}\rangle$, the performance declines. Still, one
expects to do better than by assigning memberships to the vertices at random,
as long as $p_{in}>p_{out}$, which means for $\langle k_{out}\rangle<12$. In
Section III.3 we will see that the actual threshold is lower, due to random
fluctuations.

The benchmark by Girvan and Newman, however, is not a good proxy of real
networks with community structure. For one thing, all vertices have equal
degree, whereas the degree distribution of real networks is usually highly
heterogeneous Albert _et al._ (1999). In addition, most clustering techniques
find skewed distributions of community sizes Palla _et al._ (2005); Newman
(2004a); Danon _et al._ (2007); Clauset _et al._ (2004); Radicchi _et al._
(2004); Lancichinetti _et al._ (2010). For this reason, Lancichinetti,
Fortunato and Radicchi proposed the LFR benchmark, having power-law
distributions of degree and community size Lancichinetti _et al._ (2008) (Fig.
10).

Figure 10: LFR benchmark. Vertex degree and community size are power-law
distributed, to account for the heterogeneity observed in real networks with
community structure.

The mixing parameters $\mu_{i}$ of the vertices (Section II.1) are set equal
to a constant $\mu$, which estimates the quality of the partition141414The
parameter $\mu$ is actually only the average of the mixing parameter over all
vertices. In fact, since degrees are integer, it is impossible to tune them
such to have exactly the same value of $\mu$ for each vertex, and keep the
constraint on the degree distribution at the same time.. LFR benchmark
networks are built by joining stubs at random, once one has established which
stubs are internal and which ones are external with respect to the community
of the vertex attached to the stubs. In this respect, it is basically a
configuration model Bollobás (1980); Molloy and Reed (1995) with built-in
communities.

Clearly, when $\mu$ is low, clusters are better separated from each other, and
easier to detect. When $\mu$ grows, performance starts to decline. But for
which range of $\mu$ can we expect a performance better than random guessing?
Let us suppose that the group structure is detectable for $\mu\in[0,\mu_{c}]$.
The upper limit $\mu_{c}$ should be such that the network is random for
$\mu=\mu_{c}$. The network is random when stubs are combined at random,
without distinguishing between internal and external stubs, which yields the
standard configuration model. There the expected number of edges between two
vertices with degrees $k_{i}$ and $k_{j}$ is $k_{i}k_{j}/(2m)$, $m$ being the
total number of network edges. Let us focus on a generic vertex $i$, belonging
to community $C$. We denote with $K_{C}$ and $\tilde{K}_{C}$ the sum of the
degrees of the vertices inside and outside $C$, respectively. Clearly
$K_{C}+\tilde{K}_{C}=2m$. In a random graph built with the configuration
model, vertex $i$ would have an expected internal degree151515The
approximation is justified when the community is large enough that $K_{C}\gg
k_{i}$. $k_{i}^{int\mbox{-}rand}=k_{i}(K_{C}-k_{i})/(2m)\approx
k_{i}K_{C}/(2m)$ and an expected external degree
$k_{i}^{ext\mbox{-}rand}=k_{i}\tilde{K}_{C}/(2m)$. Since, by construction,
$k_{i}^{int}=(1-\mu)k_{i}$ and $k_{i}^{ext}=\mu k_{i}$, the community $C$ is
not real when $k_{i}^{ext}=k_{i}^{ext\mbox{-}rand}$ and
$k_{i}^{int}=k_{i}^{int\mbox{-}rand}$, which implies
$\mu=\mu_{C}=\tilde{K}_{C}/(2m)=1-K_{C}/(2m)$. We see that $K_{C}$ depends on
the community $C$: the larger the community, the lower the threshold is.
Therefore, not all clusters are detectable at the same time, in general. For
this to happen, $\mu$ must be lower than the minimum of $\mu_{C}$ over all
communities: $\mu\leq\mu_{c}=\min_{C}\mu_{C}$. If communities are all much
smaller than the network as a whole, $K_{C}/(2m)\approx 0$ and $\mu_{c}$ could
get very close to the upper limit $1$ of the variable $\mu$. However, it is
possible that the actual threshold is lower than $\mu_{c}$, due to the
perturbations of the group structure induced by random fluctuations (Section
III.3). Anyway, in most cases the threshold is going to be quite a bit higher
than $1/2$, the value which is mistakenly considered as the threshold by some
scholars.

The LFR benchmark turns out to be a special version of the recently introduced
degree-corrected stochastic block model Karrer and Newman (2011), with the
degree and the block size distributed according to truncated power
laws161616In fact, the correspondence is exact for a slightly different
parametrisation of the benchmark, introduced in Peixoto (2014). In this
version of the model, instead of the mixing parameter $\mu$, which is local, a
global parameter $c$ is used, estimating how strong the community structure
is..

The LFR benchmark has been extended to directed and weighted networks with
overlapping communities Lancichinetti and Fortunato (2009). The extensions to
directed and weighted graphs are rather straightforward. Overlaps are obtained
by assigning each vertex to a number of clusters and distributing its internal
edges equally among them171717A better way to do it would be taking into
account the size of the communities the vertex is assigned to, and divide the
edges proportionally to the (total) degrees of the communities.. Recently,
another benchmark with overlapping communities has been introduced by Ball,
Karrer and Newman Ball _et al._ (2011). It consists of two clusters $A$ and
$B$, with overlap $C$. Vertices in the non-overlapping subsets $A-C$ and $B-C$
set edges only between each other, while vertices in $C$ are connected to
vertices of both $A$ and $B$. The expected degree of all vertices is set equal
to $\langle k\rangle$. The authors considered various settings, by tuning
$\langle k\rangle$, the size of the overlap and the sizes of $A$ and $B$,
which may be uneven. However, the fact that all vertices have equal degree (on
average) makes the model less realistic and flexible than the LFR benchmark.

Following the increasing availability of evolving time-stamped network data
sets, the analysis and modelling of temporal networks have received a lot of
attention lately Holme and Saramäki (2012). In particular, scholars have
started to deal with the problem of detecting evolving communities (Section
IV.8). A benchmark designed to model dynamic communities was proposed by
Granell et al. Granell _et al._ (2015). It is based on the planted
$l$-partition model, just like the benchmark of Girvan and Newman, where
$p_{in}$ and $p_{out}<p_{in}$ are the edge probabilities within communities
and between communities, respectively. Communities may grow and shrink (Fig.
11a), they may merge with each other or split into smaller clusters (Fig.
11b), or do all of the above (Fig. 11c). The dynamics unfold such that at each
time the subgraphs are proper communities in the probabilistic sense discussed
in Section II.3. In the merge-split dynamics, clusters actually merge before
the inter-community edge probability $p_{out}$ reaches the value $p_{in}$ of
the intra-community edge probability, due to random fluctuations (Section
III.3).

Figure 11: Dynamic benchmark. (a) Grow-Shrink benchmark. Starting from two
communities of equal size, vertices move from one cluster to the other and
back. (b) Merge-Split benchmark. It starts with two communities, edges are
added until there is one community with uniform link density (merge), then the
process is reversed, leading to a fragmentation into two equal-sized clusters.
(c) Mixed benchmark. There are four communities: the upper pair undergoes the
grow-shrink dynamics of (a), the lower pair the merge-split dynamics of (b).
All processes are periodic with period $\tau$. Reprinted figure with
permission from Granell _et al._ (2015). © 2015, by the American Physical
Society.

In Section II.3 we have shown why random graphs cannot have a meaningful group
structure181818Here we refer to random graphs where the edge probabilities do
not depend on their membership in groups. Examples are Erdős and Rényi random
graphs, the configuration model, etc... That means that they can be employed
as null benchmarks, to test whether algorithms are capable to recognise the
absence of groups. Many methods find non-trivial communities in such random
networks, so they fail the test. We strongly encourage doing this type of exam
on new algorithms Lancichinetti and Fortunato (2009).

###  III.2 Partition similarity measures

The accuracy of clustering techniques depends on their ability to detect the
clusters of networks, whose community structure is known. That means that the
partition detected by the method(s) has to match closely the planted partition
of the network. How can the similarity of partitions be computed? This is an
important problem, with no unique solution. In this section we discuss some
issues about partition similarity measures. More information can be found in
Meilă (2007), Fortunato (2010) and Traud _et al._ (2011).

Let us consider two partitions ${\cal X}=(X_{1},X_{2},...,X_{q_{X}})$ and
${\cal Y}=(Y_{1},Y_{2},...,Y_{q_{Y}})$ of a network $G$, with $q_{X}$ and
$q_{Y}$ clusters, respectively. Let $n$ be the total number of vertices,
$n_{i}^{X}$ and $n_{j}^{Y}$ the number of vertices in clusters $X_{i}$ and
$Y_{j}$ and $n_{ij}$ the number of vertices shared by clusters $X_{i}$ and
$Y_{j}$: $n_{ij}=|X_{i}\bigcap Y_{j}|$. The $q_{X}\times q_{Y}$ matrix
$N_{{\cal XY}}$ whose entries are the overlaps $n_{ij}$ is called confusion
matrix, association matrix or contingency table.

Most similarity measures can be divided in three categories: measures based on
pair counting, cluster matching and information theory.

Pair counting means computing the number of pairs of vertices which are
classified in the same (different) clusters in the two partitions. Let
$a_{11}$ indicate the number of pairs of vertices which are in the same
community in both partitions, $a_{01}$ ($a_{10}$) the number of pairs of
elements which are in the same community in ${\cal X}$ (${\cal Y}$) and in
different communities in ${\cal Y}$ (${\cal X}$) and $a_{00}$ the number of
pairs of vertices that are in different communities in both partitions.
Several measures can be defined by combining the above numbers in various
ways. A famous example is the Rand index Rand (1971)

$R({\cal X},{\cal Y})=\frac{a_{11}+a_{00}}{a_{11}+a_{01}+a_{10}+a_{00}},$ (4)

which is the ratio of the number of vertex pairs correctly classified in both
partitions (i. e. either in the same or in different clusters), by the total
number of pairs. Another notable option is the Jaccard index Ben-Hur _et al._
(2001),

$J({\cal X},{\cal Y})=\frac{a_{11}}{a_{11}+a_{01}+a_{10}},$ (5)

which is the ratio of the number of vertex pairs classified in the same
cluster in both partitions, by the number of vertex pairs classified in the
same cluster in at least one partition. The Jaccard index varies over a
broader range than the Rand index, due to the dominance of $a_{00}$ in
$R({\cal X},{\cal Y})$, which typically confines the Rand index to a small
interval slightly below $1$. Both measures lie between $0$ and $1$.

If we denote with ${\cal X}_{C}$ and ${\cal Y}_{C}$ the sets of vertex pairs
with are members of the same community in partitions ${\cal X}$ and ${\cal
Y}$, respectively, the Jaccard index is just the ratio between the
intersection and the union of ${\cal X}_{C}$ and ${\cal Y}_{C}$. Such concept
can be used as well to determine the similarity between two clusters $A$ and
$B$

$J_{AB}=\frac{|A\bigcap B|}{|A\bigcup B|}.$ (6)

The score $J_{AB}$ is also called Jaccard index and is the most general
definition of the score, for any two sets $A$ and $B$ Jaccard (1901).
Measuring the similarity between communities is very important to determine,
given different partitions, which cluster of a partition corresponds to which
cluster(s) of the other(s). For instance, the cluster $Y_{j}$ of ${\cal Y}$
corresponding to cluster $X_{i}$ of ${\cal Y}$ is the one maximising the
similarity between $X_{i}$ and $Y_{j}$, e. g., $J_{X_{i}Y_{j}}$. This strategy
is also used to track down the evolution of communities in temporal networks
Palla _et al._ (2007); Lancichinetti and Fortunato (2012).

Figure 12: Partition similarity measures based on cluster matching. There are
three partitions in three clusters: ${\cal C}$, ${\cal C}^{\prime}$ and ${\cal
C}^{\prime\prime}$. The clusters include all elements of columns $1-2$, $3-4$
and $5-6$, which for ${\cal C}$ are labelled in black, grey and white,
respectively. Partition ${\cal C}^{\prime}$ is obtained from ${\cal C}$ by
reassigning the same fraction of elements from one cluster to the next, while
${\cal C}^{\prime\prime}$ is derived from ${\cal C}$ by reassigning the same
fraction of elements from each cluster equally between the other clusters.
From cluster matching scores one concludes that ${\cal C}^{\prime}$ and ${\cal
C}^{\prime\prime}$ are equally similar to ${\cal C}$, while intuition suggests
that ${\cal C}^{\prime}$ is closer to ${\cal C}$ than ${\cal
C}^{\prime\prime}$. Adapted figure with permission from Meilă (2007). © 2007,
by Elsevier.

The Rand and the Jaccard indices, as defined in Eqs. (5) and (6), have the
disturbing feature that they do not take values in the entire range $[0,1]$.
For this reason, adjusted versions of both indices exist, in that a baseline
is introduced, yielding the expected values of the score for all pairs of
partitions $\tilde{\cal X}$ and $\tilde{\cal Y}$ obtained by randomly
assigning vertices to clusters such that $\tilde{\cal X}$ and $\tilde{\cal Y}$
have the same number of clusters and the same size for all clusters of ${\cal
X}$ and ${\cal Y}$, respectively Hubert and Arabie (1985). The baseline is
subtracted from the unadjusted version, and the result is divided by the range
of this difference, yielding $1$ for identical partitions and $0$ as expected
value for independent partitions. But there are problems with these
definitions as well. The null model used to compute the baseline relies on the
assumption that the communities of the independent partitions have the same
number of vertices as in the partitions whose similarity is to be compared.
But such assumption usually does not hold, in practical instances, as
algorithms sometimes need the number of communities as input, but they never
impose any constraint on the cluster sizes. Adjusted indices have also the
disadvantage of nonlocality Meilă (2005): the similarity between partitions
differing only in one region of the network depends on how the remainder of
the network is subdivided. Moreover, the adjusted scores can take negative
values, when the unadjusted similarity lies below the baseline.

A better option is to use standardised indices Brennan and Light (1974): for a
given score $S_{i}$ the value of the null model term $\mu_{i}$ is computed
along with its standard deviation $\sigma_{i}$ over many different
randomisations of the partitions ${\cal X}$ and ${\cal Y}$. By computing the
$z$-score

$z_{i}=\frac{S_{i}-\mu_{i}}{\sigma_{i}},$ (7)

we can see how non-random the measured similarity score is, and assess its
significance. It can be shown that the $z$-scores for the Jaccard, Rand and
Adjusted Rand indices coincide Traud _et al._ (2011), so the measures are
statistically equivalent. Since the actual values $S_{i}$ of these indices
differ for the same pair of partitions, in general, we conclude that the
magnitudes of the scores may give a wrong perception about the effective
similarity.

Cluster matching aims at establishing a correspondence between pairs of
clusters of different partitions based on the size of their overlap. A popular
measure is the fraction of correctly detected vertices, introduced by Girvan
and Newman Girvan and Newman (2002). A vertex is correctly classified if it is
in the same cluster as at least half of the other vertices in its cluster in
the planted partition. If the detected partition has clusters given by the
merger of two or more groups of the planted partition, all vertices of those
clusters are considered incorrectly classified. The number of correctly
classified vertices is then divided by the number $n$ of vertices of the
graph, yielding a number between $0$ and $1$. The recipe to label vertices as
correctly or incorrectly classified is somewhat arbitrary. The fraction of
correctly detected vertices is similar to

$H({\cal X},{\cal
Y})=\frac{1}{n}\sum_{k^{\prime}=\mbox{match}(k)}n_{kk^{\prime}},$ (8)

where $k^{\prime}$ is the index of the best match $Y_{k^{\prime}}$ of cluster
$X_{k}$ Meilă and Heckerman (2001). A common problem of this type of measures
is that partitions whose clusters have the same overlap would have the same
similarity, regardless of what happens to the parts of the communities which
are unmatched. The situation is illustrated schematically in Fig. 12.
Partitions ${\cal C}^{\prime}$ and ${\cal C}^{\prime\prime}$ are obtained from
${\cal C}$ by reassigning the same fraction of their elements to the other
clusters. Their overlaps with ${\cal C}$ are identical and so are the
corresponding similarity scores. However, in partition ${\cal
C}^{\prime\prime}$ the unmatched parts of the clusters are more scrambled than
in ${\cal C}^{\prime}$, which should be reflected in a lower similarity score.

Similarity can be also estimated by computing, given a partition, the
additional amount of information that one needs to have to infer the other
partition. If partitions are similar, little information is needed to go from
one to the other. Such extra information can be used as a measure of
dissimilarity. To evaluate the Shannon information content Mackay (2003) of a
partition, we start from the community assignments $\\{x_{i}\\}$ and
$\\{y_{i}\\}$, where $x_{i}$ and $y_{i}$ indicate the cluster labels of vertex
$i$ in partition ${\cal X}$ and ${\cal Y}$, respectively. The labels $x$ and
$y$ are the values of two random variables $X$ and $Y$, with joint
distribution $P(x,y)=P(X=x,Y=y)=n_{xy}/n$, so that $P(x)=P(X=x)=n_{x}^{X}/n$
and $P(y)=P(Y=y)=n_{y}^{Y}/n$. The mutual information $I(X,Y)$ of two random
variables is $I(X,Y)=H(X)-H(X|Y)$, where $H(X)=-\sum_{x}P(x)\log P(x)$ is the
Shannon entropy of $X$ and $H(X|Y)=-\sum_{x,y}P(x,y)\log P(x|y)$ is the
conditional entropy of $X$ given $Y$. The mutual information is not ideal as a
similarity measure: for a given partition ${\cal X}$, all partitions derived
from ${\cal X}$ by splitting (some of) its clusters would all have the same
mutual information with ${\cal X}$, even though they could be very different
from each other. In this case the mutual information equals the entropy
$H(X)$, because the conditional entropy is zero. It is then necessary to
introduce an explicit dependence on the other partition, that persists even in
those special cases. This has been achieved by introducing the normalized
mutual information (NMI), obtained by dividing the mutual information by the
arithmetic average191919Strehl and Ghosh introduced an earlier definition of
NMI, where the mutual information is divided by the geometric average of the
entropies Strehl and Ghosh (2002). Alternatively, one could normalise by the
larger of the entropies $H(X)$ and $H(Y)$ McDaid _et al._ (2011); Esquivel and
Rosvall (2012). of the entropies of ${\cal X}$ and ${\cal Y}$ Fred and Jain
(2003)

$I_{norm}({\cal X},{\cal Y})=\frac{2I(X,Y)}{H(X)+H(Y)}.$ (9)

The NMI equals $1$ if and only if the partitions are identical, whereas it has
an expected value of $0$ if they are independent. Since the first thorough
comparative analysis of clustering algorithms Danon _et al._ (2005), the NMI
has been regularly used to compute the similarity of partitions in the
literature. However, the measure is sensitive to the number of clusters
$q_{\cal Y}$ of the detected partition, and may attain larger values the
larger $q_{\cal Y}$, even though more refined partitions are not necessarily
closer to the planted one. This may give wrong perceptions about the relative
performance of algorithms Zhang (2015).

A more promising measure, proposed by Meilă Meilă (2007) is the variation of
information (VI)

$V({\cal X},{\cal Y})=H(X|Y)+H(Y|X).$ (10)

The VI defines a metric in the space of partitions as it has the properties of
distance (non-negativity, symmetry and triangle inequality). It is a local
measure: the VI of partitions differing only in a small portion of a graph
depends on the differences of the clusters in that region, and not on how the
rest of the graph is subdivided. The maximum value of the VI is $\log n$,
which implies that the scores of an algorithm on graphs of different sizes
cannot be compared with each other, in principle. One could divide $V({\cal
X},{\cal Y})$ by $\log n$ Karrer _et al._ (2008), to force the score to be in
the range $[0,1]$, but the actual span of values of the measure depends on the
number of clusters of the partitions. In fact, if the maximum number of
communities is $q^{\star}$, with $q^{\star}\leq\sqrt{n}$, $V({\cal X},{\cal
Y})\leq 2\log q^{\star}$. Consequently, in those cases where it is reasonable
to set an upper bound on the number of clusters of the partitions, the
similarities between planted and detected partitions on different graphs
become comparable, and it is possible to assess both the performance of an
algorithm and to compare algorithms across different benchmark graphs. We
stress, however, that the measure may not be suitable when the partitions to
be compared are very dissimilar from each other Traud _et al._ (2011) and that
it shows unintuitive behaviour in particular instances Delling _et al._
(2006).

So far we discussed of comparing partitions. What about covers? Extensions of
the measures we have presented to the case of overlapping communities are
usually not straightforward. The Omega index Collins and Dent (1988) is an
extension of the Adjusted Rand index Hubert and Arabie (1985). Let ${\cal X}$
and ${\cal Y}$ be covers of the same graph to be compared. We denote with
$a_{jj}$ the number of pairs of vertices occurring together in exactly $j$
communities in both covers. It is a natural generalisation of the variables
$a_{00}$ and $a_{11}$ we have seen above, where $j$ can also be larger than
$1$ since a pair of vertices can now belong simultaneously to multiple
communities. The variable

$o({\cal X},{\cal Y})=\frac{2}{n(n-1)}\sum_{j}a_{jj}$ (11)

is the fraction of pairs of vertices belonging to the same number of
communities in both covers (including the case $j=0$, which refers to the
pairs not being in any community together). The Omega index is defined as

$\Omega({\cal X},{\cal Y})=\frac{o({\cal X},{\cal Y})-o_{e}({\cal X},{\cal
Y})}{1-o_{e}({\cal X},{\cal Y})},$ (12)

where $o_{e}({\cal X},{\cal Y})$ is the expected value of $o({\cal X},{\cal
Y})$ according to the null model discussed earlier, in which vertex labels are
randomly reshuffled such to generate covers with the same number and size of
the communities.

The NMI has also been extended to covers by Lancichinetti, Fortunato and
Kertész Lancichinetti _et al._ (2009). The definition is non-trivial: the
community assignments of a cover are expressed by a vectorial random variable,
as each vertex may belong to multiple clusters at the same time. The measure
overestimates the similarity of two covers, in special situations, where
intuition suggests much lower values. The problem can be solved by using an
alternative normalisation, as shown in McDaid _et al._ (2011). Unfortunately
neither the definition by Lancichinetti, Fortunato and Kertész nor the one by
McDaid, Greene and Hurley are proper extensions of the NMI, as they do not
coincide with the classic definition of Eq. (9) when partitions in non-
overlapping clusters are compared. However, the differences are typically
small, and one can rely on them in practice. Esquivel and Rosvall have
proposed an actual extension Esquivel and Rosvall (2012). Following the
comparative analysis performed in Lancichinetti and Fortunato (2009), the NMI
by Lancichinetti, Fortunato and Kertész has been regularly used in the
literature, also in the case of regular partitions, without overlapping
communities202020Recently the NMI has been extended to handle the comparison
of hierarchical partitions as well Perotti _et al._ (2015)..

If covers are fuzzy (Section II.2), the similarity measures above cannot be
used, as they do not take into account the degree of membership of vertices in
the communities they belong to. A suitable option is the Fuzzy Rand index
Hüllermeier and Rifqi (2009), which is an extension of the Adjusted Rand
index. Both the Fuzzy Rand index and the Omega index coincide with the
Adjusted Rand index when communities do not overlap.

For temporal networks, a naïve approach would be comparing partitions (or
covers) corresponding to configurations of the system in the same time window,
and to see how this score varies across different time windows. However, this
does not tell if the clusters are evolving in the same way, as there would be
no connection between clusterings at different times. A sensible approach is
comparing sequences of clusterings, by building a confusion matrix that takes
into account multiple snapshots. This strategy allows one to define dynamic
versions of various indices, like the NMI and the VI Granell _et al._ (2015).

In conclusion, while there is no clear-cut criterion to establish which
similarity measure is best, we recommend to use measures based on information
theory. In particular, the VI seems to have more potential than others, for
the reasons we explained, modulo the caveats in Refs. Delling _et al._ (2006);
Traud _et al._ (2011). There are currently no extensions of the VI to handle
the comparison of covers, but it would not be difficult to engineer one, e.
g., by following a similar procedure as in Lancichinetti _et al._ (2009);
McDaid _et al._ (2011), though this might cost the sacrifice of some of its
nice features.

One should keep in mind that the choice of one similarity index or another is
a sensitive one, and warped conclusions may be drawn when different measures
are adopted. In Fig. 13 we show the accuracy of two algorithms on the LFR
benchmark (Section III.1): Ganxis, a method based on label propagation Xie and
Szymanski (2012) and LinkCommunities, a method based on grouping edges instead
of vertices Ahn _et al._ (2010) (Section IV.4). The accuracy is estimated with
the NMI by Lancichinetti, Fortunato and Kertész Lancichinetti _et al._ (2009)
(left diagram) and with the Omega index [Eq. (12)] (right diagram). From the
left plot one would think that Ganxis clearly outperforms LinkCommunities,
whereas from the right plot Ganxis still prevails for $\mu$ until about $0.5$
(though the curves are closer to each other than in the NMI plot) and
LinkCommunities is better for larger values of $\mu$.

Figure 13: Importance of choice of partition similarity measures. The plots
show the comparison between the planted partition of LFR benchmark graphs and
the ones found by two algorithms: Ganxis and LinkCommunities. In the left
diagram similarity was computed with the NMI, in the right one with the Omega
index. The performances of the algorithms appear much closer when the Omega
index is used. The LFR benchmark graphs used in the analysis have $1\,000$
vertices, average degree $15$, maximum degree $50$, exponents $2$ and $1$ for
the degree and community size distributions and range $[10,50]$ for the
community size.

###  III.3 Detectability

In validation procedures one assumes that, if the network has clusters, there
must be a way to identify them. Therefore, if we do not manage, we have to
blame the specific clustering method(s) adopted. But are we certain that
clusters are always detectable?

Most networks of interest are sparse, i. e., their average degree is much
smaller than the number of vertices. This means that the number of edges of
the graph is much smaller than the number of possible edges $n(n-1)/2$. A more
precise way to formulate this is by saying that a graph is sparse when, in the
limit of infinite size, the average degree of the graph remains finite. A
number of analytical calculations can be carried out by using network
sparsity. Many algorithms for community detection only work on sparse graphs.

On the other hand, sparsity can also give troubles. Due to the very low
density of edges, small amounts of noise could perturb considerably the
structure of the system. For instance, random fluctuations in sparse graphs
could trick algorithms into finding groups that do not really exist (Section
IV.9). Likewise, they could make actual groups undetectable. Let us consider
the simplest version of the assortative stochastic block model, which matches
the planted partition model (Section III.1). There are $q$ communities of the
same size $n/q$, and only two values for the edge probability: $p_{in}$ for
pairs of vertices in the same group and $p_{out}$ for pairs of vertices in
different groups. Since the graphs are sparse, $p_{in}$ and $p_{out}$ vanish
in the limit of infinite graph size. So we shall use the expected internal and
external degrees $\langle k_{in}\rangle=np_{in}/q$ and $\langle
k_{out}\rangle=np_{out}(q-1)/q$, which stay constant in that limit. By
construction, the groups are communities so long as $p_{in}>p_{out}$ or,
equivalently, for $\langle k_{in}\rangle>\langle k_{out}\rangle/(q-1)$. But
that does not mean that they are always detectable.

In principle, dealing with the issue of detectability involves examining all
conceivable clustering techniques, which is clearly impossible. Fortunately,
it is not necessary, because we know what model has generated the communities
of the graphs we are considering. The most effective technique to infer the
groups is then fitting the stochastic block model on the data (a posteriori
block modelling). This can be done via the maximum likelihood method Gelman
_et al._ (2014). In recent work Decelle _et al._ (2011), Decelle et al. have
shown that, in the limit of infinite graph size, the partition obtained this
way is correlated with the planted partition whenever

$\langle k_{in}\rangle-\frac{\langle k_{out}\rangle}{q-1}>\sqrt{\langle
k_{in}\rangle+\langle k_{out}\rangle},$ (13)

which implies

$\langle k_{in}\rangle>\frac{\langle
k_{out}\rangle}{q-1}+\frac{1}{2}\left(1+\sqrt{1+\frac{4q\langle
k_{out}\rangle}{q-1}}\right).$ (14)

So, given a value of $\langle k_{out}\rangle$, when $\langle k_{in}\rangle$ is
in the range $\left[\frac{\langle k_{out}\rangle}{q-1},\frac{\langle
k_{out}\rangle}{q-1}+\frac{1}{2}\left(1+\sqrt{1+\frac{4q\langle
k_{out}\rangle}{q-1}}\right)\right]$ the probability $p_{c}$ of classifying a
vertex correctly is not larger than the probability $1/q$ of assigning the
vertex to a randomly chosen group, although the groups are communities,
according to the model. We stress that this result only holds when the graphs
are sparse: if $p_{in}$ and $p_{out}$ remain non-zero in the large-n limit
(dense graph), the classic detectability threshold $p_{in}>p_{out}$ is
correct.

A fortiori, no clustering technique can detect the clusters better than random
assignment when the inference of the model parameters fails to do so. If
communities are searched via the spectral optimisation of Newman-Girvan’s
modularity Newman (2006), one obtains the same threshold of Eq. (14)
Nadakuditi and Newman (2012), provided the network is not too sparse.

For the benchmark of Girvan and Newman (Section III.1) Girvan and Newman
(2002) it has long been unclear where the actual detectability limit sits.
Girvan-Newman benchmark graphs are not infinite, their size being set to
$128$, so there is no proper detectability transition, but rather a smooth
crossover from a regime in which clusters are frequently detectable to a
regime where they are frequently undetectable. For this reason there cannot be
a sharp threshold separating the two regimes. Still it is useful to have an
idea of where the pattern changes. In the following we shall still use the
term threshold to refer to the crossover point. In the beginning, scholars
thought that clusters are detectable as long as they satisfy the definition of
strong community by Radicchi et al. Radicchi _et al._ (2004) (Section II.2),
i. e., as long as the expected internal degree exceeds the expected external
degree, yielding a threshold $\langle k_{in}\rangle=\langle k_{out}\rangle$
Girvan and Newman (2002). Since the expected total degree of a vertex is set
to $16$, communities are detectable as long as $\langle
k_{out}\rangle<k_{d}^{strong}=8$. It soon became obvious that the actual
threshold should be the one of the “modern” definition of community we have
presented in Section II.3, according to which the condition212121In the
setting of the Girvan-Newman benchmark, where edge probabilities are identical
for all vertices, the strong and weak definitions we presented in Section II.3
coincide. is $p_{in}>p_{out}$, that is $\langle
k_{out}\rangle<k_{d}^{standard}=12$. However, numerical calculations reveal
that algorithms tend to fail long before that limit. From Eq. (14) we see that
for the case of four infinite clusters and total expected degree $\langle
k_{tot}\rangle=16$, the theoretical detectability limit is $k_{d}^{theor}=9$.
In Fig. 14 we see the performance on the benchmark of three well-known
algorithms: Louvain Blondel _et al._ (2008), a greedy optimisation technique
of Newman–Girvan modularity Newman and Girvan (2004) (Section IV.6); Infomap,
which is based on random walk dynamics Rosvall and Bergstrom (2008) (Section
IV.7); OSLOM, that searches for clusters via a local optimisation of a
significance score Lancichinetti _et al._ (2011). The accuracy is estimated
via the fraction of correctly detected vertices (Section III.2). The three
thresholds $k_{d}^{strong}$, $k_{d}^{standard}$ and $k_{d}^{theor}$ are
represented by vertical lines. The performance of all methods becomes
comparable with random assignment well before $k_{d}^{standard}$. The
theoretical limit $k_{d}^{theor}$ appears to be compatible with the
performance curves.

Figure 14: Detectability of communities. Performances of three popular
algorithms on the benchmark by Girvan and Newman. The dotted vertical line at
$\langle k_{out}\rangle=8$ indicates the threshold corresponding to the
concept of strong community á la Radicchi et al., the dashed line at $\langle
k_{out}\rangle=12$ the threshold according to the probability-based definition
of strong community we have given in Section II.3. The baseline of random
assignment is $1/4$ (horizontal dashed line). All algorithms do not do better
than random assignment already before $\langle k_{out}\rangle=12$. The
theoretical detectability limit is at $\langle k_{out}\rangle=9$, in the limit
of groups of infinite size.

Graph sparsity is a necessary condition for clusters to become undetectable,
but it is not sufficient. The symmetry of the model we have considered plays a
major role too. Clusters have equal size and vertices have equal degree. This
helps to “confuse” algorithms. If communities have unequal sizes and the
degree of vertices are correlated with the size of their communities, so that
vertices have larger degree, the bigger their clusters, community detection
becomes easier, as the degrees can be used as proxy for group membership. In
this case, the non-trivial detectability limit disappears when there are four
clusters or fewer, while it persists up to a given extent of group size
inequality when there are more than four clusters Zhang _et al._ (2016). Other
types of block structure, like core-periphery, do not suffer from
detectability issues Zhang _et al._ (2015).

LFR benchmark graphs are more complex models than the one studied in Zhang _et
al._ (2016) and it is not clear whether there is a non-trivial detectability
limit, though it is unlikely, due to the big heterogeneity in the distribution
of vertex degree and community size.

###  III.4 Structure versus metadata

Another standard way to test clustering techniques is using real networks with
known community structure. Knowledge about the memberships of the vertices
typically comes from metadata, i. e., non-structural information. If vertices
are annotated communities are assumed to be groups of vertices with identical
tags. Examples are user groups in social networks like LiveJournal and product
categories for co-purchasing networks of products of online retailers such as
Amazon.

In Fig. 15 we show the most popular of such benchmark graphs, Zachary karate
club network Zachary (1977). It consists of $34$ vertices, the members of a
karate club in the United States, who were observed over a period of three
years. Edges connect individuals interacting outside the activities of the
club. Eventually a conflict between the club president (vertex $34$) and the
instructor (vertex $1$) led to the fission of the club in two separate groups,
whose members supported the instructor and the president, respectively
(indicated by the colours). Indeed, the groups make sense topologically:
vertices $1$ and $34$ are hubs, and most members are directly connected to
either of them.

Figure 15: Zachary karate club network. Symbols of different colours indicate
the two groups generated by the fission of the network, following the
disagreement between the club’s instructor (vertex 1) and its president (34).

Most algorithms of community detection have been tested on this network, as
well as others, e. g., the American college football network Girvan and Newman
(2002); Evans (2010) or Lusseau’s network of bottlenose dolphins Lusseau
(2003). The idea is that the method doing the best job at recovering groups
with identical annotations would also be the most reliable in applications.

Such idea, however, is based on a questionable principle, i. e., that the
groups corresponding to the metadata are also communities in the topological
sense we have discussed in Section II. Communities exist because their
vertices are supposed to be similar to each other, in some way. The similarity
among the vertices is then revealed topologically through the higher edge
probability among pairs of members of the same group than between pairs of
members of different groups, whose similarity is lower. Hence, when one is
provided with annotations or other sources of information that allows to
classify vertices based on their similarity, one expects that such similarity-
based classes are also the best communities that structure-based algorithms
may detect.

Figure 16: Mismatch between structural communities and metadata groups. The
vertical axis reports the similarity between communities detected via several
clustering methods and groups of vertices with identical attributes for
several networks, estimated via the NMI. Scores are grouped by data sets on
the horizontal axis. The vertical dashed line separates small classic data
sets from large ones, recently compiled. The low scores obtained for the
latter indicate that the correspondence between structural and annotated
communities is poor. Reprinted figure with permission from Hric _et al._
(2014). © 2014, by the American Physical Society.

Indeed, for some small networks like Zachary’s karate club this seems to be
the case. But for quite some time scholars could not test this hypothesis, due
to the limited number of suitable data sets. Over the past few years this has
finally become possible, due to the availability of several large network data
sets with annotated vertices Yang and Leskovec (2012a, 2013, 2014); Hric _et
al._ (2014). It turns out that the alignment between the communities found by
standard clustering algorithms and the annotated groups is not good, in
general. In Fig. 16 we show the similarity between the topological partitions
found by different methods and the annotated partitions, for several social,
information and technological networks Hric _et al._ (2014). The heights of
the vertical bars are the values of the normalised mutual information (NMI)
Lancichinetti _et al._ (2009). Groups of contiguous bars represent the scores
for a given data set. To the left of the vertical dashed line we see the
results for classic benchmarks, like LFR graphs (Section III.1) Lancichinetti
_et al._ (2008), Zachary karate club, etc., and the scores are generally good.
But for the large data sets to the right of the line the scores are rather
low, signalling a significant mismatch between topological and annotated
communities. For Amazon co-purchasing network Yang and Leskovec (2012b), in
which vertices are products and edges are set between products often purchased
by the same customer(s), the similarity is quite a bit higher than for the
other networks. This is because the classification of Amazon products is
hierarchical (e. g., Books/Fiction/Fantasy), so there are different levels of
annotated communities, and the reported scores refer to the one which is most
similar to the structural ones detected by the algorithms, while the other
levels would give lower similarity scores. Low similarity at the partition
level does not rule out that some communities of the structural partition
significantly overlap with their annotated counterparts, but precision and
recall scores show that this is not the case. Results depend more on the
network than on the specific method adopted, none of which appears to be
particularly good on any (large) data set.

So the hypothesis that structural and annotated clusters are aligned is not
warranted, in general. There can be multiple reasons for that. The attributes
could be too general or too specific, yielding communities which are too large
or too small to be interesting. Moreover, while the best partition of the
network delivered by an algorithm can be poorly correlated with the metadata,
there may be alternative topological divisions that also belong to a set of
valid solutions, according to the algorithm222222For instance, for clustering
methods based on optimisation, there are many partitions corresponding to
values of the quality function very close to the searched optimum Good _et
al._ (2010). The algorithm will return one (or some) of them, but the others
are comparably good solutions., but happen to be better correlated with the
annotations Newman and Clauset (2016).

The fact that structural and annotated communities may not be strongly
correlated has important consequences. Scholars have been regularly testing
their algorithms on small annotated graphs, like Zachary’s karate club, by
tuning parameters such to obtain the best possible performance on them. This
is not justified, in general, as it makes sense only when there is a strong
correspondence, which is a priori unknown. Also, forcing an alignment with
annotations on one data set does not guarantee that there is going to be a
good alignment with the annotations of a different network. Besides, one of
the reasons why people use clustering algorithms is to provide an improved
classification of the vertices, by using structure. If one obtained the same
thing, why bother?

The right thing to do is using structure along with the annotations, instead
of insisting on matching them. This way the information coming from structure
and metadata can be combined and we can obtain more accurate partitions, if
there is any correspondence between them. Recent approaches explicitly assume
that the metadata (or a portion thereof) are either exactly or approximately
correlated with the best topological partition Moore _et al._ (2011); Leng _et
al._ (2013); Peel (2015); Yang _et al._ (2013); Bothorel _et al._ (2015). A
better approach is not assuming a priori that the metadata correlate with the
structural communities. The goal is quantifying the relationship between
metadata and community and use it to improve the results. If there is no
correlation, the metadata would be ignored, leaving us with the partition
derived from structure alone.

Methods along these lines have been developed, using stochastic block models.
Newman and Clauset Newman and Clauset (2016) have proposed a model in which
vertices are initially assigned to clusters based on metadata, and then edges
are placed between vertices according to the degree-corrected stochastic block
model Karrer and Newman (2011). Hric et al. have designed a similar model Hric
_et al._ (2016), in which the interplay between structure and metadata is
represented by a multilayer network (Fig. 17). The generative model is an
extension of the hierarchical stochastic block model (SBM) Peixoto (2014) with
degree-correction for the case with edge layers Peixoto (2015a).

Data, $\bm{A}$Metadata, $\bm{T}$

Figure 17: Data-metadata stochastic block model by Hric et al.. One layer
consists of the network itself, with its vertices and edges. The other layer
is composed of the graph vertices and vertices representing the annotations,
the edges indicating which vertices are associated to which tag. The presence
of network vertices on both layers induces a coupling between them. Reprinted
figure with permission from Hric _et al._ (2016). © 2016, by the American
Physical Society.

Here the metadata is not supposed to correspond simply to a partition of the
vertices. The majority of data sets contain rich metadata, with vertices being
annotated multiple times, and often few vertices possess the exact same
annotations and can be thus associated to the same group. In addition, while
the number of communities is required as input by the method of Newman and
Clauset, here it is inferred from the data. Finally, it is also possible to
assess the metadata in its power to predict the network structure, not only
their correlation with latent partitions. This way it is possible to predict
missing vertices of the network, i. e., to infer the connections of a vertex
from its annotations only. We stress that neither method requires that all
vertices are annotated.

Applications of the method by Hric et al. Hric _et al._ (2016) reveal that in
many data sets there are statistically significant correlations between the
annotations and the network structure, while in some cases the metadata seems
to be largely uncorrelated with structural clusters. We conclude that network
metadata should not be used indiscriminately as ground truth for community
detection methods. Even when the metadata is strongly predictive of the
network structure, the agreement between the annotations and the network
division tends to be complex, and very different from the one-to-one mapping
that is more commonly assumed. Moreover, data sets usually contain
considerable noise in their annotations, and some metadata tags are
essentially random, with no relationship to structure.

###  III.5 Community structure in real networks

Artificial benchmark graphs are certainly very useful to assess the
performance of clustering algorithms. However, one could always question
whether the model of community structure they propose is reliable. How can we
assess this? In order to characterise “real” communities we have to find them
first. But that can only be done via some algorithm, and different algorithms
search for different types of objects, in general. Still, one may hope that
general properties of communities can be consistently uncovered across
different methods and data sets, while other features are more closely tied to
the specific method(s) used to detect the clusters and (or) the specific data
set at study (or classes thereof).

A seemingly robust feature of communities in real networks is the
heterogeneity of their size distribution. Most clustering techniques find
skewed distributions of cluster sizes in many networks. So, there appears to
be no characteristic size for a community: small communities usually coexist
with large ones. This feature is rather independent of the type of network
(Fig. 18). It may signal a hierarchy among communities, with small clusters
included in large ones. Methods unable to distinguish between hierarchical
levels might find “blended” partitions, consisting of communities of different
levels and hence of very different sizes. The LFR benchmark was the first
graph model to take explicitly into account the heterogeneity of community
sizes (Section III.1).

Figure 18: Distribution of community sizes in real networks. The clusters were
detected with Infomap Rosvall and Bergstrom (2008), but other methods yield
qualitatively similar results. Various classes of networks are considered. All
distributions are broad, spanning several orders of magnitude. Reprinted
figure with permission from Lancichinetti _et al._ (2010).

Another interesting question is how the quality of communities depends on
their size. Leskovec et al. Leskovec _et al._ (2009) carried out a systematic
analysis of clusters in many large networks, including traditional and on-line
social networks, technological, information networks and web graphs. Instead
of considering partitions, they focused on individual communities, which are
derived by optimising conductance (Section II.1) around seed vertices. We
remind that the conductance of a cluster is the ratio between the number of
external edges and the total degree of the cluster. Minimising conductance
effectively combines the two main community demands, i. e., good separation
from the rest of the graph (low numerator) and large number of internal edges
(high denominator). The measure is also relatively insensitive to the size of
the clusters, as both the numerator and the denominator are typically
proportional to the number of vertices of the community232323This is exactly
true when the ratio between the external and the total degree (mixing
parameter) is the same for all community vertices.. Therefore one could use it
to compare the quality of clusters of different sizes. For any given size $k$
Leskovec et al. identified the subgraph with $k$ vertices with the lowest
conductance. This way, for each network one can draw the network community
profile (NCP), showing the minimum conductance as a function of community
size. The NCPs of all networks studied by Leskovec et al. have a
characteristic shape: they go downwards till $k\sim 100$ vertices, and then
they rise monotonically for larger subgraphs [Fig. 19 (left)].

Figure 19: Core-periphery structure of real networks. (Left) Schematic shape
of the network community profile (NCP), showing how the minimum conductance of
subgraphs of size $k$ varies with $k$. This pattern is very common in large
social and information networks. The “best” communities in terms of
conductance have a size of about $100$ vertices (minimum of the curve),
whereas communities of larger sizes have lower quality. The curve labeled
Rewired network is the NCP of a randomised version of the network, where edges
are randomly rewired by keeping the degree distribution; the one labeled Bag
of whiskers gives the minimum conductance scores of communities composed of
disconnected pieces. (Right) Scheme of the core-periphery structure in large
social and information networks associated to the NCP above. Most vertices are
in a central core, where large communities are blended together, whereas the
best communities, which are rather small, are weakly connected to the core.
Reprinted figure with permission from Ref. Leskovec _et al._ (2009). © 2009,
by Taylor and Francis.

Alternative shapes have been recently found for other data sets Jeub _et al._
(2015).

For networks characterised by NCPs like the one in Fig. 19 (left) the most
pronounced communities are fairly small in size. Such small clusters are
weakly connected to the rest of the network, often by a single edge (in this
case they are called whiskers), and form the periphery of the graph. Large
clusters have comparatively lower quality and melt into a big core. Large
communities can often be split in parts with lower conductance, so they can be
considered conglomerates of smaller communities. A schematic picture of the
resulting network structure is shown in Fig. 19 (right). The shape of the NCP
is fairly independent of the specific technique adopted to identify the
subgraphs with minimum conductance. The different shapes of the NCPs
encountered in data suggest that core-periphery is not the only model of group
structure of real networks Jeub _et al._ (2015).

The NCP is a signature that can be used to select generative mechanisms of
community structure. Indeed, many standard models typically yield NCP sloping
steadily downwards, at odds with the ones encountered in many social and
information networks. Stochastic block models (Section II.3) are sufficiently
versatile that they can reproduce the NCP shape of Fig. 19 (left), by suitably
tuning the parameters. In the standard LFR benchmark (Section III.1) the
mixing parameters are tightly concentrated about a value $\mu$ by
construction, hence all clusters have approximately conductance $\mu$,
yielding a roughly flat NCP242424If all vertices of a subgraph have mixing
parameter equal to $\mu$, it can be easily shown that the conductance of the
subgraph is exactly equal to $\mu$. Jeub _et al._ (2015). However, the model
can be easily modified by making $\mu$ community-dependent and a large variety
of NCPs are attainable, including the one of Fig. 19 (left).

The main problem of working with NCPs is that they are based on extreme
statistics, as one systematically reports the minimum conductance for a given
cluster size. How representative is this extremal subgraph of the population
of subgraphs with the same size? There may be just a few clusters of a given
size with low conductance. It may happen that many subgraphs have conductance
near the minimum corresponding to their size(s), which would then be
representative. Alternatively most subgraphs might have much larger
conductance than the minimum but low enough that they can be still considered
communities. In this case one should conclude that communities of that size
are not of very high quality, on average. The above scenarios might lead to
different conclusions about the actual community structure of the system. In
general, even if one could produce a version of the NCP where the trend refers
to representative samples of communities of equal size (whatever that means),
the actual values of the conductance are as important as the shape of the
curve. If conductance is sufficiently low for all cluster sizes, it means that
there are good communities of any size. The fact that small clusters could be
of higher quality does not undermine the role of large clusters. The
observation that large clusters consist of smaller clusters of higher quality
may just be evidence of hierarchical structure in the network, which is a
trademark of many complex systems Simon (1962). In that case high levels of
the hierarchy are not less important than low ones, a priori. In fact, the
actual relative importance of communities should not only come from the sheer
value of specific metrics, like conductance, but also from their statistical
significance (Section IV.9).

That notwithstanding, we strongly encourage analyses like the one by Leskovec
et al., as they provide a statistical characterisation of community structure,
in a way that is only weakly algorithm-dependent. One has to define
operationally what a cluster is, but in a simple intuitive way that allows us
to draw conclusions about the structure of the graph. In principle one could
do the same by analysing the clusters delivered by any algorithm, but there
would be two important drawbacks. First, the clusters may not be easy to
interpret, as most clustering algorithms usually do not require a clear-cut
definition of community. Second, one would have to handle a partition of the
network in communities, instead of probing locally the group structure of the
network. Therefore, for a given vertex one would have only one cluster (or a
handful, if communities overlap), while a local exploration allows to analyse
a whole population of candidate subgraphs, which gives more information. The
local subgraphs recovered this way do not need to be strongly matching the
clusters delivered by any algorithm, but they provide useful signatures that
allow to restrict the set of possible model explanations for the network’s
group structure. Such investigation can be replicated on any model graph to
check whether the results match (e. g., whether the NCPs coincide).

(a) No overlaps

(b) Sparse overlaps

(c) Dense overlaps

(d) Adjacency matrix of (c)

Figure 20: Stylised views of community structure. In (a) and (b) we show the
conventional pictures of non-overlapping and overlapping clusters,
respectively. Under the network diagrams we see the corresponding adjacency
matrices. The overlaps have a lower edge density than the rest of the
communities. The analysis by Yang and Leskovec suggests that a more realistic
model could be the one shown in (c, d), where the overlaps are denser than the
non-overlapping parts. Reprinted figure with permission from Yang and Leskovec
(2014). © 2014, by the Association for Computing Machinery, Inc.

Another approach to infer properties of clusters of real networks is using
annotations. While we have shown that annotated clusters do not necessarily
coincide with structural ones (Section III.4), general features can be still
derived, provided they are consistently found across different data sets and
annotations. A recent analysis by Yang and Leskovec has questioned the common
picture of networks with overlapping communities Yang and Leskovec (2014).
Scholars usually assume that clusters overlap at their boundaries, hence edge
density should be larger in the non-overlapping parts (Fig. 5). Instead, by
analysing the overlaps of annotated clusters in large social and information
networks, Yang and Leskovec found that the probability that two vertices are
connected is larger in the overlaps, and grows with the number of communities
sharing that pair of vertices. In addition, connector vertices, i. e.,
vertices with the largest number of neighbours within a community, are more
likely to be found in the overlaps. These findings suggest that the overlaps
may play an important role in the community structure of networks. In Fig. 20
we compare the conventional view with the one resulting from the analysis. The
Community-Affiliation Graph Model (AGM) Yang and Leskovec (2014) and the
Cluster Affiliation Model for Big Networks (BIGCLAM) Yang and Leskovec (2013)
are clustering techniques based on generative models of networks featuring
communities with dense overlaps. The models are based on the principle that
vertices are more likely to be neighbours the more the communities sharing
them, in line with the empirical finding of Yang and Leskovec (2014).

Actual overlapping communities exist in many contexts. However, it is unclear
whether soft clustering is statistically founded. A recent analysis aiming at
identifying suitable stochastic block models to describe real network data
indicate that in many cases hard partitions ought to be preferred, as they
give simpler descriptions of the group structure of the data than soft
partitions Peixoto (2015b). This could be due to the fact that the underlying
models are based on placing edges independently of each other, neglecting
higher order structures between vertices, like motifs. By adopting approaches
that take into account higher-order structures things may change and community
overlaps might become a statistically robust feature. The pervasive overlaps
found by Yang and Leskovec in annotated data can be found if higher order
effects are considered Rosvall _et al._ (2014); Persson _et al._ (2016),
without ad hoc hypotheses.

##  IV Methods

There are many algorithms to detect communities in graphs. They can be grouped
in categories, based on different criteria, like the actual operational method
Fortunato (2010), or the underlying concept of community Coscia _et al._
(2011). In most applications, however, just a few popular algorithms are
employed. In this section we present a critical analysis of these methods. We
show the advantages of knowing the number of clusters before-hand and how it
is possible to derive robust solutions from partitions delivered by stochastic
clustering techniques. We discuss approaches to the problem of detecting
communities in evolving networks and how to assess the significance of the
detected clustering. We conclude by suggesting the methods that currently
appear to be most promising.

###  IV.1 How many clusters?

In general, the only preliminary information available to any algorithm is the
structure of the network, i. e., which pairs of vertices are connected to each
other and which are not (possibly including weights). Any insight about
community structure is supposed to be given as output of the procedure.
Naturally, it would be valuable to have some information on the unknown
division of the network beforehand, as one could reduce considerably the huge
space of possible solutions, and increase the chance of successfully
identifying the communities.

Among all the possible pre-detection inputs, the number $q$ of clusters plays
a prominent role. Many popular classes of algorithms require the specification
of $q$ before they run, like methods imported from data clustering or
parametric statistical inference approaches (Section IV.5). Other methods are
capable to infer $q$ as they can choose among partitions into different
numbers of communities. But even such methods could benefit from a preliminary
knowledge of $q$ Darst _et al._ (2014). In Fig. 21 we report standard accuracy
plots of two algorithms on the planted partition model (Section III.1) with
two clusters of equal size. The algorithms are modularity optimisation via
simulated annealing Guimerà and Amaral (2005) and the Absolute Potts Model
(APM) Ronhovde and Nussinov (2010) (Section IV.7). There are two performance
curves for each method: one comes from the standard application of the method,
without constraints; the other is obtained by forcing the method to explore
only the subset of partitions with the correct number of clusters $q=2$.

Figure 21: Knowing the number of clusters beforehand improves community
detection. The diagram shows the performance on the planted partition model of
two methods: modularity optimisation via simulated annealing Guimerà and
Amaral (2005) and the Absolute Potts Model (APM) Ronhovde and Nussinov (2010).
Networks have $400$ vertices, which are grouped in two equal-sized
communities. The accuracy is measured via the fraction of correctly detected
vertices (Section III.2). The horizontal line indicates the accuracy of random
guessing, the dashed vertical line the theoretical detectability limit
(Section III.3). For each algorithm we show two curves, referring to the
results of the method in the absence of any information on the number of
clusters, and when such information is fed into the model as initial input. In
both cases, knowing the number of clusters beforehand leads to a much better
performance.

We see that the accuracy improves considerably when $q$ is known. This is
particularly striking in the case of modularity optimisation, which is known
to have a limited resolution, preventing the method from identifying the
correct scale of the communities, even when the latter are very pronounced
Fortunato and Barthélemy (2007); Good _et al._ (2010) (Section IV.6). Knowing
$q$ and constraining the optimisation of the measure to partitions with fixed
$q$, the problem can be alleviated Nadakuditi and Newman (2012).

But how do we know how many clusters there are? Here we briefly discuss some
heuristic techniques, for statistically principled methods we defer the reader
to Section IV.5. It has been recently shown that in the planted partition
model $q$ can be correctly inferred all the way up to the detectability limit
from the spectra of two matrices: the non-backtracking matrix $\bf B$ Krzakala
_et al._ (2013) and the flow matrix $\bf F$ Newman (2013). They are $2m\times
2m$ matrices, where $m$ is the number of edges of the graph. Each edge is
considered in both directions, yielding $2m$ directed edges and indicated with
the notation $i\rightarrow j$, meaning that the edge goes from vertex $i$ to
vertex $j$. Their elements read

$B_{i\rightarrow j,r\rightarrow s}=\delta_{is}(1-\delta_{jr})$ (15)

and

$F_{i\rightarrow j,r\rightarrow
s}=\frac{\delta_{is}(1-\delta_{jr})}{k_{i}-1}.$ (16)

In Eq. (16) $k_{i}$ is the degree of vertex $i$. So the elements of $\bf F$
are basically the elements of $\bf B$, normalised by vertex degrees. This is
done to account for the heterogeneous degree distributions observed in most
real networks. Both matrices have non-zero elements only for each pair of
edges forming a directed path from the first vertex of one edge to the second
of the other edge. To do that, edges have to be incident at one vertex. As a
matter of fact, the non-backtracking matrix $\bf B$ is just the adjacency
matrix of the (directed) edges of the graph.

The name of the matrix ${\bf B}$ is due to a connection with the properties of
non-backtracking walks. A non-backtracking walk Angel _et al._ (2015) is a
path across the edges of a graph that is allowed to return to a vertex visited
previously only after at least two other vertices have been visited; immediate
returns like $1\rightarrow 2\rightarrow 1$ are forbidden. The elements of the
$k$-th power of ${\bf B}$ yield the number of non-backtracking walks of length
$k$ from a (directed) edge of the graph to another and the trace of the power
matrix the number of closed non-backtracking walks of length $k$ starting from
any given (directed) edge.

A remarkable property of both matrices is that on networks with homogeneous
groups (i. e., of similar size and internal edge density) most eigenvalues,
which are generally complex, are enclosed by a circle centred at the origin,
and that the number of eigenvalues lying outside of the circle is a good proxy
of the number of communities of the network Krzakala _et al._ (2013); Newman
(2013). For $\bf B$ the circle’s radius is given by the square root $\sqrt{c}$
of the leading eigenvalue $c$, which may diverge for networks with
heterogeneous degree distributions (e. g., power laws); for $\bf F$ it equals
$\sqrt{\langle k/(k-1)\rangle/\langle k\rangle}$, which is never greater than
$1$.

Unfortunately, computing the eigenvalues of the non-backtracking or the flow
matrix is lengthy. Both are $2m\times 2m$ matrices. The adjacency matrix $\bf
A$ has $n\times n$ elements, so $\bf B$ and $\bf F$ are larger by a factor of
$\langle k\rangle^{2}$, where $\langle k\rangle$ is the average degree of the
network. An approximate but reliable computation of the spectra requires a
time which scales superlinearly (approximately quadratic) with the network
size $n$. So the problem is intractable for graphs with number of edges of the
order of millions or higher. Also, if communities have diverse sizes and edge
densities, as it happens in most networks encountered in applications, the
bulk of eigenvalues may not have a circular shape, and it may become
problematic to identify eigenvalues falling outside of the bulk.

Besides, non-backtracking walks must contain cycles, hence trees252525We
remind that trees are connected acyclic graphs. dangling off the graph do not
affect the spectrum of ${\bf B}$, which remains unchanged if all dangling
trees are removed. This is a disturbing feature, as tree-like regions of the
graph may play a role in the network’s community structure, and most methods
would find different partitions if trees are kept or removed262626Singh and
Humphries showed that the problem can be solved via reluctant backtracking
walks, in which the walker has a small but non-zero probability of returning
to the vertex immediately Singh and Humphries (2015).. The spectrum of the
flow matrix, instead, changes when dangling trees are kept or removed Newman
(2013). In the limiting case in which the network itself is a tree, all
eigenvalues of ${\bf B}$ and ${\bf F}$ are zero and even if there were a
community structure one gets no relevant information.

The number of clusters can also be deduced by studying how the eigenvectors of
graph matrices rotate when the adjacency matrix of the graph is subjected to
random perturbations Sarkar _et al._ (2016). On stochastic block models this
approach infers the correct value of $q$ up to a threshold preceding the
detectability limit. The method is also computationally expensive.

In general, if one can identify a set (range) of promising $q$-values, from
preliminary information or via calculations like the ones described above or
in Section IV.5, it is better to run constrained versions of clustering
methods, searching for solutions only among partitions with those numbers of
communities, than letting the methods discover $q$ by themselves, which may
lead to solutions of lower quality.

###  IV.2 Consensus clustering

Many clustering techniques are stochastic in character and do not deliver a
unique answer. A common scenario is when the desired solution corresponds to
extrema of a cost function, that can only be found via approximation
techniques, with results depending on random seeds and on the choice of
initial conditions. Techniques not based on optimisation sometimes have the
same feature, when tie-break rules are adopted in order to choose among
multiple equivalent options encountered along the calculation.

What to do with all these partitions? Sometimes there are objective criteria
to sort out a specific partition and discard all others. For instance, in
algorithms based on optimisation, one could pick the solution yielding the
largest (smallest) value of the function to optimise. For other techniques
there is no clear-cut criterion.

A promising approach is combining the information of the different outputs
into a new partition. Consensus clustering Strehl and Ghosh (2002); Topchy _et
al._ (2005); Goder and Filkov (2008) is based on this idea. The goal is
searching for a consensus partition, that is better fitting than the input
partitions. Consensus clustering is a difficult combinatorial optimisation
problem. An alternative greedy strategy Strehl and Ghosh (2002) relies on the
consensus matrix, which is a matrix based on the co-occurrence of vertices in
communities of the input partitions (Fig. 22). The consensus matrix is used as
an input for the graph clustering technique adopted, leading to a new set of
partitions, which produce a new consensus matrix, etc., until a unique
partition is finally reached, which is not changed by further iterations.

Figure 22: Consensus clustering in networks. A simple graph has a natural
partition in two communities [squares and circles on diagrams (I) and (II)].
The combination of (I), (II), (III) and (IV) yields the weighted consensus
matrix illustrated on the right. The thickness of each edge is proportional to
its weight. In the consensus matrix the community structure of the original
network is more visible: the two communities have become cliques, with “heavy”
edges, whereas inter-community edges are rather weak. This improvement is
obtained despite the presence of two inaccurate partitions in three clusters
(III and IV). Reprinted figure with permission from Lancichinetti and
Fortunato (2012). © 2012, by the Nature Publishing Group.

The steps of the procedure are listed below. The starting point is a network
$G$ with $n$ vertices and a clustering algorithm ${\bf A}$.

  1. 1.

Apply ${\bf A}$ on $G$ $n_{P}$ times, yielding $n_{P}$ partitions.

  2. 2.

Compute the consensus matrix ${\bf D}$: $D_{ij}$ is the number of partitions
in which vertices $i$ and $j$ of $G$ are assigned to the same community,
divided by $n_{P}$.

  3. 3.

All entries of ${\bf D}$ below a chosen threshold $\tau$ are set to
zero272727Without thresholding the consensus matrix would quickly turn into a
dense matrix, rendering the application of clustering algorithms
computationally expensive. However, the method does not strictly require
thresholding, and if the network is not too large one can skip step $3$ and
use the full matrix all along Bruno _et al._ (2015)..

  4. 4.

Apply ${\bf A}$ on ${\bf D}$ $n_{P}$ times, yielding $n_{P}$ partitions.

  5. 5.

If the partitions are all equal, stop282828The consensus matrix is block-
diagonal in this case.. Otherwise go back to 2.

Since the consensus matrix is in general weighted, the algorithm ${\bf A}$
must be able to handle weighted networks, even if the graph at study is
binary. Fortunately many popular algorithms have natural extensions to the
weighted case.

The integration of consensus clustering with popular existing techniques leads
to more accurate partitions than those delivered by the methods alone on LFR
benchmark graphs Lancichinetti and Fortunato (2012). Interestingly, this holds
even for methods whose direct application gives poor results on the same
graphs, like modularity optimisation (Section IV.6). The variability of the
partitions, rather than being a problem, becomes a factor of performance
enhancement. The outcome of the procedure depends on the choice of the
threshold parameter $\tau$ and the number of input partitions $n_{P}$, which
can be selected by testing the performance on benchmark networks Lancichinetti
and Fortunato (2012). Consensus clustering is also a promising technique to
detect communities in evolving networks (Section IV.8).

###  IV.3 Spectral methods

Spectral graph clustering is an approach to detect clusters using spectral
properties of the graph von Luxburg (2006); Fortunato (2010). The eigenvalue
spectrum of several graph matrices (e. g., the adjacency matrix, the
Laplacian, etc.) typically consists of a dense bulk of closely spaced
eigenvalues, plus some outlying eigenvalues separated from the bulk by a
significant gap. The eigenvectors corresponding to these outliers contain
information about the large-scale structure of the network, like community
structure292929Typically each such eigenvector is localised, in that its
entries are markedly different from zero in correspondence of the vertices of
a community, while the other entries are close to zero.. Spectral clustering
consists in generating a projection of the graph vertices in a metric space,
by using the entries of those eigenvectors as coordinates. The $i$-th entries
of the eigenvectors are the coordinates of vertex $i$ in a $k$-dimensional
Euclidean space, where $k$ is the number of eigenvectors used. The resulting
points can be grouped in clusters by using standard partitional clustering
techniques like $k$-means clustering MacQueen (1967).

Spectral clustering is not always reliable, however. When the network is very
sparse (Section II.3) the separation between the eigenvalues of the community-
related eigenvectors and the bulk is not sharp. Eigenvectors corresponding to
eigenvalues outside of the bulk may be correlated to high-degree vertices
(hubs), instead of group structure. Likewise, community-related eigenvectors
can be associated to eigenvalues ending up inside the bulk. In these
situations, selecting eigenvectors based on whether their associated
eigenvalues are inside or outside the bulk yields a heterogeneous set,
containing information both on communities and on other features (e. g.,
hubs). Using those eigenvectors for the spectral clustering procedure renders
community detection more difficult, sometimes impossible. Unfortunately, many
of the networks encountered in practical studies are very sparse and can lead
to this type of problems.

Indeed on sparse networks constructed with the planted partition model
spectral methods relying on standard matrices [adjacency matrix, Laplacian,
modularity matrix Newman (2006), etc.] fail before the theoretical
detectability limit (Section III.3) Krzakala _et al._ (2013). The non-
backtracking matrix ${\bf B}$ of Eq. (15) was introduced to address this
problem Krzakala _et al._ (2013). On the planted partition model the
associated eigenvalues of the community-related eigenvectors of ${\bf B}$ are
separated from the bulk until the theoretical detectability limit, so spectral
methods using the top eigenvectors of ${\bf B}$ are capable to find
communities as long as they are detectable, modulo the caveats we expressed in
Section IV.1.

###  IV.4 Overlapping communities: Vertex or Edge clustering?

Soft clustering, where communities may overlap, is an even harder problem than
hard clustering, where there is no community overlap. The possibility of
having multiple memberships for the vertices introduces additional degrees of
freedom in the problem, causing a huge expansion of the space of possible
solutions. It has been pointed out that overlapping communities, especially in
social networks, reflect different types of associations between people Evans
and Lambiotte (2009); Ahn _et al._ (2010). Two actors could be co-workers,
friends, relatives, sport mates, etc.. Actor $A$ could be a work colleague of
$B$ and a friend of $C$, so she would sit in the overlap between the community
of colleagues of $B$ and the community of friends of $C$. For this reason, it
has been suggested that an effective way to recover overlapping clusters is to
group edges, rather than vertices. In the example above, the edges connecting
$A$ with $B$ and $A$ with $C$ would be placed in different groups, and since
they both have $A$ as endpoint, the latter turns out to be an overlapping
vertex.

Moreover, edge clustering is claimed to have the additional advantage of
reconciling soft clustering with hierarchical community structure Ahn _et al._
(2010). If there is hierarchy, communities are nested within each other as
many times as there are hierarchical levels. Hierarchical structure is often
represented via dendrograms303030A dendrogram, or hierarchical tree, is a tree
diagram used to represent hierarchical partitions. At the bottom there are as
many nodes as there are vertices in the graph, representing the singleton
clusters. At the top there is one node (root), standing for the partition
grouping all vertices in a single cluster. Horizontal lines indicate mergers
of a pair of clusters or, equivalently, splits of one cluster. Each vertex of
the tree identifies one cluster, whose elements can be read by following all
bifurcations starting from the vertex all the way down to the leaves of the
tree., with the network being divided in clusters, which are in turn divided
in clusters, and so on until one ends up with singleton clusters, consisting
of one vertex each. But this can be done only if communities do not share
vertices. Overlapping vertices should be assigned to multiple clusters of
lower hierarchical levels, yielding multiple copies of them in the dendrogram.
Instead, one could build a dendrogram displaying edge communities, where each
edge is assigned to a single cluster, but clusters can still overlap because
edges in different clusters may share one endpoint Ahn _et al._ (2010).

Some remarks are in order. First, there may still be overlapping communities
even if there were a single type of association between the vertices. For
instance, if we keep only the friendship relationships within a given
population of actors, there are many social circles and there could be active
actors with multiple ties within two circles, or more. Second, in the
traditional picture of networks with community structure (Fig. 4), the edges
connecting two different groups may be assigned to one of the communities they
join or they could be put together in a separate group. Either way, they would
signal an overlap between the communities, which is artificial. This happens
even in the extreme case of a single edge connecting vertices $A$ and $B$ of
two groups, as that edge will have to be assigned to a group, which inevitably
forces $A$ and $B$ into a common cluster. Third, if we rely on the picture
emerging from the analysis by Yang and Leskovec Yang and Leskovec (2014)
(Section III.5) overlaps between clusters could be much denser than we expect,
hence not only vertices but also edges may be shared among different groups,
and edge dendrograms would have the same problem as classic vertex
dendrograms313131In this case, if we used edge clustering, each edge would be
placed in one cluster only. However, when one turns edge communities into
vertex communities, multiple relationships can be still recovered Ahn _et al._
(2010).. Fourth, the computational complexity of the calculation can rise
substantially, as in networks of interest there are typically many more edges
than vertices. Finally, there is nothing revealing that there is a conceptual
or algorithmic advantage in grouping edges versus vertices, other than works
showing that a specific edge clustering technique outperforms some vertex
clustering techniques on a specific set of networks.

To shed some light on the situation, we performed the following test. We took
some network data sets with annotated vertices, giving an indication about
what the communities of those networks could be323232We have seen in Section
III.4 that metadata are not necessarily correlated with topological clusters.
We used data sets for which there is some correlation.. For each network $G$
we derived the corresponding line graph $L(G)$, which is the graph whose
vertices are the edges of $G$, while edges are set between pairs of vertices
of $L(G)$ whose corresponding edges in $G$ are adjacent at one of their
endpoints. Vertex communities of $L(G)$ are then edge communities of the
original network $G$. The question is whether by working on $L(G)$ the
detection improves or not. We searched for overlapping communities with OSLOM
Lancichinetti _et al._ (2011). We applied OSLOM on the original graphs and on
their line graphs. The covers found on the line graphs were turned into covers
of the vertices of $G$, by replacing each vertex of $L(G)$ with the pair of
vertices of the corresponding edge of $G$.

Figure 23: Comparison between edge communities and vertex communities. The
diagram shows the similarity between the covers of annotated vertices of five
social networks and the topological covers found by OSLOM on them (left bar of
each pair) and on their line graphs (right bar). The networks represent
FaceBook friendships between students of US universities Traud _et al._
(2012). There are several annotations for each student, we selected those
which are more closely related to topological groups: year of study and
dormitory. The similarity was computed by using the normalised mutual
information (NMI), in the version for covers proposed by Lancichinetti,
Fortunato and Kertész Lancichinetti _et al._ (2009). Vertex communities
detected in the original graphs are overall better correlated with the
annotated clusters than edge communities.

The results can be seen in Fig. 23, showing how similar the covers found on
the original networks and on the line graphs are with respect to the covers of
annotated vertices. Neither approach is very accurate, as expected (see
Section III.4 and Fig. 16), but vertex communities show a greater association
to the annotated clusters than edge communities, except in a few instances
where the similarity is very low. Analyses carried out on LFR benchmark graphs
(not shown) lead to the same conclusion. We stress that traditional line
graphs have the problem that edges adjacent to a hub vertex in the original
graph turn into vertices who are all connected to each other, forming giant
cliques, which might dominate the structure of the line graph, misleading
clustering techniques. The procedure can be refined by introducing weights for
the edges of the line graphs, that can be computed in various ways, e. g.,
based on the similarity of the neighbourhoods of adjacent edges in the
original network Ahn _et al._ (2010).

Still we believe that our tests provide some evidence that edge clustering is
no better than vertex clustering, in general. The superiority of algorithms
based on either approach should be assessed a posteriori, case by case, and
the answer may depend on the specific data sets under investigation.

###  IV.5 Methods based on statistical inference

Statistical inference provides a powerful set of tools to tackle the problem
of community detection. The standard approach is to fit a generative network
model on the data Hastings (2006); Newman and Leicht (2007); Guimerà and
Sales-Pardo (2009); Karrer and Newman (2011); Ball _et al._ (2011); Peixoto
(2014). The stochastic block model (SBM) is by far the most used generative
model of graphs with communities (see Section II.3 and references therein). We
have seen that it can describe other types of group structure, like
disassortative and core-periphery structure (Fig. 8). The unnormalised maximum
log-likelihood that a given partition $g$ in $q$ groups of the network $G$ is
reproduced by the standard SBM reads Karrer and Newman (2011)

${\cal
L}_{S}(G|g)=\sum_{r,s=1}^{q}e_{rs}\log\left(\frac{e_{rs}}{n_{r}n_{s}}\right),$
(17)

where $e_{rs}$ is the number of edges running from group $r$ to group $s$,
$n_{r}$ ($n_{s}$) the number of vertices in $r$ ($s$) and the sum runs over
all pairs of groups (including when $r=s$). This version of the model,
however, does not account for the degree heterogeneity of most real networks,
so it does a poor job at describing the group structure of many of them.
Therefore, Karrer and Newman proposed the degree-corrected stochastic block
model (DCSBM) Karrer and Newman (2011), in which the degrees of the vertices
are kept constant, on average, via the introduction of additional suitable
parameters333333The authors were inspired by modularity maximisation, which
gives far better results when the null model consists of rewiring edges by
preserving the degree sequence of the network (on average), than by preserving
only the total number of edges.. The unnormalised maximum log-likelihood for
the DCSBM is

${\cal
L}_{DC}(G|g)=\sum_{r,s=1}^{q}e_{rs}\log\left(\frac{e_{rs}}{e_{r}e_{s}}\right),$
(18)

where $e_{r}$ ($e_{s}$) is the sum of the degrees of the vertices in $r$
($s$).

The most important drawback of this type of approach is the need to specify
the number $q$ of groups beforehand, which is usually unknown for real
networks. This is because a straight maximisation of the likelihoods of Eqs.
(17) and (18) over the whole set of possible solutions yields the trivial
partition in which each vertex is a cluster (overfitting). In Section IV.1 we
have seen ways to extract $q$ from spectral properties of the graph. But it
would be better to have statistically principled methods, to be consistent
with the approach used to perform the inference.

A possibility is model selection, for instance by choosing the model that best
compresses the data Rissanen (1978); Grünwald _et al._ (2005). The extent of
the compression can be estimated via the total amount of information necessary
to describe the data, which includes not only the fitted model, but also the
information necessary to describe the model itself, which is a growing
function of the number of blocks $q$ Peixoto (2013). This quantity, that we
indicate with $\Sigma$, is called the description length. Minimising the
description length naturally avoids overfitting. Partitions with large $q$ are
associated to “heavy” models in terms of their information content, and do not
represent the best compression. On the other hand, partitions with low $q$
have high information content, even if the model itself is not loaded with
parameters. Hence the minimum description length corresponds to a non-trivial
number of groups and it makes sense to minimise $\Sigma$ to infer the block
structure of the graph.

It turns out that this approach has a limited resolution on the standard SBM:
the maximum number of blocks that can be resolved scales as $\sqrt{n}$ for a
fixed average degree $\langle k\rangle$, where $n$ is the number of vertices
of the network. This means that the minimum size of detectable blocks scales
as $\sqrt{n}$, just as it happens for modularity maximisation (Section IV.6).
A more refined method of model selection, consisting in a nested hierarchy of
stochastic block models, where an upper level of the hierarchy serves as prior
information to a lower level, brings the resolution limit down to $\log n$,
enabling the detection of much smaller blocks Peixoto (2014).

Other techniques to extract the number of groups have been proposed Handcock
_et al._ (2007); Daudin _et al._ (2008); Latouche _et al._ (2012); Côme and
Latouche (2015); Newman and Reinert (2016).

###  IV.6 Methods based on optimisation

Optimisation techniques have received the greatest attention in the
literature. The goal is finding an extremum, usually the maximum, of a
function indicating the quality of a clustering, over the space of all
possible clusterings. Quality functions can express the goodness of a
partition or of single clusters.

The most popular quality function is the modularity by Newman and Girvan