Abstract: Complex network similarity metrics play a vital role in network analysis applications such as anomaly detection and state division. In recent years, the similarity of static networks has been widely concerned by scholars. However, in actual scenarios, the structure of networks tends to evolve over time, and the scale of networks will gradually increase. How to quickly and accurately evaluate the similarity of dynamic networks is the main difficulty of this research. Although the spectral distance method based on static network has achieved good results, the computational cost is very high for large-scale dynamic networks. In order to solve this problem, a method for quickly calculating the similarity of dynamic networks is proposed. The method estimates the variation of dynamic network eigenvalues based on matrix perturbation theory to calculate the similarity of the network, which has linear complexity. Experiments on artificial data sets and real data sets show that the proposed method effectively reduces the computational complexity on the basis of ensuring accuracy.

Key words: dynamic network, network structure similarity, feature decomposition, matrix perturbation

摘要： 复杂网络相似性度量在异常检测、状态划分等网络分析应用中起着至关重要的作用。近年来，静态网络相似性受到学者的广泛关注，但在实际场景中，网络结构往往会随着时间的推移不断演化，网络规模也会逐渐增大，如何快速且准确地评估动态网络之间的相似性面临巨大的挑战。基于静态网络的谱距离方法尽管取得了不错的效果，但对于大规模动态网络而言计算成本很高。为了解决这一问题，提出了一种快速计算动  态网络相似性的方法。该方法基于矩阵扰动理论估算动态网络特征值的变化进而计算网络的相似性，具有线性复杂度。在人工数据集与真实数据集上的实验表明，提出的方法在保证准确率的基础上有效降低了计算复杂度。

关键词: 动态网络, 网络结构相似性, 特征分解, 矩阵扰动