A measure of betweenness centrality based on random walks
By Mark Newman. Soc. Networks, 2003
2,475 citations recorded by the source corpus.
Betweenness is a measure of the centrality of a node in a network, and is normally calculated as the fraction of shortest paths between node pairs that pass through the node of interest. 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. Here, we propose a betweenness measure that 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. We show how our measure can be calculated using matrix methods, and give some examples of its application to particular networks.
Subfields: Geometry and Topology, Statistical and Nonlinear Physics
View Paper: https://www.semanticscholar.org/paper/cf6f8ff055b3dc67d38a571be00365a6b121fc2f
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Geometry and Topology
- Ernesto Estrada
- Michael W. Mahoney
- Linyuan Lu
- Tao Zhou
- M. A. Porter
- Manlio De Domenico
- Alex Arenas
- Naomichi Hatano
In Statistical and Nonlinear Physics
- Santo Fortunato
- M. A. Porter
- Alex Arenas
- Olaf Sporns
- Mark Newman
- Renaud Lambiotte
- Naoki Masuda
- Tao Zhou
Citations in the corpus
- The evolution of the world trade web: a weighted-network analysis (2010, methodology): “Following Newman (2005) and Fisher and Vega-Redondo (2006), consider a generic node i for which we want to compute the RWBC and an impulse generated from node h (the source) and working its way to node k (the target).”
- Topological analysis and interactive visualization of biological networks and protein structures (2012, background): “Here the distance between two nodes is computed as the effective electric resistance between them (i.e., the difference of their potentials required for generating one unit of electrical current between them 77 ).”
- Graph theory and networks in Biology. (2006, background): “In the present context, it is worth noting the work in [108] where a definition of betweennness centrality based on random paths between nodes, rather than on geodesic paths was considered.”
- International trade and financial integration: a weighted network analysis (2010, methodology): “In the real world, economies of scale in the processing of information imply the emergence of a few leading financial centres that are likely to be linked by strong ties.z The last question we address relates to the role played by each country in the two networks.”
- The effect of social networks structure on innovation performance: A review and directions for research (2019, background): “shortest paths evolved into more inclusive measures that give weights also to indirect longer paths (Newman, 2005).”
- Centrality Estimation in Large Networks (2007, background): “Natural variants of closeness and betweenness are also obtained by replacing spread along shortest paths with current flow [Newman 2005, Brandes and Fleischer 2005].”
- Fast approximation of matrix coherence and statistical leverage (2011, background): “es in data graphs, very small clusters in noisy data, coherence of information, articulation points between clusters, the value of a customer in a network, space localization in sensor networks, etc. [9, 42, 38, 30, 32]. In genetics, dense matrices of size thousands by hundreds of thousands (a size ”
- CytoNCA: A cytoscape plugin for centrality analysis and evaluation of protein interaction networks (2015, methodology): “Eight centrality measures provided by CytoNCA are: Between-ness (Anthonisse, 1971; Newman, 2005), Closeness Centrality (Sabidussi, 1966), Degree Centrality (Jeong et al., 2001), Eigenvec-tor Centrality (Bonacich, 1987), Local Average Connectivity-based Centrality (Li et al., 2011), Network…”
- Modeling population connectivity by ocean currents, a graph-theoretic approach for marine conservation (2007, background): “shortest paths between all node pairs that pass through the particular node or arc of interest (Freeman 1997; Newman 2005).”
- A measure of centrality based on the network efficiency (2004, methodology): “For such a reason two other measures of betweenness, the first based on all possible paths between a couple of points (Freeman Borgatti and White, 1991), and the second based on random paths, (Newman, 2003) have been introduced more recently.”
- Vital nodes identification in complex networks (2016, background): “Random-walk betweenness centrality is another famous betweenness variant that counts all paths in networks and gives more weights to shorter paths [84].”
- Ranking in interconnected multilayer networks reveals versatile nodes (2013, background): “, betweenness and closeness centrality, should be substituted by centrality notions based on random walks [25, 35].”
- Random Walks for Image Segmentation (2006, methodology): “Newman uses concepts from random walks to introduce a notion of “betweenness” on the nodes on a graph by considering a node’s “betweenness” measure to be equal to how often a random walk starting at any pair of nodes passes through the node, averaged across all pairs [43].”