Application of Fractal Theory on Motifs Counting in Biological Networks

作者：Joveini Mahdi Barat Zadeh; Sadri Javad^*

来源：IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2018, 15(2): 613-623.

DOI：10.1109/TCBB.2016.2636215

• Fractal theory
• motif counting
• complex networks
• biological networks
• bioinformatics

Motifs in complex biological, technological, and social networks, or in other types of networks are connected to patterns that occur at significantly higher frequency compared to similar random networks. Finding motifs helps scientists to know more about networks' structure and function, and this goal cannot be achieved without efficient algorithms. Existing methods for counting network motifs are extremely costly in CPU time and memory consumption. In addition, they restrict to the larger motifs. In this paper, a new algorithm called FraMo is presented based on 'fractal theory'. This method consists of three phases: at first, a complex network is converted to a multifractal network. Then, using maximum likelihood estimation, distribution parameters is estimated for the multifractal network, and at last the approximate number of network motifs is calculated. Experimental results on several benchmark datasets show that our algorithm can efficiently approximate the number of motifs in any size in undirected networks and compare its performance favorably with similar existing algorithms in terms of CPU time and memory usage.

• 出版日期2018-4