Computing diffusion state distance using Green's function and heat kernel on graphs

DOI10.1007/978-3-319-13123-8_7MaRDI QIDQ2945275zbMATH OpenOpenAlexFDO

Authors Edward Boehnlein, Peter Chin, Linyuan Lu, Amit K. Sinha

Publication date 9 September 2015

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1410.3168

zbMATH Keywords

DSD for non-bipartite graphslazy-random walks

Mathematics Subject Classification ID

Random walks on graphs (05C81) Graph theory (including graph drawing) in computer science (68R10)

Abstract: The diffusion state distance (DSD) was introduced by Cao-Zhang-Park-Daniels-Crovella-Cowen-Hescott [{em 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 [{em 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,\mathrm{...},w_n)$. We also examined the DSD distances of two biological networks.

Recommendations

• Computing the diffusion state distance on graphs via algebraic multigrid and random projections.
• Spectral distances on graphs
• Random-walk based approximate \(k\)-nearest neighbors algorithm for diffusion state distance
• Some remarks on diffusion distances
• Diffusion state distances: multitemporal analysis, fast algorithms, and applications to biological networks

Cited in

(3)

• Computing the diffusion state distance on graphs via algebraic multigrid and random projections.
• Diffusion state distances: multitemporal analysis, fast algorithms, and applications to biological networks
• A hitting time formula for the discrete Green's function

This page was built for publication: Computing diffusion state distance using Green's function and heat kernel on graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2945275)