Title: Efficient Graph Hierarchical Decomposition with User Engagement and Tie Strength
Authors: Maryam Ghafouri, Kai Wang, Fan Zhang, Ying Zhang and Xuemin Lin
Abstract: Graph decomposition methods using k-core and k-truss hierarchically group vertices and edges from external to internal by degrees of vertices or tie strength of edges. As both the user engagement of nodes and the strength of relationships are important, the (k, s)-core model is proposed in the literature to discover strong communities. Nevertheless, the decomposition algorithm regarding (k,s)-core is not yet investigated. In this paper, we propose (k,s)-core algorithms to decompose a graph into its hierarchical structures considering both user engagement and tie strength. We first present the basic (k,s)-core decomposition methods. Then, we propose the advanced algorithms DES and DEK which index the support of edges to enable higher-level cost-sharing in the peeling process. In addition, effective pruning strategies are applied to DES/DEK to further enhance performance. Moreover, we build a novel index based on the decomposition result and investigate an efficient (k,s)-core query algorithm based on our index. Extensive experimental evaluations on 12 real-world datasets verify the efficiency of our proposed decomposition algorithms and show that our index-based query algorithm can speed up the state-of-the-art query algorithms by up to three orders of magnitude.
