Random walks on dynamic graphs

让我们考虑一个简化的通信网络模型。如果两个人之间的距离在1以内，他们就可以交流.图是一种数学对象，可用于对此类网络进行建模。我们把人看作图的顶点，如果他们可以交流，我们用一条长度为1的线段（我们称之为边）连接其中两个。这张图是连通的吗？也就是说，一个谣言能传播到全网吗？如果这个问题的答案是肯定的，那么自然的下一个问题是：网络的连接程度如何？这不是一个很好的问题。解释这一点的一种方法是询问删除该图的边是否会改变连通性。另一种探索图的几何的自然方法是分析随机游走的行为。随机游走模拟了一个在图的顶点上移动的粒子，在每个时间步跳到一个随机的邻居。混合、命中和覆盖时间是揭示底层图的几何和连通性特征的基本量。混合时间表示随机游走达到平衡所需的时间，命中时间是随机游走从一个顶点到达另一个顶点所需的时间，覆盖时间是随机游走访问图中每个顶点所需的时间。图可以用来模拟许多现实世界的情况。然而，大多数网络在本质上不是静态的，而是随着时间而变化的。因此，引入动力学并研究连通性随时间变化的图的性质是很自然的。在这种情况下，研究随机游动的混合、击中和覆盖性质可以深入了解动态图的几何和连通性。许多用于分析静态图上的过程的经典工具不能用于时间非齐次设置。因此，为了研究混合，打击和覆盖性质的步行，我们将需要开发新的工具和技术。

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.