Truss Decomposition of Probabilistic Graphs: Semantics and Algorithms

Summary: Defines (k, gamma)-truss for probabilistic graphs: maximal subgraphs where each edge has prob ≥ gamma of in ≥(k−2) triangles; provides a dynamic-programming local-decomposition algorithm. Global (k, gamma)-truss is intractable; introduces a sampling-based approximate discovery with high probability, validated on real datasets. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h30c465b3b2909ea6
Venue: SIGMOD
Year: 2016
Pagerank: 9.0668141e-05
Overall Rank: 2,072 | 86.12%
DOI: 10.1145/2882903.2882913

Incoming Non-self Citations Over Time

Authors

1. Xin Huang (University of British Columbia)
2. Wei Lu (University of British Columbia)
3. Laks V.S. Lakshmanan (University of British Columbia)

BibTeX Citation

@inproceedings{huang_sigmod16,
        title = {{Truss Decomposition of Probabilistic Graphs: Semantics and Algorithms}},
        author = {Huang, Xin and Lu, Wei and Lakshmanan, Laks V.S.},
        series = {{SIGMOD} '16},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/2882903.2882913},
        url = {https://dl.acm.org/doi/10.1145/2882903.2882913},
        year = {2016}
}

Incoming Citations (Sorted by Pagerank)

Showing 16 of 16 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,045	Truss-based Community Search: a Truss-equivalence Based Indexing Approach	2017	VLDB	0.00012318828
1,995	Efficient Algorithms for Densest Subgraph Discovery	2019	VLDB	9.2189157e-05
2,005	Fast Hierarchy Construction for Dense Subgraphs	2017	VLDB	9.1851569e-05
3,644	Efficient and Effective Algorithms for Clustering Uncertain Graphs	2019	VLDB	7.1224321e-05
3,804	Butterfly Counting on Uncertain Bipartite Graphs	2022	VLDB	6.9907371e-05
3,863	When Engagement Meets Similarity: Efficient (k,r)-Core Computation on Social Networks	2017	VLDB	6.9488207e-05
4,057	Efficient Bi-triangle Counting for Large Bipartite Networks	2021	VLDB	6.8140795e-05
4,753	Fast Maximal Clique Enumeration on Uncertain Graphs: A Pivot-based Approach	2022	SIGMOD	6.4218566e-05
5,725	Local Algorithms for Distance-generalized Core Decomposition over Large Dynamic Graphs	2021	VLDB	5.9991587e-05
6,666	Efficient Parallel D-core Decomposition at Scale	2024	VLDB	5.698709e-05
7,624	Scalable Approximate Butterfly and Bi-triangle Counting for Large Bipartite Networks	2023	SIGMOD	5.4661079e-05
8,088	Efficient Star-based Truss Maintenance on Dynamic Graphs	2023	SIGMOD	5.3746503e-05
9,491	Sage: A System for Uncertain Network Analysis	2022	VLDB	5.1549931e-05
10,879	Efficient Locally h-Clique Densest Subgraph Discovery via Divide-and-Conquer	2026	VLDB	4.9605343e-05
10,880	GPU-Accelerated eta-threshold Decomposition for Uncertain Graphs	2026	VLDB	4.9605343e-05
12,215	Finding Theme Communities from Database Networks	2019	VLDB	4.9605343e-05

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
96	Truss Decomposition in Massive Networks	2012	VLDB	0.00034261728
182	Querying K-Truss Community in Large and Dynamic Graphs	2014	SIGMOD	0.00026383593
440	Efficient Subgraph Matching on Billion Node Graphs	2012	VLDB	0.00018235529
580	Large Scale Cohesive Subgraphs Discovery for Social Network Visual Analysis	2013	VLDB	0.00016057466
643	Finding Maximal Cliques in Massive Networks by H*-graph	2010	SIGMOD	0.00015219469
1,069	k-Nearest Neighbors in Uncertain Graphs	2010	VLDB	0.00012164865
1,266	Distance-Constraint Reachability Computation in Uncertain Graphs	2011	VLDB	0.00011256294

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,078	Maximal D-truss Search in Dynamic Directed Graphs	2023	VLDB
2	182	Querying K-Truss Community in Large and Dynamic Graphs	2014	SIGMOD
3	1,045	Truss-based Community Search: a Truss-equivalence Based Indexing Approach	2017	VLDB
4	2,246	Unboundedness and Efficiency of Truss Maintenance in Evolving Graphs	2019	SIGMOD
5	3,499	Accelerating Truss Decomposition on Heterogeneous Processors	2020	VLDB
6	1,398	Local Algorithms for Hierarchical Dense Subgraph Discovery	2019	VLDB
7	10,877	Efficient Hyper-truss Decomposition over Hypergraphs	2026	VLDB
8	1,357	Truss-based Community Search over Large Directed Graphs	2020	SIGMOD
9	8,444	Truss Decomposition in Hypergraphs	2025	VLDB
10	96	Truss Decomposition in Massive Networks	2012	VLDB