Efficient Progressive Minimum k-Core Search

Summary: Progressive PSA algorithm for minimum k-core search, finding the smallest k-core containing all query vertices. Novel lower/upper bound techniques prune the search space and balance solution quality with runtime; extensive experiments on 12 real graphs demonstrate efficiency. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 12241
Venue: VLDB
Year: 2020
Pagerank: 5.0020648e-05
Overall Rank: 6,588 | 54.17%
DOI: 10.14778/3368289.3368300

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,321	Hierarchical Core Maintenance on Large Dynamic Graphs	2021	VLDB	7.223972e-05
3,969	Efficient Size-Bounded Community Search over Large Networks	2021	VLDB	6.5787567e-05
4,843	Butterfly-Core Community Search over Labeled Graphs	2021	VLDB	5.8823824e-05
10,057	Budgeted Strong Community Search in Heterogeneous Graphs	2026	SIGMOD	4.1945683e-05
10,076	Efficient Size-Bounded Community Search, Revisited: Frameworks for Practical Improvements	2026	SIGMOD	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 8 of 8 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
283	Querying K-Truss Community in Large and Dynamic Graphs	2014	SIGMOD	0.00029041257
353	Local Search of Communities in Large Graphs	2014	SIGMOD	0.00026277992
738	Large Scale Cohesive Subgraphs Discovery for Social Network Visual Analysis	2013	VLDB	0.00017435236
999	Effective Community Search for Large Attributed Graphs	2016	VLDB	0.00014726563
2,436	Efficient Structural Graph Clustering: An Index-Based Approach	2018	VLDB	8.8252104e-05
3,854	Index-based Optimal Algorithms for Computing Steiner Components with Maximum Connectivity	2015	SIGMOD	6.6988744e-05
4,394	When Engagement Meets Similarity: Efficient (k,r)-Core Computation on Social Networks	2017	VLDB	6.224902e-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
1,257	Influential Community Search in Large Networks	2015	VLDB	0.00013020648
9,403	A Counting-based Approach for Efficient k-Clique Densest Subgraph Discovery	2024	SIGMOD	4.3441378e-05
10,681	Efficient k-Clique Densest Subgraph Discovery: Towards Bridging Practice and Theory	2025	VLDB	4.1945683e-05
10,076	Efficient Size-Bounded Community Search, Revisited: Frameworks for Practical Improvements	2026	SIGMOD	4.1945683e-05
2,909	Efficient Algorithms for Densest Subgraph Discovery	2019	VLDB	7.9305767e-05
3,969	Efficient Size-Bounded Community Search over Large Networks	2021	VLDB	6.5787567e-05
6,207	Efficiently Computing k-Edge Connected Components via Graph Decomposition	2013	SIGMOD	5.1572428e-05
5,854	Diversified Top-k Subgraph Querying in a Large Graph	2016	SIGMOD	5.3006473e-05
5,643	An Optimal and Progressive Approach to Online Search of Top-K Influential Communities	2018	VLDB	5.3928286e-05
4,394	When Engagement Meets Similarity: Efficient (k,r)-Core Computation on Social Networks	2017	VLDB	6.224902e-05