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

Модель Уоттса — Строгаца — это математическая модель генерации случайных графов, обладающих свойствами «тесного мира» (small-world networks). Модель была предложена в 1998 году американскими математиками Дунканом Уоттсом и Стивеном Строгацем в статье «Collective dynamics of ’small-world’ networks». Она позволяет создавать графы, которые одновременно характеризуются высоким коэффициентом кластеризации (как у регулярных решёток) и малым средним расстоянием между вершинами (как у случайных графов). Модель Уоттса — Строгаца стала одной из основополагающих в теории сложных сетей и широко используется для анализа социальных, биологических, технологических и информационных систем.

¶История

До появления модели Уоттса — Строгаца в теории графов доминировали две крайние парадигмы: регулярные решётки (например, кольцевые или квадратные решётки) и случайные графы Эрдёша — Реньи. Регулярные решётки обладают высокой кластеризацией (соседи вершины часто связаны между собой), но большое среднее расстояние между вершинами. Случайные графы, напротив, имеют малые средние расстояния, но низкую кластеризацию. В реальных сетях, таких как социальные связи, нейронные сети или интернет, наблюдаются оба свойства: высокая кластеризация и короткие пути между любыми двумя узлами (эффект «тесного мира»). Дункан Уоттс и Стивен Строгац, работавшие в Корнеллском университете, предложили простой алгоритм, который объединяет эти характеристики.

Их работа была опубликована в журнале Nature в 1998 году и вызвала значительный интерес в научном сообществе. Модель стала отправной точкой для многочисленных исследований в области сетевой науки, включая анализ распространения инфекций, информационных потоков, устойчивости сетей и эволюции сотрудничества.

¶Алгоритм построения

Модель Уоттса — Строгаца начинается с регулярной кольцевой решётки. Алгоритм включает следующие шаги:

1. Создание регулярной решётки: строится кольцо из \( N \) вершин, каждая из которых соединена с \( K \) ближайшими соседями (по \( K/2 \) с каждой стороны, где \( K \) — чётное число). Таким образом, степень каждой вершины равна \( K \).

1. Пересоединение рёбер: для каждого ребра в решётке с вероятностью \( p \) (параметр пересоединения) одно из его концов случайным образом перенаправляется на другую вершину, выбранную равномерно из всех вершин, исключая дублирование и петли. При \( p = 0 \) граф остаётся регулярной решёткой; при \( p = 1 \) граф становится близким к случайному графу Эрдёша — Реньи с той же средней степенью.

Параметр \( p \) контролирует степень «случайности» сети. При малых \( p \) (например, \( p = 0.01 \)) граф сохраняет высокую кластеризацию, но приобретает короткие пути за счёт небольшого числа «длинных» рёбер, соединяющих удалённые части сети.

¶Свойства

¶Коэффициент кластеризации

Коэффициент кластеризации \( C \) измеряет, насколько соседи вершины связаны между собой. В регулярной решётке (\( p = 0 \)) \( C \) высок и составляет примерно \( 3/4 \) для больших \( N \) и \( K \). При увеличении \( p \) коэффициент кластеризации падает медленно, оставаясь высоким даже при значительной случайности. Для \( p = 0.1 \) \( C \) может быть на порядок выше, чем в случайном графе с той же средней степенью.

¶Средняя длина пути

Средняя длина пути \( L \) — это среднее число шагов вдоль кратчайших путей между всеми парами вершин. В регулярной решётке \( L \) растёт линейно с \( N \) (пропорционально \( N/K \)). В случайном графе \( L \) растёт логарифмически (\( \propto \ln N / \ln K \)). В модели Уоттса — Строгаца при малых \( p \) \( L \) резко падает, приближаясь к логарифмическому закону, в то время как \( C \) остаётся высоким. Это и есть эффект «тесного мира»: сеть становится «маленьким миром».

¶Распределение степеней

В отличие от многих реальных сетей, распределение степеней в модели Уоттса — Строгаца близко к пуассоновскому (как в случайных графах), с пиком около среднего значения \( K \) и экспоненциальным спадом на хвостах. Это ограничение модели, так как многие реальные сети (например, интернет или социальные сети) имеют степенное распределение степеней (безмасштабные сети). Однако модель Уоттса — Строгаца не претендует на воспроизведение всех свойств реальных сетей, а лишь демонстрирует переход от регулярности к случайности.

¶Применение

Модель Уоттса — Строгаца используется в различных областях для моделирования и анализа сетей, обладающих свойством «тесного мира»:

• Социальные сети: анализ распространения слухов, мнений, эпидемий в социальных группах. Модель помогает понять, как небольшое число «длинных» связей (например, друзей из других городов) ускоряет распространение информации.
• Эпидемиология: моделирование распространения инфекционных заболеваний. Сети «тесного мира» демонстрируют, что даже при высокой кластеризации (например, в локальных сообществах) инфекция может быстро распространяться через «длинные» контакты.
• Нейробиология: нейронные сети мозга часто обладают свойствами «тесного мира», что обеспечивает эффективную передачу сигналов при высокой локальной связности.
• Технические сети: анализ топологии интернета, электрических сетей, транспортных систем. Модель используется для оценки устойчивости сетей к случайным отказам и целенаправленным атакам.
• Информационные системы: моделирование ссылочных структур в вебе, социальных медиа, научных цитированиях.

¶Ограничения и критика

Несмотря на популярность, модель Уоттса — Строгаца имеет ряд ограничений:

• Распределение степеней: как упоминалось, оно не является степенным, что не соответствует многим реальным сетям. Для моделирования безмасштабных сетей используется модель Барабаши — Альберт.
• Однородность: модель предполагает, что все вершины имеют примерно одинаковую степень (около \( K \)), что редко встречается в реальности.
• Фиксированная размерность: начальная регулярная решётка является одномерным кольцом, что ограничивает пространственную структуру. Для двумерных или трёхмерных сетей существуют модификации.
• Параметр пересоединения: выбор \( p \) часто произволен, и модель не объясняет, как именно возникают «длинные» связи в реальных системах.

Тем не менее, модель остаётся важным инструментом для изучения фазовых переходов в сетях и понимания базовых механизмов, приводящих к эффекту «тесного мира».

¶Интересные факты

• Термин «тесный мир» (small world) был введён в 1960-х годах психологом Стэнли Милгрэмом в ходе экспериментов с пересылкой писем, которые показали, что в социальной сети среднее число рукопожатий между людьми составляет около шести (концепция «шести рукопожатий»).
• Модель Уоттса — Строгаца часто называют моделью WS (по первым буквам фамилий авторов).
• В 2003 году Дункан Уоттс получил премию «Гений» (MacArthur Fellowship) за свои работы в области сетевой науки.

¶Источники

• Watts, D. J., & Strogatz, S. H. (1998). Collective dynamics of ’small-world’ networks. Nature, 393(6684), 440–442.
• Newman, M. E. J. (2010). Networks: An Introduction. Oxford University Press.
• Barabási, A.-L. (2016). Network Science. Cambridge University Press.
• Strogatz, S. H. (2001). Exploring complex networks. Nature, 410(6825), 268–276.