Leidenbase consists of R and C++ interfaces for the basic community detection functions of Vincent Traags’s Leidenalg package. The Leidenalg algorithm is described in the article
Traag, V.A., Waltman. L., Van Eck, N.-J. (2018). From Louvain to Leiden: guaranteeing well-connected communities. Scientific reports, 9(1), 5233. 10.1038/s41598-019-41695-z
Detailed information describing use of the leiden algorithm is available at
https://leidenalg.readthedocs.io/en/latest/
leidenalg source code is available at
The R interface consists of the leiden_find_partition
function
leiden_find_partition( igraph, partition_type = c("CPMVertexPartition", "ModularityVertexPartition", "RBConfigurationVertexPartition", "RBERVertexPartition", "SignificanceVertexPartition", "SurpriseVertexPartition"), initial_membership = NULL, edge_weights = NULL, node_sizes = NULL, seed = NULL, resolution_parameter = 0.1, num_iter = 2, verbose = FALSE )
Arguments:
igraph: R igraph graph.
partition_type: String partition type name. Default is CPMVertexParition.
initial_membership: Numeric vector of initial membership assignments of nodes.
These are 1-based indices. Default is one community per
node.
edge_weights: Numeric vector of edge weights. Default is 1.0 for all edges.
node_sizes: Numeric vector of node sizes. Default is 1 for all nodes.
seed: Numeric random number generator seed. The seed value must be
either NULL for random seed values or greater than 0 for a
fixed seed value. Default is NULL.
resolution_parameter: Numeric resolution parameter. The value must be
greater than 0.0. Default is 0.1. The
resolution_parameter is ignored
for the partition_types ModularityVertexPartition,
SignificanceVertexPartition, and
SurpriseVertexPartition.
num_iter: Numeric number of iterations. Default is 2.
verbose: A logic flag to determine whether or not we should print run
diagnostics.
Value:
A named list consisting of a numeric vector where each value is the community
to which the node belongs (1-based indices), a numeric quality value, a
numeric modularity, a numeric significance, a numeric vector of edge weights
within each community, a numeric vector of edge weights from each community,
a numeric vector of edge weights to each community, and total edge weight.In order to use leiden_find_partition, create or load an
igraph graph and then call leiden_find_partition. For
example,
library(igraph)
fpath <- system.file('testdata', 'igraph_n1500_edgelist.txt.gz', package='leidenbase')
zfp <- gzfile(fpath)
igraph <- read_graph(file = zfp, format='edgelist')
res <- leiden_find_partition(igraph, partition_type = 'CPMVertexPartition', seed = 123456, resolution_parameter = 0.5)leiden_find_partition returns
str(res)## List of 8
## $ membership : int [1:1500] 22 41 2 30 39 12 40 31 30 4 ...
## $ quality : num 11835
## $ modularity : num 0.426
## $ significance : num 87495
## $ edge_weight_within_community: num [1:115] 1489 1284 1205 1147 893 ...
## $ edge_weight_from_community : num [1:115] 1786 2021 2069 1576 1742 ...
## $ edge_weight_to_community : num [1:115] 1786 2021 2069 1576 1742 ...
## $ total_edge_weight : num 61636The membership vector consists of the community value for each node. For example,
head(res[['membership']])## [1] 22 41 2 30 39 12The nodes that belong to community 1 are
which(res[['membership']]==1)## [1] 33 35 41 116 140 151 172 178 208 214 238 308 367 440 454
## [16] 496 745 814 834 836 849 854 860 869 870 927 937 1042 1062 1104
## [31] 1111 1139 1238 1248 1263 1277 1297 1323 1348 1377 1382 1407 1483The first three communities are
# lim1 <- max(res$membership)
lim1 <- 3
for( i in seq(lim1)) {
cat(paste0('Community ', i, ':'))
for(j in which(res[['membership']]==i))
cat(' ', j)
cat('\n')
}## Community 1: 33 35 41 116 140 151 172 178 208 214 238 308 367 440 454 496 745 814 834 836 849 854 860 869 870 927 937 1042 1062 1104 1111 1139 1238 1248 1263 1277 1297 1323 1348 1377 1382 1407 1483
## Community 2: 3 94 96 112 127 154 195 232 248 283 297 363 385 451 455 464 517 565 671 797 802 839 971 976 1002 1037 1051 1106 1117 1120 1123 1195 1249 1257 1281 1283 1355 1395 1397 1479
## Community 3: 168 179 220 320 327 351 417 419 423 509 594 618 623 645 733 778 801 887 929 959 998 1011 1016 1088 1147 1155 1168 1201 1206 1258 1269 1290 1295 1312 1347 1389 1427 1432 1480The C/C++ interface consists of the leidenFindPartition
function
int leidenFindPartition( igraph_t *pigraph,
std::string const partitionType,
std::vector < size_t > const *pinitialMembership,
std::vector < double > const *pedgeWeights,
std::vector < size_t > const *pnodeSizes,
size_t seed,
double resolutionParameter,
std::int32_t numIter,
std::vector < size_t > *pmembership,
std::vector < double > *pweightInCommunity,
std::vector < double > *pweightFromCommunity,
std::vector < double > *pweightToCommunity,
double *pweightTotal,
double *pquality,
double *pmodularity,
double *psignificance,
int *pstatus )
Parameters:
igraph: pointer to igraph_t graph
partitionType partition type used for optimization
initialMembership vector of initial membership assignments of nodes (NULL
for default of one community per node)
edgeWeights vector of weights of edges (NULL for default of 1.0)
nodeSizes vector of node sizes (NULL for default of 1)
seed random number generator seed (0=random seed)
resolutionParameter resolution parameter
numIter number of iterations
pmembership vector of node membership assignments
pweightInCommunity vector of edge weights within community
pweightFromCommunity vector of edge weights from community
pweightToCommunity vector of edge weights to community
pweightTotal total edge weights
pquality partition quality
pmodularity partition modularity
psignificance partition significance
pstatus function status (0=success; -1=failure)Notes for the C/C++ interface:
R_INTERFACE to 0.leidenFindPartition function, compile and
link to the files src/leidenFindPartition.(cpp|h),
src/leidenalg/src/*.cpp, and src/leidenalg/include/*.h and a C igraph
object library.