TY - GEN
T1 - NimbleCore
T2 - 2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2016
AU - Govindan, Priya
AU - Soundarajan, Sucheta
AU - Eliassi-Rad, Tina
AU - Faloutsos, Christos
N1 - Publisher Copyright:
© 2016 IEEE.
PY - 2016/11/21
Y1 - 2016/11/21
N2 - 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%.
AB - 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%.
UR - http://www.scopus.com/inward/record.url?scp=85006741676&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85006741676&partnerID=8YFLogxK
U2 - 10.1109/ASONAM.2016.7752237
DO - 10.1109/ASONAM.2016.7752237
M3 - Conference contribution
AN - SCOPUS:85006741676
T3 - Proceedings of the 2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2016
SP - 207
EP - 214
BT - Proceedings of the 2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2016
A2 - Kumar, Ravi
A2 - Caverlee, James
A2 - Tong, Hanghang
PB - Institute of Electrical and Electronics Engineers Inc.
Y2 - 18 August 2016 through 21 August 2016
ER -