\HeaderA{modularity}{Modularity of a community structure of a graph}{modularity}
\keyword{graphs}{modularity}
\begin{Description}\relax
This function calculates how modular is a given division of a
graph into subgraphs.
\end{Description}
\begin{Usage}
\begin{verbatim}
modularity(graph, membership, weights = NULL)
\end{verbatim}
\end{Usage}
\begin{Arguments}
\begin{ldescription}
\item[\code{graph}] The input graph.
\item[\code{membership}] Numeric vector, for each vertex it gives its
community. The communities are numbered from zero.

\item[\code{weights}] If not \code{NULL} then a numeric vector giving edge
weights.
\end{ldescription}
\end{Arguments}
\begin{Details}\relax
The modularity of a graph with respect to some division (or vertex
types) measures how good the division is, or how separated are the 
different vertex types from each other. It defined as 
\deqn{Q=\frac{1}{2m} \sum_{i,j} A_{ij}-\frac{k_ik_j}{2m}\delta(c_i,c_j),}{}
here \eqn{m}{} is the number of edges, \eqn{A_{ij}}{} is the element
of the \eqn{A}{} adjacency matrix 
in row \eqn{i}{} and column \eqn{j}{}, \eqn{k_i}{} is the degree of \eqn{i}{},
\eqn{k_j}{} is the degree of \eqn{j}{}, \eqn{c_i}{} is the type (or
component) of \eqn{i}{}, \eqn{c_j}{} that of \eqn{j}{}, the sum goes
over all \eqn{i}{} and \eqn{j}{} pairs of vertices, and
\eqn{\delta(x,y)}{} is 1 if \eqn{x=y}{} and 0 otherwise.

If edge weights are given, then these are considered as the element of
the \eqn{A}{} adjacency matrix, and \eqn{k_i}{} is the sum of weights
of adjacent edges for vertex \eqn{i}{}.
\end{Details}
\begin{Value}
A numeric scalar, the modularity score of the given configuration.
\end{Value}
\begin{Author}\relax
Gabor Csardi \email{csardi@rmki.kfki.hu}
\end{Author}
\begin{References}\relax
MEJ Newman and M Girvan: Finding and evaluating community
structure in networks. Physical Review E 69 026113, 2004.
\end{References}
\begin{SeeAlso}\relax
\code{\LinkA{walktrap.community}{walktrap.community}},
\code{\LinkA{edge.betweenness.community}{edge.betweenness.community}},
\code{\LinkA{fastgreedy.community}{fastgreedy.community}},
\code{\LinkA{spinglass.community}{spinglass.community}} for various 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))
wtc <- walktrap.community(g)
memb <- community.to.membership(g, wtc$merges, steps=12)
modularity(g, memb$membership)
\end{ExampleCode}
\end{Examples}

