Fast, memory-efficient low-rank approximation of SimRank

I. V. Oseledets, G. V. Ovchinnikov, A. M. Katrutsa

    Research output: Contribution to journalArticlepeer-review

    3 Citations (Scopus)


    SimRank is a well-known similarity measure between graph vertices. This measure relies on a graph topology and is built on the intuition that 'two objects are similar if they are related to similar objects'. Formalization of this intuition leads to a system of linear equations, so large that even the solution vector will not fit in the RAM for many real-world graphs. To solve this issue we propose a new method based on a low-rank approximation of the linear system solution. This approach requires less memory and provides a significant calculation speed-up. The experiments show that the proposed method provides an accurate SimRank approximation.

    Original languageEnglish
    Article numbercnw008
    Pages (from-to)111-126
    Number of pages16
    JournalJournal of Complex Networks
    Issue number1
    Publication statusPublished - 1 Mar 2017


    • Link Analysis
    • Lyapunov equation
    • Probabilistic svd
    • Similarity Search
    • SimRank
    • Svd


    Dive into the research topics of 'Fast, memory-efficient low-rank approximation of SimRank'. Together they form a unique fingerprint.

    Cite this