R: Finding communities based on propagating labels
cluster_label_prop
R Documentation
Finding communities based on propagating labels
Description
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.
The input graph, should be undirected to make sense.
weights
An optional weight vector. It should contain a positive
weight for all the edges. The ‘weight’ edge attribute is used if
present. Supply ‘NA’ here if you want to ignore the
‘weight’ edge attribute.
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.
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.”
Value
cluster_label_prop returns a
communities object, please see the communities
manual page for details.
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 and
cluster_spinglass for other community detection methods.
Examples
g <- sample_gnp(10, 5/10) %du% sample_gnp(9, 5/9)
g <- add_edges(g, c(1, 12))
cluster_label_prop(g)