TY - JOUR

T1 - Kemeny's constant for several families of graphs and real-world networks

AU - Kooij, Robert E.

AU - Dubbeldam, Johan L.A.

PY - 2020

Y1 - 2020

N2 - The linear relation between Kemeny's constant, a graph metric directly linked with random walks, and the effective graph resistance in a regular graph has been an incentive to calculate Kemeny's constant for various networks. In this paper we consider complete bipartite graphs, (generalized) windmill graphs and tree networks with large diameter and give exact expressions of Kemeny's constant. For non-regular graphs we propose two approximations for Kemeny's constant by adding to the effective graph resistance term a linear term related to the degree heterogeneity in the graph. These approximations are exact for complete bipartite graphs, but show some discrepancies for generalized windmill and tree graphs. However, we show that a recently obtained upper-bound for Kemeny's constant in Wang et al. (2017) based on the pseudo inverse Laplacian gives the exact value of Kemeny's constant for generalized windmill graphs. Finally, we have evaluated Kemeny's constant, its two approximations and its upper bound, for 243 real-world networks. This evaluation reveals that the upper bound is tight, with average relative error of only 0.73%. In most cases the upper bound clearly outperforms the other two approximations.

AB - The linear relation between Kemeny's constant, a graph metric directly linked with random walks, and the effective graph resistance in a regular graph has been an incentive to calculate Kemeny's constant for various networks. In this paper we consider complete bipartite graphs, (generalized) windmill graphs and tree networks with large diameter and give exact expressions of Kemeny's constant. For non-regular graphs we propose two approximations for Kemeny's constant by adding to the effective graph resistance term a linear term related to the degree heterogeneity in the graph. These approximations are exact for complete bipartite graphs, but show some discrepancies for generalized windmill and tree graphs. However, we show that a recently obtained upper-bound for Kemeny's constant in Wang et al. (2017) based on the pseudo inverse Laplacian gives the exact value of Kemeny's constant for generalized windmill graphs. Finally, we have evaluated Kemeny's constant, its two approximations and its upper bound, for 243 real-world networks. This evaluation reveals that the upper bound is tight, with average relative error of only 0.73%. In most cases the upper bound clearly outperforms the other two approximations.

KW - Effective graph resistance

KW - Kemeny's constant

KW - Pseudo inverse Laplacian

KW - Random walks

KW - Spectral graph theory

UR - http://www.scopus.com/inward/record.url?scp=85086397220&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2020.05.033

DO - 10.1016/j.dam.2020.05.033

M3 - Article

AN - SCOPUS:85086397220

SN - 0166-218X

VL - 285

SP - 96

EP - 107

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

ER -