\HeaderA{label.propagation.community}{Finding communities based on propagating labels}{label.propagation.community}
\keyword{graphs}{label.propagation.community}
\begin{Description}\relax
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.
\end{Description}
\begin{Usage}
\begin{verbatim}
label.propagation.community (graph, weights = NULL,
            initial = NULL, fixed = NULL)
\end{verbatim}
\end{Usage}
\begin{Arguments}
\begin{ldescription}
\item[\code{graph}] The input graph, should be undirected to make sense.
\item[\code{weights}] An optional weight vector. It should contain a positive
weight for all the edges. The \sQuote{weight} edge attribute is used
if present. Supply \sQuote{\code{NA}} here if you want to ignore the
\sQuote{weight} edge attribute.
\item[\code{initial}] The initial state. If \code{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.
\item[\code{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.
\end{ldescription}
\end{Arguments}
\begin{Details}\relax
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:
\dQuote{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.}
\end{Details}
\begin{Value}
A numeric vector giving the final label (=community) of each vertex.
\end{Value}
\begin{Author}\relax
Tamas Nepusz \email{ntamas@rmki.kfki.hu} for the C implementation,
Gabor Csardi \email{Gabor.Csardi@unil.ch} for this manual page.
\end{Author}
\begin{References}\relax
Raghavan, U.N. and Albert, R. and Kumara, S.: Near linear time algorithm
to detect community structures in large-scale networks. \emph{Phys Rev E}
76, 036106. (2007)
\end{References}
\begin{SeeAlso}\relax
\code{\LinkA{fastgreedy.community}{fastgreedy.community}},
\code{\LinkA{walktrap.community}{walktrap.community}} and \code{\LinkA{spinglass.community}{spinglass.community}}
for other community detection methods.
\end{SeeAlso}
\begin{Examples}
\begin{ExampleCode}
  g <- erdos.renyi.game(10, 5/10) %du% erdos.renyi.game(9, 5/9)
  g <- add.edges(g, c(0, 11))
  label.propagation.community(g)
\end{ExampleCode}
\end{Examples}

