Выявление и оценка структуры сообществ в сетях

Мы предлагаем и исследуем ряд алгоритмов для выявления структуры сообществ в сетях — естественного разделения узлов на группы с высокой плотностью связей. Все алгоритмы имеют две ключевые особенности. Во-первых, сеть разделяют на сообщества путём последовательного удаления рёбер, которые определяют с помощью одного из нескольких возможных показателей посреднической центральности. Во-вторых, после каждого удаления эти показатели пересчитывают. Мы также предлагаем показатель выраженности выявленной структуры сообществ, позволяющий объективно выбрать число групп, на которые следует разделить сеть. На данных искусственно созданных и реальных сетей мы показываем, что алгоритмы эффективно выявляют сообщества и помогают разобраться в сложной структуре сетевых систем.