Efficient Star-based Truss Maintenance on Dynamic Graphs

Summary: Introduces AffBall, a star-based structure for efficient k-truss maintenance on dynamic graphs with star updates, exploiting edge correlations to update inner trussness. Extends to general updates via onion-layer propagation beyond the star, with experiments showing gains over existing methods. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 6698
Venue: SIGMOD
Year: 2023
Pagerank: 5.5074939e-05
Overall Rank: 8,011 | 45.04%
DOI: 10.1145/3589278

Incoming Non-self Citations Over Time

Authors

1. Zitan Sun (Hong Kong Baptist University)
2. Xin Huang (Hong Kong Baptist University)
3. Qing Liu (Zhejiang University)
4. Jianliang Xu (Hong Kong Baptist University)

BibTeX Citation

@inproceedings{sun_sigmod23,
        title = {{Efficient Star-based Truss Maintenance on Dynamic Graphs}},
        author = {Sun, Zitan and Huang, Xin and Liu, Qing and Xu, Jianliang},
        series = {{SIGMOD} '23},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3589278},
        url = {https://dl.acm.org/doi/10.1145/3589278},
        year = {2023}
}

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
8,991	Truss-based Community Search over Streaming Directed Graphs	2024	VLDB	5.3377754e-05
10,423	A Unified Framework for Dense Subgraph Maintenance over Dynamic Bipartite Graphs	2026	SIGMOD	5.093636e-05
10,478	Order-based Algorithms for Efficient Core Maintenance in Large Bipartite Graphs	2026	SIGMOD	5.093636e-05
10,857	Truss Decomposition in Hypergraphs	2025	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 13 of 13 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
102	Truss Decomposition in Massive Networks	2012	VLDB	0.00034255289
189	Querying K-Truss Community in Large and Dynamic Graphs	2014	SIGMOD	0.00026114928
590	Large Scale Cohesive Subgraphs Discovery for Social Network Visual Analysis	2013	VLDB	0.0001605572
793	Streaming Algorithms for k-core Decomposition	2013	VLDB	0.00013978774
1,113	Approximate Closest Community Search in Networks	2016	VLDB	0.00012124571
1,239	Attribute-Driven Community Search	2017	VLDB	0.000115381
1,328	Truss-based Community Search over Large Directed Graphs	2020	SIGMOD	0.00011140898
1,416	Local Algorithms for Hierarchical Dense Subgraph Discovery	2019	VLDB	0.00010839488
2,106	Maximum Co-located Community Search in Large Scale Social Networks	2018	VLDB	9.1568079e-05
2,243	Unboundedness and Efficiency of Truss Maintenance in Evolving Graphs	2019	SIGMOD	8.8813183e-05
2,323	Truss Decomposition of Probabilistic Graphs: Semantics and Algorithms	2016	SIGMOD	8.750808e-05
3,503	Accelerating Truss Decomposition on Heterogeneous Processors	2020	VLDB	7.3592701e-05
5,697	Local Algorithms for Distance-generalized Core Decomposition over Large Dynamic Graphs	2021	VLDB	6.1174514e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,069	Truss-based Community Search: a Truss-equivalence Based Indexing Approach	2017	VLDB
2	8,991	Truss-based Community Search over Streaming Directed Graphs	2024	VLDB
3	189	Querying K-Truss Community in Large and Dynamic Graphs	2014	SIGMOD
4	10,857	Truss Decomposition in Hypergraphs	2025	VLDB
5	10,100	Parallel Colorful h-star Core Maintenance in Dynamic Graphs	2023	VLDB
6	102	Truss Decomposition in Massive Networks	2012	VLDB
7	2,826	Hierarchical Core Maintenance on Large Dynamic Graphs	2021	VLDB
8	10,423	A Unified Framework for Dense Subgraph Maintenance over Dynamic Bipartite Graphs	2026	SIGMOD
9	7,408	Efficient Triangle-Connected Truss Community Search In Dynamic Graphs	2023	VLDB
10	2,243	Unboundedness and Efficiency of Truss Maintenance in Evolving Graphs	2019	SIGMOD