\HeaderA{walktrap.community}{Community strucure via short random walks}{walktrap.community}
\keyword{graphs}{walktrap.community}
\begin{Description}\relax
This function tries to find densely connected subgraphs,
also called communities in a graph via random walks. The idea is that
short random walks tend to stay in the same community.
\end{Description}
\begin{Usage}
\begin{verbatim}
walktrap.community(graph, weights = E(graph)$weight, steps = 4, merges =
          TRUE, modularity = FALSE, labels = TRUE)
\end{verbatim}
\end{Usage}
\begin{Arguments}
\begin{ldescription}
\item[\code{graph}] The input graph.
\item[\code{weights}] The edge weights.
\item[\code{steps}] The length of the random walks to perform.
\item[\code{merges}] Logical scalar, whether to include the merge matrix in
the result.
\item[\code{modularity}] Logical scalar, whether to include the vector of the
modularity scores in the result.
\item[\code{labels}] Logical scalar, if \code{TRUE} and the graph has a
vertex attribute called \code{name} then it will be included in the
result, in the list member called \code{labels}.
\end{ldescription}
\end{Arguments}
\begin{Details}\relax
This function is the implementation of the Walktrap community
finding algorithm, see Pascal Pons, Matthieu Latapy: Computing
communities in large networks using random walks, 
http://arxiv.org/abs/physics/0512106
\end{Details}
\begin{Value}
A named list with three members:
\begin{ldescription}
\item[\code{merges}] The merges performed by the
algorithm will be stored here. Each merge is a
row in a two-column matrix and contains the ids of the merged
communities. Communities are numbered from zero and cluster number 
smaller than the number of nodes in the network belong to the
individual vertices as singleton communities. In each step a new
community is created from two other communities and its id will be 
one larger than the largest community id so far. This means that 
before the first merge we have \code{n} communities (the number of
vertices in the graph) numbered from zero to \code{n-1}. The first
merge created community \code{n}, the second community \code{n+1}, etc.

\item[\code{modularity}] Numeric vector, the modularity score of the
current community structure after each merge operation. 

\item[\code{labels}] The labels of the vertices in the graph. The
\code{name} vertex attribute will be copied here, if exists.

\end{ldescription}
\end{Value}
\begin{Author}\relax
Pascal Pons \email{google@for.it} and Gabor Csardi
\email{csardi@rmki.kfki.hu} for the R and igraph interface
\end{Author}
\begin{References}\relax
Pascal Pons, Matthieu Latapy: Computing
communities in large networks using random walks, 
http://arxiv.org/abs/physics/0512106
\end{References}
\begin{SeeAlso}\relax
\code{\LinkA{modularity}{modularity}} and 
\code{\LinkA{fastgreedy.community}{fastgreedy.community}},
\code{\LinkA{spinglass.community}{spinglass.community}},
\code{\LinkA{leading.eigenvector.community}{leading.eigenvector.community}},
\code{\LinkA{edge.betweenness.community}{edge.betweenness.community}} for other community detection
methods.
\end{SeeAlso}
\begin{Examples}
\begin{ExampleCode}
g <- graph.full(5) %du% graph.full(5) %du% graph.full(5)
g <- add.edges(g, c(0,5, 0,10, 5, 10))
walktrap.community(g)
\end{ExampleCode}
\end{Examples}

