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

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