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: 6637
Venue: SIGMOD
Year: 2023
Pagerank: 4.6014683e-05
Overall Rank: 8,017 | 44.29%
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,982	Truss-based Community Search over Streaming Directed Graphs	2024	VLDB	4.413691e-05
10,134	A Unified Framework for Dense Subgraph Maintenance over Dynamic Bipartite Graphs	2026	SIGMOD	4.1905499e-05
10,189	Order-based Algorithms for Efficient Core Maintenance in Large Bipartite Graphs	2026	SIGMOD	4.1905499e-05
10,604	Truss Decomposition in Hypergraphs	2025	VLDB	4.1905499e-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
106	Truss Decomposition in Massive Networks	2012	VLDB	0.00048373761
284	Querying K-Truss Community in Large and Dynamic Graphs	2014	SIGMOD	0.00029014359
734	Large Scale Cohesive Subgraphs Discovery for Social Network Visual Analysis	2013	VLDB	0.00017419528
966	Streaming Algorithms for k-core Decomposition	2013	VLDB	0.00014947141
1,548	Approximate Closest Community Search in Networks	2016	VLDB	0.0001141271
1,641	Truss-based Community Search over Large Directed Graphs	2020	SIGMOD	0.00011044805
1,645	Attribute-Driven Community Search	2017	VLDB	0.00011027616
2,043	Local Algorithms for Hierarchical Dense Subgraph Discovery	2019	VLDB	9.6970812e-05
2,608	Maximum Co-located Community Search in Large Scale Social Networks	2018	VLDB	8.4587487e-05
2,685	Truss Decomposition of Probabilistic Graphs: Semantics and Algorithms	2016	SIGMOD	8.314724e-05
2,852	Unboundedness and Efficiency of Truss Maintenance in Evolving Graphs	2019	SIGMOD	8.0158741e-05
3,976	Accelerating Truss Decomposition on Heterogeneous Processors	2020	VLDB	6.5694893e-05
6,145	Local Algorithms for Distance-generalized Core Decomposition over Large Dynamic Graphs	2021	VLDB	5.1853422e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
1,529	Truss-based Community Search: a Truss-equivalence Based Indexing Approach	2017	VLDB	0.00011484853
8,982	Truss-based Community Search over Streaming Directed Graphs	2024	VLDB	4.413691e-05
284	Querying K-Truss Community in Large and Dynamic Graphs	2014	SIGMOD	0.00029014359
10,604	Truss Decomposition in Hypergraphs	2025	VLDB	4.1905499e-05
9,950	Parallel Colorful h-star Core Maintenance in Dynamic Graphs	2023	VLDB	4.236537e-05
106	Truss Decomposition in Massive Networks	2012	VLDB	0.00048373761
3,323	Hierarchical Core Maintenance on Large Dynamic Graphs	2021	VLDB	7.2170169e-05
10,134	A Unified Framework for Dense Subgraph Maintenance over Dynamic Bipartite Graphs	2026	SIGMOD	4.1905499e-05
8,171	Efficient Triangle-Connected Truss Community Search In Dynamic Graphs	2023	VLDB	4.5655127e-05
2,852	Unboundedness and Efficiency of Truss Maintenance in Evolving Graphs	2019	SIGMOD	8.0158741e-05