Random walks on dynamic graphs

点击翻译按钮获取中文摘要

Let us consider a simplified model of a communication network. Two people can communicate if they are within distance 1 from each other. A graph is a mathematical object that can be used to model such a network. We think of the people as the vertices of the graph and we connect two of them by a line segment of length 1 (that we call edge) if they can communicate. Is this graph connected? In other words, can a rumour spread to the whole network? If the answer to this question is yes, then the natural next question is: how well-connected is the network? This is not a well-posed question. One way of interpreting this is by asking whether removing an edge of this graph can change the connectivity property. Another natural way to probe the geometry of the graph is to analyse the behaviour of a random walk. A random walk models a particle moving on the vertices of the graph, at each time step jumping to a random neighbour. Mixing, hitting and cover times are fundamental quantities that reveal features of the underlying graph's geometry and connectivity. The mixing time represents how long it takes the random walk to reach equilibrium, the hitting time is the time it takes for a random walk starting from one vertex to hit another, and the cover time is the amount of time it takes for the random walk to visit every vertex in the graph.Graphs serve to model many real-world situations. However, most networks are not static in nature, but change with time. So it is natural to introduce dynamics and study properties of graphs whose connectivity properties change with time. In this setting studying mixing, hitting and covering properties of a random walk can give insight on the geometry and connectivity properties of the dynamical graph. A lot of the classical tools used to analyse processes on static graphs do not carry over to the time-inhomogeneous setting. So in order to study mixing, hitting and covering properties of the walks we will need to develop new tools and techniques.