Node proximity preserved dynamic network embedding via matrix perturbation

摘要

In recent years, network embedding has attracted extensive interests, which aims at representing nodes of an original network in a low-dimensional vector space while preserving the inherent topological structures of the network. Despite the remarkable advantages of complex networks, most existing network embedding methods are mainly focused on static networks while ignoring the evolving characteristic, which is proved to be an essential property of real-world networks. In this paper, we propose Node Proximity Preserved Dynamic Network Embedding via Matrix Perturbation (NPDNE) to tackle the dilemma. Specifically, our method implements a low-rank transformation on the normalized Laplacian matrix of the given networks and then derives the embedding vectors through generalized SVD. Subsequently, the node proximities are preserved in the embedding vectors by exploiting the eigen-decomposition reweighing theorem, which reveals the intrinsic relationship among different-order proximities. Moreover, a generalized eigen perturbation is adopted to update the embedding vectors so that the evolution of given networks can be captured over time. Finally, we conduct experiments of multi-label classification, link prediction, and visualization on several real-world datasets. The experimental results demonstrate the superiority of the proposed NPDNE model compared with state-of-the-art baselines.