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: 5105
Venue: SIGMOD
Year: 2016
Pagerank: 8.314724e-05
Overall Rank: 2,685 | 81.35%
DOI: 10.1145/2882903.2882913

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 14 of 14 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,529	Truss-based Community Search: a Truss-equivalence Based Indexing Approach	2017	VLDB	0.00011484853
2,516	Fast Hierarchy Construction for Dense Subgraphs	2017	VLDB	8.6114467e-05
2,913	Efficient Algorithms for Densest Subgraph Discovery	2019	VLDB	7.9229304e-05
3,622	Efficient and Effective Algorithms for Clustering Uncertain Graphs	2019	VLDB	6.9021704e-05
4,158	Butterfly Counting on Uncertain Bipartite Graphs	2022	VLDB	6.3898204e-05
4,391	When Engagement Meets Similarity: Efficient (k,r)-Core Computation on Social Networks	2017	VLDB	6.2190075e-05
4,460	Efficient Bi-triangle Counting for Large Bipartite Networks	2021	VLDB	6.1592411e-05
5,909	Fast Maximal Clique Enumeration on Uncertain Graphs: A Pivot-based Approach	2022	SIGMOD	5.2722596e-05
6,145	Local Algorithms for Distance-generalized Core Decomposition over Large Dynamic Graphs	2021	VLDB	5.1853422e-05
6,509	Efficient Parallel D-core Decomposition at Scale	2024	VLDB	5.0273291e-05
7,450	Scalable Approximate Butterfly and Bi-triangle Counting for Large Bipartite Networks	2023	SIGMOD	4.7218383e-05
8,017	Efficient Star-based Truss Maintenance on Dynamic Graphs	2023	SIGMOD	4.6014683e-05
9,135	Sage: A System for Uncertain Network Analysis	2022	VLDB	4.3846727e-05
11,676	Finding Theme Communities from Database Networks	2019	VLDB	4.1905499e-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
106	Truss Decomposition in Massive Networks	2012	VLDB	0.00048373761
284	Querying K-Truss Community in Large and Dynamic Graphs	2014	SIGMOD	0.00029014359
648	Efficient Subgraph Matching on Billion Node Graphs	2012	VLDB	0.00018688754
682	Finding Maximal Cliques in Massive Networks by H*-graph	2010	SIGMOD	0.0001816451
734	Large Scale Cohesive Subgraphs Discovery for Social Network Visual Analysis	2013	VLDB	0.00017419528
1,159	k-Nearest Neighbors in Uncertain Graphs	2010	VLDB	0.00013584223
1,448	Distance-Constraint Reachability Computation in Uncertain Graphs	2011	VLDB	0.00011928845

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
8,171	Efficient Triangle-Connected Truss Community Search In Dynamic Graphs	2023	VLDB	4.5655127e-05
6,729	Maximal D-truss Search in Dynamic Directed Graphs	2023	VLDB	4.943658e-05
284	Querying K-Truss Community in Large and Dynamic Graphs	2014	SIGMOD	0.00029014359
1,529	Truss-based Community Search: a Truss-equivalence Based Indexing Approach	2017	VLDB	0.00011484853
2,852	Unboundedness and Efficiency of Truss Maintenance in Evolving Graphs	2019	SIGMOD	8.0158741e-05
2,043	Local Algorithms for Hierarchical Dense Subgraph Discovery	2019	VLDB	9.6970812e-05
3,976	Accelerating Truss Decomposition on Heterogeneous Processors	2020	VLDB	6.5694893e-05
1,641	Truss-based Community Search over Large Directed Graphs	2020	SIGMOD	0.00011044805
10,604	Truss Decomposition in Hypergraphs	2025	VLDB	4.1905499e-05
106	Truss Decomposition in Massive Networks	2012	VLDB	0.00048373761