Публикации
Ермолин Н.А., Мазалов В.В., Печников А.А.
Теоретико-игровые методы нахождения сообществ в академическом Вебе
// Труды СПИИРАН. Вып. 55. 2017. C. 237-254
Ключевые слова: веб-пространство; граф; сообщество; модулярность; коалиционная теория игр
Исследуется задача нахождения сообществ в графе, представляющем собой фрагмент академического Веба, вершинами которого являются сайты научных организаций, а дугами — гиперссылки. Предлагается новый подход, основанный на методах коалиционной теории игр, применение которого приводит к устойчивому коалиционному разбиению. Для этого определяется функция предпочтения для любой пары вершин в графе, и тогда нахождение стабильного разбиения сводится к нахождению максимума потенциальной функции. Описан реализованный алгоритм поиска стабильного разбиения, даны оценки его сложности. Делается сравнение предлагаемого метода с двумя известными методами нахождения сообществ, в том числе эффективность нового метода показывается на разбиении на сообществафрагмента Веба, состоящего из официальных сайтов Сибирского и Дальневосточного отделений РАН.
Индексируется в Scopus, РИНЦ
Последние изменения: 5 марта 2018