Случайные графы и распределение узлов по степеням

Примерно с середины прошлого века в теории графов основные результаты были получены для таких видов графов, в которых распределение связей между узлами имеет случайный характер (они так и называются – случайные графы).
Пусть у нас есть граф, в котором M связей случайным образом распределены между N узлами. Понятно, что у одних узлов связей будет несколько больше, у других – несколько меньше, но средняя степень узла будет равна отношению общего числа связей в графе M к общему же числу узлов N. Если в таком графе  для каждой степени узла от 1 до M сосчитать все узлы графа с именно такой степенью и построить гистограмму, получится так называемое распределение Пуассона (Рис. 7), похожее на хорошо известное всем нормальное или гауссово распределение с графиком в виде перевернутого колокола. Другими словами, в случайных графах наиболее вероятное количество связей, приходящееся на один узел, равно средней степени узла.

Рис. 7. Распределение степени узлов в случайном графе

Изучая случайные графы, математики обнаружили много интересных вещей. Например, выяснилось, что если число связей примерно равно числу узлов, большинство узлов графа  оказываются связанными между собой в единую структуру – формируется так называемая гигантская связанная компонента. Наглядную онлайновую демонстрацию процесса формирования гигантской связанной компоненты при росте числа связей в графе можно посмотреть здесь:  http://ccl.northwestern.edu/netlogo/models/GiantComponent.