Complex Network Analysis Using Parallel Approximate Motif Counting

Citations Over TimeTop 15% of 2014 papers

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.

Related Papers

• → A new algorithm for the detection of seismic quiescence: introduction of the RTM algorithm, a modified RTL algorithm(2011)29 cited
• → An improved filtering algorithm based on median filtering algorithm and medium filtering algorithm(2012)6 cited
• → Remarks on Algorithm 2, Algorithm 3, Algorithm 15, Algorithm 25 and Algorithm 26(1961)2 cited
• → Medical image registration algorithm based on Powell algorithm and improved genetic algorithm(2013)1 cited
• → Remarks on Algorithm 332: Jacobi polynomials: Algorithm 344: student's t -distribution: Algorithm 351: modified Romberg quadrature: Algorithm 359: factoral analysis of variance(1970)