Fast Algorithms for Core Maximization on Large Graphs

Xin Sun, Xin Huang, Di Jin*

*Corresponding author for this work

Research output: Contribution to journalConference articlepeer-review

Abstract

Core maximization, that enlarges the k-core as much as possible by inserting a few new edges into a graph, is particularly useful for social group engagement and network stability improvement. However, the core maximization problem has been theoretically proven to be NP-hard even APX-hard for k ≥ 3. Existing heuristic approaches suffer from the limitation of inefficiency on large graphs. To address this limitation, in this paper, we revisit this challenging yet important problem of core maximization, that is, given a graph G, a number k, and a budget b, to insert b new edges into G such that the corresponding k-core is maximized. We propose a novel algorithm FastCM+ based on several fast search strategies. The core idea is to apply graph partition to divide (k - 1)-shell into different components. Then, FastCM+ considers each (k - 1)-shell component independently to convert different layered vertices into k-core, in two manners of completely and partially. Based on the complete/partial conversions, FastCM+ is generalized to further handle (k - λ)-shell conversions for 2 ≤λ k. Leveraging dynamic programming combinations of different components' potential answers, FastCM+ finds a good-quality answer for edge insertions. Experimental results on eleven datasets demonstrate that our algorithm runs much faster than state-of-the-art methods on large graphs meanwhile achieving better answers.

Original languageEnglish
Pages (from-to)1350–1362
Number of pages13
JournalProceedings of the VLDB Endowment
Volume15
Issue number7
DOIs
Publication statusPublished - Mar 2022

Fingerprint

Dive into the research topics of 'Fast Algorithms for Core Maximization on Large Graphs'. Together they form a unique fingerprint.

Cite this