Fast Algorithms for Core Maximization on Large Graphs

Download PDF

Abstract

Core maximization which enlarges the $k$-core as much as possible by inserting a few new edges into a graph, is particularly useful to improve the dense substructure's stability on various real-life applications, such as the friendship-based communities in social networks, the topology extension in distributed networks, and the communication stability for resource exchanging in P2P networks. However, the core maximization problem has been theoretically proven to be NP-hard even APX-hard for $k\geq3$. Existing heuristic approaches suffer from the inefficiency limitation, which is not scalable on large graphs. To address this limitation, in this paper, we revisit this challenging but 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 $k$-core subgraph is maximized. We propose a novel algorithm \FCM based on three fast search strategies. The core idea is applying graph partition to divide $(k-1)$-shell into different components, and then considering each component independently to convert different level vertices into $k$-core. The time complexity of \FCM is theoretically analyzed in $O(mn+bhn)$ where $n$, $m$, $h$ are the number of vertices, edges, and $(k-1)$-shell subsets respectively and $h\ll n$, which is clearly faster than $O(bmn^2)$ by the SOTA algorithm \EKC~\cite{zhou2019k}. Experimental results on eleven datasets demonstrate that our algorithm runs 27,000\textbf{x} faster than \EKC on large graphs meanwhile achieving highly competitive quality results.