betweenness

0th

Percentile

Vertex and edge betweenness centrality

The vertex and edge betweenness are (roughly) defined by the number of geodesics (shortest paths) going through a vertex or an edge.

Keywords
graphs
Usage
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)
Arguments
graph
The graph to analyze.
v
The vertices for which the vertex betweenness will be calculated.
e
The edges for which the edge betweenness will be calculated.
directed
Logical, whether directed paths should be considered while determining the shortest paths.
verbose
Logical, whether to show a progress bar.
vids
The vertices for which the vertex betweenness estimation will be calculated.
cutoff
The maximum path length to consider when calculating the betweenness. If zero or negative then there is no such limit.
Details

The vertex betweenness of vertex $v$ is defined by

$$\sum_{i\ne j, i\ne v, j\ne v} g_{ivj}/g_{ij}$$ The edge betweenness of edge $e$ is defined by

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

betweenness calculates vertex betweenness, edge.betweenness calculates edge.betweenness.

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

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.

Value

• A numeric vector with the betweenness score for each vertex in v for betweenness.

A numeric vector with the edge betweenness score for each edge in e for edge.betweenness.

betweenness.estimate returns the estimated betweenness scores for vertices in vids, edge.betweenness.estimate the estimated edge betweenness score for all edges; both in a numeric vector.

Note

edge.betweenness might give false values for graphs with multiple edges.

concept

• Betweenness centrality
• Edge betweenness

References

Freeman, L.C. (1979). Centrality in Social Networks I: Conceptual Clarification. Social Networks, 1, 215-239.

Ulrik Brandes, A Faster Algorithm for Betweenness Centrality. Journal of Mathematical Sociology 25(2):163-177, 2001.

closeness, degree

Aliases
• betweenness
• edge.betweenness
• betweenness.estimate
• edge.betweenness.estimate
Examples
g <- random.graph.game(10, 3/10)
betweenness(g)
edge.betweenness(g)
Documentation reproduced from package igraph, version 0.5.3, License: GPL (>= 2)

Community examples

Looks like there are no examples yet.