IEEE/ACM Trans Comput Biol Bioinform. 2018 Mar-Apr;15(2):613-623. doi: 10.1109/TCBB.2016.2636215. Epub 2016 Dec 6.
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.
复杂的生物、技术和社交网络中的模式，或者其他类型的网络中的模式，与相似的随机网络相比，出现的频率更高。发现模式可以帮助科学家更好地了解网络的结构和功能，如果没有有效的算法，这一目标是无法实现的。现有的网络模式计数方法在 CPU 时间和内存消耗方面非常昂贵。此外，它们还限制了更大的模式。在本文中，提出了一种新的算法，称为 FraMo，它基于“分形理论”。该方法包括三个阶段：首先，将复杂网络转换为多重分形网络。然后，使用最大似然估计，对多重分形网络的分布参数进行估计，最后计算网络模式的近似数量。在几个基准数据集上的实验结果表明，我们的算法可以有效地估计无向网络中任何大小的模式数量，并在 CPU 时间和内存使用方面与类似的现有算法相比具有更好的性能。
