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: 4867
Venue: SIGMOD
Year: 2014
Pagerank: 0.00029014359
Overall Rank: 284 | 98.03%
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,017	Efficient Star-based Truss Maintenance on Dynamic Graphs	2023	SIGMOD	4.6014683e-05
8,171	Efficient Triangle-Connected Truss Community Search In Dynamic Graphs	2023	VLDB	4.5655127e-05
8,809	Efficient Maximal Motif-Clique Enumeration over Large Heterogeneous Information Networks	2024	VLDB	4.4401156e-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,056	Behavior Query Discovery in System-Generated Temporal Graphs	2016	VLDB	4.3997447e-05
9,231	Efficiently Counting Triangles in Large Temporal Graphs	2025	SIGMOD	4.3648789e-05
9,246	Efficient Algorithms for Pseudoarboricity Computation in Large Static and Dynamic Graphs	2024	VLDB	4.3648789e-05
9,396	Efficient Maximum s-Bundle Search via Local Vertex Connectivity	2025	SIGMOD	4.3399748e-05
9,404	Maximum k-Plex Search: An Alternated Reduction-and-Bound Method	2025	VLDB	4.3399748e-05
9,552	Cohesiveness-aware Hierarchical Compressed Index for Community Search on Attributed Graphs	2025	SIGMOD	4.3212967e-05
9,553	Deep Overlapping Community Search via Subspace Embedding	2025	SIGMOD	4.3212967e-05
9,652	Efficient and Effective Algorithms for Generalized Densest Subgraph Discovery	2023	SIGMOD	4.3067693e-05
9,861	Sage: Parallel Semi-Asymmetric Graph Algorithms for NVRAMs	2020	VLDB	4.2642656e-05
9,950	Parallel Colorful h-star Core Maintenance in Dynamic Graphs	2023	VLDB	4.236537e-05
10,033	Scaling Up k-Clique Percolation Community Detection	2026	SIGMOD	4.1905499e-05
10,076	Efficient Size-Bounded Community Search, Revisited: Frameworks for Practical Improvements	2026	SIGMOD	4.1905499e-05
10,134	A Unified Framework for Dense Subgraph Maintenance over Dynamic Bipartite Graphs	2026	SIGMOD	4.1905499e-05
10,136	Accelerating Triangle-Connected Truss Community Search Across Heterogeneous Hardware	2026	SIGMOD	4.1905499e-05
10,159	Efficient Influential Community Search over Dynamic Graphs	2026	SIGMOD	4.1905499e-05
10,189	Order-based Algorithms for Efficient Core Maintenance in Large Bipartite Graphs	2026	SIGMOD	4.1905499e-05
10,240	Effective Durable Community Search in Large Temporal Graph	2026	VLDB	4.1905499e-05
10,323	Efficient Temporal Edge-Core Maintenance in Streaming Graphs	2026	VLDB	4.1905499e-05
10,375	A Local Search Approach to Efficient (k, p)-Core Maintenance	2025	SIGMOD	4.1905499e-05
10,484	Community Detection in Heterogeneous Information Networks Without Materialization	2025	SIGMOD	4.1905499e-05
10,515	SWASH: A Flexible Communication Framework with Sliding Window-Based Cache Sharing for Scalable DGNN Training	2025	SIGMOD	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,604	Truss Decomposition in Hypergraphs	2025	VLDB	4.1905499e-05
10,656	A Comprehensive Survey and Experimental Study of Learning-based 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
10,869	Approximate Anchored Densest Subgraph Search on Large Static and Dynamic Graphs	2025	VLDB	4.1905499e-05
10,950	Parallel Algorithms for Hierarchical Nucleus Decomposition	2024	SIGMOD	4.1905499e-05
11,045	Efficient Index for Temporal Core Queries over Bipartite Graphs	2024	VLDB	4.1905499e-05
11,047	Evolution Forest Index: Towards Optimal Temporal k-Core Component Search via Time-Topology Isomorphic Computation	2024	VLDB	4.1905499e-05
11,051	Efficient Algorithms for Density Decomposition on Large Static and Dynamic Graphs	2024	VLDB	4.1905499e-05
11,143	MOSER: Scalable Network Motif Discovery using Serial Test	2024	VLDB	4.1905499e-05
11,496	On Analyzing Graphs with Motif-Paths	2021	VLDB	4.1905499e-05
11,676	Finding Theme Communities from Database Networks	2019	VLDB	4.1905499e-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.00065421423
106	Truss Decomposition in Massive Networks	2012	VLDB	0.00048373761
110	On Triangulation-based Dense Neighborhood Graph Discovery	2011	VLDB	0.00047955011
370	Online Search of Overlapping Communities	2013	SIGMOD	0.00025391823
682	Finding Maximal Cliques in Massive Networks by H*-graph	2010	SIGMOD	0.0001816451
966	Streaming Algorithms for k-core Decomposition	2013	VLDB	0.00014947141

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
2,726	Effective and Efficient Relational Community Detection and Search in Large Dynamic Heterogeneous Information Networks	2020	VLDB	8.2266116e-05
6,501	Reliable Community Search in Dynamic Networks	2022	VLDB	5.0293058e-05
1,548	Approximate Closest Community Search in Networks	2016	VLDB	0.0001141271
5,656	An Optimal and Progressive Approach to Online Search of Top-K Influential Communities	2018	VLDB	5.3876479e-05
6,729	Maximal D-truss Search in Dynamic Directed Graphs	2023	VLDB	4.943658e-05
2,608	Maximum Co-located Community Search in Large Scale Social Networks	2018	VLDB	8.4587487e-05
1,641	Truss-based Community Search over Large Directed Graphs	2020	SIGMOD	0.00011044805
8,171	Efficient Triangle-Connected Truss Community Search In Dynamic Graphs	2023	VLDB	4.5655127e-05
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