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: 6636
Venue: SIGMOD
Year: 2023
Pagerank: 4.6058845e-05
Overall Rank: 8,014 | 44.25%
DOI: 10.1145/3589278

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
8,975	Truss-based Community Search over Streaming Directed Graphs	2024	VLDB	4.4179255e-05
10,134	A Unified Framework for Dense Subgraph Maintenance over Dynamic Bipartite Graphs	2026	SIGMOD	4.1945683e-05
10,189	Order-based Algorithms for Efficient Core Maintenance in Large Bipartite Graphs	2026	SIGMOD	4.1945683e-05
10,596	Truss Decomposition in Hypergraphs	2025	VLDB	4.1945683e-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
108	Truss Decomposition in Massive Networks	2012	VLDB	0.00048300163
283	Querying K-Truss Community in Large and Dynamic Graphs	2014	SIGMOD	0.00029041257
738	Large Scale Cohesive Subgraphs Discovery for Social Network Visual Analysis	2013	VLDB	0.00017435236
966	Streaming Algorithms for k-core Decomposition	2013	VLDB	0.00014960672
1,550	Approximate Closest Community Search in Networks	2016	VLDB	0.00011423628
1,637	Truss-based Community Search over Large Directed Graphs	2020	SIGMOD	0.0001105259
1,645	Attribute-Driven Community Search	2017	VLDB	0.00011037459
2,039	Local Algorithms for Hierarchical Dense Subgraph Discovery	2019	VLDB	9.7061003e-05
2,603	Maximum Co-located Community Search in Large Scale Social Networks	2018	VLDB	8.4666465e-05
2,684	Truss Decomposition of Probabilistic Graphs: Semantics and Algorithms	2016	SIGMOD	8.3136866e-05
2,846	Unboundedness and Efficiency of Truss Maintenance in Evolving Graphs	2019	SIGMOD	8.0234377e-05
3,975	Accelerating Truss Decomposition on Heterogeneous Processors	2020	VLDB	6.5736847e-05
6,141	Local Algorithms for Distance-generalized Core Decomposition over Large Dynamic Graphs	2021	VLDB	5.1903263e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
6,725	Maximal D-truss Search in Dynamic Directed Graphs	2023	VLDB	4.9484066e-05
8,975	Truss-based Community Search over Streaming Directed Graphs	2024	VLDB	4.4179255e-05
283	Querying K-Truss Community in Large and Dynamic Graphs	2014	SIGMOD	0.00029041257
10,596	Truss Decomposition in Hypergraphs	2025	VLDB	4.1945683e-05
9,951	Parallel Colorful h-star Core Maintenance in Dynamic Graphs	2023	VLDB	4.2405999e-05
108	Truss Decomposition in Massive Networks	2012	VLDB	0.00048300163
3,321	Hierarchical Core Maintenance on Large Dynamic Graphs	2021	VLDB	7.223972e-05
10,134	A Unified Framework for Dense Subgraph Maintenance over Dynamic Bipartite Graphs	2026	SIGMOD	4.1945683e-05
8,169	Efficient Triangle-Connected Truss Community Search In Dynamic Graphs	2023	VLDB	4.5698941e-05
2,846	Unboundedness and Efficiency of Truss Maintenance in Evolving Graphs	2019	SIGMOD	8.0234377e-05