Large Scale Subgraph Node Centrality Computations

In recent years, graph analytics has become one of the most important and ubiquitous tools for a wide variety of research areas and applications. Indeed, modern applications such as ad hoc wireless telecommunication networks, or social networks, have dramatically increased the number of nodes of the involved graphs, which now routinely range in the tens of millions and outreaching to the billions in notable cases. Here we describe a near linear (O(N)) method for the calculation of subgraph centralities of very large sparse graphs, where N is the number of nodes of the graph. Node centralities capture information about the importance of a node in a graph and have a multitude of applications. The method employs stochastic estimation and Krylov subspace techniques to drastically reduce the complexity which, using standard methods, is typically O(N^3). The described technique allows one to approximate centralities quickly and accurately, and thereby opens the way for centrality-based graph analytics that would have been nearly impossible with standard techniques.

A copy of this report is available from pub@zurich.ibm.com

By: Yves Ineichen, Costas Bekas, and Alessandro Curioni

Published in: RZ3863 in 2014

This Research Report is not available electronically. Please request a copy from the contact listed below. IBM employees should contact ITIRC for a copy.


Questions about this service can be mailed to reports@us.ibm.com .