Truss decomposition of probabilistic graphs: Semantics and algorithms

Xin Huang, Wei Lu, Laks V.S. Lakshmanan

Research output: Chapter in book/report/conference proceedingConference proceedingpeer-review

87 Citations (Scopus)


A key operation in network analysis is the discovery of cohesive subgraphs. The notion of κ-truss has gained considerable popularity in this regard, based on its rich structure and efficient computability. However, many complex networks such as social, biological and communication networks feature uncertainty, best modeled using probabilities. Unfortunately the problem of discovering κ-trusses in probabilistic graphs has received little attention to date. In this paper, given a probabilistic graph G, number κ and parameter γ ∈ (0, 1], we define a (κ, γ)-truss as a maximal connected subgraph H ⊆ G, in which for each edge, the probability that it is contained in at least (κ - 2) triangles is at least γ. We develop an efficient dynamic programming algorithm for decomposing a probabilistic graph into such maximal (κ, γ)-trusses. The above definition is local in that the "witness" graphs that has the (κ - 2) triangles containing an edge in H may be quite different for distinct edges. Hence, we also propose global (κ, γ)-truss, which in addition to being a local (κ, γ)-truss, has to satisfy the condition that the probability that H contains a κ-truss is at least γ. We show that unlike local (κ, γ)-trusses, the global (κ, γ)-truss decomposition on a probabilistic graph is intractable. We propose a novel sampling technique which enables approximate discovery of global (κ, γ)-trusses with high probability. Our extensive experiments on real datasets demonstrate the efficacy of our proposed approach and the usefulness of local and global (κ, γ)-truss.

Original languageEnglish
Title of host publicationSIGMOD '16: Proceedings of the 2016 International Conference on Management of Data
PublisherAssociation for Computing Machinery (ACM)
Number of pages14
ISBN (Print)9781450335317
Publication statusPublished - 26 Jun 2016
EventACM SIGMOD International Conference on Management of Data, SIGMOD 2016 - San Francisco, United States
Duration: 26 Jun 20161 Jul 2016

Publication series

NameProceedings of the ACM SIGMOD International Conference on Management of Data
ISSN (Print)0730-8078


ConferenceACM SIGMOD International Conference on Management of Data, SIGMOD 2016
Country/TerritoryUnited States
CitySan Francisco
Internet address

Scopus Subject Areas

  • Software
  • Information Systems


Dive into the research topics of 'Truss decomposition of probabilistic graphs: Semantics and algorithms'. Together they form a unique fingerprint.

Cite this