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: 10710
Venue: VLDB
Year: 2012
Pagerank: 0.00034255289
Overall Rank: 102 | 99.31%
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 18 of 68 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
9,387	Efficient Algorithms for Pseudoarboricity Computation in Large Static and Dynamic Graphs	2024	VLDB	5.2755515e-05
9,540	Efficient Maximum s-Bundle Search via Local Vertex Connectivity	2025	SIGMOD	5.2528121e-05
9,551	Maximum k-Plex Search: An Alternated Reduction-and-Bound Method	2025	VLDB	5.2528121e-05
9,625	I/O Efficient Label-Constrained Reachability Queries in Large Graphs	2024	VLDB	5.2434488e-05
9,695	Parallel Algorithms for Hierarchical Nucleus Decomposition	2024	SIGMOD	5.2351259e-05
10,011	Sage: Parallel Semi-Asymmetric Graph Algorithms for NVRAMs	2020	VLDB	5.1772034e-05
10,273	Nucleus Decomposition Revisited: An Efficient Counting-Based Approach	2026	SIGMOD	5.093636e-05
10,283	Querying Cohesive Subgraphs in Temporal Graphs	2026	SIGMOD	5.093636e-05
10,332	The Power of Core Clique Removal for Exact Clique Enumeration	2026	SIGMOD	5.093636e-05
10,423	A Unified Framework for Dense Subgraph Maintenance over Dynamic Bipartite Graphs	2026	SIGMOD	5.093636e-05
10,425	Accelerating Triangle-Connected Truss Community Search Across Heterogeneous Hardware	2026	SIGMOD	5.093636e-05
10,802	Most Similar Biclique Search at Scale	2025	VLDB	5.093636e-05
10,857	Truss Decomposition in Hypergraphs	2025	VLDB	5.093636e-05
10,921	Sectric: Towards Accurate, Privacy-preserving and Efficient Triangle Counting	2025	VLDB	5.093636e-05
10,941	Effective and Efficient Community Search for Complex Network Semantics Capture: From Coarse-Grain to Fine-Grain	2025	VLDB	5.093636e-05
11,094	Efficient Computation of Hyper-triangles on Hypergraphs	2025	VLDB	5.093636e-05
11,256	Efficient Algorithms for Density Decomposition on Large Static and Dynamic Graphs	2024	VLDB	5.093636e-05
11,866	Finding Theme Communities from Database Networks	2019	VLDB	5.093636e-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
262	On Triangulation-based Dense Neighborhood Graph Discovery	2011	VLDB	0.00023084332
674	Finding Maximal Cliques in Massive Networks by H*-graph	2010	SIGMOD	0.00015081844

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,991	Truss-based Community Search over Streaming Directed Graphs	2024	VLDB
2	189	Querying K-Truss Community in Large and Dynamic Graphs	2014	SIGMOD
3	793	Streaming Algorithms for k-core Decomposition	2013	VLDB
4	4,667	Efficient Cohesive Subgraphs Detection in Parallel	2014	SIGMOD
5	1,416	Local Algorithms for Hierarchical Dense Subgraph Discovery	2019	VLDB
6	1,328	Truss-based Community Search over Large Directed Graphs	2020	SIGMOD
7	1,069	Truss-based Community Search: a Truss-equivalence Based Indexing Approach	2017	VLDB
8	2,323	Truss Decomposition of Probabilistic Graphs: Semantics and Algorithms	2016	SIGMOD
9	3,503	Accelerating Truss Decomposition on Heterogeneous Processors	2020	VLDB
10	10,857	Truss Decomposition in Hypergraphs	2025	VLDB