Authors: Saeed Shahrivari Saeed Jalili
Publish Date: 2015/02/26
Volume: 97, Issue: 11, Pages: 1101-1120
Abstract
Discovery of frequent subgraphs of a network is a challenging and timeconsuming process Several heuristics and improvements have been proposed before However when the size of subgraphs or the size of network is big the process cannot be done in feasible time on a single machine One of the promising solutions is using the processing power of available parallel and distributed systems In this paper we present a distributed solution for discovery of frequent subgraphs of a network using the MapReduce framework The solution is named MRSUB and is developed to run over the Hadoop framework MRSUB uses a novel and loadbalanced parallel subgraph enumeration algorithm and fits it into the MapReduce framework Also a fast subgraph isomorphism detection heuristic is used which accelerates the whole process further We executed MRSUB on a private cloud infrastructure with 40 machines and performed several experiments with different networks Experimental results show that MRSUB scales well and offers an effective solution for discovery of frequent subgraphs of networks which are not possible on a single machine in feasible time
Keywords: