# BottleNeck Centrality

#### Definition

For each node v in the undirected graph, construct a tree T

P

For each node v in an interaction network, a tree of shortest paths starting from v is constructed. Taking v as the root of the tree T

_{v}of shortest paths from that node to all other nodes in the graph. For a node v, n_{v}is the number of nodes that are directly or indirectly connected to node v (i.e. the tree T_{v}contains n_{v}nodes). So extract all nodes w on the above defined tree T_{v}of shortest paths from node v, such that more than nv/4 paths from v to other nodes in the tree meet at node w. Nodes w extracted in this way represent ‘bottle necks’ of the shortest path tree T_{v}rooted at node v, since at least n_{v}/4 paths of the n_{v}-node tree T_{v}‘meet’ at w. For every node v of the graph, construct these shortest path trees T_{v}rooted at v, and extracted their ‘bottle neck’ nodes. Note that the same node may be a ‘bottle neck’ of different shortest path trees. So counted in how many shortest path trees each of the extracted ‘bottle neck’ nodes appeared [PRŽULJ, N., 2004].**BN(v) = Σ**_{s∈v}P_{s}(v)

_{s}be a shortest path tree rooted at node s.P

_{s}(v) = 1 if more than |V(T_{s})|/4 paths from node s to other nodes in T_{s}meet at the vertex v, otherwise P_{s}(v) = 0.For each node v in an interaction network, a tree of shortest paths starting from v is constructed. Taking v as the root of the tree T

_{v}, the weight of a node w in the tree T_{v}is the number of descendants of w, that is to say, equal to the number of shortest paths starting from v passing through w. A node w is called a bottle-neck node in T_{v}if the weight of w is no less than n/4, where n is the number of nodes in T_{v}. The score of node w, BN(v), is defined to be the number of node v such that w is a bottle-neck node in T_{v}[LIN, C.-Y. 2008].#### References

- LIN, C.-Y., CHIN, C.-H., WU, H.-H., CHEN, S.-H., HO, C.-W. & KO, M.-T. 2008. Hubba: hub objects analyzer—a framework of interactome hubs identification for network biology. Nucleic acids research, 36, W438-W443.
- PRŽULJ, N., WIGLE, D. A. & JURISICA, I. 2004. Functional topology in a network of protein interactions. Bioinformatics, 20, 340-348.
- YU, H., KIM, P. M., SPRECHER, E., TRIFONOV, V. & GERSTEIN, M. 2007. The importance of bottlenecks in protein networks: correlation with gene essentiality and expression dynamics. PLoS computational biology, 3, e59.