Using Persistent Homology to Recover Spatial Information From Encounter Traces

In order to better understand human and animal mobility and its potential effects on Mobile Ad-Hoc networks and Delay-Tolerant Networks, many researchers have conducted experiments which collect encounter data. Most analyses of these data have focused on isolated statistical properties such as the distribution of node inter-encounter times and the degree distribution of the connectivity graph. On the other hand, new developments in computational topology, in particular persistent homology, have made it possible to compute topological invariants from noisy data. These homological methods provide a natural way to draw conclusions about global structure based on collections of local information. We use persistent homology techniques to show that in some cases encounter traces can be used to deduce information about the topology of the physical space the experiment was conducted in, and detect certain changes in the space. We also show that one can distinguish between simulated encounter traces generated on a bounded rectangular grid from traces generated on a grid with the opposite edges wrapped (a toroidal grid). Finally, we have found that non-trivial topological features also appear in real experimental encounter traces, and we speculate on types of node behavior that could produce these results. This demonstrates the ability of persistent homology to detect topological features in encounter data that could be difficult to describe using traditional statistical and geometric methods.