Алгоритмы и методы нахождения сообществ на примере научных веб-пространств СО РАН и Общества Фраунгофера, Германия

Семинар: Информационные технологии
Начало заседания: 14:35

Дата выступления: 3 Декабрь 2013

Организация: ИМ СО РАН, Новосибирск; Central European University, Budapest

Авторы: Медведев Алексей Николаевич

Сети и графы получили широкое распространение в современных исследованиях. Социальные сети можно представить в виде графа, вершинами которого являются различные социальные группы, а ребра представляют связи между группами. Интернет есть не что иное, как множество роутеров, связанных линиями связи, и, следовательно, может быть представлен графом. Сети такого рода зачастую имеют огромное количество вершин и ребер (> 1 млн.), не поддаются визуальному анализу, и имеют очень сложную и неоднородную структуру. Одним из инструментов исследования этой структуры является поиск сообществ в сети. Одним из определений сообщества является разделение вершин на группы с большой плотностью ребер внутри группы, относительно ребер между ними. Данная задача является NP полной, но было предложено множество эвристических алгоритмов для поиска такого рода сообществ. Также можно рассматривать разделения вершин на пересекающиеся сообщества или рассматривать реберные сообщества. В докладе будут рассмотрены основные определения, алгоритмы и техники нахождения сообществ на примере научных веб-пространств СО РАН и Общества Фраунгофера, Германия. Будут представлены алгоритмы, программные комплексы и результаты на указанных выше графах, с последующим обсуждением.