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 50 of 69 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
182	Querying K-Truss Community in Large and Dynamic Graphs	2014	SIGMOD	0.00026383593
580	Large Scale Cohesive Subgraphs Discovery for Social Network Visual Analysis	2013	VLDB	0.00016057466
599	Massive Graph Triangulation	2013	SIGMOD	0.00015700433
931	Blogel: A Block-Centric Framework for Distributed Computation on Real-World Graphs	2014	VLDB	0.00012993132
970	Influential Community Search in Large Networks	2015	VLDB	0.00012749284
1,045	Truss-based Community Search: a Truss-equivalence Based Indexing Approach	2017	VLDB	0.00012318828
1,118	Approximate Closest Community Search in Networks	2016	VLDB	0.0001192817
1,234	Attribute-Driven Community Search	2017	VLDB	0.0001138939
1,398	Local Algorithms for Hierarchical Dense Subgraph Discovery	2019	VLDB	0.0001076734
1,495	Finding the Maximum Clique in Massive Graphs	2017	VLDB	0.0001046246
1,564	TF-Label: a Topological-Folding Labeling Scheme for Reachability Querying in a Large Graph	2013	SIGMOD	0.00010186448
1,565	Scalable Subgraph Enumeration in MapReduce	2015	VLDB	0.00010185615
1,613	Distance-generalized Core Decomposition	2019	SIGMOD	0.00010057822
2,005	Fast Hierarchy Construction for Dense Subgraphs	2017	VLDB	9.1851569e-05
2,072	Truss Decomposition of Probabilistic Graphs: Semantics and Algorithms	2016	SIGMOD	9.0668141e-05
2,101	DUALSIM: Parallel Subgraph Enumeration in a Massive Graph on a Single Machine	2016	SIGMOD	9.0309825e-05
2,110	Maximum Co-located Community Search in Large Scale Social Networks	2018	VLDB	9.0222862e-05
2,246	Unboundedness and Efficiency of Truss Maintenance in Evolving Graphs	2019	SIGMOD	8.7594692e-05
2,285	Effective and Efficient Relational Community Detection and Search in Large Dynamic Heterogeneous Information Networks	2020	VLDB	8.6875058e-05
2,470	Efficient Structural Graph Clustering: An Index-Based Approach	2018	VLDB	8.4015437e-05
2,478	GPU-Accelerated Subgraph Enumeration on Partitioned Graphs	2020	SIGMOD	8.3890338e-05
2,815	SCAN++: Efficient Algorithm for Finding Clusters, Hubs and Outliers on Large-scale Graphs	2015	VLDB	7.9544959e-05
2,873	Hierarchical Core Maintenance on Large Dynamic Graphs	2021	VLDB	7.9005874e-05
2,893	Online Density Bursting Subgraph Detection from Temporal Graphs	2019	VLDB	7.8870831e-05
2,926	Finding Locally Densest Subgraphs: A Convex Programming Approach	2022	VLDB	7.837861e-05
3,000	Efficient Maximum k-Plex Computation over Large Sparse Graphs	2023	VLDB	7.7498183e-05
3,221	Skyline Community Search in Multi-valued Networks	2018	SIGMOD	7.5060153e-05
3,321	Accelerating Triangle Counting on GPU	2021	SIGMOD	7.4117038e-05
3,499	Accelerating Truss Decomposition on Heterogeneous Processors	2020	VLDB	7.2351042e-05
3,591	Efficient Maximum k-Defective Clique Computation with Improved Time Complexity	2023	SIGMOD	7.1655231e-05
3,597	Efficient k-Clique Listing: An Edge-Oriented Branching Strategy	2024	SIGMOD	7.1598365e-05
3,881	Cohesive Subgraph Search over Big Heterogeneous Information Networks: Applications, Challenges, and Solutions	2021	SIGMOD	6.9309694e-05
4,180	Global Reinforcement of Social Networks: The Anchored Coreness Problem	2020	SIGMOD	6.7474268e-05
4,333	Neighborhood-based Hypergraph Core Decomposition	2023	VLDB	6.6444874e-05
4,731	Efficient Cohesive Subgraphs Detection in Parallel	2014	SIGMOD	6.4313179e-05
5,066	Maximum k-Plex Computation: Theory and Practice	2024	SIGMOD	6.2786224e-05
5,298	Top-K Structural Diversity Search in Large Networks	2013	VLDB	6.1768321e-05
5,575	Theoretically and Practically Efficient Parallel Nucleus Decomposition	2022	VLDB	6.0626208e-05
5,725	Local Algorithms for Distance-generalized Core Decomposition over Large Dynamic Graphs	2021	VLDB	5.9991587e-05
6,226	I/O Efficient ECC Graph Decomposition via Graph Reduction	2016	VLDB	5.8266364e-05
6,578	Data-driven Visual Query Interfaces for Graphs: Past, Present, and (Near) Future	2022	SIGMOD	5.7253513e-05
6,666	Efficient Parallel D-core Decomposition at Scale	2024	VLDB	5.698709e-05
7,000	Towards Plug-and-Play Visual Graph Query Interfaces: Data-driven Selection of Canned Patterns for Large Networks	2021	VLDB	5.6080933e-05
7,165	Topic-based Community Search over Spatial-Social Networks	2020	VLDB	5.5797415e-05
7,568	Efficient Triangle-Connected Truss Community Search In Dynamic Graphs	2023	VLDB	5.4773947e-05
7,639	PLAYPEN: Plug-and-Play Visual Graph Query Interfaces for Top-down and Bottom-Up Search on Large Networks	2022	SIGMOD	5.4626456e-05
7,752	RECEIPT: REfine CoarsE-grained IndePendent Tasks for Parallel Tip decomposition of Bipartite Graphs	2021	VLDB	5.4440674e-05
8,087	Cohesiveness-aware Hierarchical Compressed Index for Community Search on Attributed Graphs	2025	SIGMOD	5.3746995e-05
8,088	Efficient Star-based Truss Maintenance on Dynamic Graphs	2023	SIGMOD	5.3746503e-05
8,339	Efficient Index for Temporal Core Queries over Bipartite Graphs	2024	VLDB	5.3353302e-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