Выявление структуры сообществ в очень больших сетях

Выявление и анализ структуры сообществ в сетях в последнее время вызывают значительный интерес у физиков, однако большинство предложенных методов непригодны для очень больших сетей из-за высоких вычислительных затрат. Мы представляем алгоритм иерархической агломерации для выявления структуры сообществ, который работает быстрее многих конкурирующих алгоритмов: его время работы для сети с n вершинами и m рёбрами составляет O(md log n), где d — глубина дендрограммы, описывающей структуру сообществ. Многие реальные сети разрежены и имеют иерархическую структуру: m приблизительно равно n, а d — log n. В этом случае алгоритм работает практически за линейное время — O(n log² n). В качестве примера применения алгоритма мы анализируем сеть товаров, продаваемых на сайте крупного интернет-магазина. Товары в этой сети связаны, если их часто покупает один и тот же покупатель. Сеть включает более 400 000 вершин и 2 × 10⁶ рёбер. Мы показываем, что алгоритм позволяет выявлять в ней осмысленные сообщества и обнаруживать крупномасштабные закономерности в покупательском поведении клиентов.