This is a fast, nearly linear time algorithm for detecting community structure in networks. In works by labeling the vertices with unique labels and then updating the labels by majority voting in the neighborhood of the vertex.
Usage
cluster_label_prop(
graph,
weights = NULL,
...,
mode = c("out", "in", "all"),
initial = NULL,
fixed = NULL
)
Arguments
- graph
The input graph. Note that the algorithm wsa originally defined for undirected graphs. You are advised to set ‘mode’ to
all
if you pass a directed graph here to treat it as undirected.- weights
The weights of the edges. It must be a positive numeric vector,
NULL
orNA
. If it isNULL
and the input graph has a ‘weight’ edge attribute, then that attribute will be used. IfNULL
and no such attribute is present, then the edges will have equal weights. Set this toNA
if the graph was a ‘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.- ...
These dots are for future extensions and must be empty.
- mode
Logical, whether to consider edge directions for the label propagation, and if so, in which direction the labels should propagate. Ignored for undirected graphs. "all" means to ignore edge directions (even in directed graphs). "out" means to propagate labels along the natural direction of the edges. "in" means to propagate labels backwards (i.e. from head to tail).
- initial
The initial state. If
NULL
, every vertex will have a different label at the beginning. Otherwise it must be a vector with an entry for each vertex. Non-negative values denote different labels, negative entries denote vertices without labels.- fixed
Logical vector denoting which labels are fixed. Of course this makes sense only if you provided an initial state, otherwise this element will be ignored. Also note that vertices without labels cannot be fixed.
Value
cluster_label_prop()
returns a
communities()
object, please see the communities()
manual page for details.
Details
This function implements the community detection method described in: Raghavan, U.N. and Albert, R. and Kumara, S.: Near linear time algorithm to detect community structures in large-scale networks. Phys Rev E 76, 036106. (2007). This version extends the original method by the ability to take edge weights into consideration and also by allowing some labels to be fixed.
From the abstract of the paper: “In our algorithm every node is initialized with a unique label and at every step each node adopts the label that most of its neighbors currently have. In this iterative process densely connected groups of nodes form a consensus on a unique label to form communities.”
References
Raghavan, U.N. and Albert, R. and Kumara, S.: Near linear time algorithm to detect community structures in large-scale networks. Phys Rev E 76, 036106. (2007)
See also
communities()
for extracting the actual results.
cluster_fast_greedy()
, cluster_walktrap()
,
cluster_spinglass()
, cluster_louvain()
and
cluster_leiden()
for other community detection methods.
Community detection
as_membership()
,
cluster_edge_betweenness()
,
cluster_fast_greedy()
,
cluster_fluid_communities()
,
cluster_infomap()
,
cluster_leading_eigen()
,
cluster_leiden()
,
cluster_louvain()
,
cluster_optimal()
,
cluster_spinglass()
,
cluster_walktrap()
,
compare()
,
groups()
,
make_clusters()
,
modularity.igraph()
,
plot_dendrogram()
,
split_join_distance()
Author
Tamas Nepusz ntamas@gmail.com for the C implementation, Gabor Csardi csardi.gabor@gmail.com for this manual page.
Examples
g <- sample_gnp(10, 5 / 10) %du% sample_gnp(9, 5 / 9)
g <- add_edges(g, c(1, 12))
cluster_label_prop(g)
#> IGRAPH clustering label propagation, groups: 2, mod: 0.48
#> + groups:
#> $`1`
#> [1] 1 2 3 4 5 6 7 8 9 10
#>
#> $`2`
#> [1] 11 12 13 14 15 16 17 18 19
#>