SC is the International Conference for
 High Performnance Computing, Networking, Storage and Analysis

SCHEDULE: NOV 13-19, 2010

Parallel Color Coding and Graph Partitioning Enabling Subgraph Counting for Massive Graphs

SESSION: Research Poster Reception


TIME: 5:15PM - 7:00PM

AUTHOR(S):Zhao Zhao, Maleq Khan, Anil Vullikanti, Madhav Marathe

ROOM:Main Lobby

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.

Chair/Author Details:

Zhao Zhao - Virginia Tech

Maleq Khan - Virginia Tech

Anil Vullikanti - Virginia Tech

Madhav Marathe - Virginia Tech

Add to iCal  Click here to download .ics calendar file

Add to Outlook  Click here to download .vcs calendar file

Add to Google Calendarss  Click here to add event to your Google Calendar

   Sponsors    IEEE    ACM