Abstract:
Kemeny’s constant of a network is the expected number of steps a random walker takes to reach a vertex randomly chosen according to the stationary distribution, regardless of the starting position. Kemeny’s constant is a valuable measure for assessing the mixing properties of a random walk on the network, and it has many applications, such as modeling traffic flow in road networks or the spread of infectious diseases. In this talk, we discuss how various techniques from spectral graph theory can be used to obtain new results about Kemeny’s constant. First, for a certain family of semiregular networks, we prove a spectral result that leads to a novel expression for Kemeny's constant. Then, for general networks, we propose using spectral sparsification to efficiently compute an approximation of Kemeny's constant, and we provide bounds for this approximation. Finally, we apply the technique of eigenvalue interlacing to derive bounds for Kemeny's constant in terms of the Kemeny constant of specific subnetworks, such as those obtained by removing an edge. This talk is based on joint work with Aida Abiad, Ángeles Carmona, Andrés Marcos Encinas, and María José Jiménez.