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

Министерство образования  и науки Российской Федерации

САРАТОВСКИЙ ГОСУДАРСТВЕННЫЙ  УНИВЕРСИТЕТ 

ИМЕНИ Н. Г. ЧЕРНЫШЕВСКОГО

 

 

 

 

 

 

Кафедра дискретной математики и

информационных технологий

 

 

 

 

 

 

МОДЕЛИ СЛУЧАЙНЫХ  ГРАФОВ

 

 

РЕФЕРАТ

 

 

 

 

Студентки 1 курса,

дневного отделения факультета КНиИТ

 

 

Зав. кафедрой ДМиИТ

к. ф.-м.н., доцент     ________________Л. Б. Тяпаев 

 

 

 

 

Саратов, 2012 г.

 

Содержание

Введение……………………………………………………………………………..3

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

10.1Генерация графа………………………………………………………..........23

10.2Основные результаты………………………………………………… …..23       

11. Модель Янсона – Лучака………………………………………………..............24
1. Генерация графа………………………………………………………..24
2. Основные результаты…………………………………………… …..25
3. Основные результаты для схожих моделей…………………… …..26
12. Получение и обработка экспериментальных данных из социальных сетей..26

Заключение …………………………………………………………………….28

Список использованных источников…………………………………………29

 

Введение

Теория графов играет огромную роль в фундаментальной  и прикладной математике. Нас будет  интересовать лишь одно направление, которое  с каждым годом становится все  более актуальным.

В рамках этого направления графы  изучаются с вероятностной точки зрения. Типичная постановка вопроса (говоря не совсем строго) такова: велика ли вероятность того, что граф обладает данным свойством? Вопрос исключительно важный, и мы в этом не раз убедимся ниже. Правда, в нем ни

слова не сказано о  том, как именно мы понимаем термин “вероятность”. Всякий человек, имеющий представление об аксиоматике Колмогорова, хорошо знает, что можно вложить множество разных смыслов в этот термин. И его можно действительно определять по-разному. В зависимости от определения получится та или иная модель случайного графа. С чисто математических позиций любая такая модель имеет право на существование. Однако для приложений – в том числе приложений к транспортной проблематике – некоторые из этих моделей более интересны, некоторые – менее.

Соответственно, ниже в реферате будет рассказано о классах моделей, каждый из которых за десятилетия, прошедшие с момента своего появления, зарекомендовал себя плодотворным как в рамках “чистой” математики, так и в рамках ее разнообразных приложений, среди которых надежность транспортной сети, рост Интернета и других социальных и биологических сетей, теория алгоритмов и пр.

  Не претендуя на полноту изложения (это было бы нелепо, т.к. и здесь наука разрослась безгранично), в реферате постараемся выделить лишь самые основные и принципиальные моменты теории случайных графов.

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

Это породило много новых исследований математических моделей случайных графов, о некоторых из которых и будет идти речь в данной статье.

В задачах описания динамики социальных сетей основное значение имеет правильный выбор математической модели. На данный момент известно множество моделей случайных графов и безмасштабных (scale-free) сетей, некоторые из которых показали удовлетворительные результаты при сравнении с экспериментальными данными. Наиболее полным справочником по моделям безмасштабных сетей является [1].

Вообще говоря, модели социальных сетей можно разделить на три класса: модели случайных графов (модель Эрдеша-Реньи [2] и ее обобщения), простейшие модели безмасштабных сетей (модель Боллобаша [9] и ее обобщения, модель копирования [8] и др.) и более гибкие модели безмасштабных сетей (модель Чунг-Лу [3], модель Янсона-Лучака [4] и др.). Третий класс моделей представляет наибольший интерес при моделировании больших реальных социальных сетей, таких как Facebook.

Данный обзор не претендует на полноту и служит в основном для обозначения трендов в обозначенной теме.

 

 

 

1 Основные концепции моделирования

