Subgraph Enumeration in Large Social Contact Networks Using Parallel Color Coding and Streaming
Authors:
- Zhao ZhaoZZZhao Zhao
- Maleq KhanMKMaleq Khan
- V. S. Anil KumarVKV. S. Anil Kumar
- Madhav V. MaratheMMMadhav V. Marathe
- 1 September 2010
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 01903918,p. 594-603
Abstract
Identifying motifs (or commonly occurring subgraphs/templates) has been found to be useful in a number of applications, such as biological and social networks; they have been used to identify building blocks and functional properties, as well as to characterize the underlying networks. Enumerating subgraphs is a challenging computational problem, and all prior results have considered networks with a few thousand nodes. In this paper, we develop a parallel subgraph enumeration 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 those considered in prior work. Our approach is based on parallelization of an approach called color coding, combined with a stream based partitioning. We also show that ParSE scales well with the number of processors, over a large range.Keywords
This publication has 13 references indexed in Scilit:
- Counting Stars and Other Small Subgraphs in Sublinear Time2010
- Generation and analysis of large synthetic social contact networks2009
- A scalable, parallel algorithm for maximal clique enumerationJournal of Parallel and Distributed Computing, 2009
- Approximating the Number of Network Motifs2009
- A Parallel Algorithm for Extracting Transcription Regulatory Network Motifs2006
- Patterns of Influence in a Recommendation Network2006
- Finding Frequent Patterns in a Large Sparse Graph*Data Mining and Knowledge Discovery, 2005
- A (sub)graph isomorphism algorithm for matching large graphsIEEE Transactions on Pattern Analysis and Machine Intelligence, 2004
- Network Motifs: Simple Building Blocks of Complex NetworksScience, 2002
- Algorithm 457: finding all cliques of an undirected graphCommunications of the ACM, 1973