Parallel Color Coding and Graph Partitioning Enabling Subgraph Counting for Massive Graphs
SESSION: Research Poster Reception
EVENT TYPE: Poster
TIME: 5:15PM - 7:00PM
AUTHOR(S):Zhao Zhao, Maleq Khan, Anil Vullikanti, Madhav Marathe
ABSTRACT: Counting the number of template embeddings in large network has been found to be useful in a number of applications, such as biological and social networks. However, due to large computational cost, template counting remains a challenging problem, and all prior results have considered networks
with a few thousand nodes.
We develop a parallel subgraph counting algorithm, ParSE, that scales to networks with millions of nodes. Our algorithm is a randomized approximation scheme, that estimates the subgraph frequency to any desired level of accuracy, and allows enumeration of a class of motifs that extends the tree-like templates which is considered in prior work. Our approach is based on parallelization of so called color coding technique, combined with a stream based graph partitioning.
The detailed algorithm, implementation issues, as well as experiment results will be presented in the poster session.