BottleNeck Centrality


For each node v in the undirected graph, construct a tree Tv of shortest paths from that node to all other nodes in the graph. For a node v, nv is the number of nodes that are directly or indirectly connected to node v (i.e. the tree Tv contains nv nodes). So extract all nodes w on the above defined tree Tv 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 Tv rooted at node v, since at least nv/4 paths of the nv-node tree Tv ‘meet’ at w. For every node v of the graph, construct these shortest path trees Tv 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 Ps(v)
Let Ts be a shortest path tree rooted at node s.
Ps(v) = 1 if more than |V(Ts)|/4 paths from node s to other nodes in Ts meet at the vertex v, otherwise Ps(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 Tv, the weight of a node w in the tree Tv 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 Tv if the weight of w is no less than n/4, where n is the number of nodes in Tv. 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 Tv [LIN, C.-Y. 2008].


  • 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.


There are no comment yet.

Add your comment

Sum of    and