Name
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%.
|
Year | DOI | Venue |
|---|---|---|
2016 | 10.5555/3192424.3192464 | ASONAM '16: Advances in Social Networks Analysis and Mining 2016
Davis
California
August, 2016 |
Keywords | Field | DocType |
NimbleCore,space-efficient external memory algorithm,node core number estimation,graph mining tasks,iterative external-memory algorithm,maximum graph node-degree,power-law degree distributions | Graph,Computer science,Workload,Algorithm,Theoretical computer science,User role,Approximation error,Auxiliary memory | Conference |
ISBN | Citations | PageRank |
978-1-5090-2846-7 | 3 | 0.41 |
References | Authors | |
15 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Priya Govindan | 1 | 37 | 3.30 |
| Sucheta Soundarajan | 2 | 120 | 15.00 |
| Tina Eliassi-Rad | 3 | 1597 | 108.63 |
| Christos Faloutsos | 4 | 27972 | 4490.38 |