IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

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

  • April 24, 2015
  • 2:30 p.m.
  • LeConte 312

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,\ldots, w _ n)$. We also examined the DSD distances of two biological networks. Joint work with Peter Chin (Boston Univ.), Linyuan Lu, and Amit Sinha (Boston Univ.).

© Interdisciplinary Mathematics Institute | The University of South Carolina Board of Trustees | Webmaster
USC