DBScholar

Back to papers

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

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 68 citing papers.

Rank Citing Paper Year Venue Pagerank
189 Querying K-Truss Community in Large and Dynamic Graphs 2014 SIGMOD 0.00026114928
590 Large Scale Cohesive Subgraphs Discovery for Social Network Visual Analysis 2013 VLDB 0.0001605572
594 Massive Graph Triangulation 2013 SIGMOD 0.00015979077
937 Blogel: A Block-Centric Framework for Distributed Computation on Real-World Graphs 2014 VLDB 0.00013091546
982 Influential Community Search in Large Networks 2015 VLDB 0.0001283311
1,069 Truss-based Community Search: a Truss-equivalence Based Indexing Approach 2017 VLDB 0.00012323497
1,113 Approximate Closest Community Search in Networks 2016 VLDB 0.00012124571
1,239 Attribute-Driven Community Search 2017 VLDB 0.000115381
1,416 Local Algorithms for Hierarchical Dense Subgraph Discovery 2019 VLDB 0.00010839488
1,509 Finding the Maximum Clique in Massive Graphs 2017 VLDB 0.00010539891
1,533 TF-Label: a Topological-Folding Labeling Scheme for Reachability Querying in a Large Graph 2013 SIGMOD 0.00010467148
1,552 Scalable Subgraph Enumeration in MapReduce 2015 VLDB 0.00010379532
1,640 Distance-generalized Core Decomposition 2019 SIGMOD 0.00010153865
2,083 Fast Hierarchy Construction for Dense Subgraphs 2017 VLDB 9.1976617e-05
2,106 Maximum Co-located Community Search in Large Scale Social Networks 2018 VLDB 9.1568079e-05
2,119 DUALSIM: Parallel Subgraph Enumeration in a Massive Graph on a Single Machine 2016 SIGMOD 9.141144e-05
2,243 Unboundedness and Efficiency of Truss Maintenance in Evolving Graphs 2019 SIGMOD 8.8813183e-05
2,321 Effective and Efficient Relational Community Detection and Search in Large Dynamic Heterogeneous Information Networks 2020 VLDB 8.7540322e-05
2,323 Truss Decomposition of Probabilistic Graphs: Semantics and Algorithms 2016 SIGMOD 8.750808e-05
2,482 Efficient Structural Graph Clustering: An Index-Based Approach 2018 VLDB 8.5183361e-05
2,607 GPU-Accelerated Subgraph Enumeration on Partitioned Graphs 2020 SIGMOD 8.3489531e-05
2,826 Hierarchical Core Maintenance on Large Dynamic Graphs 2021 VLDB 8.0865974e-05
2,839 SCAN++: Efficient Algorithm for Finding Clusters, Hubs and Outliers on Large-scale Graphs 2015 VLDB 8.066541e-05
2,896 Online Density Bursting Subgraph Detection from Temporal Graphs 2019 VLDB 7.9828452e-05
3,148 Finding Locally Densest Subgraphs: A Convex Programming Approach 2022 VLDB 7.707548e-05
3,254 Skyline Community Search in Multi-valued Networks 2018 SIGMOD 7.5928992e-05
3,503 Accelerating Truss Decomposition on Heterogeneous Processors 2020 VLDB 7.3592701e-05
3,686 Accelerating Triangle Counting on GPU 2021 SIGMOD 7.2029305e-05
3,831 Efficient Maximum k-Plex Computation over Large Sparse Graphs 2023 VLDB 7.0862742e-05
3,993 Efficient k-Clique Listing: An Edge-Oriented Branching Strategy 2024 SIGMOD 6.9688824e-05
4,331 Global Reinforcement of Social Networks: The Anchored Coreness Problem 2020 SIGMOD 6.7561061e-05
4,579 Cohesive Subgraph Search over Big Heterogeneous Information Networks: Applications, Challenges, and Solutions 2021 SIGMOD 6.6203846e-05
4,667 Efficient Cohesive Subgraphs Detection in Parallel 2014 SIGMOD 6.5768564e-05
4,672 Efficient Maximum k-Defective Clique Computation with Improved Time Complexity 2023 SIGMOD 6.5731244e-05
4,916 Neighborhood-based Hypergraph Core Decomposition 2023 VLDB 6.4474058e-05
5,471 Maximum k-Plex Computation: Theory and Practice 2024 SIGMOD 6.2061433e-05
5,697 Local Algorithms for Distance-generalized Core Decomposition over Large Dynamic Graphs 2021 VLDB 6.1174514e-05
6,368 Theoretically and Practically Efficient Parallel Nucleus Decomposition 2022 VLDB 5.8975125e-05
6,463 Data-driven Visual Query Interfaces for Graphs: Past, Present, and (Near) Future 2022 SIGMOD 5.871484e-05
6,535 I/O Efficient ECC Graph Decomposition via Graph Reduction 2016 VLDB 5.8486743e-05
6,617 Efficient Parallel D-core Decomposition at Scale 2024 VLDB 5.8212982e-05
6,866 Towards Plug-and-Play Visual Graph Query Interfaces: Data-driven Selection of Canned Patterns for Large Networks 2021 VLDB 5.7507099e-05
7,006 Topic-based Community Search over Spatial-Social Networks 2020 VLDB 5.726836e-05
7,094 Top-K Structural Diversity Search in Large Networks 2013 VLDB 5.7055799e-05
7,408 Efficient Triangle-Connected Truss Community Search In Dynamic Graphs 2023 VLDB 5.6243648e-05
7,475 PLAYPEN: Plug-and-Play Visual Graph Query Interfaces for Top-down and Bottom-Up Search on Large Networks 2022 SIGMOD 5.60922e-05
7,624 RECEIPT: REfine CoarsE-grained IndePendent Tasks for Parallel Tip decomposition of Bipartite Graphs 2021 VLDB 5.5805027e-05
8,011 Efficient Star-based Truss Maintenance on Dynamic Graphs 2023 SIGMOD 5.5074939e-05
8,149 Efficient Index for Temporal Core Queries over Bipartite Graphs 2024 VLDB 5.4784885e-05
8,477 Cohesiveness-aware Hierarchical Compressed Index for Community Search on Attributed Graphs 2025 SIGMOD 5.4170414e-05
Previous Page 1 / 2 Next

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
Previous Page 1 / 1 Next

Semantically Similar Papers