Computing Diffusion State Distance Using Green's Function and Heat Kernel on Graphs

Abstract

The diffusion state distance (DSD) was introduced by Cao-Zhang-Park-Daniels-Crovella-Cowen-Hescott [PLoS ONE, 2013] to capture functional similarity in protein-protein interaction networks. They proved the convergence of DSD for non-bipartite graphs. In this paper, we extend the DSD to bipartite graphs using lazy-random walks and consider the general $$L_q$$-version of DSD. We discovered the connection between the DSD $$L_q$$-distance and Green’s function, which was studied by Chung and Yau [J. Combinatorial Theory (A), 2000]. Based on that, we computed the DSD $$L_q$$-distance for Paths, Cycles, Hypercubes, as well as random graphs $$G(n,p)$$and $$G(w_1,backslashldots , w_n)$$. We also examined the DSD distances of two biological networks.