Finer-Grained Engagement in Hypergraphs

Vertex engagement has extraordinary significance for social resilience and network stability. There have been lots of existing work studying this fundamental problem in pairwise graphs, but in the more generalized hypergraphs, it has not been well explored, due to the great challenges of sparsity, complex connectivity and dynamicity of hypergraphs. In this work, we initialize the study of the vertex engagement problem in hypergraphs. Based on the observation that the engagement of vertices in hypergraphs needs to consider two critical parameters, group engagement and neighbor engagement, we propose a vertex engagement model integrating the merits of these two measures, called constrained core, to address the ineffectiveness and incomprehensiveness caused by just using a single engagement factor. By giving an algorithm for the constrained core decomposition, we show that the constrained core number of vertices can be computed in linear time. Furthermore, by showing a localized property of contained core, efficient maintenance algorithms for updating the constrained core number of vertices in dynamic hypergraphs are proposed, to avoid the large amount of redundant computations caused by the decomposition from scratch. Extensive experiments conducted on real-world hypergraphs well exhibit the effectiveness of our model and the efficiency of the proposed algorithms.