Motif Discovery Algorithms in Static and Temporal Networks: A Survey
Motif Discovery Algorithms in Static and Temporal Networks: A Survey
复制标题
DOI：
10.1093/comnet/cnaa031
复制
发表时间：
2020-05
期刊：
影响因子：
--
通讯作者：
A. Jazayeri;Christopher C. Yang
中科院分区：
文献类型：
--
作者：
A. Jazayeri;Christopher C. Yang
基序是复杂系统的基本组成部分。代表复杂系统的网络的拓扑结构以及这些网络中主题的频率和分布是交织在一起的。作为频繁子图挖掘的核心，与图和子图同构问题相关的复杂性直接影响模体发现算法的性能。研究人员采用了不同的候选生成、枚举和频率计算策略来应对这些复杂性。此外，在过去的几年里，人们对时态网络的分析和挖掘越来越感兴趣。与静态网络相比，这些网络随着时间的推移以插入、删除或替换边或顶点或其属性的形式发生变化。在本文中，我们对文献中提出的用于挖掘静态和时间网络的主题发现算法进行了调查，并根据其采用的候选生成和频率计算策略回顾了相应的算法。当我们见证社交媒体平台、生物信息学应用、通信和运输网络中大量网络数据的产生以及分布式计算和大数据技术的进步时，我们还对为解决挖掘静态和时间网络中的CPU限制和I/O限制问题而提出的算法进行了调查。
Motifs are the fundamental components of complex systems. The topological structure of networks representing complex systems and the frequency and distribution of motifs in these networks are intertwined. The complexities associated with graph and subgraph isomorphism problems, as the core of frequent subgraph mining, directly impact the performance of motif discovery algorithms. Researchers have adopted different strategies for candidate generation and enumeration and frequency computation to cope with these complexities. Besides, in the past few years, there has been an increasing interest in the analysis and mining of temporal networks. In contrast to their static counterparts, these networks change over time in the form of insertion, deletion or substitution of edges or vertices or their attributes. In this article, we provide a survey of motif discovery algorithms proposed in the literature for mining static and temporal networks and review the corresponding algorithms based on their adopted strategies for candidate generation and frequency computation. As we witness the generation of a large amount of network data in social media platforms, bioinformatics applications and communication and transportation networks and the advance in distributed computing and big data technology, we also conduct a survey on the algorithms proposed to resolve the CPU-bound and I/O bound problems in mining static and temporal networks.