Random Walk Laplacian and Network Centrality Measures
For researchers studying directed networks (e.g., social networks, influence propagation), this provides a unified and efficient method for computing multiple centrality measures.
The paper shows how the pseudoinverse of the random walk Laplacian can be used to efficiently compute various network centrality measures, such as average visit counts and betweenness, for directed graphs. This approach allows rapid computation of many quantities with a single matrix inversion.
Random walks over directed graphs are used to model activities in many domains, such as social networks, influence propagation, and Bayesian graphical models. They are often used to compute the importance or centrality of individual nodes according to a variety of different criteria. Here we show how the pseudoinverse of the "random walk" Laplacian can be used to quickly compute measures such as the average number of visits to a given node and various centrality and betweenness measures for individual nodes, both for the network in general and in the case a subset of nodes is to be avoided. We show that with a single matrix inversion it is possible to rapidly compute many such quantities.