Skip to content
Назад к результатам поиска

Стохастическая блочная модель — Вероятностное обнаружение сообществ в сетях

Год
1983
Тип
Probabilistic generative graph model

Этот текст переведён машинным способом и ещё не проверен. Читать оригинал на английском

Размер шрифта

Что он делает?

Стохастическая блочная модель (SBM), представленная Холландом, Лэски и Лейнхардтом (1983), является вероятностной генеративной моделью для графов, которая присваивает узлы скрытым блокам и параметрически оценивает вероятности связей между блоками.

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

Интуиция метода

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

История

Стохастическая блочная модель была представлена Холландом, Лэски и Лейнхардтом в их статье 1983 года в журнале Social Networks как вероятностное обобщение более ранних работ по блочному моделированию в анализе социальных сетей. В течение двух десятилетий она оставалась в основном теоретическим инструментом; практическое применение она получила с разработкой масштабируемых алгоритмов вывода — вариационного EM и MCMC — в 2010-х годах. Стохастическая блочная модель с поправкой на степень была представлена Каррером и Ньюманом (2011) для решения проблемы гетерогенности степеней. Обзор Ли и Уилкинсона 2019 года в Applied Network Science обобщил семейство расширений, охватывая модели с посаженным разбиением, SBM со смешанными членствами и иерархические варианты. Сегодня SBM и ее производные являются эталонной вероятностной основой для обнаружения сообществ и кластеризации графов.

Когда применять

Используйте Стохастическую блочную модель, когда у вас есть сеть с как минимум 50 узлами, и вы хотите обнаружить скрытую групповую структуру, не предполагая, что группы должны быть плотными кликами. Она подходит для ориентированных или неориентированных графов, взвешенных или невзвешенных, и подходит как для исследовательских, так и для задач классификации. Вариант DCSBM предпочтителен, когда степени узлов существенно различаются. Если граф имеет менее 20 узлов, структуру сообщества нельзя надежно оценить, и вместо этого следует использовать более простые описательные метрики. Предположения: членство в блоках скрыто и не наблюдается; матрица связей блоков предполагается однородной в пределах каждой пары блоков; и K должно быть выбрано с помощью BIC или Байесовского фактора, а не установлено произвольно.

Ограничения и замечания

  • Требует как минимум около 50 узлов для надежной оценки блоков; очень маленькие графы дают нестабильные решения.
  • Вывод вычислительно затратен для больших графов: требуется вариационный EM или MCMC, и сходимость не гарантируется.
  • Предположение о гомогенности базовой SBM внутри пар блоков нарушается, когда скорости соединений внутри блоков варьируются — DCSBM смягчает, но не устраняет это.
  • Выбор блоков с помощью BIC или Байесовского фактора все еще может привести к недо- или пере-сегментации, если граф имеет слабо разделенные сообщества.

Условия из источника не заменяют независимую научную проверку или валидацию аналитическим движком.

Сильные стороны

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

Применение

  • Обнаружение исследовательских сообществ в сетях цитирования и сотрудничества в социальных и естественных науках.
  • Идентификация функциональных модулей в биологических сетях, таких как графы взаимодействий белков и совместной экспрессии генов.
  • Обнаружение сегментов клиентов или мошеннических колец в транзакционных и финансовых сетях.
  • Характеристика структуры ядро-периферия в межорганизационных или межстрановых торговых сетях.
  • Бенчмаркинг и оценка других алгоритмов обнаружения сообществ с использованием синтетических графов, сгенерированных SBM, в качестве истинных данных.

Как это работает

Как это работает

1

Аналитик указывает диапазон кандидатов для числа блоков K и выбирает вариант: базовая SBM предполагает однородное распределение степеней внутри блока, в то время как SBM с поправкой на степень (DCSBM) добавляет параметры степени на уровне узла для обработки хабов и гетерогенных последовательностей степеней. Выбор варианта основывается на распределении степеней наблюдаемого графа.

2

