Querying K-Truss Community in Large and Dynamic Graphs

Summary: Online k-truss community search for a query vertex in large, dynamic graphs. A compact index enables linear-cost k-truss search by community size and supports swift updates under frequent graph insertions/deletions; validated on real networks. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 4866
Venue: SIGMOD
Year: 2014
Pagerank: 0.00029041257
Overall Rank: 283 | 98.04%
DOI: 10.1145/2588555.2610495

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 42 of 92 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
8,014	Efficient Star-based Truss Maintenance on Dynamic Graphs	2023	SIGMOD	4.6058845e-05
8,169	Efficient Triangle-Connected Truss Community Search In Dynamic Graphs	2023	VLDB	4.5698941e-05
8,809	Efficient Maximal Motif-Clique Enumeration over Large Heterogeneous Information Networks	2024	VLDB	4.4443756e-05
8,821	Efficient Unsupervised Community Search with Pre-trained Graph Transformer	2024	VLDB	4.4417735e-05
8,918	Time-Topology Analysis	2021	VLDB	4.427232e-05
8,975	Truss-based Community Search over Streaming Directed Graphs	2024	VLDB	4.4179255e-05
9,057	Behavior Query Discovery in System-Generated Temporal Graphs	2016	VLDB	4.4039656e-05
9,228	Efficiently Counting Triangles in Large Temporal Graphs	2025	SIGMOD	4.3690661e-05
9,239	Efficient Algorithms for Pseudoarboricity Computation in Large Static and Dynamic Graphs	2024	VLDB	4.3690661e-05
9,390	Efficient Maximum s-Bundle Search via Local Vertex Connectivity	2025	SIGMOD	4.3441378e-05
9,398	Maximum k-Plex Search: An Alternated Reduction-and-Bound Method	2025	VLDB	4.3441378e-05
9,552	Cohesiveness-aware Hierarchical Compressed Index for Community Search on Attributed Graphs	2025	SIGMOD	4.3254416e-05
9,553	Deep Overlapping Community Search via Subspace Embedding	2025	SIGMOD	4.3254416e-05
9,651	Efficient and Effective Algorithms for Generalized Densest Subgraph Discovery	2023	SIGMOD	4.3109001e-05
9,862	Sage: Parallel Semi-Asymmetric Graph Algorithms for NVRAMs	2020	VLDB	4.2683554e-05
9,951	Parallel Colorful h-star Core Maintenance in Dynamic Graphs	2023	VLDB	4.2405999e-05
10,033	Scaling Up k-Clique Percolation Community Detection	2026	SIGMOD	4.1945683e-05
10,076	Efficient Size-Bounded Community Search, Revisited: Frameworks for Practical Improvements	2026	SIGMOD	4.1945683e-05
10,134	A Unified Framework for Dense Subgraph Maintenance over Dynamic Bipartite Graphs	2026	SIGMOD	4.1945683e-05
10,136	Accelerating Triangle-Connected Truss Community Search Across Heterogeneous Hardware	2026	SIGMOD	4.1945683e-05
10,159	Efficient Influential Community Search over Dynamic Graphs	2026	SIGMOD	4.1945683e-05
10,189	Order-based Algorithms for Efficient Core Maintenance in Large Bipartite Graphs	2026	SIGMOD	4.1945683e-05
10,240	Effective Durable Community Search in Large Temporal Graph	2026	VLDB	4.1945683e-05
10,311	Efficient Temporal Edge-Core Maintenance in Streaming Graphs	2026	VLDB	4.1945683e-05
10,363	A Local Search Approach to Efficient (k, p)-Core Maintenance	2025	SIGMOD	4.1945683e-05
10,474	Community Detection in Heterogeneous Information Networks Without Materialization	2025	SIGMOD	4.1945683e-05
10,506	SWASH: A Flexible Communication Framework with Sliding Window-Based Cache Sharing for Scalable DGNN Training	2025	SIGMOD	4.1945683e-05
10,552	Synergetic Community Search over Large Multilayer Graphs	2025	VLDB	4.1945683e-05
10,553	Searching and Detecting Structurally Similar Communities in Large Heterogeneous Information Networks	2025	VLDB	4.1945683e-05
10,582	A Flexible Framework for Query-oriented Interactive Community Search	2025	VLDB	4.1945683e-05
10,596	Truss Decomposition in Hypergraphs	2025	VLDB	4.1945683e-05
10,648	A Comprehensive Survey and Experimental Study of Learning-based Community Search	2025	VLDB	4.1945683e-05
10,694	Effective and Efficient Community Search for Complex Network Semantics Capture: From Coarse-Grain to Fine-Grain	2025	VLDB	4.1945683e-05
10,861	Finding Time-Proximity Communities in Temporal Heterogeneous Information Networks	2025	VLDB	4.1945683e-05
10,865	Approximate Anchored Densest Subgraph Search on Large Static and Dynamic Graphs	2025	VLDB	4.1945683e-05
10,947	Parallel Algorithms for Hierarchical Nucleus Decomposition	2024	SIGMOD	4.1945683e-05
11,042	Efficient Index for Temporal Core Queries over Bipartite Graphs	2024	VLDB	4.1945683e-05
11,044	Evolution Forest Index: Towards Optimal Temporal k-Core Component Search via Time-Topology Isomorphic Computation	2024	VLDB	4.1945683e-05
11,048	Efficient Algorithms for Density Decomposition on Large Static and Dynamic Graphs	2024	VLDB	4.1945683e-05
11,140	MOSER: Scalable Network Motif Discovery using Serial Test	2024	VLDB	4.1945683e-05
11,492	On Analyzing Graphs with Motif-Paths	2021	VLDB	4.1945683e-05
11,671	Finding Theme Communities from Database Networks	2019	VLDB	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 6 of 6 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
57	Discovering Large Dense Subgraphs in Massive Graphs	2005	VLDB	0.00065491112
108	Truss Decomposition in Massive Networks	2012	VLDB	0.00048300163
110	On Triangulation-based Dense Neighborhood Graph Discovery	2011	VLDB	0.00047892924
370	Online Search of Overlapping Communities	2013	SIGMOD	0.00025415479
686	Finding Maximal Cliques in Massive Networks by H*-graph	2010	SIGMOD	0.00018178029
966	Streaming Algorithms for k-core Decomposition	2013	VLDB	0.00014960672

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
2,721	Effective and Efficient Relational Community Detection and Search in Large Dynamic Heterogeneous Information Networks	2020	VLDB	8.2345495e-05
6,506	Reliable Community Search in Dynamic Networks	2022	VLDB	5.0341364e-05
1,550	Approximate Closest Community Search in Networks	2016	VLDB	0.00011423628
5,643	An Optimal and Progressive Approach to Online Search of Top-K Influential Communities	2018	VLDB	5.3928286e-05
6,725	Maximal D-truss Search in Dynamic Directed Graphs	2023	VLDB	4.9484066e-05
2,603	Maximum Co-located Community Search in Large Scale Social Networks	2018	VLDB	8.4666465e-05
1,637	Truss-based Community Search over Large Directed Graphs	2020	SIGMOD	0.0001105259
8,169	Efficient Triangle-Connected Truss Community Search In Dynamic Graphs	2023	VLDB	4.5698941e-05
1,257	Influential Community Search in Large Networks	2015	VLDB	0.00013020648
1,530	Truss-based Community Search: a Truss-equivalence Based Indexing Approach	2017	VLDB	0.00011495611