В рамках доклада будет рассказано о мере оценки близости вершин в графе — SimRank. SimRank имеет рекурсивное определение и алгоритм вычисления  имеющий сложность O(N^4), где N — количество вершин.  Высокая вычислительная сложность не позволяет применить данную меру к реальным задачам, таким как анализ социальных сетей, где количество вершин может превышать сотни миллионов. Однако потенциальная польза подсчета близости вершин на основе SimRank заставляют исследователей искать более эффективные алгоритмы. Доклад будет посвящен обзору новых подходов к вычислению этой меры.

Докладчик: Денис Турдаков

Материалы:

1. Glen Jeh and Jennifer Widom. 2002. SimRank: a measure of structural-context similarity. In Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining (KDD ’02). ACM, New York, NY, USA, 538-543.
2. Dmitry Lizorkin, Pavel Velikhov, Maxim N. Grinev, Denis Turdakov: Accuracy estimate and optimization techniques for SimRank computation. VLDB J. 19(1): 45-66 (2010)
3. Weiren Yu, Wenjie Zhang, Xuemin Lin, Qing Zhang, Jiajin Le: A space and time efficient algorithm for SimRank computation. World Wide Web 15(3): 327-353 (2012)
4. Cuiping Li, Jiawei Han, Guoming He, Xin Jin, Yizhou Sun, Yintao Yu, and Tianyi Wu. 2010. Fast computation of SimRank for static and dynamic information networks. In Proceedings of the 13th International Conference on Extending Database Technology (EDBT ’10)