Finding a k-Truss: Fast and Scalable Subgraph Isomorphism using Dynamic Graph Techniques

Finding well-connected subgraphs is a common graph analysis goal. However, well-known formulations such as the k-Clique are computationally intractable and often too restrictive. The k-Truss 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 k-Truss of a graph, by combining dynamic graph data structure with dynamic triangle counting techniques. Our approach won an Innovation Award for the DARPA-HIVE GraphChallenge, and performs anywhere from 100x to 10000x faster than GraphChallenge baseline benchmarks.