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: h1498663b88683948
Venue: SIGMOD
Year: 2023
Pagerank: 5.3950351e-05
Overall Rank: 8,066 | 45.77%
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,419	Truss Decomposition in Hypergraphs	2025	VLDB	5.3350162e-05
9,150	Truss-based Community Search over Streaming Directed Graphs	2024	VLDB	5.21801e-05
10,612	A Unified Framework for Dense Subgraph Maintenance over Dynamic Bipartite Graphs	2026	SIGMOD	4.9793485e-05
10,665	Order-based Algorithms for Efficient Core Maintenance in Large Bipartite Graphs	2026	SIGMOD	4.9793485e-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
100	Truss Decomposition in Massive Networks	2012	VLDB	0.00033977856
184	Querying K-Truss Community in Large and Dynamic Graphs	2014	SIGMOD	0.00026100147
589	Large Scale Cohesive Subgraphs Discovery for Social Network Visual Analysis	2013	VLDB	0.00015905948
758	Streaming Algorithms for k-core Decomposition	2013	VLDB	0.00014188163
1,129	Approximate Closest Community Search in Networks	2016	VLDB	0.00011903608
1,261	Attribute-Driven Community Search	2017	VLDB	0.00011289708
1,354	Truss-based Community Search over Large Directed Graphs	2020	SIGMOD	0.0001092812
1,443	Local Algorithms for Hierarchical Dense Subgraph Discovery	2019	VLDB	0.00010635542
2,086	Truss Decomposition of Probabilistic Graphs: Semantics and Algorithms	2016	SIGMOD	9.0689711e-05
2,146	Maximum Co-located Community Search in Large Scale Social Networks	2018	VLDB	8.9595369e-05
2,285	Unboundedness and Efficiency of Truss Maintenance in Evolving Graphs	2019	SIGMOD	8.6948587e-05
3,495	Accelerating Truss Decomposition on Heterogeneous Processors	2020	VLDB	7.2562279e-05
5,720	Local Algorithms for Distance-generalized Core Decomposition over Large Dynamic Graphs	2021	VLDB	6.018559e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,061	Maximal D-truss Search in Dynamic Directed Graphs	2023	VLDB
2	9,150	Truss-based Community Search over Streaming Directed Graphs	2024	VLDB
3	184	Querying K-Truss Community in Large and Dynamic Graphs	2014	SIGMOD
4	8,419	Truss Decomposition in Hypergraphs	2025	VLDB
5	10,327	Parallel Colorful h-star Core Maintenance in Dynamic Graphs	2023	VLDB
6	100	Truss Decomposition in Massive Networks	2012	VLDB
7	2,869	Hierarchical Core Maintenance on Large Dynamic Graphs	2021	VLDB
8	10,612	A Unified Framework for Dense Subgraph Maintenance over Dynamic Bipartite Graphs	2026	SIGMOD
9	7,547	Efficient Triangle-Connected Truss Community Search In Dynamic Graphs	2023	VLDB
10	2,285	Unboundedness and Efficiency of Truss Maintenance in Evolving Graphs	2019	SIGMOD