Малые миры. Концепция малых миров довольно просто описывает тот факт, что, несмотря на их огромные размеры, в большинстве сетей существует сравнительно короткий путь между двумя любыми вершинами. Расстояние между двумя вершинами определяется как число ребер наикратчайшего пути, их соединяющего. Но, принцип «малых миров», хотя и интригует, не является специальным принципом организации. Наконец, Эрдёшем и Реньи показано, что среднее расстояние между двумя вершинами в случайном графе растет как логарифм от числа вершин. Тем не менее, случайные графы являются малыми мирами.

Кластерность. Общее свойство социальных сетей состоит в том, чем является клика графа, представляя собой круг друзей и знакомых, в котором каждый участник знаком друг с другом. Эта тенденция к разбиению на кластеры определяется коэффициентом кластерности (Watts, Strogats 1998). Сначала выберем в сети некоторую вершину i, имеющую Ki ребер, которые соединяют ее с Ki другими вершинами. Если первые ближние соседи этой вершины являются частью клики, между ними существует   ребер. Отношение между числом Ei ребер, действительно существующих между Ki вершинами, и общим числом ребер  является значением коэффициента кластерности вершины i:  . Общий коэффициент кластерности сети находится как сумма коэффициентов отдельных вершин. В случайном графе, поскольку ребра распределяются случайным образом, коэффициент кластерности составляет C = p. Правда, Ватс и Строгатс первыми указали на факт, что во многих, если не во всех, реальных сетях коэффициент кластерности обычно значительно больше, чем в случайных сетях с таким же количеством ребер и вершин.

Распределение степеней. Не все вершины сети имеют одинаковое количество ребер. Распределение количества ребер вершины, то есть степень вершины, характеризуется функцией P(k), которая определяет вероятность того, что случайно выбранная вершина будет иметь ровно k ребер. Поскольку в случайном графе ребра распределяются случайным образом, большая часть вершин имеет приблизительно одинаковую степень, близкую к средней степени <k> сети. Распределение степеней вершин случайного графа является распределением Пуассона с пиком в P(<k>). С другой стороны, последние эмпирические результаты говорят о том, что для большинства сетей распределение степеней значительно отличается от распределения Пуассона. В частности, для многих сетей, включая Всемирную паутину (Albert, Jeong, Barabasi 1999), Интернет (Falautsos 1999), распределение степеней вершин является степенным: P(k) ≈ k^−π. Такие сети называют сетями без масштабирования (Barabasi, Albert 1999). В то время как некоторые сети имеют экспоненциальное распределение, часто форма функции P(k) значительно отличается от распределения Пуассона, ожидаемого для случайного графа.

Эти три концепции (малая  длина пути, кластерность, степень  без масштабирования) привели к  раздору в моделировании сетей  в последние несколько лет, дав  жизнь трем основным классам парадигм моделирования. Во-первых, случайные графы, являющиеся вариантом модели Эрдёша-Реньи, до сих пор используются во многих областях и являются основой для моделирования и эмпирических учений. Во-вторых, сразу после формулировки кластерности, появился класс моделей, в целом называемых моделями малого мира. Эти модели представляют собой нечто среднее между высоко фрагментированными регулярными решетками и случайными графами. Наконец, открытие степенного распределения степеней вершин привело к появлению различных моделей без масштабирования, которые, концентрируясь на динамике сетей, должны объяснить происхождение степенного распределения степеней вершин и прочих отклонений от распределения Пуассона, имеющих место в реальных системах.

2 Теория случайных графов

Теория случайных графов была основана Полом Эрдёшем и Альфредом Реньи (1959, 1960, 1961), после открытия Эрдёшем того, что случайный анализ зачастую удобен для решения проблем теории графов. Далее, мы, приводим основные факты теории случайных графов, концентрируя внимание, в основном на материале, напрямую связанном со сложными сетями.

2.1 Модель Эрдёша-Реньи

В своей первой статье по случайным графам, Эрдёш и Реньи  определяют случайный граф как N помеченных вершин, соединенных n ребрами, которые выбираются случайным образом из   возможных (Эрдёш и Реньи 1959). Всего существует   графов с N вершинами и n ребрами, которые образуют вероятностное пространство с равной вероятностью для каждой реализации.

