Parallelization of network motif discovery using star contraction
Articles > Article · 2021
Authors: Esra Ruzgar Ateskan, Kayhan Erciyes, Mehmet Emin DALKILIÇ
PARALLEL COMPUTING, Journal Indexed in SCI Expanded, International, 2021, vol 101, pp 102734-102734
DOI: 10.1016/j.parco.2020.102734
Summary
Network motifs are widely used to uncover structural design principles of complex networks. Current sequential network motif discovery algorithms become inefficient as motif size grows, thus parallelization methods have been proposed in the literature. In this study, we use star contraction algorithm to partition complex networks efficiently for parallel discovery of network motifs. We propose two new heuristics to make star contraction more suitable for partitioning of complex networks. The effectiveness of our partitioning strategies is verified using the ESU algorithm for subgraph counting. We also propose a ghost vertices detection algorithm to ensure that all the motifs located in multiple parts are exactly found. We implement our method using MPI libraries and tested on real-life complex networks of different domains. We compared speedups of star contraction algorithm with speedups of other graph partitioning algorithms. Our algorithm obtained better speedups than those of other partitioning algorithms for most cases. Our algorithm provides significant speedups when compared to sequential ESU algorithm allowing discovery of larger network motifs.