Случайный граф Эрдоша и Ренуи (P. Erdős, A. Renyi) начинается с фиксированного числа вершин и 0 связей между ними. Далее, выбираются случайные две вершины и между ними создаётся ненаправленная связь. Производные характеристики: p — вероятность что между вершинами есть связь.

Для расчёта вероятности что заданная вершина a будет иметь степень k, можно использовать такую формулу..

B(N1;k;p)=(N1k)pk(1p)N1kB(N−1;k;p)=(N−1k)pk(1−p)N−1−k
N-1 — число попыток для вершины получить новых связей
p — вероятность получить связь на одну попытку
k — окончательная степень вершины после всех попыток
B — биномиальное распределение
(N-1 k) — биномиальный коэффициент
Биномиальное распределение числа связей на вершину в случайном графе

У нас есть k выбранных вершин, которые мы выбираем, и у нас N-1-k вершин, которые мы не выбираем, соответсвенно вероятность обратная и всё перемножается.

Если порядок выборки имеет значение, то надо учесть и биномиальный коэффициент, который вычисляется так, что у нас есть пространство из N! комбинаций связать вершину с другими. Если нам всё равно в каком порядке остались несвязанные вершины, то комбинаций:

(N1k)=(n1)!k!(n1k)!(N−1k)=(n−1)!k!(n−1−k)!
(n-1)! — число способов соединить все вершины
k! — число способов соединить k вершин
(n-1-k)! — число способов не соединять оставшиеся вершины
Биномиальный коэффициент

Стандартное отклонение в таком случае будет

σ2=(n1)p(1p)σ2=(n−1)p(1−p)
σ — стандартное отклонение
Стандартное отклонение

Поскольку биномиальное распределение считать непрактично для высоких N, используются приближения — распределения Пуассана и нормальное распределение, которые дают красивую колоколо-подобную кривую

pk=zkezk!pk=zke−zk!
Распределение Пуассана
pk=1σ2π−−√e(kz)22σ2pk=1σ2πe−(k−z)22σ2
Нормальное распределение

Если порядок связей важен, то надо учитывать биномиальное распределениеБиномиальное распределение для вероятности 0.5 и 7 вершин

Такая модель математически показывает во-первых что в случайных сетях не бывает хабов — степени вершины находятся близко к среднему значению, с экспоненциально убывающей вероятностью отклонения.

Во-вторых, что неизбежно возникновение наибольшего компонента (large component), причём в его росте будет наблюдаться пограничное свойство. При плотности рёбер более 1, начинает явно выделяться нибольший компонент

В-третьих, по мере роста числа вершин, диаметр будет рости логарифмически. Например при увеличении со 100 до 10 тыс. вершин, диаметр удвоится.

Другие случайные модели

Кроме статичной классической модели с фиксированным числом вершин, можно так-же смоделировать сети

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

Все эти модели довольно специфичны и в деталях зависят от конкретного алгоритма

Модель с ростом

Пусть на каждый шаг, появляется новая вершина с m вершинами. Тогда для вершины k, рождённой на i-шаг к шагу t, изменение в числе её связей будет..

d(ki(t))dt=mt−→−−−−−−получаеминтегрируяki(t)=m+mlog(ti)d(ki(t))dt=mt→получаеминтегрируяki(t)=m+mlog(ti)
m — число связей с которыми рождается вершина
t — число вершин которые получат эти новые связи
Динамика роста сети

Легко видеть, что для вершин, родившихся раньше, k выше, чем для родившихся поздней.

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *