Быстрый алгоритм выявления структуры сообществ в сетях

Во многих сетях есть сообщества — группы вершин с большим числом связей внутри группы и меньшим числом связей между группами. В последние годы разработаны высокочувствительные вычислительные алгоритмы для выявления такой структуры. Однако эти алгоритмы требуют значительных вычислительных ресурсов, что ограничивает их применение небольшими сетями. Мы описываем алгоритм, который показывает отличные результаты на синтетических и реальных сетях и обычно работает в тысячи раз быстрее предшествующих алгоритмов. В числе примеров применения — анализ сети сотрудничества более чем 50 000 физиков.