Premium
Computing the diffusion state distance on graphs via algebraic multigrid and random projections
Author(s) -
Lin Junyuan,
Cowen Lenore J.,
Hescott Benjamin,
Hu Xiaozhe
Publication year - 2018
Publication title -
numerical linear algebra with applications
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.02
H-Index - 53
eISSN - 1099-1506
pISSN - 1070-5325
DOI - 10.1002/nla.2156
Subject(s) - multigrid method , robustness (evolution) , algebraic number , mathematics , lemma (botany) , metric (unit) , computer science , algorithm , partial differential equation , mathematical analysis , ecology , biochemistry , chemistry , operations management , poaceae , biology , economics , gene
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.