Index-based Optimal Algorithms for Computing Steiner Components with Maximum Connectivity

Summary: Index-based optimal algorithms for Steiner components with maximum connectivity (SMCC) using a novel index; runtime linear in the result size. Supports size-constrained SMCC, connectivity-only metrics, batch processing, and incremental updates; experiments show speedups. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 5036
Venue: SIGMOD
Year: 2015
Pagerank: 6.6924202e-05
Overall Rank: 3,857 | 73.20%
DOI: 10.1145/2723372.2746486

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 22 of 22 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,291	Effective and Efficient Community Search over Large Heterogeneous Information Networks	2020	VLDB	9.0894835e-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,972	Efficient Size-Bounded Community Search over Large Networks	2021	VLDB	6.5724209e-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,656	An Optimal and Progressive Approach to Online Search of Top-K Influential Communities	2018	VLDB	5.3876479e-05
6,259	Neural Attributed Community Search at Billion Scale	2023	SIGMOD	5.1305787e-05
6,588	Efficient Progressive Minimum k-Core Search	2020	VLDB	4.9972607e-05
7,343	I/O Efficient ECC Graph Decomposition via Graph Reduction	2016	VLDB	4.7511136e-05
8,630	A Near-Optimal Approach to Edge Connectivity-Based Hierarchical Graph Decomposition	2022	VLDB	4.4765914e-05
8,821	Efficient Unsupervised Community Search with Pre-trained Graph Transformer	2024	VLDB	4.437516e-05
8,897	BCviz: A Linear-Space Index for Mining and Visualizing Cohesive Bipartite Subgraphs	2025	SIGMOD	4.4229886e-05
8,982	Truss-based Community Search over Streaming Directed Graphs	2024	VLDB	4.413691e-05
9,396	Efficient Maximum s-Bundle Search via Local Vertex Connectivity	2025	SIGMOD	4.3399748e-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,240	Effective Durable Community Search in Large Temporal Graph	2026	VLDB	4.1905499e-05
10,280	FB*: A Compact Index for Efficient and Exact Density-based Clustering	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

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
110	On Triangulation-based Dense Neighborhood Graph Discovery	2011	VLDB	0.00047955011
284	Querying K-Truss Community in Large and Dynamic Graphs	2014	SIGMOD	0.00029014359
354	Local Search of Communities in Large Graphs	2014	SIGMOD	0.00026253833
370	Online Search of Overlapping Communities	2013	SIGMOD	0.00025391823
682	Finding Maximal Cliques in Massive Networks by H*-graph	2010	SIGMOD	0.0001816451
3,024	GConnect: A Connectivity Index for Massive Disk-Resident Graphs	2009	VLDB	7.691835e-05
6,206	Efficiently Computing k-Edge Connected Components via Graph Decomposition	2013	SIGMOD	5.1522897e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
7,714	Minimum Strongly Connected Subgraph Collection in Dynamic Graphs	2024	VLDB	4.6651585e-05
1,776	Reachability Queries on Large Dynamic Graphs: A Total Order Approach	2014	SIGMOD	0.0001058029
6,660	On Querying Historical Connectivity in Temporal Graphs	2024	SIGMOD	4.9672425e-05
7,343	I/O Efficient ECC Graph Decomposition via Graph Reduction	2016	VLDB	4.7511136e-05
10,988	Constant-time Connectivity Querying in Dynamic Graphs	2024	SIGMOD	4.1905499e-05
8,630	A Near-Optimal Approach to Edge Connectivity-Based Hierarchical Graph Decomposition	2022	VLDB	4.4765914e-05
2,440	Efficient Structural Graph Clustering: An Index-Based Approach	2018	VLDB	8.8166939e-05
4,726	On Querying Connected Components in Large Temporal Graphs	2023	SIGMOD	5.9632682e-05
12,049	I/O Efficient: Computing SCCs in Massive Graphs	2013	SIGMOD	4.1905499e-05
6,206	Efficiently Computing k-Edge Connected Components via Graph Decomposition	2013	SIGMOD	5.1522897e-05