A Review of Motif Discovery Algorithms as the Main Units of the Complex Networks

Abstract

Today, Motif discovery has evolved into a comprehensive method in social, biological, technological and other types of complex networks in order to better understand their structure and function, providing significant information. As one of the structural characteristics of any network, motifs are small subnets (sub-graphs) within the input network that being observed more frequently than in randomized networks and have been called the building blocks of networks [2]. The main problem with recognition of large networks motifs is the increase exponentially in possible sub-graphs of the networks in terms of the motif size. Various algorithms have been already suggested to solve the problem with great computational complexity, requiring considerable execution time and consumption memory which have practically restrictions on the size of motifs. The present case study tries to show the importance and aims of the motif discovery as well as some strategies to solve the problems. Then, using a simple framework, the available algorithms are classified and their strengths and weaknesses are explored considering the experimental and laboratory data