Exact and Parallel Triangle Counting in Dynamic Graphs

Devavret Makkar, David A. Bader, Oded Green

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

12 Scopus citations

Abstract

Triangle counting is an important building block for finding key players in a graph. It is an integral part of the popular clustering coefficient analytic and can be used for pattern matching in social networks. A triangle, which is also a 3-clique, represents a strong connection between three players that are all connected. While counting triangles is not overly expensive from a computational standpoint, especially in comparison to centrality metrics (such as betweenness centrality and closeness centrality), it can still prove to be prohibitive for large scale networks, especially for those with a power-law distribution. This problem only deepens for dynamic graphs where the network is constantly changing, requiring constant updating of the graph and the analytic. In this paper, we present a new dynamic graph algorithm for counting triangles that is based on an inclusion-exclusion formulation. While our algorithm is independent of the computing platform, we show performance results on an NVIDIA GPU. Our approach handles 32 million updates per second, or up to 11 million updates per second if the graph data structure is also updated. In past approaches, when a vertex was affected due to an edge insertion or deletion, it was necessary to find the triangles from scratch for that given vertex. Our new formulation does not need this and only requires considering the affected edges. As such our algorithm is typically several hundred times faster than the past approach - in some cases up to 819X faster.

Original languageEnglish (US)
Title of host publicationProceedings - 24th IEEE International Conference on High Performance Computing, HiPC 2017
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages2-12
Number of pages11
ISBN (Electronic)9781538622933
DOIs
StatePublished - Jul 2 2017
Externally publishedYes
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

Conference

Conference24th 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

Keywords

  • Dynamic data
  • Scalable analytics

Fingerprint

Dive into the research topics of 'Exact and Parallel Triangle Counting in Dynamic Graphs'. Together they form a unique fingerprint.

Cite this