Shared-Memory Graph Truss Decomposition

Humayun Kabir, Kamesh Madduri

Research output: Chapter in Book/Report/Conference proceedingConference contribution

21 Scopus citations

Abstract

We present PKT, a new shared-memory parallel algorithm and OpenMP implementation for the truss decomposition of large sparse graphs. A k-truss is a dense subgraph definition that can be considered a relaxation of a clique. Truss decomposition refers to a partitioning of all the edges in the graph based on their k-truss membership. The truss decomposition of a graph has many applications. We show that our new approach PKT consistently outperforms other truss decomposition approaches for a collection of large sparse graphs and on a 24-core shared-memory server. PKT is based on a recently proposed algorithm for k-core decomposition.

Original languageEnglish (US)
Title of host publicationProceedings - 24th IEEE International Conference on High Performance Computing, HiPC 2017
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages13-22
Number of pages10
ISBN (Electronic)9781538622933
DOIs
StatePublished - Jul 2 2017
Event24th IEEE International Conference on High Performance Computing, HiPC 2017 - Jaipur, India
Duration: Dec 18 2017Dec 21 2017

Publication series

NameProceedings - 24th IEEE International Conference on High Performance Computing, HiPC 2017
Volume2017-December

Other

Other24th IEEE International Conference on High Performance Computing, HiPC 2017
Country/TerritoryIndia
CityJaipur
Period12/18/1712/21/17

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications
  • Hardware and Architecture
  • Modeling and Simulation

Fingerprint

Dive into the research topics of 'Shared-Memory Graph Truss Decomposition'. Together they form a unique fingerprint.

Cite this