Finding Critical Users in Social Communities: The Collapsed Core and Truss Problems

Publication Type:
Journal Article
IEEE Transactions on Knowledge and Data Engineering, 2020, 32 (1), pp. 78 - 91
Issue Date:
Filename Description Size
TKDE_2018.pdfPublished Version1.13 MB
Adobe PDF
Full metadata record
© 1989-2012 IEEE. In social networks, the leave of critical users may significantly break network engagement, i.e., lead a large number of other users to drop out. A popular model to measure social network engagement is kk-core, the maximal subgraph in which every vertex has at least kk neighbors. To identify critical users, we propose the collapsed kk-core problem: given a graph GG, a positive integer kk and a budget bb, we aim to find bb vertices in GG such that the deletion of the bb vertices leads to the smallest kk-core. We prove the problem is NP-hard and inapproximate. An efficient algorithm is proposed, which significantly reduces the number of candidate vertices. We also study the user leave towards the model of kk-truss which further considers tie strength by conducting additional computation w.r.t. kk-core. We prove the corresponding collapsed kk-truss problem is also NP-hard and inapproximate. An efficient algorithm is proposed to solve the problem. The advantages and disadvantages of the two proposed models are experimentally compared. Comprehensive experiments on nine real-life social networks demonstrate the effectiveness and efficiency of our proposed methods.
Please use this identifier to cite or link to this item: