Parallel network motif discovery in complex networks

In this thesis, we first provide a literature survey of network motifs, existing sequential and parallel network motif discovery algorithms. We present new parallel motif discovery algorithms using network and tree parallelization approaches. For network parallelization, we propose two network parallelization algorithms based on Breadth First Search and Star Contraction. We develop two new heuristics to make star contraction suitable for partitioning of complex networks. We present Ghost Vertex Detection algorithms to ensure that the motifs located in multiple partitions are exactly found. Moreover, for tree parallelization, we propose a new algorithm and improve its speedup and memory usage using a novel relabelling scheme for vertex identifiers. In order to increase speedups of our network parallelization algorithms, we need to distribute the workload fairly among the processors. We attain this goal by using three dynamic load balancing algorithms: centralized masterslave, random polling distributed and ring distributed. For all parallelization methods, we use the ESU algorithm to count subgraphs and Nauty to group motif candidates into isomorphic classes. We implement a random network generation algorithm based on Markov-chain method. We calculate z-scores of isomorphic classes to obtain network motifs. We provide comparison of parallel algorithms in terms of speedup, parallelization overhead, running time, memory usage and scalability. Experiments on complex networks of different types demonstrate that the proposed algorithms provide significant speedups when compared to sequential ESU algorithm allowing discovery of larger motifs.