Random-Walk Betweenness Centrality
Definition
Random Walk Betweenness measures how many times a vertex appears on random
walks between all vertex-pairs in the graph. It is an alternative measure
for Betweenness.
Betweenness is, in some sense, a measure of the influence a node has over the spread of information through the network. By counting only shortest paths, however, the conventional definition implicitly assumes that information spreads only along those shortest paths. With relaxes this assumption, including contributions from essentially all paths between nodes, not just the shortest, although it still gives more weight to short paths. The measure is based on random walks, counting how often a node is traversed by a random walk between two other nodes [NEWMAN, M. E. 2005].
The random-walk betweenness centrality introduced in [NEWMAN, M. E. 2005] is based on the idea that information propagated from source s will travel through randomly chosen intermediate visiting nodes to target t. A random walk can be modeled by a discrete-time stochastic process. At initial time 0, vertex s propagates information to one of its neighbors using random probability. This random propagation continues until the target vertex t is encountered. Newman [NEWMAN, M. E. 2005] and Brandes et al. [BRANDES, U. 2005] showed that random-walk betweenness is equivalent to current-flow betweenness.
See Current-Flow Betweenness Centrality
Nakajima, K. and Shudo, K., 2020. Estimating High Betweenness Centrality Nodes via Random walk in Social Networks. Journal of Information Processing, 28, pp.1-9.
Gillani, I.A., Bagchi, A. and Ranu, S., 2021. A group-to-group version of random walk betweenness centrality. In 8th ACM IKDD CODS and 26th COMAD (pp. 127-135).
Betweenness is, in some sense, a measure of the influence a node has over the spread of information through the network. By counting only shortest paths, however, the conventional definition implicitly assumes that information spreads only along those shortest paths. With relaxes this assumption, including contributions from essentially all paths between nodes, not just the shortest, although it still gives more weight to short paths. The measure is based on random walks, counting how often a node is traversed by a random walk between two other nodes [NEWMAN, M. E. 2005].
The random-walk betweenness centrality introduced in [NEWMAN, M. E. 2005] is based on the idea that information propagated from source s will travel through randomly chosen intermediate visiting nodes to target t. A random walk can be modeled by a discrete-time stochastic process. At initial time 0, vertex s propagates information to one of its neighbors using random probability. This random propagation continues until the target vertex t is encountered. Newman [NEWMAN, M. E. 2005] and Brandes et al. [BRANDES, U. 2005] showed that random-walk betweenness is equivalent to current-flow betweenness.
See Current-Flow Betweenness Centrality
Nakajima, K. and Shudo, K., 2020. Estimating High Betweenness Centrality Nodes via Random walk in Social Networks. Journal of Information Processing, 28, pp.1-9.
Gillani, I.A., Bagchi, A. and Ranu, S., 2021. A group-to-group version of random walk betweenness centrality. In 8th ACM IKDD CODS and 26th COMAD (pp. 127-135).
Software
References
- BORGATTI, S. P. & EVERETT, M. G. 2006. A graph-theoretic perspective on centrality. Social networks, 28, 466-484.
DOI: 10.1016/j.socnet.2005.11.005
- BRANDES, U. & FLEISCHER, D. 2005. Centrality Measures Based on Current Flow. In: DIEKERT, V. & DURAND, B. (eds.) STACS 2005. Springer Berlin Heidelberg.
- NEWMAN, M. E. 2005. A measure of betweenness centrality based on random walks. Social networks, 27, 39-54.