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 journalArticlepeer-review

4 Citations (Scopus)


Finding critical users in social networks is an important issue. The criticalness of a user can be 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, the problem of finding critical users is to find a set of nodes, U, of size b in a k-core that maximizes the number of nodes to be deleted from the k-core when all nodes in U are deleted. This problem is NP-hard. The state-of-the-art greedy algorithm is with no guarantee on the set of nodes U found. In this paper, 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)1-12
Number of pages12
JournalIEEE Transactions on Knowledge and Data Engineering
Publication statusE-pub ahead of print - 16 Jun 2021

Scopus Subject Areas

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

User-Defined Keywords

  • Complexity theory
  • Greedy algorithms
  • Social networking (online)
  • Task analysis
  • Testing
  • Topology
  • Training


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

Cite this