When Engagement Meets Similarity: Efficient (k, r)-Core Computation on Social Networks

VLDB Endowment
Publication Type:
Journal Article
Proceedings of the VLDB Endowment, 2017, 10 (10), pp. 998 - 1009
Issue Date:
Full metadata record
Files in This Item:
Filename Description Size
p998-zhang.pdfPublished Version1.11 MB
Adobe PDF
In this paper, we investigate the problem of (k,r)-core which 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 performance of the maximum (k,r)-core computation. We also devise effective search orders for two mining algorithms where search priorities for vertices are different. Comprehensive experiments on real-life data demonstrate that the maximal/maximum (k,r)-cores enable us to find interesting cohesive subgraphs, and performance of two mining algorithms is effectively improved by proposed techniques.
Please use this identifier to cite or link to this item: