In this paper, we consider efficient and robust algorithms for computing the diffusion state distance (DSD) metric on graphs developed recently. In order to efficiently compute DSD, we reformulate the problem into graph Laplacians and use unsmoothed aggregation algebraic multigrid to solve the resulting linear system of equations. To further reduce the computational cost, we approximate DSD by ... read moreusing random projections based on the Johnson-Lindenstrauss lemma. Numerical results for real‐world protein-protein interaction networks are presented to demonstrate the efficiency and robustness of the proposed new approaches.
Computing the diffusion state distance on graphs via algebraic multigrid and random projections. Numer Linear Algebra Appl. 2018; 25:e2156, which has been published in final form at https://doi.org/10.1002/nla.2156. This article may be used for non-commercial purposes in accordance with Wiley Terms and Conditions for Use of Self-Archived Versions."read less
Lin, J, Cowen, LJ, Hescott, B, Hu, X. Computing the diffusion state distance on graphs via algebraic multigrid and random projections. Numer Linear Algebra Appl. 2018; 25:e2156. https://doi.org/10.1002/nla.2156.