Случайный граф

Описание	Случайный граф — общий термин для обозначения вероятностного распределения графов. Случайные графы можно описать просто распределением вероятности или случайным процессом, создающим эти графы. Теория случайных графов находится на стыке теории графов и теории вероятностей. С математической точки зрения случайные графы необходимы для ответа на вопрос о свойствах типичных графов. Случайные графы нашли практическое применение во всех областях, где нужно смоделировать сложные сети — известно большое число случайных моделей графов, отражающих разнообразные типы сложных сетей в различных областях. В математическом контексте термин случайный граф означает почти всегда модель случайных графов Эрдёша — Реньи. В других контекстах любая модель графов означает случайный граф.
Область знаний	Математика, Социология, NetSci
Авторы
Поясняющее видео
Близкие понятия
Среды и средства для освоения понятия	statnet

Модель Эрдёша — Реньи, обозначаемая [math]\displaystyle{ G(n,M) }[/math], даёт одинаковую вероятность всем графам, имеющим в точности M рёбер. Если обозначить [math]\displaystyle{ N = {n\choose 2}, }[/math] с [math]\displaystyle{ 0\le M \le N }[/math], то [math]\displaystyle{ G(n,p) }[/math] будет содержать [math]\displaystyle{ \tbinom NM }[/math] элементов и любой элемент выпадает с вероятностью [math]\displaystyle{ \tbinom NM^{-1} }[/math]

Эту модель можно рассматривать как снимок для некоторого момента времени (M) случайного процесса на графе [math]\displaystyle{ \tilde{G}_n }[/math], который начинается с n вершин без рёбер и на каждом шагу добавляется новое ребро, выбираемое равномерно из множества отсутствующих рёбер.