Другое определение  случайного графа называют также  биноминальной моделью. В этом случае, имея N вершин, соединяем каждые 2 из них с вероятностью p. В конечном итоге, полученное количество ребер будет случайной величиной с ожидаемым значением N → ∞. Если G₀ — граф с вершинами P₁, P₂, …, P_N и n ребрами, вероятность получить его с помощью этого процесса составит  .

Теория случайных графов изучает вероятностное пространство графов с N вершинами при N → ∞. Многие свойства таких случайных графов могут быть получены с помощью случайного анализа. С этой точки зрения Эрдёш и Реньи определили, что каждый граф обладает свойством Q, если при N → ∞, вероятность выполнения Q равна 1. Среди вопросов, рассмотренных Эрдёшем и Реньи, некоторые имеют прямое отношение к сложным сетям. Например, такие: Является ли стандартный граф связным? Содержится ли в нем треугольник из соединенных вершин? Каким образом диаметр зависит от размеров графа?

Процесс создания случайного графа в литературе часто называют эволюцией: начиная с N изолированных вершин, граф последовательно развивается благодаря добавлению новых случайных ребер. Графы, полученные на разных стадиях этого процесса, соответствуют все большим и большим вероятностям p, в конце концов, получаем полный граф (имеющий максимальное количество ребер  ) при p = 1.

Основная идея теории случайных графов состоит в том, чтобы определить при какой вероятности p будет проявлено некоторое свойство. Наибольшее открытие Эрдёша и Реньи том, что многие важные свойства случайных графов начинают проявляться довольно внезапно. То есть, при заданной вероятности, либо практически каждый граф обладает свойством Q (состоящем, например, в том, что каждая пара вершин соединена последовательными ребрами), либо практически ни один граф им не обладает. Переход от вероятного к маловероятному событию происходит при этом очень резко. Для многих из таких свойств существует критическая вероятность pc(N). Если p(N) возрастает медленнее, чем pc(N) при N → ∞, то практически ни один граф не будет обладать свойством Q. Если p(N) возрастает несколько быстрее, чем pc(N), практически любой граф будет обладать свойством Q. Таким образом, вероятность того, что граф с N вершинами и функцией распределения ребер p = p(N) обладает свойством Q, задается таким образом:

Наконец, в теории случайных  графов вероятность определена как  функция от размера системы: p представляет собой дробь от наибольшего возможного количества вершин  . Графы большего размера с тем же самым p будут содержать больше ребер, и, в конце концов, такие свойства, как появление циклов, скорее проявятся в них, чем в графах меньшего размера. Это означает, что для многих свойств случайных графов нет единственного (не зависимого от N) допуска и что мы должны определить функцию допуска, зависящую от размера системы, при  . С другой стороны, можем утверждать, что средняя степень графа имеет критическое значение, не зависящее от размера системы. В следующем подразделе мы проиллюстрируем эти идеи путем рассмотрения появления различных подграфов случайных графов.

2.2 Подграфы

Первым свойством случайных  графов, изученным Эрдёшем и Реньи (1959), было появление подграфов. Граф G₁, состоящий из множества P₁ вершин и множества E₁ребер, является подграфом графа G = {P, E}, если все вершины E₁ также являются вершинами E. Простейшими примерами подграфов являются циклы, деревья и полные подграфы. Цикл порядка k — это замкнутый путь из k ребер, в котором только два последовательных ребра имеют общую вершину. Таким образом, треугольник — это цикл 3-го порядка, а четырехугольник — 4-го. Средняя степень цикла равна 2, поскольку каждая вершина имеет 2 ребра. Противоположность циклам составляют деревья, которые не могут образовывать замкнутый контур. Точнее, деревом порядка k является граф, не имеющий циклов, у которого k вершин иk−1 ребер. Средняя степень дерева порядка k составляет <k> = 2 − k ⁄ 2 и стремится к 2 для больших деревьев. Полные подграфы порядка k содержат k вершин и все из возможных   ребер, другими словами, все их вершины соединены.