  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.
