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)

Paper ID: hafe0fbb3504f7c95
Venue: SIGMOD
Year: 2019
Pagerank: 8.7594692e-05
Overall Rank: 2,246 | 84.95%
DOI: 10.1145/3299869.3300082

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 19 of 19 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,590	Effective and Efficient Community Search over Large Heterogeneous Information Networks	2020	VLDB	0.00010110798
3,499	Accelerating Truss Decomposition on Heterogeneous Processors	2020	VLDB	7.2351042e-05
4,595	Influential Community Search over Large Heterogeneous Information Networks	2023	VLDB	6.4993083e-05
4,973	Effective Community Search over Large Star-Schema Heterogeneous Information Networks	2022	VLDB	6.3201026e-05
5,575	Theoretically and Practically Efficient Parallel Nucleus Decomposition	2022	VLDB	6.0626208e-05
6,078	Maximal D-truss Search in Dynamic Directed Graphs	2023	VLDB	5.8765432e-05
7,568	Efficient Triangle-Connected Truss Community Search In Dynamic Graphs	2023	VLDB	5.4773947e-05
8,088	Efficient Star-based Truss Maintenance on Dynamic Graphs	2023	SIGMOD	5.3746503e-05
8,339	Efficient Index for Temporal Core Queries over Bipartite Graphs	2024	VLDB	5.3353302e-05
9,336	Searching and Detecting Structurally Similar Communities in Large Heterogeneous Information Networks	2025	VLDB	5.1783355e-05
9,768	Approximate Anchored Densest Subgraph Search on Large Static and Dynamic Graphs	2025	VLDB	5.115551e-05
9,911	Parallel Algorithms for Hierarchical Nucleus Decomposition	2024	SIGMOD	5.0983269e-05
10,394	Effective Structurally Similar Community Search in Large Temporal Graphs	2027	SIGMOD	4.9605343e-05
10,684	A Unified Framework for Dense Subgraph Maintenance over Dynamic Bipartite Graphs	2026	SIGMOD	4.9605343e-05
10,708	Efficient Influential Community Search over Dynamic Graphs	2026	SIGMOD	4.9605343e-05
10,737	Order-based Algorithms for Efficient Core Maintenance in Large Bipartite Graphs	2026	SIGMOD	4.9605343e-05
10,783	Effective Durable Community Search in Large Temporal Graph	2026	VLDB	4.9605343e-05
11,169	A Local Search Approach to Efficient (k, p)-Core Maintenance	2025	SIGMOD	4.9605343e-05
12,176	Parallel Graph Algorithms in Constant Adaptive Rounds: Theory meets Practice	2020	VLDB	4.9605343e-05

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
96	Truss Decomposition in Massive Networks	2012	VLDB	0.00034261728
182	Querying K-Truss Community in Large and Dynamic Graphs	2014	SIGMOD	0.00026383593
902	Parallelizing Sequential Graph Computations	2017	SIGMOD	0.00013142001
1,045	Truss-based Community Search: a Truss-equivalence Based Indexing Approach	2017	VLDB	0.00012318828
1,323	Incremental Graph Pattern Matching	2011	SIGMOD	0.00011019578
1,398	Local Algorithms for Hierarchical Dense Subgraph Discovery	2019	VLDB	0.0001076734
2,005	Fast Hierarchy Construction for Dense Subgraphs	2017	VLDB	9.1851569e-05
2,854	Incremental Graph Computations: Doable and Undoable	2017	SIGMOD	7.9179612e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	9,184	Truss-based Community Search over Streaming Directed Graphs	2024	VLDB
2	11,402	Approximate 2-hop neighborhoods on incremental graphs: An efficient lazy approach	2025	VLDB
3	10,737	Order-based Algorithms for Efficient Core Maintenance in Large Bipartite Graphs	2026	SIGMOD
4	11,182	Minimum Spanning Tree Maintenance in Dynamic Graphs	2025	SIGMOD
5	9,604	Efficient Algorithms for Pseudoarboricity Computation in Large Static and Dynamic Graphs	2024	VLDB
6	96	Truss Decomposition in Massive Networks	2012	VLDB
7	2,854	Incremental Graph Computations: Doable and Undoable	2017	SIGMOD
8	4,557	Incrementalizing Graph Algorithms	2021	SIGMOD
9	2,873	Hierarchical Core Maintenance on Large Dynamic Graphs	2021	VLDB
10	8,088	Efficient Star-based Truss Maintenance on Dynamic Graphs	2023	SIGMOD