Truss Decomposition in Hypergraphs

Summary: Introduces hypergraph k-truss (nodes in ≥k hyper‑triangles) and a truss decomposition framework identifying hyper‑triangle counting as the bottleneck. Proposes an edge‑iterator, a hybrid edge+node iterator with pruning, a prefix‑forest encoding for shared nodes, reordering optimizations, and empirical validation on real hypergraphs. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 13870
Venue: VLDB
Year: 2025
Pagerank: 4.1945683e-05
Overall Rank: 10,596 | 26.29%
DOI: 10.14778/3734839.3734854

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 16 of 16 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
1,257	Influential Community Search in Large Networks	2015	VLDB	0.00013020648
1,550	Approximate Closest Community Search in Networks	2016	VLDB	0.00011423628
1,836	Distance-generalized Core Decomposition	2019	SIGMOD	0.00010365753
3,063	Sliding Window-based Approximate Triangle Counting over Streaming Graphs with Duplicate Edges	2021	SIGMOD	7.6321424e-05
3,603	Skyline Community Search in Multi-valued Networks	2018	SIGMOD	6.9306814e-05
4,168	Accelerating Triangle Counting on GPU	2021	SIGMOD	6.391271e-05
5,298	Distributed D-core Decomposition over Large Directed Graphs	2022	VLDB	5.5799987e-05
5,589	Neighborhood-based Hypergraph Core Decomposition	2023	VLDB	5.4216989e-05
6,141	Local Algorithms for Distance-generalized Core Decomposition over Large Dynamic Graphs	2021	VLDB	5.1903263e-05
6,530	Fast Algorithms for Core Maximization on Large Graphs	2022	VLDB	5.0246792e-05
6,725	Maximal D-truss Search in Dynamic Directed Graphs	2023	VLDB	4.9484066e-05
6,864	Triangle and Four Cycle Counting in the Data Stream Model	2020	PODS	4.9050236e-05
7,111	Fast Maximal Quasi-clique Enumeration: A Pruning and Branching Co-Design Approach	2023	SIGMOD	4.8284522e-05
8,014	Efficient Star-based Truss Maintenance on Dynamic Graphs	2023	SIGMOD	4.6058845e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
10,123	Triangle Counting in Hypergraph Streams: A Complete and Practical Approach	2026	SIGMOD	4.1945683e-05
8,169	Efficient Triangle-Connected Truss Community Search In Dynamic Graphs	2023	VLDB	4.5698941e-05
2,512	Fast Hierarchy Construction for Dense Subgraphs	2017	VLDB	8.6196023e-05
8,975	Truss-based Community Search over Streaming Directed Graphs	2024	VLDB	4.4179255e-05
2,039	Local Algorithms for Hierarchical Dense Subgraph Discovery	2019	VLDB	9.7061003e-05
2,684	Truss Decomposition of Probabilistic Graphs: Semantics and Algorithms	2016	SIGMOD	8.3136866e-05
9,146	Accelerating Core Decomposition in Billion-Scale Hypergraphs	2025	SIGMOD	4.3849295e-05
10,871	Efficient Computation of Hyper-triangles on Hypergraphs	2025	VLDB	4.1945683e-05
108	Truss Decomposition in Massive Networks	2012	VLDB	0.00048300163
3,975	Accelerating Truss Decomposition on Heterogeneous Processors	2020	VLDB	6.5736847e-05