Truss Decomposition in Massive Networks

Summary: Truss decomposition for massive networks; the paper uses k-truss as a polynomial-time, informative core of the k-core. It strengthens the in-memory algorithm and introduces two I/O-efficient methods for out-of-core graphs, with real-data experiments showing scalability and the value of k-truss. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 10522
Venue: VLDB
Year: 2012
Pagerank: 0.00048300163
Overall Rank: 108 | 99.26%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Jia Wang
2. James Cheng

Incoming Citations (Sorted by Pagerank)

Showing 16 of 66 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
9,398	Maximum k-Plex Search: An Alternated Reduction-and-Bound Method	2025	VLDB	4.3441378e-05
9,483	I/O Efficient Label-Constrained Reachability Queries in Large Graphs	2024	VLDB	4.3341665e-05
9,552	Cohesiveness-aware Hierarchical Compressed Index for Community Search on Attributed Graphs	2025	SIGMOD	4.3254416e-05
9,862	Sage: Parallel Semi-Asymmetric Graph Algorithms for NVRAMs	2020	VLDB	4.2683554e-05
10,037	The Power of Core Clique Removal for Exact Clique Enumeration	2026	SIGMOD	4.1945683e-05
10,134	A Unified Framework for Dense Subgraph Maintenance over Dynamic Bipartite Graphs	2026	SIGMOD	4.1945683e-05
10,136	Accelerating Triangle-Connected Truss Community Search Across Heterogeneous Hardware	2026	SIGMOD	4.1945683e-05
10,530	Most Similar Biclique Search at Scale	2025	VLDB	4.1945683e-05
10,596	Truss Decomposition in Hypergraphs	2025	VLDB	4.1945683e-05
10,672	Sectric: Towards Accurate, Privacy-preserving and Efficient Triangle Counting	2025	VLDB	4.1945683e-05
10,694	Effective and Efficient Community Search for Complex Network Semantics Capture: From Coarse-Grain to Fine-Grain	2025	VLDB	4.1945683e-05
10,871	Efficient Computation of Hyper-triangles on Hypergraphs	2025	VLDB	4.1945683e-05
10,947	Parallel Algorithms for Hierarchical Nucleus Decomposition	2024	SIGMOD	4.1945683e-05
11,042	Efficient Index for Temporal Core Queries over Bipartite Graphs	2024	VLDB	4.1945683e-05
11,048	Efficient Algorithms for Density Decomposition on Large Static and Dynamic Graphs	2024	VLDB	4.1945683e-05
11,671	Finding Theme Communities from Database Networks	2019	VLDB	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 2 of 2 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
110	On Triangulation-based Dense Neighborhood Graph Discovery	2011	VLDB	0.00047892924
686	Finding Maximal Cliques in Massive Networks by H*-graph	2010	SIGMOD	0.00018178029

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
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
966	Streaming Algorithms for k-core Decomposition	2013	VLDB	0.00014960672
4,921	Efficient Cohesive Subgraphs Detection in Parallel	2014	SIGMOD	5.8237536e-05
2,039	Local Algorithms for Hierarchical Dense Subgraph Discovery	2019	VLDB	9.7061003e-05
1,637	Truss-based Community Search over Large Directed Graphs	2020	SIGMOD	0.0001105259
1,530	Truss-based Community Search: a Truss-equivalence Based Indexing Approach	2017	VLDB	0.00011495611
2,684	Truss Decomposition of Probabilistic Graphs: Semantics and Algorithms	2016	SIGMOD	8.3136866e-05
3,975	Accelerating Truss Decomposition on Heterogeneous Processors	2020	VLDB	6.5736847e-05
10,596	Truss Decomposition in Hypergraphs	2025	VLDB	4.1945683e-05