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

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