Finding Critical Users in Social Communities via Graph Convolutions (Extended Abstract)

Finding critical users whose existence keeps a social community cohesive is an important problem in social networks. Considering a k-core community, finding critical users is to find a set of nodes U, with a given size b, in the community that maximizes the number of nodes to be deleted when nodes U are deleted. The problem is NP-complete. The state-of-the-art algorithm is a greedy algorithm without a performance guaran-tee. To improve the performance, we propose a novel learning-based heuristic. A neural network model, Self-attentive Core Graph Convolution Network, SCGCN is learned for inference the criticalness of unseen node combinations. Furthermore, to reduce the inference space, we propose a deterministic strategy to prune unpromising nodes. Our experiments show that SCGCN signifi-cantly improves the quality of the solutions compared with the state-of-the-art algorithms.