Skip to content

Network-Clustering-part-2.md

Latest commit

 

History

History
163 lines (119 loc) · 14.3 KB

Network-Clustering-part-2.md

File metadata and controls

163 lines (119 loc) · 14.3 KB

Кластеризация в сетях — Часть 2 – поиск пересекающихся сообществ

1. Постановка задачи поиска пересекающихся сообществ

Формальная постановка:

Пусть $G = (V, E)$ - граф с $n$ узлами $V = {v_1, v_2, ..., v_n}$ и $m$ ребрами $E \subseteq V \times V$.

Задача обнаружения пересекающихся сообществ может быть определена через матрицу принадлежности $F$, где $F_{vc}$ обозначает степень принадлежности узла $v$ сообществу $c$.

  • Для пересекающихся сообществ: $0 \leq F_{vc} \leq 1, \forall v \in V, \forall c \in C$
  • Для непересекающихся сообществ: $F_{vc} \in {0, 1}$

Особенности пересекающихся сообществ:

  • Узел может принадлежать одновременно нескольким сообществам
  • Степень принадлежности может быть непрерывной величиной (soft clustering)
  • Более реалистично отражает структуру многих реальных сетей (социальные сети, биологические сети и др.)

2. Подход Link Partitioning

Основная идея:

  • Вместо разделения узлов на сообщества, разделяем множество ребер
  • Сообщества определяются через отношения между узлами, а не через сами узлы
  • Узел принадлежит сообществу, если он имеет смежные ребра, принадлежащие этому сообществу

Иллюстративный пример: Человек может играть в футбол с друзьями по выходным и работать с коллегами по будням. При этом некоторые коллеги могут быть его друзьями. Таким образом, человек имеет два типа отношений: "играет в футбол с" и "работает с", и принадлежит двум сообществам: "футбольные игроки" и "коллеги".

Математическая реализация:

  1. Строится линейный граф $L(G)$, где:

    • Вершины $L(G)$ соответствуют ребрам исходного графа $G$
    • Две вершины в $L(G)$ соединены ребром, если соответствующие ребра в $G$ имеют общую вершину

  2. Выполняется разделение вершин линейного графа на непересекающиеся сообщества

  3. Вершина исходного графа принадлежит сообществу, если инцидентные ей ребра принадлежат этому сообществу в линейном графе

История развития:

  • Evans и Lambiotte (2009-2010) первыми применили разделение узлов линейного графа для получения разделения ребер исходного графа
  • Kim и Jeong (2011) предложили модифицированную версию метода Infomap для обнаружения link communities
  • Evans (2010) расширил подход линейного графа на кликовые графы

3. Метод LPAM (Link Partitioning Around Medoids)

Основная идея метода: Метод LPAM объединяет подход link partitioning с алгоритмом Partitioning Around Medoids (PAM) для обнаружения пересекающихся сообществ в сетях с заданным количеством кластеров.

Этапы алгоритма LPAM:

  1. Построение линейного графа:

    • Создается линейный граф $L(G)$ исходного графа $G$
    • Вершины $L(G)$ соответствуют ребрам $G$
    • Ребра в $L(G)$ соединяют вершины, соответствующие смежным ребрам в $G$

  2. Обнаружение непересекающихся сообществ в линейном графе:

    • Вычисляется матрица расстояний $D = (d_{ij}) \in \mathbb{R}^{m \times m}$ для вершин $L(G)$

    • В работе используются два типа функций расстояния:

      • Commute distance - время, необходимое случайной прогулке, чтобы дойти от узла $i$ до узла $j$ и вернуться обратно
      • Amplified commute distance - модификация commute distance, дающая более точные результаты

    • Применяется алгоритм Partitioning Around Medoids (PAM) для получения $k$ кластеров

  3. Преобразование кластеров ребер в кластеры узлов:

    • Узел $v$ принадлежит сообществу $c$ с коэффициентом $F_{vc}$, пропорциональным количеству смежных ребер, принадлежащих кластеру $c$
    • Параметр $\theta$ контролирует степень пересечения сообществ: с увеличением $\theta$ возрастает степень пересечения

Вычислительная сложность:

  • Точная версия: экспоненциальная сложность $O(2^{|E|})$, так как задача k-median является NP-полной
  • Эвристическая версия: использует метод CLARANS с теоретической сложностью, близкой к квадратичной

Преимущества метода LPAM:

  • Естественным образом порождает пересекающиеся сообщества
  • Может работать с заданным количеством кластеров
  • Использует более информативные метрики расстояния (commute distance и его усиленную версию)
  • Экспериментальные результаты показывают конкурентоспособность с существующими методами

Визуальное представление: На рисунке 1 статьи показан пример 8×8 решетки и соответствующего линейного графа. Кластеры выделены цветными прямоугольниками, медоиды на линейном графе представлены большими кругами, а в исходном графе медоиды обозначены жирными ребрами.

