Случайные сети представляют собой совокупности узлов (вершин), соединённых случайным образом рёбрами. В отличие от регулярных кристаллических или решётчатых структур, топология случайной сети определяется вероятностным распределением связей между узлами. Основная цель изучения случайных сетей в физике сложных систем — выявление универсальных свойств, характерных для большого числа взаимодействующих объектов, без привязки к конкретной геометрии.
$$ \langle k \rangle = \frac{2E}{N}. $$
Эти параметры позволяют количественно описать топологию сети и переходить к статистическому анализу её структуры.
Модель Эрдёша-Реньи (G(N, p)) — фундаментальная модель случайных графов, предложенная П. Эрдёшем и А. Реньи в 1959 году. В этой модели каждая пара узлов соединяется рёбром с независимой вероятностью p.
Вероятность того, что вершина имеет степень k, описывается биномиальным распределением:
$$ P(k) = \binom{N-1}{k} p^k (1-p)^{N-1-k}. $$
Для больших N и малых p биномиальное распределение аппроксимируется распределением Пуассона:
$$ P(k) \approx \frac{\langle k \rangle^k e^{-\langle k \rangle}}{k!}. $$
Это ключевой результат, который подчёркивает случайный характер соединений и редкость узлов с сильно отличающейся степенью.
Среднее число рёбер:
$$ \langle E \rangle = p \binom{N}{2} = p \frac{N(N-1)}{2}. $$
Плотность сети ρ определяется как отношение числа существующих рёбер к максимально возможному:
$$ \rho = \frac{2E}{N(N-1)} \approx p. $$
В случайной сети вероятность образования треугольников крайне мала:
C = p,
где C — коэффициент кластеризации. Это отличает модель Эрдёша-Реньи от реальных социальных и биологических сетей, где наблюдается высокая локальная связность.
Связанные компоненты — подмножества вершин, соединённых между собой рёбрами, из которых нельзя выйти, не пройдя через рёбра. Для маленьких p сеть состоит из множества маленьких компонентов, но при превышении критического значения $p_c = \frac{1}{N}$ возникает гигантская компонента, охватывающая конечную долю сети.
Ключевое свойство модели — фазовый переход. Пусть ⟨k⟩ = p(N − 1) — средняя степень вершины. Для ⟨k⟩ < 1 все компоненты малы, их размеры ограничены. При ⟨k⟩ > 1 появляется гигантская компонента, и её размер S подчиняется уравнению:
S = 1 − e−⟨k⟩S.
Этот переход аналогичен перколяционному и описывает момент, когда сеть перестаёт быть разрозненной и начинает демонстрировать глобальную связность.
Модель G(N, M) — фиксированное число рёбер M. Отличие от G(N, p) в том, что вероятность соединения не задаётся напрямую, а определяется комбинаторикой всех графов с M рёбрами. При больших N обе модели эквивалентны.
Эволюционные случайные сети — динамическое добавление узлов и рёбер с вероятностью, зависящей от степени вершины (см. модели с предпочтительным присоединением).
Случайные сети с ограниченной степенью — полезны для моделирования реальных систем, где степень узла не может превышать физический предел.
Модель Эрдёша-Реньи задаёт базовую платформу для понимания случайной структуры, служит отправной точкой для сложных моделей с нелинейными, коррелированными или масштабно-инвариантными свойствами.