Стохастическая блочная модель
-
Основы стохастической блочной модели
- Стохастическая блочная модель — это вероятностная модель для описания структуры сообществ в графах.
- Модель основана на блоках, где вершины в каждом блоке имеют одинаковые вероятности соединения с вершинами в других блоках.
- Модель может быть использована для обнаружения скрытых сообществ в графах, а также для частичного и точного восстановления этих сообществ.
-
Типы стохастических блочных моделей
- Существует несколько типов стохастических блочных моделей, включая ассортативные и диссортативные модели.
- Ассортативные модели предполагают, что вероятность соединения между вершинами в одном блоке выше, чем между вершинами в разных блоках.
- Диссортативные модели предполагают обратное соотношение вероятностей соединения.
-
Статистические задачи и пороги
- Стохастические блочные модели демонстрируют резкие пороговые эффекты, аналогичные порогам просачивания.
- При частичном восстановлении порог зависит от отношения вероятностей соединения между блоками.
- При точном восстановлении порог зависит от степени разделения блоков.
-
Алгоритмы и варианты
- Алгоритмы для точного восстановления могут быть неэффективными, но многие алгоритмы работают хорошо в среднем.
- Существуют различные варианты стохастической блочной модели, включая стохастическую блочную модель с корректировкой по степени и блочную модель с цензурой.
-
Тематические модели и расширения
- Стохастическая блочная модель признана тематической моделью для анализа двунаправленных сетей.
- Модель может быть расширена для анализа подписанных графов с положительными и отрицательными весами ребер.
-
Задачи анализа данных
- GraphChallenge поощряет разработку новых подходов для анализа графиков и данных, полученных из различных источников.
- Спектральная кластеризация показала высокую производительность и скорость по сравнению с оригинальной моделью.
Полный текст статьи: