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: 5104
Venue: SIGMOD
Year: 2016
Pagerank: 8.3136866e-05
Overall Rank: 2,684 | 81.33%
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,530	Truss-based Community Search: a Truss-equivalence Based Indexing Approach	2017	VLDB	0.00011495611
2,512	Fast Hierarchy Construction for Dense Subgraphs	2017	VLDB	8.6196023e-05
2,909	Efficient Algorithms for Densest Subgraph Discovery	2019	VLDB	7.9305767e-05
3,636	Efficient and Effective Algorithms for Clustering Uncertain Graphs	2019	VLDB	6.8976555e-05
4,171	Butterfly Counting on Uncertain Bipartite Graphs	2022	VLDB	6.3879236e-05
4,394	When Engagement Meets Similarity: Efficient (k,r)-Core Computation on Social Networks	2017	VLDB	6.224902e-05
4,459	Efficient Bi-triangle Counting for Large Bipartite Networks	2021	VLDB	6.1651553e-05
5,908	Fast Maximal Clique Enumeration on Uncertain Graphs: A Pivot-based Approach	2022	SIGMOD	5.2773278e-05
6,141	Local Algorithms for Distance-generalized Core Decomposition over Large Dynamic Graphs	2021	VLDB	5.1903263e-05
6,513	Efficient Parallel D-core Decomposition at Scale	2024	VLDB	5.0321577e-05
7,451	Scalable Approximate Butterfly and Bi-triangle Counting for Large Bipartite Networks	2023	SIGMOD	4.7263711e-05
8,014	Efficient Star-based Truss Maintenance on Dynamic Graphs	2023	SIGMOD	4.6058845e-05
9,135	Sage: A System for Uncertain Network Analysis	2022	VLDB	4.3888791e-05
11,671	Finding Theme Communities from Database Networks	2019	VLDB	4.1945683e-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
108	Truss Decomposition in Massive Networks	2012	VLDB	0.00048300163
283	Querying K-Truss Community in Large and Dynamic Graphs	2014	SIGMOD	0.00029041257
651	Efficient Subgraph Matching on Billion Node Graphs	2012	VLDB	0.00018648572
686	Finding Maximal Cliques in Massive Networks by H*-graph	2010	SIGMOD	0.00018178029
738	Large Scale Cohesive Subgraphs Discovery for Social Network Visual Analysis	2013	VLDB	0.00017435236
1,162	k-Nearest Neighbors in Uncertain Graphs	2010	VLDB	0.0001358105
1,450	Distance-Constraint Reachability Computation in Uncertain Graphs	2011	VLDB	0.00011925844

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
8,169	Efficient Triangle-Connected Truss Community Search In Dynamic Graphs	2023	VLDB	4.5698941e-05
6,725	Maximal D-truss Search in Dynamic Directed Graphs	2023	VLDB	4.9484066e-05
283	Querying K-Truss Community in Large and Dynamic Graphs	2014	SIGMOD	0.00029041257
1,530	Truss-based Community Search: a Truss-equivalence Based Indexing Approach	2017	VLDB	0.00011495611
2,846	Unboundedness and Efficiency of Truss Maintenance in Evolving Graphs	2019	SIGMOD	8.0234377e-05
2,039	Local Algorithms for Hierarchical Dense Subgraph Discovery	2019	VLDB	9.7061003e-05
3,975	Accelerating Truss Decomposition on Heterogeneous Processors	2020	VLDB	6.5736847e-05
1,637	Truss-based Community Search over Large Directed Graphs	2020	SIGMOD	0.0001105259
10,596	Truss Decomposition in Hypergraphs	2025	VLDB	4.1945683e-05
108	Truss Decomposition in Massive Networks	2012	VLDB	0.00048300163