Unboundedness and Efficiency of Truss Maintenance in Evolving Graphs
Summary: Under locally persistent model, truss maintenance on evolving graphs is bounded for removals but unbounded for insertions. Proposes AFF, an affected-edge set, enabling bounded insertion with O(f(||AFF||_c)); beats full recompute on 12 graphs by up to 1e3x. (summarized by gpt-5-nano on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Yikai Zhang (Chinese University of Hong Kong)
- 2. Jeffrey Xu Yu (Chinese University of Hong Kong)
BibTeX Citation
@inproceedings{zhang_sigmod19,
title = {{Unboundedness and Efficiency of Truss Maintenance in Evolving Graphs}},
author = {Zhang, Yikai and Yu, Jeffrey Xu},
series = {{SIGMOD} '19},
booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
publisher = {Association for Computing Machinery},
doi = {10.1145/3299869.3300082},
url = {https://dl.acm.org/doi/10.1145/3299869.3300082},
year = {2019}
}Incoming Citations (Sorted by Pagerank)
Showing 18 of 18 citing papers.
Previous
Page 1 / 1
Next
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 |
|---|---|---|---|---|
| 100 | Truss Decomposition in Massive Networks | 2012 | VLDB | 0.0003396253 |
| 184 | Querying K-Truss Community in Large and Dynamic Graphs | 2014 | SIGMOD | 0.00026097449 |
| 948 | Parallelizing Sequential Graph Computations | 2017 | SIGMOD | 0.00012908602 |
| 1,092 | Truss-based Community Search: a Truss-equivalence Based Indexing Approach | 2017 | VLDB | 0.00012066667 |
| 1,318 | Incremental Graph Pattern Matching | 2011 | SIGMOD | 0.00011044781 |
| 1,444 | Local Algorithms for Hierarchical Dense Subgraph Discovery | 2019 | VLDB | 0.00010630508 |
| 2,121 | Fast Hierarchy Construction for Dense Subgraphs | 2017 | VLDB | 9.0060232e-05 |
| 2,851 | Incremental Graph Computations: Doable and Undoable | 2017 | SIGMOD | 7.9382307e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 9,160 | Truss-based Community Search over Streaming Directed Graphs | 2024 | VLDB |
| 2 | 11,349 | Approximate 2-hop neighborhoods on incremental graphs: An efficient lazy approach | 2025 | VLDB |
| 3 | 10,676 | Order-based Algorithms for Efficient Core Maintenance in Large Bipartite Graphs | 2026 | SIGMOD |
| 4 | 11,121 | Minimum Spanning Tree Maintenance in Dynamic Graphs | 2025 | SIGMOD |
| 5 | 9,579 | Efficient Algorithms for Pseudoarboricity Computation in Large Static and Dynamic Graphs | 2024 | VLDB |
| 6 | 100 | Truss Decomposition in Massive Networks | 2012 | VLDB |
| 7 | 2,851 | Incremental Graph Computations: Doable and Undoable | 2017 | SIGMOD |
| 8 | 4,541 | Incrementalizing Graph Algorithms | 2021 | SIGMOD |
| 9 | 2,869 | Hierarchical Core Maintenance on Large Dynamic Graphs | 2021 | VLDB |
| 10 | 8,072 | Efficient Star-based Truss Maintenance on Dynamic Graphs | 2023 | SIGMOD |