Network Change Detection Based on Random Walk in Latent Space

The detection of network changes over time is based on identifying deviations of the network structure. The challenge mainly lies in designing a good summary or descriptor of the network structure for facilitating the measure of deviations. In particular, a network may have a huge number of nodes and edges. Moreover, there can exist complicated dependences among edges, e.g., the existence of some edges may be because of others. Therefore, it is non-trivial to measure the contribution of each node and each edge to the deviation of the entire network structure. Existing descriptors are designed to have factors less than the number of nodes and edges. They also model edge dependences, but can only achieve partial modeling. In this paper, we propose a novel type of descriptor. We first obtain node coordinates or positions in a latent space where nodes connected by edges have close positions by network embedding. Node positions are low-dimensional. More importantly, node positions can fully model edge dependences. We then design the descriptor based on random walk on the node positions. We conducted extensive experiments on synthetic datasets and three real-world datasets to demonstrate the effectiveness of our proposed change detection framework with the descriptor.