Finding critical users for social network engagement: The collapsed k-core problem
- Publication Type:
- Conference Proceeding
- Citation:
- 31st AAAI Conference on Artificial Intelligence, AAAI 2017, 2017, pp. 245 - 251
- Issue Date:
- 2017-01-01
Closed Access
| Filename | Description | Size | |||
|---|---|---|---|---|---|
| [2017 AAAI] Finding Critical Users for Social Network Engagement - The Collapsed k-Core Problem.pdf | Published version | 1.12 MB |
Copyright Clearance Process
- Recently Added
- In Progress
- Closed Access
This item is closed access and not available.
Copyright © 2017, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved. 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 k-core, the maximal induced subgraph in which every vertex has at least k neighbors. To identify critical users for social network engagement, we propose the collapsed k-core problem: given a graph G, a positive integer k and a budget b, we aim to find b vertices in G such that the deletion of the b vertices leads to the smallest k-core. We prove the problem is NP-hard. Then, an efficient algorithm is proposed, which significantly reduces the number of candidate vertices to speed up the computation. Our comprehensive experiments on 9 real-life social networks demonstrate the effectiveness and efficiency of our proposed method.
Please use this identifier to cite or link to this item: