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.00033977856
Overall Rank: 100 | 99.33%
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
8,644	Cohesiveness-aware Hierarchical Compressed Index for Community Search on Attributed Graphs	2025	SIGMOD	5.2954976e-05
9,571	Efficient Algorithms for Pseudoarboricity Computation in Large Static and Dynamic Graphs	2024	VLDB	5.1571823e-05
9,677	Efficient Maximum s-Bundle Search via Local Vertex Connectivity	2025	SIGMOD	5.1435978e-05
9,678	Maximum k-Plex Search: An Alternated Reduction-and-Bound Method	2025	VLDB	5.1435978e-05
9,805	I/O Efficient Label-Constrained Reachability Queries in Large Graphs	2024	VLDB	5.1257999e-05
9,871	Parallel Algorithms for Hierarchical Nucleus Decomposition	2024	SIGMOD	5.1176637e-05
9,915	Efficient Algorithms for Density Decomposition on Large Static and Dynamic Graphs	2024	VLDB	5.1103839e-05
10,202	Sage: Parallel Semi-Asymmetric Graph Algorithms for NVRAMs	2020	VLDB	5.0610409e-05
10,485	Nucleus Decomposition Revisited: An Efficient Counting-Based Approach	2026	SIGMOD	4.9793485e-05
10,495	Querying Cohesive Subgraphs in Temporal Graphs	2026	SIGMOD	4.9793485e-05
10,537	The Power of Core Clique Removal for Exact Clique Enumeration	2026	SIGMOD	4.9793485e-05
10,612	A Unified Framework for Dense Subgraph Maintenance over Dynamic Bipartite Graphs	2026	SIGMOD	4.9793485e-05
10,614	Accelerating Triangle-Connected Truss Community Search Across Heterogeneous Hardware	2026	SIGMOD	4.9793485e-05
11,215	Most Similar Biclique Search at Scale	2025	VLDB	4.9793485e-05
11,313	Sectric: Towards Accurate, Privacy-preserving and Efficient Triangle Counting	2025	VLDB	4.9793485e-05
11,329	Effective and Efficient Community Search for Complex Network Semantics Capture: From Coarse-Grain to Fine-Grain	2025	VLDB	4.9793485e-05
11,446	Efficient Computation of Hyper-triangles on Hypergraphs	2025	VLDB	4.9793485e-05
12,166	Finding Theme Communities from Database Networks	2019	VLDB	4.9793485e-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
265	On Triangulation-based Dense Neighborhood Graph Discovery	2011	VLDB	0.00022748633
645	Finding Maximal Cliques in Massive Networks by H*-graph	2010	SIGMOD	0.00015213733

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	184	Querying K-Truss Community in Large and Dynamic Graphs	2014	SIGMOD
2	758	Streaming Algorithms for k-core Decomposition	2013	VLDB
3	4,755	Efficient Cohesive Subgraphs Detection in Parallel	2014	SIGMOD
4	10,806	Efficient Hyper-truss Decomposition over Hypergraphs	2026	VLDB
5	1,443	Local Algorithms for Hierarchical Dense Subgraph Discovery	2019	VLDB
6	1,354	Truss-based Community Search over Large Directed Graphs	2020	SIGMOD
7	1,092	Truss-based Community Search: a Truss-equivalence Based Indexing Approach	2017	VLDB
8	2,086	Truss Decomposition of Probabilistic Graphs: Semantics and Algorithms	2016	SIGMOD
9	3,495	Accelerating Truss Decomposition on Heterogeneous Processors	2020	VLDB
10	8,419	Truss Decomposition in Hypergraphs	2025	VLDB