Efficient probabilistic truss indexing on uncertain graphs

Zitan Sun, Xin Huang*, Jianliang Xu, Francesco Bonchi

*Corresponding author for this work

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

7 Citations (Scopus)


Networks in many real-world applications come with an inherent uncertainty in their structure, due to e.g., noisy measurements, inference and prediction models, or for privacy purposes. Modeling and analyzing uncertain graphs has attracted a great deal of attention. Among the various graph analytic tasks studied, the extraction of dense substructures, such as cores or trusses, has a central role. In this paper, we study the problem of (k, 3)-truss indexing and querying over an uncertain graph . A (k, 3)-truss is the largest subgraph of , such that the probability of each edge being contained in at least k - 2 triangles is no less than 3. Our first proposal, CPT-index, keeps all the (k, 3)-trusses: retrieval for any given k and ?can be executed in an optimal linear time w.r.t. the graph size of the queried (k, 3)-truss. We develop a bottom-up CPT-indexconstruction scheme and an improved algorithm for fast CPT-indexconstruction using top-down graph partitions. For trading off between (k, 3)-truss offline indexing and online querying, we further develop an approximate indexing approach ( µ, "r)-APXequipped with two parameters, µ and "r, that govern tolerated errors. Extensive experiments using large-scale uncertain graphs with 261 million edges validate the efficiency of our proposed indexing and querying algorithms against state-of-the-art methods.

Original languageEnglish
Title of host publicationWWW '21: Proceedings of the Web Conference 2021
EditorsJure Leskovec, Marko Grobelnik
PublisherAssociation for Computing Machinery (ACM)
Number of pages13
ISBN (Electronic)9781450383127
Publication statusPublished - 19 Apr 2021
Event2021 World Wide Web Conference, WWW 2021 - Ljubljana, Slovenia
Duration: 19 Apr 202123 Apr 2021


Conference2021 World Wide Web Conference, WWW 2021
Internet address

Scopus Subject Areas

  • Computer Networks and Communications
  • Software

User-Defined Keywords

  • Indexing
  • Probabilistic k-truss
  • Query
  • Uncertain graph


Dive into the research topics of 'Efficient probabilistic truss indexing on uncertain graphs'. Together they form a unique fingerprint.

Cite this