Стохастична блокова модель — це генеративна модель для випадкових графів. Ця модель, як правило, створює графи, що містять спільноти, підмножини вузлів, що характеризуються тим, що вони пов'язані один з одним певною щільністю ребер. Наприклад, ребра можуть бути більш поширеними в межах спільнот, ніж між спільнотами. Її математичне формулювання вперше було запропоновано в 1983 році в галузі аналізу соціальних мереж Полом В. Голландом та ін. Стохастична блокова модель важлива в статистиці, машинному навчанні та мережевій науці, де вона служить корисним орієнтиром для завдання відновлення структури спільноти в графових даних.

Визначення Стохастична блокова модель приймає такі параметри:

Число вершин; Розбиття множини вершин на непересічні підмножини , які називаються громадами ; Симетричний матриця граничних ймовірностей.

Потім набір ребер випадковим чином вибирається наступним чином: будь-які дві вершини і з'єднані ребром з ймовірністю Приклад задачі: задано графік з вершини, де ребра вибірково відбираються, як описано, відновлюють групи .

Особливі випадки

Якщо матриця ймовірностей є константою, у тому сенсі, що для всіх , тоді результатом є модель Ердеша–Реньї Цей випадок є виродженим — поділ на спільноти стає неактуальним — але він ілюструє тісний зв'язок з моделлю Ердеша-Реньї.

Модель посадженого розбиття є окремим випадком, у якому значення матриці ймовірностей є сталою величиною на діагоналі та іншою сталою величиною поза діагоналлю. Таким чином, дві вершини, що належать до однієї спільноти, мають спільне ребро з імовірністю , тоді як дві вершини з різних спільнот мають спільне ребро з імовірністю . Іноді саме цю обмежену модель називають стохастичною блоковою моделлю. Випадок називається асортативною моделлю, тоді як випадок — дезасортативною моделлю.

Повертаючись до загальної стохастичної блокової моделі, модель називається сильно асортативною, якщо коли завгодно : усі діагональні записи домінують над усіма позадіагональними записами. Модель називається слабо асортативною, якщо коли завгодно : кожен діагональний елемент повинен домінувати лише над рештою свого рядка та стовпця. Існують дизасортативні форми цієї термінології шляхом обернення всіх нерівностей. Для деяких алгоритмів відновлення може бути простішим для блокових моделей з асортативними або дизасортативними умовами такої форми.

Типові статистичні завдання Значна частина літератури з алгоритмічного виявлення спільноти стосується трьох статистичних завдань:

виявлення; часткове відновлення; точне відновлення.

Виявлення Мета алгоритмів виявлення полягає в тому, щоб просто визначити, чи має граф латентну структуру спільноти, враховуючи вибірковий граф. Точніше, граф може бути згенерований, з деякою відомою апріорною ймовірністю, з відомої стохастичної блокової моделі, а в іншому випадку - з подібної моделі Ердеша—Реньї. Алгоритмічне завдання полягає в тому, щоб правильно визначити, яка з цих двох базових моделей згенерувала граф.

Точне відновлення При частковому відновленні метою є приблизно визначити прихований розподіл за спільнотами, тобто знайти такий розподіл, який корелює з істинним розподілом значно краще, ніж випадкове припущення.

Exact recovery У точному відновленні метою є точне відновлення латентного розбиття на спільноти. Розміри спільнот та матриця ймовірностей можуть бути відомими або невідомими.

Нижні статистичні межі та порогова поведінка Стохастичні блокові моделі демонструють різкий пороговий ефект, подібний до порогів перколяції. Припустимо, що розмір графа зростає, тоді як розміри спільнот зберігаються у фіксованих пропорціях.

Якщо матриця ймовірностей залишається сталою, такі завдання, як часткове та точне відновлення, стають здійсненними для всіх невироджених наборів параметрів. Однак, якщо матриця ймовірностей зменшується з відповідною швидкістю зі зростанням , спостерігається різкий фазовий перехід: для певних значень параметрів стає можливим досягти відновлення з імовірністю, що прямує до 1, тоді як по інший бік порогу ймовірність відновлення прямує до 0 незалежно від використовуваного алгоритму.

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

Для точного відновлення слід вжити відповідних заходів масштабування , що призводить до графіків логарифмічного середнього ступеня. Тут існує аналогічний поріг: для асортативної моделі посадженого розподілу з громади рівного розміру, поріг знаходиться на рівні Фактично, точний поріг відновлення відомий для повністю загальної стохастичної блочної моделі.

Алгоритми В принципі, точне відновлення можна вирішити в допустимому діапазоні, використовуючи метод максимальної правдоподібності, але це зводиться до розв'язання задачі обмеженого або регуляризованого розрізу, такої як мінімальний бісекційний переріз, яка зазвичай є NP-повною. Отже, жоден відомий ефективний алгоритм не зможе правильно обчислити оцінку максимальної правдоподібності в найгіршому випадку.

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

Варіанти Існує кілька варіантів моделі. Одне незначне налаштування розподіляє вершини спільнотам випадковим чином, відповідно до категоріального розподілу, а не у фіксованому розділі.

Більш значні варіанти включають стохастичну блокову модель з корекцією ступеня, ієрархічну стохастичну блокову модель, геометричну блокову модель, цензуровану блокову модель та блокову модель зі змішаним членством.

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

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

Випробування DARPA/MIT/AWS Graph Challenge: потокове стохастичне розбиття блоків GraphChallenge DARPA/MIT/AWS Graph Challenge заохочує спільнотні підходи до розробки нових рішень для аналізу графіків та розріджених даних, отриманих із соціальних мереж, даних датчиків та наукових даних, щоб дозволити виявляти зв'язки між подіями в міру їх розгортання в польових умовах. Потокове стохастичне розбиття блоків є одним із завдань з 2017 року DARPA/MIT/AWS Graph Challenge Champions.

Спектральна кластеризація продемонструвала видатну продуктивність порівняно з оригінальним та навіть покращеним базовим алгоритмом, що відповідає якості кластерів, але при цьому на кілька порядків швидша.

Посилання <references> ref name="decelle11"></ref>

</references>