Network Change Detection Based on Random Walk in Latent Space

Chuan hao Lin, Linchuan Xu, Kenji Yamanishi

Research output: Journal article publicationJournal articleAcademic researchpeer-review

1 Citation (Scopus)


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.

Original languageEnglish
Pages (from-to)1-12
JournalIEEE Transactions on Knowledge and Data Engineering
Publication statusAccepted/In press - 2022


  • Data models
  • Encoding
  • Image edge detection
  • latent space model
  • Matrix decomposition
  • minimum description length
  • Network change detection
  • network embedding
  • Particle measurements
  • Probabilistic logic
  • random walk
  • Tensors

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics


Dive into the research topics of 'Network Change Detection Based on Random Walk in Latent Space'. Together they form a unique fingerprint.

Cite this