OLAK: An Efficient Algorithm to Prevent Unraveling in Social Networks

VLDB Endowment
Publication Type:
Journal Article
Proceedings of the VLDB Endowment, 2017, 10 (6), pp. 649 - 660
Issue Date:
Full metadata record
Files in This Item:
Filename Description Size
OLAK An Efficient Algorithm to Prevent Unraveling in Social Networks.pdfPublished Version493.23 kB
Adobe PDF
In this paper, we study the problem of the anchored k-core. Given a graph G, an integer k and a budget b, we aim to identify b vertices in G so that we can determine the largest induced subgraph J in which every vertex, except the b vertices, has at least k neighbors in J. This problem was introduced by Bhawalkar and Kleinberg et al. in the context of user engagement in social networks, where a user may leave a community if he/she has less than k friends engaged. The problem has been shown to be NP-hard and inapproximable. A polynomial-time algorithm for graphs with bounded tree width has been proposed. However, this assumption usually does not hold in real-life graphs, and their techniques cannot be extended to handle general graphs. Motivated by this, we propose an efficient algorithm, namely onion-layer based anchored k-core (OLAK), for the anchored k-core problem on large scale graphs. To facilitate computation of the anchored k-core, we design an onion layer structure, which is generated by a simple onion-peeling like algorithm against a small set of vertices in the graph. We show that computation of the best anchor can simply be conducted upon the vertices on the onion layers, which significantly reduces the search space. Based on the well organized layer structure, we develop efficient candidates exploration, early termination and pruning techniques to further speed up computation. Comprehensive experiments on 10 real-life graphs demonstrate the effectiveness and efficiency of our proposed methods.
Please use this identifier to cite or link to this item: