论文标题
群集确定图表上随机步行的局部波动
Clusters determine local fluctuations of random walks on graphs
论文作者
论文摘要
许多随机系统的演变由图形上的随机步行准确地描述。在这里，我们探讨了随机步行的局部稳态波动与基础图的全局结构之间的密切联系。在固定时间窗口中，通过相应的计数统计数据，通过在固定时间窗口中随机行走边缘的遍历数量来量化波动。如果一个边缘的两个末端顶点属于光谱群集定义的不同簇，则计数统计的方差均值比率通常会降低。特别是，我们将波动与代数连接性和图形的Fiedler向量联系起来。在这些结果的基础上，我们建议基于随机步行的波动的中心分数。我们的发现表明，除了特定的过渡速率外，在离散状态空间上连续时间马尔可夫过程的局部波动很大程度上取决于基础图的全球拓扑。
The evolution of many stochastic systems is accurately described by random walks on graphs. We here explore the close connection between local steady-state fluctuations of random walks and the global structure of the underlying graph. Fluctuations are quantified by the number of traversals of the random walk across edges during a fixed time window, more precisely, by the corresponding counting statistics. The variance-to-mean ratio of the counting statistics is typically lowered if two end vertices of an edge belong to different clusters as defined by spectral clustering. In particular, we relate the fluctuations to the algebraic connectivity and the Fiedler vector of the graph. Building on these results we suggest a centrality score based on fluctuations of random walks. Our findings imply that local fluctuations of continuous-time Markov processes on discrete state space depend strongly on the global topology of the underlying graph in addition to the specific transition rates.
