期刊
VLDB JOURNAL
卷 28, 期 6, 页码 987-1012出版社
SPRINGER
DOI: 10.1007/s00778-019-00579-4
关键词
Community detection; User engagement; User similarity; Diversification
资金
- ARC [DP170101628, DP180103096, FT170100128, DP160101513]
- [2018YFB1003504]
- [NSFC61232006]
In this paper, we investigate the problem of (k,r)-corewhich intends to find cohesive subgraphs on social networks considering both user engagement and similarity perspectives. In particular, we adopt the popular concept of k-core to guarantee the engagement of the users (vertices) in a group (subgraph) where each vertex in a (k,r)-core connects to at least k other vertices. Meanwhile, we consider the pairwise similarity among users based on their attributes. Efficient algorithms are proposed to enumerate all maximal (k,r)-cores and find the maximum (k,r)-core, where both problems are shown to be NP-hard. Effective pruning techniques substantially reduce the search space of two algorithms. A novel (k,k )-core based (k,r)-core size upper bound enhances the performance of the maximum (k,r)-core computation. We also devise effective search orders for two algorithms with different search priorities for vertices. Besides, we study the diversified (k,r)-core search problem to find l maximal (k,r)-cores which cover the most vertices in total. Thesemaximal (k,r)-cores are distinctive and informationally rich. An efficient algorithm is proposed with a guaranteed approximation ratio. We design a tight upper bound to prune unpromising partial (k,r)-cores. A new search order is designed to speed up the search. Initial candidates with large size are generated to further enhance the pruning power. Comprehensive experiments on real-life data demonstrate that the maximal (k,r)-cores enable us to find interesting cohesive subgraphs, and performance of three mining algorithms is effectively improved by all the proposed techniques.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据