Behavioral clusters in dynamic graphs

James P. Fairbanks, Ramakrishnan Kannan, Haesun Park, David A. Bader

Research output: Contribution to journalArticlepeer-review

11 Scopus citations

Abstract

Abstract This paper contributes a method for combining sparse parallel graph algorithms with dense parallel linear algebra algorithms in order to understand dynamic graphs including the temporal behavior of vertices. Our method is the first to cluster vertices in a dynamic graph based on arbitrary temporal behaviors. In order to successfully implement this method, we develop a feature based pipeline for dynamic graphs and apply Nonnegative Matrix Factorization (NMF) to these features. We demonstrate these steps with a sample of the Twitter mentions graph as well as a CAIDA network traffic graph. We contribute and analyze a parallel NMF algorithm presenting both theoretical and empirical studies of performance. This work can be leveraged by graph/network analysts to understand the temporal behavior cluster structure and segmentation structure of dynamic graphs.

Original languageEnglish (US)
Article number2240
Pages (from-to)38-50
Number of pages13
JournalParallel Computing
Volume47
DOIs
StatePublished - Aug 4 2015
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computer Networks and Communications
  • Computer Graphics and Computer-Aided Design
  • Artificial Intelligence

Keywords

  • Behavioral clusters
  • Dynamic graph analysis
  • Low rank approximation
  • Matrix factorization
  • Nonnegative Matrix Factorization (NMF)
  • Streaming

Fingerprint

Dive into the research topics of 'Behavioral clusters in dynamic graphs'. Together they form a unique fingerprint.

Cite this