Finding Critical Users in Social Communities via Graph Convolutions

Kangfei Zhao, Zhiwei Zhang, Yu Rong, Jeffrey Xu Yu*, Junzhou Huang

*Corresponding author for this work

Research output: Contribution to journalJournal articlepeer-review

5 Citations (Scopus)


Finding critical users whose existence keeps a social community cohesive and large is an important issue in social networks. In the literature, such criticalness of a user is measured by the number of followers who will leave the community together when the user leaves. By taking a social community as a k-core, which can be computed in linear time, the problem of finding critical users is to find a set of nodes, U, with a user-given size b in a k-core community that maximizes the number of nodes (followers) to be deleted from the k-core when all nodes in $U$U are deleted. This problem is known to be NP-hard. In the literature, the state-of-the-art approach, a greedy algorithm is proposed with no guarantee on the set of nodes U found, since there does not exist a submodular function the greedy algorithm can use to get a better answer iteratively. Furthermore, the greedy algorithm designed is to handle k-core in any social networks such that it does not consider the structural complexity of a given single graph and cannot get the global optimal by the local optimal found in iterations. In this paper, we propose a novel learning-based approach. Distinguished from traditional experience-based heuristics, we propose a neural network model, called Self-attentive Core Graph Convolution Network (SCGCN), to capture the hidden structure of the criticalness among node combinations that break the engagement of a specific social community. Supervised by sampling node combinations, SCGCN has the ability to inference the criticalness of unseen combinations of nodes. To further reduce the sampling and inference space, we propose a deterministic strategy to prune unpromising nodes on the graph. Our experiments conducted on many real-world graphs show that SCGCN significantly improves the quality of the solution compared with the state-of-the-art greedy algorithm.

Original languageEnglish
Pages (from-to)456-468
Number of pages13
JournalIEEE Transactions on Knowledge and Data Engineering
Issue number1
Early online date16 Jun 2021
Publication statusPublished - 1 Jan 2023

Scopus Subject Areas

  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics

User-Defined Keywords

  • Social network analysis
  • k-core collapsion
  • graph neural network


Dive into the research topics of 'Finding Critical Users in Social Communities via Graph Convolutions'. Together they form a unique fingerprint.

Cite this