Bottlenecks, burstiness and fat tails regulate mixing times of diffusion over temporal networks

30 January 2014
Many real-life complex systems arise as a network of simple interconnected individual agents. A central question is to determine how network topology and individual agent dynamics combine to create the global dynamics. In this talk we focus on the case of continuous-time random walks on networks, with a waiting time of the walker on each node assuming arbitrary probability distributions. Such random walks are useful to model diffusion processes over complex temporal networks representing human interactions, often characterized by non-Poissonian contact patterns. We find that the mixing time of the random walker, i.e. the relaxation time for the process to reach stationarity, is determined by a combination of three factors: the spectral gap, associated to bottlenecks in the underlying topology, burstiness, related to the second moment of the waiting time distribution, and the characteristic time of its exponential tail, which is an indicator of the tail `fatness'. We show theoretically that a strong modular structure dampens the importance of burstiness, and empirically that either of the three factors may be dominant in real-life data. These results are available in arXiv:1309.4155
  • Industrial and Applied Mathematics Seminar