\HeaderA{edge.betweenness.community}{Community structure detection based on edge betweenness}{edge.betweenness.community}
\methaliasA{edge.betweenness.community.merges}{edge.betweenness.community}{edge.betweenness.community.merges}
\keyword{graphs}{edge.betweenness.community}
\begin{Description}\relax
Many networks consist of modules which are densely
connected themselves but sparsely connected to other modules.
\end{Description}
\begin{Usage}
\begin{verbatim}
edge.betweenness.community (graph, directed = TRUE,
    edge.betweenness = TRUE, merges = TRUE, bridges = TRUE,
    labels = TRUE)
edge.betweenness.community.merges (graph, edges)
\end{verbatim}
\end{Usage}
\begin{Arguments}
\begin{ldescription}
\item[\code{graph}] The graph to analyze.
\item[\code{directed}] Logical constant, whether to calculate directed edge
betweenness for directed graphs. It is ignored for undirected
graphs.
\item[\code{edge.betweenness}] Logical constant, whether to return the edge
betweenness of the edges at the time of their removal.
\item[\code{merges}] Logical constant, whether to return the merge matrix
representing the hierarchical community structure of the network.
This argument is called \code{merges}, even if the community
structure algorithm itself is divisive and not agglomerative: it
builds the tree from top to bottom. There is one line for each merge
(ie. split) in matrix, the first line is the first merge (last
split). The communities are identified by integer number starting from
zero. Community ids smaller than \sQuote{\code{N}}, the number of
vertices in the graph, belong to singleton communities, ie. individual
vertices. Before the first merge we have \sQuote{\code{N}} communities
numbered from zero to \sQuote{\code{N-1}}. The first merge, the
first line of the matrix creates community \sQuote{\code{N}}, the
second merge creates community \sQuote{\code{N+1}}, etc.

\item[\code{bridges}] Logical constant, whether to return a list the edge
removals which actually splitted a component of the graph.
\item[\code{labels}] Logical constant, whether to contain the labels of the
vertices in the result. More precisely, if the graph has a vertex
attribute valled \sQuote{name}, it will be part of the result
object.
\item[\code{edges}] Numeric vector, the ids of the edges to be removed from a
graph, all edges should be present in the vector, their order
specifies the order of removal.
\end{ldescription}
\end{Arguments}
\begin{Details}\relax
The edge betweenness score of an edge measures the number of shortest
paths through it, see \code{\LinkA{edge.betweenness}{edge.betweenness}} for details. The
idea of the edge betweenness based community structure detection is
that it is likely that edges connecting separate modules have high
edge betweenness as all the shortest paths from one module to another
must traverse through them. So if we gradually remove the edge with
the highest edge betweenness score we will get a hierarchical map, a
rooted tree, called a dendrogram of the graph. The leafs of the tree
are the individual vertices and the root of the tree represents the
whole graph. 

\code{edge.betweenness.community} performs this algorithm by
calculating the edge betweenness of the graph, removing the edge with
the highest edge betweenness score, then recalculating edge
betweenness of the edges and again removing the one with the highest
score, etc.

\code{edge.betweeness.community} returns various information collected
throught the run of the algorithm. See the return value down here.

\code{edge.betweenness.community.merges} gets a list of edges and by
gradually removes them from the graph it creates a merge matrix
similar to the one returned by \code{edge.betweenness.community}.
\end{Details}
\begin{Value}
A named list is returned by \code{edge.betweenness.community},
with the following components:
\begin{ldescription}
\item[\code{removed.edges}] Numeric vector, the edges of the graph, in the
order of their removal.
\item[\code{edge.betweenness}] Numeric vector, the edge betweenness value
of the removed edges, the order is the same as in
\code{removed.edges}.
\item[\code{merges}] Matrix containing the merges (ie. divisions) the
algorithm performed, see the \code{merges} argument for the
format.
\item[\code{bridges}] Numeric vector, the steps (ie. edge removals) which
resulted a split of a component in the graph.
\item[\code{labels}] The \code{name} argument of the vertices.
\end{ldescription}


Note that some components may be missing or \code{NULL} if you do not
request them, see the parameters.

A numeric matrix is returned by
\code{edge.betweenness.community.merges}.
The matrix has two column and its format is the same as the
\code{merges} slot of the result of
\code{edge.betweenness.community}.
\end{Value}
\begin{Author}\relax
Gabor Csardi \email{csardi@rmki.kfki.hu}
\end{Author}
\begin{References}\relax
M Newman and M Girvan: Finding and evaluating community
structure in networks, \emph{Physical Review E} 69, 026113 (2004)
\end{References}
\begin{SeeAlso}\relax
\code{\LinkA{edge.betweenness}{edge.betweenness}} for the definition and
calculation of the edge betweenness,
\code{\LinkA{walktrap.community}{walktrap.community}}, \code{\LinkA{fastgreedy.community}{fastgreedy.community}},
\code{\LinkA{leading.eigenvector.community}{leading.eigenvector.community}} for other community
detection methods. \code{\LinkA{as.dendrogram}{as.dendrogram}} for creating an
R dendrogram object from the result of the clustering. See
\code{\LinkA{community.to.membership}{community.to.membership}} to create the actual communities
after a number of edges removed from the network.
\end{SeeAlso}
\begin{Examples}
\begin{ExampleCode}
g <- barabasi.game(100,m=2)
eb <- edge.betweenness.community(g)

g <- graph.full(10) %du% graph.full(10)
g <- add.edges(g, c(0,10))
eb <- edge.betweenness.community(g)
E(g) [ eb$removed.edges[1] ]            
\end{ExampleCode}
\end{Examples}

