How often is a vertex a bottleneck for other vertices in the graph?
The input graph as igraph object, a network object, or a, adjacency matrix
Character constant, gives whether the shortest paths to or from
the given vertices should be calculated for directed graphs.
If out then the shortest paths from the vertex, if in then to
it will be considered. If all, the default, then the corresponding
undirected graph will be used. This argument is ignored for undirected graphs.
Numeric vertex sequence, the vertices that should be considered.
Default is all vertices. Otherwise, the operation is performed on the
subgraph only containing vertices vids.
scalar, defaults to 4.
A data.frame with vertex names (if they exist) and bottleneck centrality scores. Otherwise, a numeric vector contaning the centrality scores for the selected vertices.
Consider the geodesics from \(i\) to all other vertices.
If node \(v\) is part of at least 1/n-th of these geodesics, \(v\) is said
to be a bottleneck for \(i\).
By default, n == 4, so \(v\) is a bottleneck for \(i\)
if \(v\) is part of least one quarter of all of the geodesics from \(i\).
The bottleneck centrality of \(v\) is the number of vertices that \(v\) is a bottleneck for.
The score runs from 0 (ie. the vertex is a bottleneck for no other vertex)
to \(g - 1\), with g being the number of vertices in graph.
The calculation does not use edge weights, even if the graph is weighted (but the implementation could easily be altered to include weight as well).
Especially when densely connected subgroups exist, multiple shortest paths are possible between two vertices. If a vertex appear on at least one of them, that path counts as part of the calculation. This implies that being a _bottleneck_ does not take into account whether there are alternative geodesics between the two vertices; in other words, it does not matter whether the geodesic that \(v\) is part of is redundant or not and alternative geodesics exist between the pair of vertices that \(v\) is not part of and have the same length as the geodesic(s) that \(v\) is on. Hence, removal of the bottleneck node from the graph may not affect the efficiency of the graph in these cases.
Note that geodesics that end at \(v\) also count in the calculation. So, when there are multiple geodesics from \(i\) to \(v\), it is likely that \(v\) will count as a bottleneck for \(i\), although this may not be realistic. An alteration of this measure to discard geodesics to \(v\) might be advisable.
Also note that the implementation of this measure in the centiserve package
is incorrect, so use our function and not theirs.
Also note that geodesics that end at \(v\) also count in the calculation. So, when there are multiple geodesics from \(i\) to \(v\), it is likely that \(v\) will count as a bottleneck for \(i\), although this may not be realistic. An alteration of this measure to discard geodesics to \(v\) might be advisable.
Przulj, N., Dennis A. Wigle, and Igor Jurisica. "Functional topology in a network of protein interactions." Bioinformatics 20.3 (2004): 340-348.
g <- igraph::graph(c(1,2,2,3,3,4,4,2))
v_bottleneck(g)
#> name bottleneck
#> 1 1 0
#> 2 2 3
#> 3 3 0
#> 4 4 0
v_bottleneck(g, vids = c(1, 2, 4))
#> name bottleneck
#> 1 1 2
#> 2 2 2
#> 4 3 2
v_bottleneck(g, mode = "out")
#> name bottleneck
#> 1 1 0
#> 2 2 3
#> 3 3 3
#> 4 4 2
v_bottleneck(g, mode = "in")
#> name bottleneck
#> 1 1 0
#> 2 2 2
#> 3 3 1
#> 4 4 1
g <- igraph::make_star(10, mode = "undirected")
v_bottleneck(g)
#> name bottleneck
#> 1 1 9
#> 2 2 0
#> 3 3 0
#> 4 4 0
#> 5 5 0
#> 6 6 0
#> 7 7 0
#> 8 8 0
#> 9 9 0
#> 10 10 0
g <- igraph::make_ring(10)
v_bottleneck(g) # all 0
#> name bottleneck
#> 1 1 6
#> 2 2 6
#> 3 3 6
#> 4 4 6
#> 5 5 6
#> 6 6 6
#> 7 7 6
#> 8 8 6
#> 9 9 6
#> 10 10 6
v_bottleneck(g, n = Inf) # all 9
#> name bottleneck
#> 1 1 9
#> 2 2 9
#> 3 3 9
#> 4 4 9
#> 5 5 9
#> 6 6 9
#> 7 7 9
#> 8 8 9
#> 9 9 9
#> 10 10 9