DocumentCode :
1783247
Title :
Complex Network Analysis Using Parallel Approximate Motif Counting
Author :
Slota, George M. ; Madduri, Kamesh
Author_Institution :
Dept. of Comput. Sci. & Eng., Pennsylvania State Univ., University Park, PA, USA
fYear :
2014
fDate :
19-23 May 2014
Firstpage :
405
Lastpage :
414
Abstract :
Subgraph counting forms the basis of many complex network analysis metrics, including motif and anti-motif finding, relative graph let frequency distance, and graph let degree distribution agreements. Determining exact subgraph counts is computationally very expensive. In recent work, we present FASCIA, a shared-memory parallel algorithm and implementation for approximate subgraph counting. FASCIA uses a dynamic programming-based approach and is significantly faster than exhaustive enumeration, while generating high-quality approximations of subgraph counts. However, the memory usage of the dynamic programming step prohibits us from applying FASCIA to very large graphs. In this paper, we introduce a distributed-memory parallelization of FASCIA by partitioning the graph and the dynamic programming table. We discuss a new collective communication scheme to make the dynamic programming step memory-efficient. These optimizations enable scaling to much larger networks than before. We also present a simple parallelization strategy for distributed subgraph counting on smaller networks. The new additions let us use subgraph counts as graph signatures for a large network collection, and we analyze this collection using various subgraph count-based graph analytics.
Keywords :
complex networks; distributed memory systems; dynamic programming; graph theory; mathematics computing; network theory (graphs); parallel algorithms; FASCIA; anti-motif finding; approximate subgraph counting; collective communication scheme; complex network analysis metrics; distributed subgraph counting; distributed-memory parallelization strategy; dynamic programming table; exact subgraph count determination; graph let degree distribution agreements; graph partitioning; graph signatures; large network collection; parallel approximate motif counting; relative graph let frequency distance; shared-memory parallel algorithm; subgraph count-based graph analytics; Approximation methods; Color; Dynamic programming; Fascia; Heuristic algorithms; Image color analysis; Peer-to-peer computing; color-coding; network analysis; network motifs; subgraph counting;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Parallel and Distributed Processing Symposium, 2014 IEEE 28th International
Conference_Location :
Phoenix, AZ
ISSN :
1530-2075
Print_ISBN :
978-1-4799-3799-8
Type :
conf
DOI :
10.1109/IPDPS.2014.50
Filename :
6877274
Link To Document :
بازگشت