Small World — Феномен малого мира

Короткие пути между любыми двумя вершинами при высокой локальной кластеризации.

Ключевые тезисы

Средняя длина пути растёт как логарифм числа вершин — отсюда «шесть рукопожатий».
Модель Уоттса — Строгаца: регулярная решётка плюс небольшая доля случайных перемычек.
Практическое следствие: распространение информации и фрода по сети идёт очень быстро.

Подробный разбор

2 подтем — раскройте любую, чтобы увидеть объяснение, формулы, примеры и интерактивные графики.

Модель Уоттса — Строгаца

Как из решётки получить малый мир.

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

L \sim \frac{ln N}{ln ⟨ k ⟩}

Обозначения

$n$ число объектов в выборке
$k$ степень вершины — число её связей
$L$ функция потерь — то, что минимизируется при обучении
$⟨ a, b ⟩$ скалярное произведение: мера согласованности векторов
$lo g$ логарифм: превращает произведения в суммы и сжимает масштаб

Длина пути растёт логарифмически — отсюда «шесть рукопожатий»

Следствия для систем

Быстрое распространение — не всегда хорошая новость.

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

Связанные темы

Структура реальных сетей

Scale-free Networks80%

Безмасштабные сети · Графы и сети

Сети, в которых распределение степеней вершин подчиняется степенному закону: немного «хабов» и очень много слабо связанных вершин.

Network Motifs80%

Мотивы и триады · Графы и сети

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

Centrality80%

Центральности · Графы и сети

Меры важности вершины: по числу связей, по посредничеству, по близости и по влиянию соседей.

Power Law80%

Степенное распределение · Теория вероятностей и распределения

Плотность убывает как степень: редкие события встречаются намного чаще, чем предсказывает нормальный закон. Распределения Парето и Ципфа — его классические формы.

Complex Systems80%

Сложные системы · Динамические системы и фракталы

Системы из множества взаимодействующих элементов, где коллективное поведение не сводится к сумме частей.