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
|
% Generated by roxygen2 (4.1.1): do not edit by hand
% Please edit documentation in R/structural.properties.R
\name{estimate_betweenness}
\alias{betweenness}
\alias{betweenness.estimate}
\alias{edge.betweenness}
\alias{edge.betweenness.estimate}
\alias{edge_betweenness}
\alias{estimate_betweenness}
\alias{estimate_edge_betweenness}
\title{Vertex and edge betweenness centrality}
\usage{
estimate_betweenness(graph, vids = V(graph), directed = TRUE, cutoff,
weights = NULL, nobigint = TRUE)
betweenness(graph, v = V(graph), directed = TRUE, weights = NULL,
nobigint = TRUE, normalized = FALSE)
edge_betweenness(graph, e = E(graph), directed = TRUE, weights = NULL)
}
\arguments{
\item{graph}{The graph to analyze.}
\item{vids}{The vertices for which the vertex betweenness estimation will be
calculated.}
\item{directed}{Logical, whether directed paths should be considered while
determining the shortest paths.}
\item{cutoff}{The maximum path length to consider when calculating the
betweenness. If zero or negative then there is no such limit.}
\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.}
\item{nobigint}{Logical scalar, whether to use big integers during the
calculation. This is only required for lattice-like graphs that have very
many shortest paths between a pair of vertices. If \code{TRUE} (the
default), then big integers are not used.}
\item{v}{The vertices for which the vertex betweenness will be calculated.}
\item{normalized}{Logical scalar, whether to normalize the betweenness
scores. If \code{TRUE}, then the results are normalized according to
\deqn{B^n=\frac{2B}{n^2-3n+2}}{Bnorm=2*B/(n*n-3*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.}
\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}.
\code{estimate_betweenness} returns the estimated betweenness scores for
vertices in \code{vids}, \code{estimate_edge_betweenness} the estimated edge
betweenness score for \emph{all} edges; both in a numeric vector.
}
\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 \eqn{v}{\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 \eqn{e}{\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.
\code{estimate_betweenness} 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{estimate_edge_betweenness} is similar, but for edges.
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)
}
\author{
Gabor Csardi \email{csardi.gabor@gmail.com}
}
\references{
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.
}
\seealso{
\code{\link{closeness}}, \code{\link{degree}}
}
\keyword{graphs}
|
