\HeaderA{betweenness}{Vertex and edge betweenness centrality}{betweenness}
\methaliasA{betweenness.estimate}{betweenness}{betweenness.estimate}
\aliasA{edge.betweenness}{betweenness}{edge.betweenness}
\methaliasA{edge.betweenness.estimate}{betweenness}{edge.betweenness.estimate}
\keyword{graphs}{betweenness}
\begin{Description}\relax
The vertex and edge betweenness are (roughly) defined by
the number of geodesics (shortest paths) going through a vertex or an
edge.
\end{Description}
\begin{Usage}
\begin{verbatim}
betweenness(graph, v=V(graph), directed = TRUE, verbose = igraph.par("verbose"))
edge.betweenness(graph, e=E(graph), directed = TRUE)
betweenness.estimate(graph, vids = V(graph), directed = TRUE, cutoff,
     verbose = igraph.par("verbose"))
edge.betweenness.estimate(graph, directed = TRUE, cutoff)
\end{verbatim}
\end{Usage}
\begin{Arguments}
\begin{ldescription}
\item[\code{graph}] The graph to analyze.
\item[\code{v}] The vertices for which the vertex betweenness will be
calculated.
\item[\code{e}] The edges for which the edge betweenness will be
calculated.
\item[\code{directed}] Logical, whether directed paths should be considered
while determining the shortest paths.
\item[\code{verbose}] Logical, whether to show a progress bar.
\item[\code{vids}] The vertices for which the vertex betweenness estimation
will be calculated.
\item[\code{cutoff}] The maximum path length to consider when calculating the
betweenness. If zero or negative then there is no such limit.
\end{ldescription}
\end{Arguments}
\begin{Details}\relax
The vertex betweenness of vertex \eqn{v}{} is defined
by

\deqn{\sum_{i\ne j, i\ne v, j\ne v} g_{ivj}/g_{ij}}{}

The edge betweenness of edge \eqn{e}{} is defined by

\deqn{\sum_{i\ne j} g{iej}/g_{ij}}{}.

\code{betweenness} calculates vertex betweenness,
\code{edge.betweenness} calculates edge.betweenness.

\code{betweenness.estimate} only considers paths of length
\code{cutoff} or smaller, this can be run for larger graphs, as the
running time is not quadratic (if \code{cutoff} is small). If
\code{cutoff} is zero or negative then the function calculates the
exact betweenness scores.

\code{edge.betweenness.estimate} is similar, but for edges.

For calculating the betweenness a similar algorithm to the one
proposed by Brandes (see References) is used.
\end{Details}
\begin{Value}
A numeric vector with the betweenness score for each vertex in
\code{v} for \code{betweenness}.

A numeric vector with the edge betweenness score for each edge in
\code{e} for \code{edge.betweenness}.

\code{betweenness.estimate} returns the estimated betweenness scores
for vertices in \code{vids}, \code{edge.betweenness.estimate}
the estimated edge betweenness score for \emph{all} edges; both in
a numeric vector.
\end{Value}
\begin{Note}\relax
\code{edge.betweenness} might give false values for graphs with
multiple edges.
\end{Note}
\begin{Author}\relax
Gabor Csardi \email{csardi@rmki.kfki.hu}
\end{Author}
\begin{References}\relax
Freeman, L.C. (1979). Centrality in Social Networks I:
Conceptual Clarification. \emph{Social Networks}, 1, 215-239.

Ulrik Brandes, A Faster Algorithm for Betweenness Centrality. \emph{Journal
of Mathematical Sociology} 25(2):163-177, 2001.
\end{References}
\begin{SeeAlso}\relax
\code{\LinkA{closeness}{closeness}}, \code{\LinkA{degree}{degree}}
\end{SeeAlso}
\begin{Examples}
\begin{ExampleCode}
g <- random.graph.game(10, 3/10)
betweenness(g)
edge.betweenness(g)
\end{ExampleCode}
\end{Examples}

