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: 10523
Venue: VLDB
Year: 2012
Pagerank: 0.00034018471
Overall Rank: 102 | 99.30%
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,399	Maximum k-Plex Search: An Alternated Reduction-and-Bound Method	2025	VLDB	5.3341661e-05
9,479	I/O Efficient Label-Constrained Reachability Queries in Large Graphs	2024	VLDB	5.3246578e-05
9,546	Cohesiveness-aware Hierarchical Compressed Index for Community Search on Attributed Graphs	2025	SIGMOD	5.316206e-05
9,859	Sage: Parallel Semi-Asymmetric Graph Algorithms for NVRAMs	2020	VLDB	5.2573864e-05
10,037	The Power of Core Clique Removal for Exact Clique Enumeration	2026	SIGMOD	5.1725247e-05
10,134	A Unified Framework for Dense Subgraph Maintenance over Dynamic Bipartite Graphs	2026	SIGMOD	5.1725247e-05
10,136	Accelerating Triangle-Connected Truss Community Search Across Heterogeneous Hardware	2026	SIGMOD	5.1725247e-05
10,539	Most Similar Biclique Search at Scale	2025	VLDB	5.1725247e-05
10,604	Truss Decomposition in Hypergraphs	2025	VLDB	5.1725247e-05
10,680	Sectric: Towards Accurate, Privacy-preserving and Efficient Triangle Counting	2025	VLDB	5.1725247e-05
10,702	Effective and Efficient Community Search for Complex Network Semantics Capture: From Coarse-Grain to Fine-Grain	2025	VLDB	5.1725247e-05
10,875	Efficient Computation of Hyper-triangles on Hypergraphs	2025	VLDB	5.1725247e-05
10,950	Parallel Algorithms for Hierarchical Nucleus Decomposition	2024	SIGMOD	5.1725247e-05
11,045	Efficient Index for Temporal Core Queries over Bipartite Graphs	2024	VLDB	5.1725247e-05
11,051	Efficient Algorithms for Density Decomposition on Large Static and Dynamic Graphs	2024	VLDB	5.1725247e-05
11,676	Finding Theme Communities from Database Networks	2019	VLDB	5.1725247e-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.00023104293
701	Finding Maximal Cliques in Massive Networks by H*-graph	2010	SIGMOD	0.00014954424

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
8,860	Truss-based Community Search over Streaming Directed Graphs	2024	VLDB	5.4204453e-05
202	Querying K-Truss Community in Large and Dynamic Graphs	2014	SIGMOD	0.00025608916
812	Streaming Algorithms for k-core Decomposition	2013	VLDB	0.00013910201
4,662	Efficient Cohesive Subgraphs Detection in Parallel	2014	SIGMOD	6.6385168e-05
1,574	Local Algorithms for Hierarchical Dense Subgraph Discovery	2019	VLDB	0.00010374281
1,377	Truss-based Community Search over Large Directed Graphs	2020	SIGMOD	0.00011078472
1,128	Truss-based Community Search: a Truss-equivalence Based Indexing Approach	2017	VLDB	0.00012139459
2,331	Truss Decomposition of Probabilistic Graphs: Semantics and Algorithms	2016	SIGMOD	8.819467e-05
3,634	Accelerating Truss Decomposition on Heterogeneous Processors	2020	VLDB	7.3118793e-05
10,604	Truss Decomposition in Hypergraphs	2025	VLDB	5.1725247e-05