Efficient Triangle-Connected Truss Community Search In Dynamic Graphs

Summary: Revisit k-TTC search in dynamic graphs: prove a diameter upper bound for k-TTC (≤ ⌊2n/(k+1)⌋) and formalize triangle connectivity via the novel concepts of partial class and truss-precedence. Build EquiTree, a compact index with efficient construction/maintenance achieving up to two-orders-of-magnitude query speedups. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 13497
Venue: VLDB
Year: 2023
Pagerank: 5.6243648e-05
Overall Rank: 7,408 | 49.18%
DOI: 10.14778/3570690.3570701

Incoming Non-self Citations Over Time

Authors

1. Tianyang Xu (Wuhan University)
2. Zhao Lu (Wuhan University)
3. Yuanyuan Zhu (Wuhan University)

BibTeX Citation

@article{xu_vldb23,
        title = {{Efficient Triangle-Connected Truss Community Search In Dynamic Graphs}},
        author = {Xu, Tianyang and Lu, Zhao and Zhu, Yuanyuan},
        journal = {PVLDB},
        series = {{VLDB} '23},
        volume = {16},
        number = {3},
        pages = {519--531},
        doi = {10.14778/3570690.3570701},
        url = {https://doi.org/10.14778/3570690.3570701},
        year = {2023}
}

Incoming Citations (Sorted by Pagerank)

Showing 6 of 6 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
8,504	Enabling Window-Based Monotonic Graph Analytics with Reusable Transitional Results for Pattern-Consistent Queries	2024	VLDB	5.4132367e-05
9,691	A Flexible Framework for Query-oriented Interactive Community Search	2025	VLDB	5.2351259e-05
10,273	Nucleus Decomposition Revisited: An Efficient Counting-Based Approach	2026	SIGMOD	5.093636e-05
10,425	Accelerating Triangle-Connected Truss Community Search Across Heterogeneous Hardware	2026	SIGMOD	5.093636e-05
10,478	Order-based Algorithms for Efficient Core Maintenance in Large Bipartite Graphs	2026	SIGMOD	5.093636e-05
10,656	A Local Search Approach to Efficient (k, p)-Core Maintenance	2025	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 14 of 14 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
273	Online Search of Overlapping Communities	2013	SIGMOD	0.00022671795
706	Effective Community Search for Large Attributed Graphs	2016	VLDB	0.00014789612
825	K-Core Decomposition of Large Networks on a Single PC	2016	VLDB	0.00013779895
1,069	Truss-based Community Search: a Truss-equivalence Based Indexing Approach	2017	VLDB	0.00012323497
1,113	Approximate Closest Community Search in Networks	2016	VLDB	0.00012124571
1,239	Attribute-Driven Community Search	2017	VLDB	0.000115381
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,383	ICS-GNN: Lightweight Interactive Community Search via Graph Neural Network	2021	VLDB	8.6527736e-05
2,826	Hierarchical Core Maintenance on Large Dynamic Graphs	2021	VLDB	8.0865974e-05
2,873	Query Driven-Graph Neural Networks for Community Search: From Non-Attributed, Attributed, to Interactive Attributed	2022	VLDB	8.0099557e-05
6,179	Densely Connected User Community and Location Cluster Search in Location-Based Social Networks	2020	SIGMOD	5.9496108e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,452	FirmTruss Community Search in Multilayer Networks	2023	VLDB
2	1,239	Attribute-Driven Community Search	2017	VLDB
3	2,106	Maximum Co-located Community Search in Large Scale Social Networks	2018	VLDB
4	1,113	Approximate Closest Community Search in Networks	2016	VLDB
5	8,991	Truss-based Community Search over Streaming Directed Graphs	2024	VLDB
6	10,425	Accelerating Triangle-Connected Truss Community Search Across Heterogeneous Hardware	2026	SIGMOD
7	5,977	Maximal D-truss Search in Dynamic Directed Graphs	2023	VLDB
8	1,328	Truss-based Community Search over Large Directed Graphs	2020	SIGMOD
9	189	Querying K-Truss Community in Large and Dynamic Graphs	2014	SIGMOD
10	1,069	Truss-based Community Search: a Truss-equivalence Based Indexing Approach	2017	VLDB