Случайные сети незаменимы в качестве точки сравнения при исследовании сложных реальных сетей. В конечном счете, мы можем понять свойства сети, которые обусловлены исключительно случайностью, а не конкретными предопределенными отношениями или механизмами.
Оглавление
1. Модель Эрдёша–Реньи (МО)
2. Модель Барабаши–Альберта (BA)
3. Модель Уоттса-Строгаца (WS)
1. Модель Эрдёша – Реньи (ER)
Классическая модель случайных сетей названа в честь двух математиков, Пала Эрдёша и Альфреда Реньи, которые сыграли важную роль в понимании свойств этих сетей.
По существу случайная сеть — это сеть, которую можно создать путем многократного повторения этих двух простых шагов для каждой из пар узлов N(N-1)/2:
- Начните с
Nизолированных узлов. - Выберите пару узлов и сгенерируйте случайное число от 0 до 1. Если число превышает
p, соедините выбранную пару узлов ссылкой, в противном случае оставьте их отключенными.
Таким образом, модель ER генерирует сеть случайным образом, соединяя узлы с фиксированной вероятностью. В этой модели любые два узла имеют равные шансы на соединение. Результирующая сеть обычно характеризуется распределением степени Пуассона, что означает, что количество соединений, которые узел выполнил, следует распределению Пуассона.
# Generate an ER random graph with 100 nodes and probability p=0.1 G = nx.erdos_renyi_graph(100, 0.1)
2. Модель Барабаши-Альберта (BA)
Модель Барабаси-Альберта (BA) – отличный выбор для моделирования сетей, в которых одни узлы имеют гораздо большее количество подключений, чем другие. Этот тип сети обычно наблюдается в различных реальных системах, например, в школьной сети, которую мы обсуждали в предыдущих эпизодах
Модель Барабаши-Альберта (BA) представляет собой безмасштабную сетевую модель, которая генерирует сети со степенным распределением степени, что означает, что несколько узлов имеют много соединений (высокая степень), в то время как большинство узлов имеют лишь несколько соединений (низкая степень). . Модель BA основана на идее роста и предпочтительного подключения, что означает, что новые узлы добавляются в сеть и с большей вероятностью подключаются к существующим узлам с высокой степенью.
Модель BA широко используется для моделирования различных сложных сетей, включая World Wide Web, социальные сети и биологические сети. Распределение степеней по степеням и наличие узлов (концентраторов) высоких степеней — два ключевых свойства сетей БА, которые делают их полезными для моделирования сетей реального мира.
Вот пример того, как сгенерировать сеть BA со 100 узлами, m = 2, где m — фиксированное целое число, определяющее количество соединений, которое каждый новый узел имеет при добавлении в сеть.
# Create BA model G = nx.barabasi_albert_graph(100, 2)
Подробнее о модели BA я напишу в следующем выпуске про безмасштабные сети.
3. Модель Уоттса-Строгаца (WS)
Модель Уоттса-Строгаца (WS) — это популярная сетевая модель, представленная Дунканом Дж. Уоттсом и Стивеном Х. Строгацем в 1998 году. способ изучить, как сети могут демонстрировать как локальную кластеризацию, так и глобальную связность.
Модель Уоттса-Строгаца (WS) представляет собой случайную сетевую модель, которая генерирует сети малого мира, что означает, что сети имеют как высокую кластеризацию, так и небольшую среднюю длину кратчайшего пути. Модель основана на идее начать с регулярной решетки или кольца узлов, где каждый узел соединен со своими k ближайшими соседями, и случайным образом перемонтировать часть p ребер.
Чтобы создать сеть WS, нужно начать с регулярной решетки из N узлов, каждый из которых связан с k ближайшими соседями. Затем для каждого ребра с вероятностью p переподключают его к случайно выбранному узлу, сохраняя степень узлов. В результате процесса перемонтажа получается сеть с высокой степенью кластеризации, а также с более короткой средней длиной кратчайшего пути по сравнению со случайной сетью.
Модель WS полезна для моделирования множества реальных сетей, включая социальные сети, транспортные сети и нейронные сети. Возможность настройки параметров модели, таких как количество ближайших соседей (k) и вероятность переподключения (p), делает модель WS гибким инструментом для изучения структуры и динамики сложных сетей.
В NetworkX модель WS может быть сгенерирована с помощью функции watts_strogatz_graph. Вот пример создания сети WS со 100 узлами, k = 4 и p = 0.1:
# create Watts-Strogatz model G = nx.watts_strogatz_graph(100, 4, 0.1)
Заключение
Тремя наиболее часто используемыми моделями случайных сетей являются модели Эрдёша-Реньи (ER), Барабаши-Альберта (BA) и Уоттса-Строгаца (WS). Хотя каждая из этих моделей генерирует случайные сети, они различаются по методу, который они используют для создания соединений между узлами, а также по разным целям, которых можно достичь, моделируя реальные ситуации с помощью случайной сети. Например, модели ER и WS не могут предсказать хабы, поэтому мы используем модель BA, но пока ее достаточно.
На данном этапе важно отметить, что модель BA связана с безмасштабными сетями, а модель Уоттса-Строгаца связана с сетями малого мира. Тем не менее, мы углубимся в эти концепции более подробно в следующих эпизодах.
На данный момент достаточно понять, что существуют различные способы моделирования случайных сетей и что эти модели можно использовать для изучения влияния свойств сети на их поведение. Это включает в себя анализ формирования кластеров, распределения связей и появления закономерностей, среди прочего.
