There are no comment yet.
BottleNeck Centrality
Definition
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].
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].
- BN(v) = Σs∈v Ps(v)
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].
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.