I/O-Efficient Algorithms for Degeneracy Computation on Massive Networks

Rong Hua Li, Qiushuo Song, Xiaokui Xiao, Lu Qin, Guoren Wang*, Jeffrey Xu Yu, Rui Mao

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

4 Citations (Scopus)

Abstract

Degeneracy is an important concept to measure the sparsity of a graph which has been widely used in many network analysis applications. Many network analysis algorithms, such as clique enumeration and truss decomposition, perform very well in graphs having small degeneracies. In this paper, we propose an I/O-efficient algorithm to compute the degeneracy of the massive graph that cannot be fully kept in the main memory. The proposed algorithm only uses O(n) memory, where n denotes the number of nodes of the graph. We also develop an I/O-efficient algorithm to incrementally maintain the degeneracy on dynamic graphs. Extensive experiments show that our algorithms significantly outperform the state-of-the-art degeneracy computation algorithms in terms of both running time and I/O costs. The results also demonstrate high scalability of the proposed algorithms. For example, in a real-world web graph with 930 million nodes and 13.3 billion edges, the proposed algorithm takes only 633 seconds and uses less than 4.5GB memory to compute the degeneracy.

Original languageEnglish
Pages (from-to)3335-3348
Number of pages14
JournalIEEE Transactions on Knowledge and Data Engineering
Volume34
Issue number7
DOIs
Publication statusPublished - 1 Jul 2022

Keywords

  • Degeneracy
  • I/O-efficient algorithm
  • k-core
  • massive graphs

Fingerprint

Dive into the research topics of 'I/O-Efficient Algorithms for Degeneracy Computation on Massive Networks'. Together they form a unique fingerprint.

Cite this