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

Докладчик: Георгий Овчинников

Презентация: simrank_talk_ru

Видео: http://www.youtube.com/watch?v=rGBGOO0gmMI