Случайный граф Эрдоша и Ренуи (P. Erdős, A. Renyi) начинается с фиксированного числа вершин и 0 связей между ними. Далее, выбираются случайные две вершины и между ними создаётся ненаправленная связь. Производные характеристики: p — вероятность что между вершинами есть связь.
Для расчёта вероятности что заданная вершина a будет иметь степень k, можно использовать такую формулу..
p — вероятность получить связь на одну попытку
k — окончательная степень вершины после всех попыток
B — биномиальное распределение
(N-1 k) — биномиальный коэффициент
У нас есть k выбранных вершин, которые мы выбираем, и у нас N-1-k вершин, которые мы не выбираем, соответсвенно вероятность обратная и всё перемножается.
Если порядок выборки имеет значение, то надо учесть и биномиальный коэффициент, который вычисляется так, что у нас есть пространство из N! комбинаций связать вершину с другими. Если нам всё равно в каком порядке остались несвязанные вершины, то комбинаций:
k! — число способов соединить k вершин
(n-1-k)! — число способов не соединять оставшиеся вершины
Стандартное отклонение в таком случае будет
Поскольку биномиальное распределение считать непрактично для высоких N, используются приближения — распределения Пуассана и нормальное распределение, которые дают красивую колоколо-подобную кривую
Такая модель математически показывает во-первых что в случайных сетях не бывает хабов — степени вершины находятся близко к среднему значению, с экспоненциально убывающей вероятностью отклонения.
Во-вторых, что неизбежно возникновение наибольшего компонента (large component), причём в его росте будет наблюдаться пограничное свойство. При плотности рёбер более 1, начинает явно выделяться нибольший компонент
В-третьих, по мере роста числа вершин, диаметр будет рости логарифмически. Например при увеличении со 100 до 10 тыс. вершин, диаметр удвоится.
Другие случайные модели
Кроме статичной классической модели с фиксированным числом вершин, можно так-же смоделировать сети
- географические — геометрически наиболее близкие вершины образуют сетьи
- геометрические с движением — если вершины двигаются и соприкасаются друг с другом, то образуются новые связи (физическая симуляция налипания)
- с рождением — добавляются новые вершины и новые связи
- с рождением и смертью вершин
Все эти модели довольно специфичны и в деталях зависят от конкретного алгоритма
Модель с ростом
Пусть на каждый шаг, появляется новая вершина с m вершинами. Тогда для вершины k, рождённой на i-шаг к шагу t, изменение в числе её связей будет..
t — число вершин которые получат эти новые связи
Легко видеть, что для вершин, родившихся раньше, k выше, чем для родившихся поздней.