Local Search of Communities in Large Graphs

Summary: Local search strategy for community search in large graphs; confines exploration to a vertex's neighborhood rather than a global traversal. Non-monotonic minimum-degree quality measure complicates local search; the paper proposes theories and algorithms and validates them on synthetic and real networks with millions of nodes. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 4913
Venue: SIGMOD
Year: 2014
Pagerank: 0.00026253833
Overall Rank: 354 | 97.55%
DOI: 10.1145/2588555.2612179

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 47 of 47 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,000	Effective Community Search for Large Attributed Graphs	2016	VLDB	0.00014714977
1,014	Robust Local Community Detection: On Free Rider Effect and Its Elimination	2015	VLDB	0.00014631717
1,256	Influential Community Search in Large Networks	2015	VLDB	0.00013009097
1,529	Truss-based Community Search: a Truss-equivalence Based Indexing Approach	2017	VLDB	0.00011484853
1,548	Approximate Closest Community Search in Networks	2016	VLDB	0.0001141271
1,641	Truss-based Community Search over Large Directed Graphs	2020	SIGMOD	0.00011044805
1,645	Attribute-Driven Community Search	2017	VLDB	0.00011027616
1,837	Distance-generalized Core Decomposition	2019	SIGMOD	0.00010355705
1,848	Effective Community Search over Large Spatial Graphs	2017	VLDB	0.00010331574
2,291	Effective and Efficient Community Search over Large Heterogeneous Information Networks	2020	VLDB	9.0894835e-05
2,608	Maximum Co-located Community Search in Large Scale Social Networks	2018	VLDB	8.4587487e-05
2,726	Effective and Efficient Relational Community Detection and Search in Large Dynamic Heterogeneous Information Networks	2020	VLDB	8.2266116e-05
3,370	Query Driven-Graph Neural Networks for Community Search: From Non-Attributed, Attributed, to Interactive Attributed	2022	VLDB	7.1645471e-05
3,608	Skyline Community Search in Multi-valued Networks	2018	SIGMOD	6.9241653e-05
3,857	Index-based Optimal Algorithms for Computing Steiner Components with Maximum Connectivity	2015	SIGMOD	6.6924202e-05
3,972	Efficient Size-Bounded Community Search over Large Networks	2021	VLDB	6.5724209e-05
4,133	On Querying Historical K-Cores	2021	VLDB	6.4185206e-05
4,727	OLAK: An Efficient Algorithm to Prevent Unraveling in Social Networks	2017	VLDB	5.9628488e-05
4,843	Butterfly-Core Community Search over Labeled Graphs	2021	VLDB	5.8767265e-05
4,877	Discovering Polarization Niches via Dense Subgraphs with Attractors and Repulsers	2022	VLDB	5.8537804e-05
5,525	Effective Community Search over Large Star-Schema Heterogeneous Information Networks	2022	VLDB	5.4589218e-05
5,620	Influential Community Search over Large Heterogeneous Information Networks	2023	VLDB	5.4066581e-05
5,953	DMCS : Density Modularity based Community Search	2022	SIGMOD	5.2542333e-05
6,145	Local Algorithms for Distance-generalized Core Decomposition over Large Dynamic Graphs	2021	VLDB	5.1853422e-05
6,259	Neural Attributed Community Search at Billion Scale	2023	SIGMOD	5.1305787e-05
6,495	The Flexible Socio Spatial Group Queries	2019	VLDB	5.0334905e-05
6,501	Reliable Community Search in Dynamic Networks	2022	VLDB	5.0293058e-05
6,563	Densely Connected User Community and Location Cluster Search in Location-Based Social Networks	2020	SIGMOD	5.0038354e-05
6,588	Efficient Progressive Minimum k-Core Search	2020	VLDB	4.9972607e-05
6,977	C-Explorer: Browsing Communities in Large Graphs	2017	VLDB	4.8705543e-05
7,156	The Minimum Wiener Connector Problem	2015	SIGMOD	4.8098527e-05
7,287	Topic-based Community Search over Spatial-Social Networks	2020	VLDB	4.7697047e-05
7,446	QTCS: Efficient Query-Centered Temporal Community Search	2024	VLDB	4.7232788e-05
8,821	Efficient Unsupervised Community Search with Pre-trained Graph Transformer	2024	VLDB	4.437516e-05
8,920	Time-Topology Analysis	2021	VLDB	4.4229886e-05
8,982	Truss-based Community Search over Streaming Directed Graphs	2024	VLDB	4.413691e-05
9,146	Accelerating Core Decomposition in Billion-Scale Hypergraphs	2025	SIGMOD	4.380727e-05
9,552	Cohesiveness-aware Hierarchical Compressed Index for Community Search on Attributed Graphs	2025	SIGMOD	4.3212967e-05
10,076	Efficient Size-Bounded Community Search, Revisited: Frameworks for Practical Improvements	2026	SIGMOD	4.1905499e-05
10,159	Efficient Influential Community Search over Dynamic Graphs	2026	SIGMOD	4.1905499e-05
10,181	LMSC: Local Sketch Modularity Optimisation for Size-Constrained Community Search in Networks	2026	SIGMOD	4.1905499e-05
10,240	Effective Durable Community Search in Large Temporal Graph	2026	VLDB	4.1905499e-05
10,561	Synergetic Community Search over Large Multilayer Graphs	2025	VLDB	4.1905499e-05
10,562	Searching and Detecting Structurally Similar Communities in Large Heterogeneous Information Networks	2025	VLDB	4.1905499e-05
10,591	A Flexible Framework for Query-oriented Interactive Community Search	2025	VLDB	4.1905499e-05
10,702	Effective and Efficient Community Search for Complex Network Semantics Capture: From Coarse-Grain to Fine-Grain	2025	VLDB	4.1905499e-05
10,865	Finding Time-Proximity Communities in Temporal Heterogeneous Information Networks	2025	VLDB	4.1905499e-05

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
313	Graph Clustering Based on Structural/Attribute Similarities	2009	VLDB	0.0002809849
370	Online Search of Overlapping Communities	2013	SIGMOD	0.00025391823
773	Local Graph Sparsification for Scalable Clustering	2011	SIGMOD	0.00016788213
2,541	Scalable Discovery of Best Clusters on Large Graphs	2010	VLDB	8.5710863e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
2,055	Community Detection in Social Networks: An In-depth Benchmarking Study with a Procedure-Oriented Framework	2015	VLDB	9.680119e-05
2,291	Effective and Efficient Community Search over Large Heterogeneous Information Networks	2020	VLDB	9.0894835e-05
7,287	Topic-based Community Search over Spatial-Social Networks	2020	VLDB	4.7697047e-05
6,563	Densely Connected User Community and Location Cluster Search in Location-Based Social Networks	2020	SIGMOD	5.0038354e-05
284	Querying K-Truss Community in Large and Dynamic Graphs	2014	SIGMOD	0.00029014359
10,076	Efficient Size-Bounded Community Search, Revisited: Frameworks for Practical Improvements	2026	SIGMOD	4.1905499e-05
1,256	Influential Community Search in Large Networks	2015	VLDB	0.00013009097
3,972	Efficient Size-Bounded Community Search over Large Networks	2021	VLDB	6.5724209e-05
1,848	Effective Community Search over Large Spatial Graphs	2017	VLDB	0.00010331574
5,656	An Optimal and Progressive Approach to Online Search of Top-K Influential Communities	2018	VLDB	5.3876479e-05