Конспект лекции: Навигационный тесный мир (модель Клейнберга)
На основе презентации А. Пономаренко "Navigable Small Worlds – 2"
Социальные и информационные сети часто демонстрируют эффект тесного мира — между любыми двумя узлами существует короткий путь, несмотря на большую размерность сети. Однако наличие коротких путей ещё не означает, что их можно найти без глобального знания структуры сети.
Навигационный тесный мир — это сеть, в которой:
- Малый диаметр: порядка $ \log n $, где $ n $ — число узлов.
- Высокий коэффициент кластеризации.
- Степенной закон распределения степеней узлов: $ P(k) \sim k^{-3} $.
- Навигируемость: возможность эффективного поиска пути с помощью децентрализованного алгоритма, использующего только локальную информацию.
🔑 Главный вопрос: Каким образом индивидуумы в социальной сети могут найти кратчайший путь к цели, зная лишь локальных знакомых и местоположение цели?
- Объясняет малый диаметр и высокую кластеризацию.
- Не объясняет навигируемость: нет механизма для эффективного поиска пути с локальной информацией.
- Генерирует сети со степенным распределением степеней.
- Использует механизм предпочтительного присоединения: вероятность соединения нового узла с узлом $ i $ пропорциональна его степени: $$ p_i = \frac{k_i}{\sum_j k_j} $$
- Также не решает задачу навигации.
⚠️ Эти модели описывают структуру, но не отвечают на вопрос: почему мы можем быстро находить пути в огромной сети?
Цель: выяснить, при каких условиях сеть становится навигационным тесным миром, то есть допускает эффективный децентрализованный поиск.
- Узлы расположены на двумерной решётке $ n \times n $.
- Расстояние между узлами $ u = (i,j) $ и $ v = (k,l) $ — манхэттенское: $$ d(u,v) = |k - i| + |l - j| $$
- Каждый узел имеет:
- Локальные связи (например, до ближайших соседей).
- Длинные дистанционные рёбра, добавляемые случайно с вероятностью: $$ P((u,v) \in E) \propto d(u,v)^{-r} $$ где $ r $ — ключевой параметр модели.
💡 Чем больше $ r $, тем чаще создаются короткие рёбра; чем меньше $ r $, тем выше вероятность далёких связей.
Существует децентрализованный алгоритм $ A $, такой что при $ r = 2 $ и $ p = q = 1 $, ожидаемое время доставки сообщения составляет $ O((\log n)^2) $.
Это означает, что сеть становится навигационным тесным миром только при строго определённом значении параметра $ r = 2 $.
- При $ r < 2 $: слишком много далёких рёбер → сеть хаотична, направление поиска теряется.
- При $ r > 2 $: преобладают локальные рёбра → нет «скачков», необходимых для быстрого приближения к цели.
- При $ r = 2 $: достигается оптимальный баланс — длинные рёбра распределены так, что позволяют эффективно «приближаться» к цели шаг за шагом.
Вероятность наличия ребра между узлами на расстоянии $ d
Оценка суммы в знаменателе: $$ \sum_{u \neq v} d(u,v)^{-2} \leq \sum_{j=1}^{2n-2} 4j \cdot j^{-2} = 4 \sum_{j=1}^{2n-2} j^{-1} \leq 4(1 + \ln(2n - 2)) \leq 4 \ln(6n) $$
Следовательно: $$ P((u,v) \in E) \geq \frac{1}{4 \ln(6n) \cdot d(u,v)^2} $$
Алгоритм работает по правилу: передать сообщение тому соседу, который ближе всего к цели (по манхэттенскому расстоянию).
- Мы находимся в фазе $ j $, если $ 2^j < d(t, x) \leq 2^{j+1} $, где $ x $ — текущее положение сообщения.
- Цель: последовательно проходить фазы $ j = \log n, \log n - 1, \dots, 0 $, пока не достигнем цели.
Обозначим:
- $ B_j = { x : d(t,x) \leq 2^j } $ — шар радиуса $ 2^j $ вокруг цели.
- На каждом шаге мы хотим, чтобы из текущего узла существовало ребро в $ B_j $, чтобы перейти в более раннюю фазу.
Пусть текущее расстояние до цели $ \in (2^j, 2^{j+1}] $. Тогда:
-
Минимальное расстояние от текущего узла до узла в $ B_j $: $ \leq 2^{j+2} $.
-
Вероятность наличия ребра в $ B_j $:
$$ P(\text{ребро в } B_j) \geq |B_j| \cdot \min_{v \in B_j} P((u,v) \in E) $$
-
Оценим:
- $ |B_j| > 2^{2j} $ (площадь шара радиуса $ 2^j $ на решётке),
- $ P((u,v) \in E) \geq \frac{1}{4 \ln(6n) \cdot (2^{j+2})^2} = \frac{1}{4 \ln(6n) \cdot 2^{2j+4}} $
Тогда: $$ P(\text{успех}) \geq 2^{2j} \cdot \frac{1}{4 \ln(6n) \cdot 2^{2j+4}} = \frac{1}{128 \ln(6n)} $$
— постоянная по $ j $ вероятность выхода из фазы на каждом шаге.
Пусть $ X_j $ — число шагов в фазе $ j $. Поскольку на каждом шаге есть вероятность $ \Omega(1 / \ln n) $ завершить фазу, математическое ожидание длительности фазы:
Число фаз: от $ j = 0 $ до $ j \approx \log n $, т.е. $ O(\log n) $.
Общее ожидаемое число шагов: $$ E[X] = \sum_{j=0}^{\log n} E[X_j] \leq (1 + \log n) \cdot 128 \ln(6n) = O((\log n)^2) $$
- Модель Клейнберга объясняет, почему некоторые сети являются навигационными тесными мирами.
- Ключевым условием является структурированное распределение длинных рёбер с показателем $ r = 2 $.
- Только при этом значении возможен эффективный децентрализованный поиск за $ O((\log n)^2) $ шагов.
- Это объясняет результаты эксперимента Милгрэма: люди используют локальные правила ("передать тому, кто ближе к цели"), и это работает благодаря скрытой геометрии социальных связей.
- Kleinberg J. The small-world phenomenon: An algorithmic perspective // Proceedings of the thirty-second annual ACM symposium on Theory of computing. – ACM, 2000. – P. 163–170.
- Ostroumova L. et al. Generalized preferential attachment.
Вывод:
Навигационный тесный мир — это не просто сеть с короткими путями, а сеть, в которой эти пути можно найти, пользуясь только локальной информацией. Модель Клейнберга показывает, что навигируемость возникает не случайно, а вследствие точного баланса между локальностью и дальностью связей.