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

Теория случайных графов стала интенсивно развиваться с конца 50-х годов прошлого века после публикации статей Эрдеша-Реньи об эволюции случайных графов. В этой модели все ребра появляются случайно и независимо с одинаковой вероятностью p и под эволюцией понимается изменение свойств графов с ростом вероятности p. Оказалось, что в некоторых значениях p происходит так называемый фазовый переход и свойства графа кардинально меняются. В этом направлении было получено много интересных и глубоких результатов. Однако, в начале 2000-х выяснилось, что модель Эрдеша-Реньи плохо описывает реальные графы, возникающие в различных областях, в частности в графы таких социальных сетей как Facebook, Twitter и т.п.

Введение……………………………………………………………………………..3
Основные концепции моделирования…………………………………….........5
Теория случайных графов………………………………………………............7
Модель Эрдёша-Реньи………………………………………………………7
Подграфы………………………………………………………………... ….9
Распределение степеней………………………………………………….. 11
Связность и диаметр……………………………………………………… 12
Кластерный коэффициент……………………………………………... …14
Модель Эрдеша-Реньи…………………………………………………….......15
Наблюдения Барабаши – Альберт………………………………………… …17
Модель Боллбаша-Риордана…………………………………………………..18
Генерация графа……………………………………………………….. ….18
Основные результаты…………………………………………………. …18
Модель LCD…………………………………………………………………... 20
Модель Buckley-Osthus…………………………………………………………..21
Модель копирования………………………………………………………. ….22
Генерация графа……………………………………………………………22
Основной результат……………………………………………………. …22
Ориентированные безмасштабные графы……………………………….. ….22
Модель Чунг-Лу…………………………………………………………….........23
10.1Генерация графа………………………………………………………..........23
10.2Основные результаты………………………………………………… …..23
Модель Янсона – Лучака………………………………………………..............24
Генерация графа………………………………………………………..24
Основные результаты…………………………………………… …..25
Основные результаты для схожих моделей…………………… …..26
Получение и обработка экспериментальных данных из социальных сетей..26
Заключение …………………………………………………………………….28
Список использованных источников………………