Absorbing random walk centrality

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.

ARW-centrality quantifies how central one set of nodes (blue nodes, in the example) is with respect to another (red nodes, in the example).
ARW-centrality quantifies how central one set of nodes (blue nodes, in the example) is with respect to another (red nodes, in the example).

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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s