NimbleCore: A space-efficient external memory algorithm for estimating core numbers

Priya Govindan, Sucheta Soundarajan, Tina Eliassi-Rad, Christos Faloutsos

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Citations (Scopus)

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%.

Original languageEnglish (US)
Title of host publicationProceedings of the 2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2016
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages207-214
Number of pages8
ISBN (Electronic)9781509028467
DOIs
StatePublished - Nov 21 2016
Event2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2016 - San Francisco, United States
Duration: Aug 18 2016Aug 21 2016

Other

Other2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2016
CountryUnited States
CitySan Francisco
Period8/18/168/21/16

Fingerprint

Data storage equipment
Spreaders
savings
Law
experiment
community
Experiments

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Sociology and Political Science
  • Communication

Cite this

Govindan, P., Soundarajan, S., Eliassi-Rad, T., & Faloutsos, C. (2016). NimbleCore: A space-efficient external memory algorithm for estimating core numbers. In Proceedings of the 2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2016 (pp. 207-214). [7752237] Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ASONAM.2016.7752237

NimbleCore : A space-efficient external memory algorithm for estimating core numbers. / Govindan, Priya; Soundarajan, Sucheta; Eliassi-Rad, Tina; Faloutsos, Christos.

Proceedings of the 2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2016. Institute of Electrical and Electronics Engineers Inc., 2016. p. 207-214 7752237.

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Govindan, P, Soundarajan, S, Eliassi-Rad, T & Faloutsos, C 2016, NimbleCore: A space-efficient external memory algorithm for estimating core numbers. in Proceedings of the 2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2016., 7752237, Institute of Electrical and Electronics Engineers Inc., pp. 207-214, 2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2016, San Francisco, United States, 8/18/16. https://doi.org/10.1109/ASONAM.2016.7752237
Govindan P, Soundarajan S, Eliassi-Rad T, Faloutsos C. NimbleCore: A space-efficient external memory algorithm for estimating core numbers. In Proceedings of the 2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2016. Institute of Electrical and Electronics Engineers Inc. 2016. p. 207-214. 7752237 https://doi.org/10.1109/ASONAM.2016.7752237
Govindan, Priya ; Soundarajan, Sucheta ; Eliassi-Rad, Tina ; Faloutsos, Christos. / NimbleCore : A space-efficient external memory algorithm for estimating core numbers. Proceedings of the 2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2016. Institute of Electrical and Electronics Engineers Inc., 2016. pp. 207-214
@inproceedings{19b6d3d3b8cf4f67876392ad7239cf31,
title = "NimbleCore: A space-efficient external memory algorithm for estimating core numbers",
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{\%}.",
author = "Priya Govindan and Sucheta Soundarajan and Tina Eliassi-Rad and Christos Faloutsos",
year = "2016",
month = "11",
day = "21",
doi = "10.1109/ASONAM.2016.7752237",
language = "English (US)",
pages = "207--214",
booktitle = "Proceedings of the 2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2016",
publisher = "Institute of Electrical and Electronics Engineers Inc.",

}

TY - GEN

T1 - NimbleCore

T2 - A space-efficient external memory algorithm for estimating core numbers

AU - Govindan, Priya

AU - Soundarajan, Sucheta

AU - Eliassi-Rad, Tina

AU - Faloutsos, Christos

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

SP - 207

EP - 214

BT - Proceedings of the 2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2016

PB - Institute of Electrical and Electronics Engineers Inc.

ER -