Our paper on absorbing random-walk centrality will be presented at ICDM next week. It is a joint work with Harry Mavroforakis and Aristides Gionis.
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 personalised pagerank 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
[2] As implemented on networkx.