Учитывая матрицу смежности, модель оценивает членство в блоках и матрицу вероятностей связей K×K с помощью алгоритма вывода. Для малых и средних графов возможна точная максимизация; для больших графов используется вариационный метод ожидания-максимизации (вариационный EM) или выборка методом Монте-Карло по цепи Маркова (MCMC), чтобы сделать вывод вычислительно осуществимым.

3

Число блоков K заранее неизвестно и должно быть выбрано из данных. Предпочтительными критериями выбора являются Байесовский информационный критерий (BIC) и Байесовский фактор, оба из которых штрафуют сложность модели и выбирают K, которое наилучшим образом балансирует соответствие с парсимонией. Принцип минимальной длины описания (MDL) лежит в основе реализации graph-tool.

4

Как только оптимальное K и присвоения блоков определены, матрица связей блоков анализируется для характеристики структуры: ассортитивные блоки соответствуют сообществам, диссортативные блоки — двудольным паттернам, а смешанные профили — расположениям ядро-периферия. Членство узлов сообщается с апостериорными вероятностями, если алгоритм вывода их предоставляет.

Частые ошибки

  • Произвольная установка K вместо выбора с помощью BIC или Байесовского фактора приводит к ненадежным разбиениям — всегда используйте принципиальный критерий выбора модели.
  • Применение базовой SBM к графу с гетерогенной последовательностью степеней (хабы, распределение степеней по закону степенной функции) завышает оценки числа блоков; вместо этого используйте DCSBM.
  • Рассмотрение членства в блоке как достоверного, когда апостериорное распределение размыто, преувеличивает уверенность — сообщайте о неопределенности, когда она доступна.
  • Смешивание выходных данных SBM с истинными сообществами: модель находит статистически правдоподобную скрытую структуру, а не обязательно социально значимые группы. Проверяйте с учетом знаний предметной области.
  • Запуск SBM на менее чем 20 узлах дает вырожденные решения — для малых графов используйте описательные сетевые метрики или простое обнаружение сообществ.

Часто задаваемые вопросы

Чем Стохастическая блочная модель отличается от обнаружения сообществ на основе модульности?

Максимизация модульности (например, Louvain, Leiden) оптимизирует эвристическую цель, которая неявно предполагает ассортитивные сообщества примерно одинакового размера и имеет известный предел разрешения, препятствующий обнаружению малых сообществ. SBM — это вероятностная генеративная модель с явными предположениями; количество блоков выбирается путем выбора модели (BIC или Байесовский фактор), а не эвристической оптимизации, и она может обнаруживать диссортативные структуры и структуры ядро-периферия, которые упускают методы на основе модульности.

Когда следует использовать DCSBM вместо базовой SBM?

Используйте DCSBM, когда распределение степеней узлов гетерогенно — например, когда небольшое количество хабов составляет большую часть ребер, или когда последовательность степеней следует приближенному степенному закону. Базовая SBM рассматривает все узлы внутри блока как взаимозаменяемые, что приводит к тому, что хабы попадают в свои собственные ложные блоки. DCSBM добавляет член поправки на степень, который отделяет структурную позицию от степени, что приводит к более интерпретируемым присвоениям блоков в таких графах.

Как выбрать количество блоков K?

Подгоните модели для диапазона значений K и выберите ту, которая минимизирует BIC или максимизирует Байесовский фактор (или эквивалентно минимизирует длину описания). Не выбирайте K на основе визуального осмотра графа или предварительных ожиданий. Большинство реализаций (graph-tool, blockmodels в R) автоматизируют этот поиск. Также рекомендуется анализ чувствительности — проверка того, изменяется ли качественная структура блоков при изменении K на единицу.

Каков минимальный размер сети для надежного применения SBM?

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

Похожие методы

Источники

  1. Holland, P.W., Laskey, K.B. & Leinhardt, S. (1983). Stochastic Blockmodels: First Steps. Social Networks, 5(2), 109-137.

    Открыть ссылку DOI
    Скопировано.
  2. Lee, C. & Wilkinson, D.J. (2019). A Review of Stochastic Block Models and Extensions for Graph Clustering. Applied Network Science, 4(1), 122.

    Открыть ссылку DOI
    Скопировано.