Стохастическая блочная модель

Стохастическая графов блочная модель это генеративная модель для случайных — . Эта модель имеет тенденцию создавать графы, содержащие сообщества , подмножества узлов, характеризующиеся связью друг с другом с определенной плотностью ребер. Например, ребра могут быть более распространены внутри сообществ, чем между сообществами. Его математическая формулировка была впервые представлена ​​в 1983 году в области анализа социальных сетей Полом У. Холландом и др. Стохастическая блочная модель важна в статистике , машинном обучении и сетевых науках , где она служит полезным ориентиром для задачи восстановления структуры сообщества в графовых данных.

Определение

Стохастическая блочная модель принимает следующие параметры:

• Число $n$ вершин;
• раздел множества вершин $\{1,\ldots ,n\}$ на непересекающиеся подмножества $C_{1},\ldots ,C_{r}$, называемые сообществами ;
• симметричный $r\times r$ матрица $P$ вероятностей ребер.

Затем набор ребер выбирается случайным образом следующим образом: любые две вершины $u\in C_{i}$ и $v\in C_{j}$ соединены ребром с вероятностью $P_{ij}$. Пример проблемы: задан график с $n$ вершины, где ребра выбираются, как описано, восстанавливают группы $C_{1},\ldots ,C_{r}$.

Особые случаи

Пример ассортативного случая для стохастической блочной модели.

Если матрица вероятностей является константой в том смысле, что $P_{ij}=p$ для всех $i,j$, то результатом будет модель Эрдеша – Реньи $G(n,p)$. Этот случай является вырожденным — разделение на сообщества становится неактуальным, — но он иллюстрирует тесную связь с моделью Эрдеша-Реньи.

Модель установленного раздела представляет собой особый случай, когда значения матрицы вероятности $P$ являются константой $p$ по диагонали и еще одна константа $q$ за пределами диагонали. Таким образом, две вершины в одном сообществе имеют общее ребро с вероятностью $p$, а две вершины в разных сообществах имеют общее ребро с вероятностью $q$. Иногда именно эту ограниченную модель называют стохастической блочной моделью. Случай, когда $p>q$ называется ассортативной моделью, а случай $p<q$ называется дисассортативным .

Возвращаясь к общей стохастической блочной модели, модель называется сильно ассортативной, если $P_{ii}>P_{jk}$ в любое время $j\neq k$: все диагональные записи доминируют над всеми недиагональными записями. Модель называется слабоассортативной, если $P_{ii}>P_{ij}$ в любое время $i\neq j$: каждая диагональная запись должна доминировать только над остальной частью своей строки и столбца. Существуют дисассортативные формы этой терминологии, обращающие все неравенства вспять. Для некоторых алгоритмов восстановление может быть проще для блочных моделей с ассортативными или неассортативными условиями такой формы.

Типичные статистические задачи

Большая часть литературы по алгоритмическому обнаружению сообщества решает три статистические задачи: обнаружение, частичное восстановление и точное восстановление.

Обнаружение

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

Частичное восстановление

При частичном восстановлении цель состоит в том, чтобы приблизительно определить скрытое разделение на сообщества, то есть найти раздел, который коррелирует с истинным разделом значительно лучше, чем случайное предположение.

Точное восстановление

Целью точного восстановления является точное восстановление скрытого разделения на сообщества. Размеры сообщества и матрица вероятностей могут быть известны. или неизвестно.

нижние границы и

Стохастические блочные модели демонстрируют резкий пороговый эффект, напоминающий пороги перколяции . Предположим, что мы допускаем размер $n$ графа расти, сохраняя размеры сообщества в фиксированных пропорциях. Если матрица вероятностей остается фиксированной, такие задачи, как частичное и точное восстановление, становятся выполнимыми для всех невырожденных настроек параметров. Однако, если мы уменьшим матрицу вероятностей с подходящей скоростью, как $n$ увеличивается, мы наблюдаем резкий фазовый переход: при определенных настройках параметров станет возможным добиться восстановления с вероятностью, стремящейся к 1, тогда как на противоположной стороне порога параметра вероятность восстановления стремится к 0 независимо от того, какой алгоритм используется.

Для частичного восстановления соответствующее масштабирование должно приниматься $P_{ij}={\tilde {P}}_{ij}/n$ для фиксированного ${\tilde {P}}$, что приводит к графикам постоянной средней степени. В случае двух сообществ одинакового размера в модели ассортативного засаженного участка с матрицей вероятности

$$P=\left({\begin{array}{cc}{\tilde {p}}/n&{\tilde {q}}/n\\{\tilde {q}}/n&{\tilde {p}}/n\end{array}}\right),$$

частичное восстановление возможно с вероятностью $1-o(1)$ в любое время $({\tilde {p}}-{\tilde {q}})^{2}>2({\tilde {p}}+{\tilde {q}})$, тогда как любая оценка терпит неудачу частичное восстановление с вероятностью $1-o(1)$ в любое время $({\tilde {p}}-{\tilde {q}})^{2}<2({\tilde {p}}+{\tilde {q}})$.

Для точного восстановления необходимо принять соответствующее масштабирование $P_{ij}={\tilde {P}}_{ij}\log n/n$, что приводит к графикам средней логарифмической степени. Здесь аналогичный порог существует: для модели ассортативной насаждённой перегородки с $r$ равных по размеру сообществ, порог находится на уровне ${\sqrt {\tilde {p}}}-{\sqrt {\tilde {q}}}={\sqrt {r}}$. Фактически, точный порог восстановления известен для полностью общей стохастической блочной модели.

Алгоритмы

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

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

Варианты

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

Тематические модели

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

Расширения подписанных графов

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

DARPA/MIT/AWS Graph Challenge: потоковая стохастическая блокировка раздела

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

См. также

• блочное моделирование
• Алгоритм Гирвана – Ньюмана - Алгоритм обнаружения сообщества
• Тест Ланчикинетти – Фортунато – Радикки – страницы алгоритмов с краткими описаниями без пробелов для создания эталонных сетей с сообществами.