NimbleCore: A Space-efficient External Memory Algorithm for Estimating Core Numbers

P. Govindan, S. Soundarajan, T. Eliassi-Rad, C. Faloutsos
Proceedings of the 2016 IEEE/ACM ASONAM
San Francisco, CA, August 2016
August 18, 2016

Abstract

We address the  problem of estimating core numbers of nodes by reading edges of a large graph  stored in external memory. The core number of a node is the highest k-core in  which the node participates. Core numbers are useful in many graph mining  tasks, especially ones that involve finding communities of nodes, influential  spreaders and dense subgraphs. Large graphs often do not fit on the memory of  a single machine. Existing external memory solutions do not give bounds on  the required space. In practice, existing solutions also do not scale with  the size of the graph. We propose NimbleCore, an iterative external-memory  algorithm, which estimates core numbers of nodes using O(n log dmax) space,  where n is the number of nodes and dmax is the maximum node-degree in the  graph. We also show that NimbleCore requires O(n) space for graphs with  power-law degree distributions. Experiments on forty-eight large graphs from  various domains demonstrate that NimbleCore gives space savings up to 60X,  while accurately estimating core numbers with average relative error less  than 2.3%.