Community Detection — Поиск сообществ

Разбиение графа на плотно связанные группы: клиенты одного круга, связанные аккаунты, тематические кластеры документов.

Q = \frac{1}{2 m} ij \sum (A_{ij} - \frac{k _{i} k _{j}}{2 m}) δ (c_{i}, c_{j})

Что означает каждый компонент

$A_{ij}$ есть ли ребро между вершинами на самом деле
$k_{i} k_{j} /2 m$ сколько рёбер ожидалось бы между ними в случайном графе с теми же степенями
$δ (c_{i}, c_{j})$ учитываются только пары внутри одного сообщества

Модулярность = насколько связей внутри групп больше, чем в случайной сети

Ключевые тезисы

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

Подробный разбор

2 подтем — раскройте любую, чтобы увидеть объяснение, формулы, примеры и интерактивные графики.

Модулярность и её предел

Что максимизируют алгоритмы и где они ошибаются.

Q = \frac{1}{2 m} ij \sum (A_{ij} - \frac{k _{i} k _{j}}{2 m}) δ (c_{i}, c_{j})

Обозначения

$Δ$ приращение — малое изменение величины
$k$ степень вершины — число её связей
$A$ матрица смежности графа: есть ли ребро между вершинами
$\sum$ суммирование по всем перечисленным элементам

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

Прикладные сценарии

Где сообщества дают деньги.

Антифрод: плотная группа новых аккаунтов с общими устройствами — типичная схема.
Маркетинг: сегменты клиентов по совместным покупкам, а не по демографии.
Контент: тематические кластеры документов через граф цитирований или ссылок.
Инфраструктура: группы сервисов с плотными зависимостями — кандидаты на выделение.

Связанные темы

Машинное обучение на графах

Graph Basics85%

Основы графов · Графы и сети

Вершины, рёбра, веса и направления. Матрица смежности и список рёбер — два способа хранить одно и то же.

Centrality85%

Центральности · Графы и сети

Меры важности вершины: по числу связей, по посредничеству, по близости и по влиянию соседей.

PageRank85%

PageRank · Графы и сети

Стационарное распределение случайного блуждания по графу с телепортацией. Классический алгоритм ранжирования, который до сих пор используется как признак.

Graph Embeddings85%

Графовые эмбеддинги · Графы и сети

Векторные представления вершин, в которых близость отражает связанность в графе.

Graph Neural Networks85%

Графовые нейросети · Графы и сети

Нейросети, работающие прямо на структуре графа: представление вершины обновляется по представлениям соседей.

Message Passing85%

Передача сообщений · Графы и сети

Единая схема, к которой сводятся почти все архитектуры GNN: собрать сообщения от соседей, агрегировать, обновить состояние.

Link Prediction85%

Предсказание связей · Графы и сети

Задача «появится ли ребро между вершинами»: рекомендации друзей и товаров, достройка графов знаний.

Knowledge Graphs85%

Графы знаний · Графы и сети

Факты в виде троек «субъект — предикат — объект». Структурированная память, которую всё чаще подключают к языковым моделям.

Network Motifs85%

Мотивы и триады · Графы и сети

Маленькие повторяющиеся подграфы, встречающиеся чаще, чем в случайной сети. Хорошие признаки для классификации вершин.

Clustering85%

Кластеризация · Обучение без учителя

Разбиение объектов на группы похожих без заранее известных меток.

Eigenvector85%

Собственный вектор · Математический справочник

Направление, сохраняющееся при линейном преобразовании с точностью до масштаба.