Экспериментальные результаты:

  • Метод был протестирован на реальных сетях и синтетических бенчмарках
  • Для небольших и средних сетей был найден точный результат
  • Для крупных сетей использовалась эвристическая версия LPAM
  • Результаты показали, что эвристическая версия дает решения, близкие к точным
  • Метод конкурентоспособен с существующими подходами по метрикам F1, ONMI и другим

Заключение по методы LPAM: Метод LPAM представляет собой эффективный подход к обнаружению пересекающихся сообществ, основанный на комбинации link partitioning и алгоритма Partitioning Around Medoids. Он преобразует задачу поиска пересекающихся сообществ в задачу поиска непересекающихся сообществ в линейном графе, что позволяет использовать хорошо изученные методы для непересекающихся кластеров и естественным образом получать пересекающиеся сообщества в исходной сети.

Конспект лекции: Поиск пересекающихся сообществ в сетях. Методы LPAM и BIGCLAM

4. Метод BIGCLAM (Cluster Affiliation Model for Big Networks)

Основная идея метода:

BIGCLAM (Cluster Affiliation Model for Big Networks) - это метод обнаружения пересекающихся сообществ, основанный на модели аффилиаций узлов к сообществам. В отличие от многих существующих методов, BIGCLAM учитывает, что пересечения сообществ часто имеют более плотную структуру связей, чем непересекающиеся части сообществ.

Ключевые принципы:

  • Сообщества возникают из-за общих аффилиаций узлов к группам
  • Узел может иметь разную степень принадлежности к разным сообществам
  • Плотность связей в пересечениях сообществ выше, чем в непересекающихся частях

Математическая модель:

  1. Представление сообществ:

    • Модель использует матрицу принадлежности $F \in \mathbb{R}^{N \times K}$, где $F_{uc} \geq 0$ обозначает степень принадлежности узла $u$ к сообществу $c$
    • Чем выше значение $F_{uc}$, тем сильнее узел $u$ связан с сообществом $c$

  2. Генерация сети:

    • Вероятность существования ребра между узлами $u$ и $v$ определяется как: $$p(u, v) = 1 - \exp(-F_u \cdot F_v^T)$$
    • Эта вероятность увеличивается с количеством общих сообществ и силой аффилиаций

  3. Оптимизационная задача:

    • Цель: найти матрицу $F$, максимизирующую правдоподобие наблюдаемой сети $$\hat{F} = \underset{F \geq 0}{\arg\max} , l(F)$$ где $$l(F) = \sum_{(u,v) \in E} \log(1 - \exp(-F_u F_v^T)) - \sum_{(u,v) \notin E} F_u F_v^T$$

Алгоритмическая реализация:

  1. Оптимизация:

    • BIGCLAM формулируется как задача неотрицательного матричного разложения (NMF)
    • Используется модифицированный блочный стохастический градиентный спуск
    • Для ускорения вычислений применяется оптимизация, описанная в статье, которая ускоряет алгоритм примерно в 100 раз

  2. Определение числа сообществ $K$:

    • Для больших сетей: метод удержания (hold-out)
      • 20% пар узлов резервируются для проверки
      • Варьируя $K$, обучают модель на 80% пар узлов
      • Выбирается $K$ с максимальным правдоподобием на удерживаемом наборе
    • Для малых сетей (менее 50 ребер): критерий BIC
      • $BIC(K) = -2l(\hat{F}) + NK \log|E|$
      • Выбирается $K$, минимизирующий BIC

  3. Масштабируемость:

    • Для очень больших сетей применяется $l_1$-регуляризация: $$\underset{F_{uc} \geq 0}{\arg\max} , l(F) - \lambda \sum_{u,c} |F_{uc}|$$
    • Регуляризация обеспечивает разреженность матрицы $F$, снижая требования к памяти
    • Для LiveJournal (4 млн узлов, 35 млн ребер) с 20 потоками время обработки составляет около одного дня

Преимущества метода BIGCLAM:

  1. Точность:

    • Превосходит существующие методы по метрикам F1-score, Omega-index и Recall
    • В 98% случаев находит истинные сообщества с высокой точностью (F1 > 0.85)
    • В 27% случаев обнаруживает сообщества почти идеально (F1 > 0.95)

  2. Масштабируемость:

    • Может обрабатывать сети с сотнями тысяч узлов за 20 минут
    • Обрабатывает сети в 10-100 раз быстрее, чем другие методы
    • Позволяет анализировать сети с миллионами узлов (в 10 раз больше, чем предыдущие методы)

  3. Гибкость модели:

    • Естественным образом моделирует различные типы структур:
      • Непересекающиеся сообщества
      • Пересекающиеся сообщества
      • Иерархически вложенные сообщества
    • Учитывает плотные соединения в пересечениях сообществ

Заключение по BIGCLAM: BIGCLAM – очень стройный метод в котором идеи матричной факторизации применяются для поиска пересекающихся сообществ