1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
|
% Generated by roxygen2: do not edit by hand
% Please edit documentation in R/community.R
\name{cluster_edge_betweenness}
\alias{cluster_edge_betweenness}
\title{Community structure detection based on edge betweenness}
\usage{
cluster_edge_betweenness(
graph,
weights = NULL,
directed = TRUE,
edge.betweenness = TRUE,
merges = TRUE,
bridges = TRUE,
modularity = TRUE,
membership = TRUE
)
}
\arguments{
\item{graph}{The graph to analyze.}
\item{weights}{The weights of the edges. It must be a positive numeric vector,
\code{NULL} or \code{NA}. If it is \code{NULL} and the input graph has a
\sQuote{weight} edge attribute, then that attribute will be used. If
\code{NULL} and no such attribute is present, then the edges will have equal
weights. Set this to \code{NA} if the graph was a \sQuote{weight} edge
attribute, but you don't want to use it for community detection. Edge weights
are used to calculate weighted edge betweenness. This means that edges are
interpreted as distances, not as connection strengths.}
\item{directed}{Logical constant, whether to calculate directed edge
betweenness for directed graphs. It is ignored for undirected graphs.}
\item{edge.betweenness}{Logical constant, whether to return the edge
betweenness of the edges at the time of their removal.}
\item{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 (i.e. split) in matrix, the first
line is the first merge (last split). The communities are identified by
integer number starting from one. Community ids smaller than or equal to
\eqn{N}, the number of vertices in the graph, belong to singleton
communities, i.e. individual vertices. Before the first merge we have \eqn{N}
communities numbered from one to \eqn{N}. The first merge, the first line of
the matrix creates community \eqn{N+1}, the second merge creates community
\eqn{N+2}, etc.}
\item{bridges}{Logical constant, whether to return a list the edge removals
which actually splitted a component of the graph.}
\item{modularity}{Logical constant, whether to calculate the maximum
modularity score, considering all possibly community structures along the
edge-betweenness based edge removals.}
\item{membership}{Logical constant, whether to calculate the membership
vector corresponding to the highest possible modularity score.}
}
\value{
\code{cluster_edge_betweenness()} returns a
\code{\link[=communities]{communities()}} object, please see the \code{\link[=communities]{communities()}}
manual page for details.
}
\description{
Community structure detection based on the betweenness of the edges
in the network. This method is also known as the Girvan-Newman
algorithm.
}
\details{
The idea behind this method is that the betweenness of the edges connecting
two communities is typically high, as many of the shortest paths between
vertices in separate communities pass through them. The algorithm
successively removes edges with the highest betweenness, recalculating
betweenness values after each removal. This way eventually the network splits
into two components, then one of these components splits again, and so on,
until all edges are removed. The resulting hierarhical partitioning of the
vertices can be encoded as a dendrogram.
\code{cluster_edge_betweenness()} returns various information collected
through the run of the algorithm. Specifically, \code{removed.edges} contains
the edge IDs in order of the edges' removal; \code{edge.betweenness} contains
the betweenness of each of these at the time of their removal; and
\code{bridges} contains the IDs of edges whose removal caused a split.
}
\examples{
g <- sample_pa(100, m = 2, directed = FALSE)
eb <- cluster_edge_betweenness(g)
g <- make_full_graph(10) \%du\% make_full_graph(10)
g <- add_edges(g, c(1, 11))
eb <- cluster_edge_betweenness(g)
eb
}
\references{
M Newman and M Girvan: Finding and evaluating community
structure in networks, \emph{Physical Review E} 69, 026113 (2004)
}
\seealso{
\code{\link[=edge_betweenness]{edge_betweenness()}} for the definition and calculation
of the edge betweenness, \code{\link[=cluster_walktrap]{cluster_walktrap()}},
\code{\link[=cluster_fast_greedy]{cluster_fast_greedy()}},
\code{\link[=cluster_leading_eigen]{cluster_leading_eigen()}} for other community detection
methods.
See \code{\link[=communities]{communities()}} for extracting the results of the community
detection.
Community detection
\code{\link{as_membership}()},
\code{\link{cluster_fast_greedy}()},
\code{\link{cluster_fluid_communities}()},
\code{\link{cluster_infomap}()},
\code{\link{cluster_label_prop}()},
\code{\link{cluster_leading_eigen}()},
\code{\link{cluster_leiden}()},
\code{\link{cluster_louvain}()},
\code{\link{cluster_optimal}()},
\code{\link{cluster_spinglass}()},
\code{\link{cluster_walktrap}()},
\code{\link{compare}()},
\code{\link{groups}()},
\code{\link{make_clusters}()},
\code{\link{membership}()},
\code{\link{modularity.igraph}()},
\code{\link{plot_dendrogram}()},
\code{\link{split_join_distance}()},
\code{\link{voronoi_cells}()}
}
\author{
Gabor Csardi \email{csardi.gabor@gmail.com}
}
\concept{community}
\keyword{graphs}
|
