We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Computing the diffusion state distance on graphs via algebraic multigrid and random projections.
- Authors
Lin, Junyuan; Cowen, Lenore J.; Hescott, Benjamin; Hu, Xiaozhe
- Abstract
Summary: 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 using 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.
- Subjects
DIFFUSION; GRAPH theory; MULTIGRID methods (Numerical analysis); RANDOM projection method; ELASTICITY
- Publication
Numerical Linear Algebra with Applications, 2018, Vol 25, Issue 3, p1
- ISSN
1070-5325
- Publication type
Article
- DOI
10.1002/nla.2156