What is absorbing random-walk centrality (ARW-centrality)?

It is a measure that tells us how central one set of nodes (let’s call it C) is with respect to another set of nodes (let’s call it Q) in a graph. As an example, consider the graph shown in the figure below. In that graph, we use color to indicate the two sets of nodes — Q is shown in red and C is shown in blue.

To quantify how central nodes C are with respect to nodes Q on the graph, we consider a random walk that starts from one Q-node and continues until it reaches one C-node for the first time – at which point we say that the random walk becomes absorbed by that C-node and stops. We ask the question: what is the expected number of steps of the walk until it gets absorbed? This value is what we call the ARW-centrality of C with respect to Q. The smaller the value of ARW-centrality, the more central nodes C are considered with respect to Q.

The problem and our contributions

We study the following optimization problem: given nodes Q, what is the set of nodes C with the best ARW-centrality with respect to Q?

In the ICDM paper [1], we show that the problem is NP-hard. We also show that a natural greedy algorithm offers solutions with approximation guarantee. Furthermore, we compare the performance of the greedy algorithm with faster heuristics – and found empirically that the personalisedpagerank algorithm [2] achieves comparable performance in a fraction of the time.

Code

Our code is publicly available on github, with installation instructions and documentation. Moreover, if you’re planning to use the library, this notebook contains a session that should help you get acquainted with the code, but also technical details about the problem.

Notes

[1] Harry Mavroforakis, Michael Mathioudakis, Aristides Gionis. Absorbing Random Walk Centrality: Theory and Algorithms. 2015. arxiv.org/abs/1509.02533