Behavioral clusters in dynamic graphs

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

doi:10.1016/j.parco.2015.03.002

Behavioral clusters in dynamic graphs

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

Research output: Contribution to journal › Article › peer-review

12 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 language	English
Article number	2240
Pages (from-to)	38-50
Number of pages	13
Journal	Parallel Computing
Volume	47
DOIs	https://doi.org/10.1016/j.parco.2015.03.002
State	Published - Aug 4 2015
Externally published	Yes

Funding

This work was partially supported by the American Society for Engineering Education (ASEE) National Defense Science and Engineering Graduate (NDSEG) Fellowship as well as the National Science Foundation (NSF) Grants IIS-1348152 and ACI-1338745 . This work was also partially supported by the Defense Advanced Research Projects Agency (DARPA) XDATA program Grant FA8750–12-2–0309 . Any opinions, findings and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the ASEE, NSF or DARPA.

Funders	Funder number
National Science Foundation	1339745, IIS-1348152, ACI-1338745
Defense Advanced Research Projects Agency	FA8750–12-2–0309
American Society for Engineering Education
National Defense Science and Engineering Graduate

Keywords

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

Access to Document

10.1016/j.parco.2015.03.002

Cite this

@article{edd7b5bc2d3e4ab382085ea78d20e792,

title = "Behavioral clusters in dynamic graphs",

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.",

keywords = "Behavioral clusters, Dynamic graph analysis, Low rank approximation, Matrix factorization, Nonnegative Matrix Factorization (NMF), Streaming",

author = "Fairbanks, {James P.} and Ramakrishnan Kannan and Haesun Park and Bader, {David A.}",

note = "Publisher Copyright: {\textcopyright} 2015 Elsevier B.V.",

year = "2015",

month = aug,

day = "4",

doi = "10.1016/j.parco.2015.03.002",

language = "English",

volume = "47",

pages = "38--50",

journal = "Parallel Computing",

issn = "0167-8191",

publisher = "Elsevier",

}

TY - JOUR

T1 - Behavioral clusters in dynamic graphs

AU - Fairbanks, James P.

AU - Kannan, Ramakrishnan

AU - Park, Haesun

AU - Bader, David A.

PY - 2015/8/4

Y1 - 2015/8/4

N2 - 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.

AB - 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.

KW - Behavioral clusters

KW - Dynamic graph analysis

KW - Low rank approximation

KW - Matrix factorization

KW - Nonnegative Matrix Factorization (NMF)

KW - Streaming

UR - http://www.scopus.com/inward/record.url?scp=84938422229&partnerID=8YFLogxK

U2 - 10.1016/j.parco.2015.03.002

DO - 10.1016/j.parco.2015.03.002

M3 - Article

AN - SCOPUS:84938422229

SN - 0167-8191

VL - 47

SP - 38

EP - 50

JO - Parallel Computing

JF - Parallel Computing

M1 - 2240

ER -

Behavioral clusters in dynamic graphs

Abstract

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this