SimRank — популярный индекс похожести вершин графа нашедший применение во многих задачах, основным недостатком которого является высокая сложность вычисления и высокие затраты оперативной памяти. В данной работе предложена малоранговая аппроксимация симранка, вычисляемая за O(n^2r) и требующая O(nr) памяти (r – ранк аппроксимации), приводятся численные эксперименты на графах из коллекции DIMACS10 и графе Simple English Wikipedia.
Докладчик: Георгий Овчинников
Презентация: simrank_talk_ru