Wednesday Oct 04, 12pm1pm, 1116E Klaus
Finding a kTruss: Fast and Scalable Subgraph Isomorphism using Dynamic Graph TechniquesJames Fox
Advisor: Prof. David Bader


ABSTRACT
Finding wellconnected subgraphs is a common graph analysis goal. However, wellknown formulations such as the kClique are computationally intractable and often too restrictive. The kTruss of a graph is defined in terms of minimal triangle counts, and is computationally tractable. We present a novel algorithm and scalable implementation for finding the kTruss of a graph, by combining dynamic graph data structure with dynamic triangle counting techniques. Our approach won an Innovation Award for the DARPAHIVE GraphChallenge, and performs anywhere from 100x to 10000x faster than GraphChallenge baseline benchmarks.
BIO
James Fox is a 2nd year Ph.D. student in CS, advised by Dr. David Bader. He earned his bachelorâ€™s degree in CS at UC Berkeley. His research interests are currently in applying HPC towards largescale graph analytics.