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: h4060b042ad2a133e
Venue: VLDB
Year: 2012
Pagerank: 0.00034261728
Overall Rank: 96 | 99.36%
DOI: 10.14778/2315356.2315361

Incoming Non-self Citations Over Time

Authors

1. Jia Wang (Chinese University of Hong Kong)
2. James Cheng (Nanyang Technological University)

BibTeX Citation

@article{wang_vldb12,
        title = {{Truss Decomposition in Massive Networks}},
        author = {Wang, Jia and Cheng, James},
        journal = {PVLDB},
        series = {{VLDB} '12},
        volume = {5},
        number = {9},
        pages = {812--823},
        doi = {10.14778/2315356.2315361},
        url = {https://doi.org/10.14778/2315356.2315361},
        year = {2012}
}

Incoming Citations (Sorted by Pagerank)

Showing 19 of 69 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
8,444	Truss Decomposition in Hypergraphs	2025	VLDB	5.3148581e-05
9,604	Efficient Algorithms for Pseudoarboricity Computation in Large Static and Dynamic Graphs	2024	VLDB	5.1376962e-05
9,713	Efficient Maximum s-Bundle Search via Local Vertex Connectivity	2025	SIGMOD	5.124163e-05
9,714	Maximum k-Plex Search: An Alternated Reduction-and-Bound Method	2025	VLDB	5.124163e-05
9,846	I/O Efficient Label-Constrained Reachability Queries in Large Graphs	2024	VLDB	5.1064323e-05
9,911	Parallel Algorithms for Hierarchical Nucleus Decomposition	2024	SIGMOD	5.0983269e-05
9,957	Efficient Algorithms for Density Decomposition on Large Static and Dynamic Graphs	2024	VLDB	5.0910746e-05
10,241	Sage: Parallel Semi-Asymmetric Graph Algorithms for NVRAMs	2020	VLDB	5.041918e-05
10,407	Scaling Up Density Decomposition on Massive Graphs	2027	SIGMOD	4.9605343e-05
10,562	Nucleus Decomposition Revisited: An Efficient Counting-Based Approach	2026	SIGMOD	4.9605343e-05
10,572	Querying Cohesive Subgraphs in Temporal Graphs	2026	SIGMOD	4.9605343e-05
10,613	The Power of Core Clique Removal for Exact Clique Enumeration	2026	SIGMOD	4.9605343e-05
10,684	A Unified Framework for Dense Subgraph Maintenance over Dynamic Bipartite Graphs	2026	SIGMOD	4.9605343e-05
10,686	Accelerating Triangle-Connected Truss Community Search Across Heterogeneous Hardware	2026	SIGMOD	4.9605343e-05
11,280	Most Similar Biclique Search at Scale	2025	VLDB	4.9605343e-05
11,375	Sectric: Towards Accurate, Privacy-preserving and Efficient Triangle Counting	2025	VLDB	4.9605343e-05
11,390	Effective and Efficient Community Search for Complex Network Semantics Capture: From Coarse-Grain to Fine-Grain	2025	VLDB	4.9605343e-05
11,504	Efficient Computation of Hyper-triangles on Hypergraphs	2025	VLDB	4.9605343e-05
12,215	Finding Theme Communities from Database Networks	2019	VLDB	4.9605343e-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
255	On Triangulation-based Dense Neighborhood Graph Discovery	2011	VLDB	0.00022949287
643	Finding Maximal Cliques in Massive Networks by H*-graph	2010	SIGMOD	0.00015219469

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	182	Querying K-Truss Community in Large and Dynamic Graphs	2014	SIGMOD
2	732	Streaming Algorithms for k-core Decomposition	2013	VLDB
3	4,731	Efficient Cohesive Subgraphs Detection in Parallel	2014	SIGMOD
4	10,877	Efficient Hyper-truss Decomposition over Hypergraphs	2026	VLDB
5	1,398	Local Algorithms for Hierarchical Dense Subgraph Discovery	2019	VLDB
6	1,357	Truss-based Community Search over Large Directed Graphs	2020	SIGMOD
7	1,045	Truss-based Community Search: a Truss-equivalence Based Indexing Approach	2017	VLDB
8	2,072	Truss Decomposition of Probabilistic Graphs: Semantics and Algorithms	2016	SIGMOD
9	3,499	Accelerating Truss Decomposition on Heterogeneous Processors	2020	VLDB
10	8,444	Truss Decomposition in Hypergraphs	2025	VLDB