СоНоты

Похожесть графов и сетей

Видеолекция из цикла Google TechTalks: Similarity in Graphs and Networks, прочитана профессором Винсентом Блонделем из Католического университета Лувэна (Бельгия).

В данной лекции дается описание алгоритма Кляйнберга (Kleinberg) нахождения хабов и авторитетов среди вершин графа. Затем описывается расширение этого алгоритма от схемы hubs -> authorities к схеме 1 -> 2 -> 3, и построение на его основе метрики похожести вершин графа или подграфов с учётом ребёр, входящих или исходящих из рассматриваемых вершин. В конце приводятся примеры практичекого применения этого алгоритма: автоматическое нахождение синонимов по толковому словарю, а также анализ телефоных звонков абонетов бельгийской сотовой компании.

Если у кого-то нет возможности тянуть видео по инету, а также тем, кто хочет разобраться с алгоритмами по-подробне, рекомендую эту статью, наиболее близкую к содержанию этой видеолекции: Vincent D. Blondel, Anahí Gajardo, Maureen Heymans, Pierre Senellart, Paul Van Dooren, A measure of similarity between graph vertices. With applications to synonym extraction and web searching, SIAM Review, 46:4, pp. 647-666, 2004. Было бы неплохо, если бы гугловцы помимо самих съёмок лекций, также находили подобные статьи и приводили ссылки на них рядом с роликами Google TechTalks.