1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
|
% Generated by roxygen2: do not edit by hand
% Please edit documentation in R/community.R
\name{cluster_leiden}
\alias{cluster_leiden}
\title{Finding community structure of a graph using the Leiden algorithm of Traag,
van Eck & Waltman.}
\usage{
cluster_leiden(
graph,
objective_function = c("CPM", "modularity"),
...,
weights = NULL,
resolution = 1,
resolution_parameter = deprecated(),
beta = 0.01,
initial_membership = NULL,
n_iterations = 2,
vertex_weights = NULL
)
}
\arguments{
\item{graph}{The input graph. It must be undirected.}
\item{objective_function}{Whether to use the Constant Potts Model (CPM) or
modularity. Must be either \code{"CPM"} or \code{"modularity"}.}
\item{...}{These dots are for future extensions and must be empty.}
\item{weights}{The weights of the edges. It must be a positive numeric vector,
\code{NULL} or \code{NA}. If it is \code{NULL} and the input graph has a
\sQuote{weight} edge attribute, then that attribute will be used. If
\code{NULL} and no such attribute is present, then the edges will have equal
weights. Set this to \code{NA} if the graph was a \sQuote{weight} edge
attribute, but you don't want to use it for community detection. A larger
edge weight means a stronger connection for this function.}
\item{resolution}{The resolution parameter to use. Higher
resolutions lead to more smaller communities, while lower resolutions lead
to fewer larger communities.}
\item{resolution_parameter}{\ifelse{html}{\href{https://lifecycle.r-lib.org/articles/stages.html#superseded}{\figure{lifecycle-superseded.svg}{options: alt='[Superseded]'}}}{\strong{[Superseded]}} Use \code{resolution} instead.}
\item{beta}{Parameter affecting the randomness in the Leiden algorithm.
This affects only the refinement step of the algorithm.}
\item{initial_membership}{If provided, the Leiden algorithm
will try to improve this provided membership. If no argument is
provided, the aglorithm simply starts from the singleton partition.}
\item{n_iterations}{the number of iterations to iterate the Leiden
algorithm. Each iteration may improve the partition further.}
\item{vertex_weights}{the vertex weights used in the Leiden algorithm.
If this is not provided, it will be automatically determined on the basis
of the \code{objective_function}. Please see the details of this function
how to interpret the vertex weights.}
}
\value{
\code{cluster_leiden()} returns a \code{\link[=communities]{communities()}}
object, please see the \code{\link[=communities]{communities()}} manual page for details.
}
\description{
The Leiden algorithm is similar to the Louvain algorithm,
\code{\link[=cluster_louvain]{cluster_louvain()}}, but it is faster and yields higher quality
solutions. It can optimize both modularity and the Constant Potts Model,
which does not suffer from the resolution-limit (see preprint
http://arxiv.org/abs/1104.3083).
}
\details{
The Leiden algorithm consists of three phases: (1) local moving of nodes,
(2) refinement of the partition and (3) aggregation of the network based on
the refined partition, using the non-refined partition to create an initial
partition for the aggregate network. In the local move procedure in the
Leiden algorithm, only nodes whose neighborhood has changed are visited. The
refinement is done by restarting from a singleton partition within each
cluster and gradually merging the subclusters. When aggregating, a single
cluster may then be represented by several nodes (which are the subclusters
identified in the refinement).
The Leiden algorithm provides several guarantees. The Leiden algorithm is
typically iterated: the output of one iteration is used as the input for the
next iteration. At each iteration all clusters are guaranteed to be
connected and well-separated. After an iteration in which nothing has
changed, all nodes and some parts are guaranteed to be locally optimally
assigned. Finally, asymptotically, all subsets of all clusters are
guaranteed to be locally optimally assigned. For more details, please see
Traag, Waltman & van Eck (2019).
The objective function being optimized is
\deqn{\frac{1}{2m} \sum_{ij} (A_{ij} - \gamma n_i n_j)\delta(\sigma_i, \sigma_j)}{1 / 2m sum_ij (A_ij - gamma n_i n_j)d(s_i, s_j)}
where \eqn{m}{m} is the total edge weight, \eqn{A_{ij}}{A_ij} is the weight
of edge \eqn{(i, j)}, \eqn{\gamma}{gamma} is the so-called resolution
parameter, \eqn{n_i} is the node weight of node \eqn{i}, \eqn{\sigma_i}{s_i}
is the cluster of node \eqn{i} and \eqn{\delta(x, y) = 1}{d(x, y) = 1} if and
only if \eqn{x = y} and \eqn{0} otherwise. By setting \eqn{n_i = k_i}, the
degree of node \eqn{i}, and dividing \eqn{\gamma}{gamma} by \eqn{2m}, you
effectively obtain an expression for modularity.
Hence, the standard modularity will be optimized when you supply the degrees
as \code{vertex_weights} and by supplying as a resolution parameter
\eqn{\frac{1}{2m}}{1/(2m)}, with \eqn{m} the number of edges. If you do not
specify any \code{vertex_weights}, the correct vertex weights and scaling of
\eqn{\gamma}{gamma} is determined automatically by the
\code{objective_function} argument.
}
\examples{
g <- make_graph("Zachary")
# By default CPM is used
r <- quantile(strength(g))[2] / (gorder(g) - 1)
# Set seed for sake of reproducibility
set.seed(1)
ldc <- cluster_leiden(g, resolution = r)
print(ldc)
plot(ldc, g)
}
\references{
Traag, V. A., Waltman, L., & van Eck, N. J. (2019). From Louvain
to Leiden: guaranteeing well-connected communities. Scientific
reports, 9(1), 5233. doi: 10.1038/s41598-019-41695-z, arXiv:1810.08473v3 [cs.SI]
}
\seealso{
See \code{\link[=communities]{communities()}} for extracting the membership,
modularity scores, etc. from the results.
Other community detection algorithms: \code{\link[=cluster_walktrap]{cluster_walktrap()}},
\code{\link[=cluster_spinglass]{cluster_spinglass()}},
\code{\link[=cluster_leading_eigen]{cluster_leading_eigen()}},
\code{\link[=cluster_edge_betweenness]{cluster_edge_betweenness()}},
\code{\link[=cluster_fast_greedy]{cluster_fast_greedy()}},
\code{\link[=cluster_label_prop]{cluster_label_prop()}}
\code{\link[=cluster_louvain]{cluster_louvain()}}
\code{\link[=cluster_fluid_communities]{cluster_fluid_communities()}}
\code{\link[=cluster_infomap]{cluster_infomap()}}
\code{\link[=cluster_optimal]{cluster_optimal()}}
\code{\link[=cluster_walktrap]{cluster_walktrap()}}
Community detection
\code{\link{as_membership}()},
\code{\link{cluster_edge_betweenness}()},
\code{\link{cluster_fast_greedy}()},
\code{\link{cluster_fluid_communities}()},
\code{\link{cluster_infomap}()},
\code{\link{cluster_label_prop}()},
\code{\link{cluster_leading_eigen}()},
\code{\link{cluster_louvain}()},
\code{\link{cluster_optimal}()},
\code{\link{cluster_spinglass}()},
\code{\link{cluster_walktrap}()},
\code{\link{compare}()},
\code{\link{groups}()},
\code{\link{make_clusters}()},
\code{\link{membership}()},
\code{\link{modularity.igraph}()},
\code{\link{plot_dendrogram}()},
\code{\link{split_join_distance}()},
\code{\link{voronoi_cells}()}
}
\author{
Vincent Traag
}
\concept{community}
\keyword{graphs}
|
