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

Summary: Defines (k,r)-cores combining k-core engagement constraints with pairwise attribute similarity, yielding cohesive social subgraphs. For NP-hard maximal enumeration and maximum-core search, it introduces pruning, search orders, and a novel (k,k′)-core size bound. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 11781
Venue: VLDB
Year: 2017
Pagerank: 6.9619668e-05
Overall Rank: 4,008 | 72.51%
DOI: 10.14778/3115404.3115412

Incoming Non-self Citations Over Time

Authors

1. Fan Zhang (East China Normal University; University of Technology Sydney)
2. Ying Zhang (University of Technology Sydney)
3. Lu Qin (University of Technology Sydney)
4. Wenjie Zhang (University of New South Wales)
5. Xuemin Lin (East China Normal University; University of New South Wales)

BibTeX Citation

@article{zhang_vldb17,
        title = {{When Engagement Meets Similarity: Efficient (k,r)-Core Computation on Social Networks}},
        author = {Zhang, Fan and Zhang, Ying and Qin, Lu and Zhang, Wenjie and Lin, Xuemin},
        journal = {PVLDB},
        series = {{VLDB} '17},
        volume = {10},
        number = {10},
        pages = {998--1009},
        doi = {10.14778/3115404.3115412},
        url = {https://doi.org/10.14778/3115404.3115412},
        year = {2017}
}

Incoming Citations (Sorted by Pagerank)

Showing 13 of 13 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,211	Vertex Priority Based Butterfly Counting for Large-scale Bipartite Networks	2019	VLDB	0.00011648789
1,640	Distance-generalized Core Decomposition	2019	SIGMOD	0.00010153865
2,106	Maximum Co-located Community Search in Large Scale Social Networks	2018	VLDB	9.1568079e-05
2,826	Hierarchical Core Maintenance on Large Dynamic Graphs	2021	VLDB	8.0865974e-05
4,579	Cohesive Subgraph Search over Big Heterogeneous Information Networks: Applications, Challenges, and Solutions	2021	SIGMOD	6.6203846e-05
5,877	Neural Attributed Community Search at Billion Scale	2023	SIGMOD	6.0551011e-05
6,179	Densely Connected User Community and Location Cluster Search in Location-Based Social Networks	2020	SIGMOD	5.9496108e-05
6,342	Efficient Progressive Minimum k-Core Search	2020	VLDB	5.9068493e-05
6,465	Fast Algorithms for Core Maximization on Large Graphs	2022	VLDB	5.871325e-05
10,656	A Local Search Approach to Efficient (k, p)-Core Maintenance	2025	SIGMOD	5.093636e-05
10,802	Most Similar Biclique Search at Scale	2025	VLDB	5.093636e-05
11,256	Efficient Algorithms for Density Decomposition on Large Static and Dynamic Graphs	2024	VLDB	5.093636e-05
11,502	Density Personalized Group Query	2023	VLDB	5.093636e-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
706	Effective Community Search for Large Attributed Graphs	2016	VLDB	0.00014789612
1,378	Effective Community Search over Large Spatial Graphs	2017	VLDB	0.00010971508
2,323	Truss Decomposition of Probabilistic Graphs: Semantics and Algorithms	2016	SIGMOD	8.750808e-05
2,644	A Model-based Approach to Attributed Graph Clustering	2012	SIGMOD	8.3043854e-05
4,485	OLAK: An Efficient Algorithm to Prevent Unraveling in Social Networks	2017	VLDB	6.6715036e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,465	Fast Algorithms for Core Maximization on Large Graphs	2022	VLDB
2	10,656	A Local Search Approach to Efficient (k, p)-Core Maintenance	2025	SIGMOD
3	793	Streaming Algorithms for k-core Decomposition	2013	VLDB
4	982	Influential Community Search in Large Networks	2015	VLDB
5	2,106	Maximum Co-located Community Search in Large Scale Social Networks	2018	VLDB
6	10,941	Effective and Efficient Community Search for Complex Network Semantics Capture: From Coarse-Grain to Fine-Grain	2025	VLDB
7	4,331	Global Reinforcement of Social Networks: The Anchored Coreness Problem	2020	SIGMOD
8	6,342	Efficient Progressive Minimum k-Core Search	2020	VLDB
9	8,206	Mining Top-k Pairs of Correlated Subgraphs in a Large Network	2020	VLDB
10	10,534	Anchored Maximum Communities over Large Directed Graphs	2026	VLDB