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: h28f28c1dfbbeb73b
Venue: VLDB
Year: 2017
Pagerank: 6.9488207e-05
Overall Rank: 3,863 | 74.11%
DOI: 10.14778/3115404.3115412
PDF: Download (CC BY-NC-ND 4.0)

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 14 of 14 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,227	Vertex Priority Based Butterfly Counting for Large-scale Bipartite Networks	2019	VLDB	0.00011426039
1,613	Distance-generalized Core Decomposition	2019	SIGMOD	0.00010057822
2,110	Maximum Co-located Community Search in Large Scale Social Networks	2018	VLDB	9.0222862e-05
2,873	Hierarchical Core Maintenance on Large Dynamic Graphs	2021	VLDB	7.9005874e-05
3,881	Cohesive Subgraph Search over Big Heterogeneous Information Networks: Applications, Challenges, and Solutions	2021	SIGMOD	6.9309694e-05
6,002	Neural Attributed Community Search at Billion Scale	2023	SIGMOD	5.9028394e-05
6,316	Densely Connected User Community and Location Cluster Search in Location-Based Social Networks	2020	SIGMOD	5.7968726e-05
6,465	Efficient Progressive Minimum k-Core Search	2020	VLDB	5.7596353e-05
6,559	Fast Algorithms for Core Maximization on Large Graphs	2022	VLDB	5.7289742e-05
9,957	Efficient Algorithms for Density Decomposition on Large Static and Dynamic Graphs	2024	VLDB	5.0910746e-05
10,407	Scaling Up Density Decomposition on Massive Graphs	2027	SIGMOD	4.9605343e-05
11,169	A Local Search Approach to Efficient (k, p)-Core Maintenance	2025	SIGMOD	4.9605343e-05
11,280	Most Similar Biclique Search at Scale	2025	VLDB	4.9605343e-05
11,861	Density Personalized Group Query	2023	VLDB	4.9605343e-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
696	Effective Community Search for Large Attributed Graphs	2016	VLDB	0.00014671367
1,405	Effective Community Search over Large Spatial Graphs	2017	VLDB	0.00010745719
2,072	Truss Decomposition of Probabilistic Graphs: Semantics and Algorithms	2016	SIGMOD	9.0668141e-05
2,690	A Model-based Approach to Attributed Graph Clustering	2012	SIGMOD	8.1126575e-05
4,597	OLAK: An Efficient Algorithm to Prevent Unraveling in Social Networks	2017	VLDB	6.4979622e-05

Semantically Similar Papers

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