Fast Algorithms for Core Maximization on Large Graphs

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.