igraph (version 1.3.5)

estimate_betweenness: Vertex and edge betweenness centrality

Description

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

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,
  cutoff = -1
)
edge_betweenness(
  graph,
  e = E(graph),
  directed = TRUE,
  weights = NULL,
  cutoff = -1
)

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.

Arguments

graph

The graph to analyze.

vids

The vertices for which the vertex betweenness estimation will be calculated.

directed

Logical, whether directed paths should be considered while determining the shortest paths.

cutoff

The maximum path length to consider when calculating the betweenness. If zero or negative then there is no such limit.

weights

Optional positive weight vector for calculating weighted betweenness. If the graph has a weight edge attribute, then this is used by default. Weights are used to calculate weighted shortest paths, so they are interpreted as distances.

nobigint

Logical scalar, whether to use big integers during the calculation. Deprecated since igraph 1.3 and will be removed in igraph 1.4.

v

The vertices for which the vertex betweenness will be calculated.

normalized

Logical scalar, whether to normalize the betweenness scores. If 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, $$B^n=\frac{2B}{(n-1)(n-2)},$$ where \(B^n\) is the normalized, \(B\) the raw betweenness, and \(n\) is the number of vertices in the graph.

e

The edges for which the edge betweenness will be calculated.

Author

Gabor Csardi

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.

Here \(g_{ij}\) is the total number of shortest paths between vertices \(i\) and \(j\) while \(g_{ivj}\) is the number of those shortest paths which pass though vertex \(v\).

Both functions allow you to consider only 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. Using zero as a cutoff is deprecated and future versions (from 1.4.0) will treat zero cutoff literally (i.e. no paths considered at all). If you want no cutoff, use a negative number.

estimate_betweenness and estimate_edge_betweenness are aliases for betweenness and edge_betweenness, with a different argument order, for sake of compatibility with older versions of igraph.

For calculating the betweenness a similar algorithm to the one proposed by Brandes (see References) is used.

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.

See Also

closeness, degree, harmonic_centrality

Examples

g <- sample_gnp(10, 3/10)
betweenness(g)
edge_betweenness(g)