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
136
|
% Generated by roxygen2: do not edit by hand
% Please edit documentation in R/centrality.R
\name{betweenness}
\alias{betweenness}
\alias{betweenness.estimate}
\alias{edge.betweenness.estimate}
\alias{edge_betweenness}
\title{Vertex and edge betweenness centrality}
\usage{
betweenness(
graph,
v = V(graph),
directed = TRUE,
weights = NULL,
normalized = FALSE,
cutoff = -1
)
edge_betweenness(
graph,
e = E(graph),
directed = TRUE,
weights = NULL,
cutoff = -1
)
}
\arguments{
\item{graph}{The graph to analyze.}
\item{v}{The vertices for which the vertex betweenness will be calculated.}
\item{directed}{Logical, whether directed paths should be considered while
determining the shortest paths.}
\item{weights}{Optional positive weight vector for calculating weighted
betweenness. If the graph has a \code{weight} edge attribute, then this is
used by default. Weights are used to calculate weighted shortest paths,
so they are interpreted as distances.}
\item{normalized}{Logical scalar, whether to normalize the betweenness
scores. If \code{TRUE}, then the results are normalized by the number of ordered
or unordered vertex pairs in directed and undirected graphs, respectively.
In an undirected graph,
\deqn{B^n=\frac{2B}{(n-1)(n-2)},}{Bnorm=2 B / ((n-1)(n-2)),}
where
\eqn{B^n}{Bnorm} is the normalized, \eqn{B} the raw betweenness, and
\eqn{n} is the number of vertices in the graph. Note that the same
normalization factor is used even when setting a \code{cutoff} on the considered
shortest path lengths, even though the number of vertex pairs reachable
from each other may be less than \eqn{(n-1)(n-2)/2}.}
\item{cutoff}{The maximum shortest path length to consider when calculating
betweenness. If negative, then there is no such limit.}
\item{e}{The edges for which the edge betweenness will be calculated.}
}
\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()}.
}
\description{
The vertex and edge betweenness are (roughly) defined by the number of
geodesics (shortest paths) going through a vertex or an edge.
}
\details{
The vertex betweenness of vertex \code{v} is defined by
\deqn{\sum_{i\ne j, i\ne v, j\ne v} g_{ivj}/g_{ij}}{sum( g_ivj / g_ij,
i!=j,i!=v,j!=v)}
The edge betweenness of edge \code{e} is defined by
\deqn{\sum_{i\ne j} g_{iej}/g_{ij}.}{sum( g_iej / g_ij, i!=j).}
\code{betweenness()} calculates vertex betweenness, \code{edge_betweenness()}
calculates edge betweenness.
Here \eqn{g_{ij}}{g_ij} is the total number of shortest paths between vertices
\eqn{i} and \eqn{j} while \eqn{g_{ivj}} is the number of those shortest paths
which pass though vertex \eqn{v}.
Both functions allow you to consider only 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 negative (the default),
then the function calculates the exact betweenness scores. Since igraph 1.6.0,
a \code{cutoff} value of zero is treated literally, i.e. paths of length larger
than zero are ignored.
For calculating the betweenness a similar algorithm to the one proposed by
Brandes (see References) is used.
}
\note{
\code{edge_betweenness()} might give false values for graphs with
multiple edges.
}
\examples{
g <- sample_gnp(10, 3 / 10)
betweenness(g)
edge_betweenness(g)
}
\references{
Freeman, L.C. (1979). Centrality in Social Networks I:
Conceptual Clarification. \emph{Social Networks}, 1, 215-239.
\doi{10.1016/0378-8733(78)90021-7}
Ulrik Brandes, A Faster Algorithm for Betweenness Centrality. \emph{Journal
of Mathematical Sociology} 25(2):163-177, 2001.
\doi{10.1080/0022250X.2001.9990249}
}
\seealso{
\code{\link[=closeness]{closeness()}}, \code{\link[=degree]{degree()}}, \code{\link[=harmonic_centrality]{harmonic_centrality()}}
Centrality measures
\code{\link{alpha_centrality}()},
\code{\link{authority_score}()},
\code{\link{closeness}()},
\code{\link{diversity}()},
\code{\link{eigen_centrality}()},
\code{\link{harmonic_centrality}()},
\code{\link{hits_scores}()},
\code{\link{page_rank}()},
\code{\link{power_centrality}()},
\code{\link{spectrum}()},
\code{\link{strength}()},
\code{\link{subgraph_centrality}()}
}
\author{
Gabor Csardi \email{csardi.gabor@gmail.com}
}
\concept{centrality}
\keyword{graphs}
|
