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

Summary: Defines the (k,r)-core to jointly enforce engagement (min degree k) and pairwise attribute similarity in social networks, with algorithms to enumerate all maximal (k,r)-cores and compute the maximum core (NP-hard). Introduces pruning techniques, a novel (k,k')-core upper bound, and vertex-order heuristics to accelerate two mining algorithms; experiments on real data show effective cohesive subgraph discovery and substantial performance gains. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 11593
Venue: VLDB
Year: 2017
Pagerank: 6.224902e-05
Overall Rank: 4,394 | 69.44%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 13 of 13 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,484	Vertex Priority Based Butterfly Counting for Large-scale Bipartite Networks	2019	VLDB	0.00011714263
1,836	Distance-generalized Core Decomposition	2019	SIGMOD	0.00010365753
2,603	Maximum Co-located Community Search in Large Scale Social Networks	2018	VLDB	8.4666465e-05
3,321	Hierarchical Core Maintenance on Large Dynamic Graphs	2021	VLDB	7.223972e-05
4,743	Cohesive Subgraph Search over Big Heterogeneous Information Networks: Applications, Challenges, and Solutions	2021	SIGMOD	5.9586508e-05
6,259	Neural Attributed Community Search at Billion Scale	2023	SIGMOD	5.1355079e-05
6,530	Fast Algorithms for Core Maximization on Large Graphs	2022	VLDB	5.0246792e-05
6,570	Densely Connected User Community and Location Cluster Search in Location-Based Social Networks	2020	SIGMOD	5.0065377e-05
6,588	Efficient Progressive Minimum k-Core Search	2020	VLDB	5.0020648e-05
10,363	A Local Search Approach to Efficient (k, p)-Core Maintenance	2025	SIGMOD	4.1945683e-05
10,530	Most Similar Biclique Search at Scale	2025	VLDB	4.1945683e-05
11,048	Efficient Algorithms for Density Decomposition on Large Static and Dynamic Graphs	2024	VLDB	4.1945683e-05
11,303	Density Personalized Group Query	2023	VLDB	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
999	Effective Community Search for Large Attributed Graphs	2016	VLDB	0.00014726563
1,844	Effective Community Search over Large Spatial Graphs	2017	VLDB	0.00010341077
2,684	Truss Decomposition of Probabilistic Graphs: Semantics and Algorithms	2016	SIGMOD	8.3136866e-05
2,807	A Model-based Approach to Attributed Graph Clustering	2012	SIGMOD	8.0905959e-05
4,728	OLAK: An Efficient Algorithm to Prevent Unraveling in Social Networks	2017	VLDB	5.968586e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
6,530	Fast Algorithms for Core Maximization on Large Graphs	2022	VLDB	5.0246792e-05
10,363	A Local Search Approach to Efficient (k, p)-Core Maintenance	2025	SIGMOD	4.1945683e-05
966	Streaming Algorithms for k-core Decomposition	2013	VLDB	0.00014960672
1,257	Influential Community Search in Large Networks	2015	VLDB	0.00013020648
2,603	Maximum Co-located Community Search in Large Scale Social Networks	2018	VLDB	8.4666465e-05
10,694	Effective and Efficient Community Search for Complex Network Semantics Capture: From Coarse-Grain to Fine-Grain	2025	VLDB	4.1945683e-05
3,273	Global Reinforcement of Social Networks: The Anchored Coreness Problem	2020	SIGMOD	7.2956944e-05
6,588	Efficient Progressive Minimum k-Core Search	2020	VLDB	5.0020648e-05
8,210	Mining Top-k Pairs of Correlated Subgraphs in a Large Network	2020	VLDB	4.5581054e-05
10,246	Anchored Maximum Communities over Large Directed Graphs	2026	VLDB	4.1945683e-05