Time: Thursday, 26/June/2025: 3:40pm - 5:20pm Session Chair: Martin Everett |
Location: Room 112 16 |
Graph inference from the contacts of random walkers
TU Delft, Netherlands, The
The relationship between the dynamics of a process and the underlying network topology is crucial to understand complex systems. On one hand, there is significant interest in understanding how the structure of the network impacts the dynamics of processes. On the other hand, there is also interest in the inverse problem: given the dynamics of a particular process, to what extent can the underlying network structure be inferred? This problem is crucial in various fields, including biology, recommendation systems, and communication networks, where the initial structure of the network is unknown while understanding the underlying graph structure can provide valuable insights and predictions.
In this talk, we infer the initial topology of the graph G from the contact data of random walkers. More precisely, we consider M independent random walkers that traverse an unknown underlying graph G with N nodes and L links with respect to the NxN probability transition matrix P. The nodes in the graph G represent different physical locations (e.g. workplaces, homes, hospitals, schools or public transport stations) and links are physical paths between locations. What can we infer about the graph G only from the interactions of random walkers? Although it is tempting to conclude that network reconstruction is impossible from the K-length random contact sequence, which represents only one possible realization of the Markov process, we show the opposite. We demonstrate that if the NxN probability transition matrix P of the random walkers admits a steady-state distribution (the process is ergodic) and the K-length contacts sequence is sufficiently long, we can infer
- the number of nodes N in the underlying graph G,
- the number of links L in the underlying graph G,
- the Markov chain with matrix P and the reversed Markov chain with matrix P',
- the underlying topology of graph G.
We would like to point out that the formulation of the network reconstruction problem is motivated by the analysis of empirical datasets that provide contact information between people but lack details about the underlying graph topology and the location of contacts. We also believe that the obtained results represent a significant step forward in gaining a deeper understanding of network evolutionary processes.