bottleneck {centiserve}R Documentation

Find the BottleNeck centrality score

Description

BottleNeck Centrality for vertex v defined as:

BN(v)=svPs(v)BN(v) = \sum_{s\in v} P_{s}(v)

Let TsT_{s} be a shortest path tree rooted at node ss. Ps(v)=1P_{s}(v) = 1 if more than V(Ts)/4|V(T{s})|/4 paths from node ss to other nodes in TsT_{s} meet at the vertex vv, otherwise Ps(v)=0P_{s}(v) = 0.

Usage

bottleneck(graph, vids = V(graph), mode = c("all", "out", "in"))

Arguments

graph

The input graph as igraph object

vids

Vertex sequence, the vertices for which the centrality values are returned. Default is all vertices.

mode

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, ie. not directed paths are searched. This argument is ignored for undirected graphs.

Details

For each node vv in the graph, construct a tree TvT_{v} of shortest paths from that node to all other nodes in the graph. For a node vv, nvn_{v} is the number of nodes that are directly or indirectly connected to node vv (i.e. the tree TvT_{v} contains nvn_{v} nodes). So extract all nodes ww on the above defined tree TvT_{v} of shortest paths from node vv, such that more than nv/4n_{v}/4 paths from vv to other nodes in the tree meet at node ww. Nodes ww extracted in this way represent 'bottle necks' of the shortest path tree TvT_{v} rooted at node vv, since at least nv/4n_{v}/4 paths of the nvnoden_{v}-node tree TvT_{v} 'meet' at ww.
More detail at BottleNeck

Value

A numeric vector contaning the centrality scores for the selected vertices.

Author(s)

Mahdi Jalili m_jalili@farabi.tums.ac.ir

References

Przulj, N., Dennis A. Wigle, and Igor Jurisica. "Functional topology in a network of protein interactions." Bioinformatics 20.3 (2004): 340-348.

Examples

g <- graph(c(1,2,2,3,3,4,4,2))
bottleneck(g)

[Package centiserve version 1.0.0 Index]