2016/11/10 by Fan Zhang, Ying Zhang, Zhang, Fan +7
Computer Science · Physics and Astronomy · #Advanced Graph Neural Networks #Complex Network Analysis Techniques #Data Management and Algorithms #Databases (cs.DB) #FOS: Computer and information sciences #Social and Information Networks (cs.SI)
paper · pdf · doi:10.48550/arxiv.1611.03254
openalex publication_date 2016/11/10 · openalex created_date 2019/06/27 · openalex updated_date 2026/07/28
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 also consider the pairwise similarity between users based on their profiles. For a given similarity metric and a similarity threshold r, the similarity between any two vertices in a (k,r)-core is ensured not less than r. 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 significantly reduce the search space of two algorithms and 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 to accommodate the different nature of two mining algorithms. 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 significantly improved by proposed techniques.