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

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

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

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

 

 

 

 

 

 

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

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

 

 

 

 

 

 

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

 

 

РЕФЕРАТ

 

 

 

 

Студентки 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 вершин и все из возможных   ребер, другими словами, все их вершины соединены.

В теории случайных графов имеется точный ответ на этот вопрос (Bollobas 1985). Рассмотрим случайный граф G = G(N, p). Дополнительно рассмотрим небольшой граф F, состоящий из k вершин и l ребер. В принципе, случайный граф G может содержать несколько таких подграфов. Во-первых, определим, сколько таких подграфов существует. k вершин могут быть выбраны из общего числа N вершин   способами, а l ребер могут быть образованы с вероятностью p^l. К тому же, мы можем переставлять k вершин и в итоге получить k! новых графов (точное значение равно  , где a — количество взаимно изоморфных графов). Таким образом, ожидаемое количество подграфов F графа G составит   Подразумеваем, что реальное число таких подграфов может отличаться от E(X), но в большинстве случаев оно будет соответствовать данному выражению. Заметим, что подграфы не должны быть изолированными, то есть могут существовать вершины, имеющие свое начало в подграфе, а конец — вне его. Уравнение показывает, что если p(N) таково, что   при N → ∞, ожидаемое количество подграфов E(X) → 0, то есть, практически ни один из случайных графов не содержит подграфа F. С другой стороны, если  , количество подграфов будет конечным числом, определяемым  , что говорит о том, что эта функция может быть критической вероятностью. Правильность этого утверждения может быть проверена расчетами распределения количества подграфов P_p(X = r), что дает (согласно Боллобашу 1995):

Вероятность того, что  граф G содержит, по крайней мере, один подграф F, составляет в таком случае

что стремится к 1 при  увеличении c. Для значений p, удовлетворяющих   вероятность   стремится к 1, тем не менее, критическая вероятность того, что практически каждый граф содержит подграф с k вершинами и l ребрами, составляет P_p(X = r)

Некоторые важные свойства:

1. Критическая вероятность наличия дерева порядка k составляет 
2. Критическая вероятность наличия цикла порядка k составляет 
3. Критическая вероятность наличия полного подграфа порядка k составляет 

2.3 Распределение степеней

Эрдёш и Реньи (1959) были первыми, кто изучил распределение максимальных и минимальных степеней в случайном графе, полное распределение степеней было получено позднее Боллобашом (1981). В случайном графе с вероятностью связности p степень k_i вершины i следует биномиальному распределению с параметрами N−1 и p:

   (*)

Эта вероятность представляет количество способов, которыми k ребер могут быть проведены из определенной вершины: вероятность для k ребер составляет p^k, вероятность отсутствия дополнительных ребер составляет (1−p)^N−1−k и существует   эквивалентных способов выбора k конечных точек для этих ребер. Тем более, если вершины i и j являются различными, P(k_i = k) и P(k_j = k) близки к тому, чтобы быть независимыми случайными переменными. Для нахождения распределения степеней графа, необходимо изучить количество вершин со степенью k (обозначим X_k). Нашей основной целью будет определить вероятность того, что X_k принимает заданное значение P(X_k = r)

Согласно (*), ожидаемое количество вершин со cтепенью k составит  , где  . C хорошим приближением для распределения степеней в случайном графе подходит биномиальное распределение  , которое для больших N может быть заменено распределением Пуассона:

2.4 Связность и диаметр

Диаметр графа — наибольшее расстояние между двумя любыми его  вершинами. Точно выражаясь, диаметр несвязного графа (например, образованного несколькими изолированными кластерами) бесконечен, но может быть определен, как максимальный из диаметров его кластеров. Случайные графы имеют малый диаметр, при условии, что p мало. Причина этого в том, что случайный граф кажется расширяющимся: с большой вероятностью количество вершин с расстоянием l от выбранной вершины пропорционально ln(N) ⁄ ln(<k>), то есть, оно логарифмически зависит только от количества вершин. Диаметр случайных графов изучался многими людьми (Chang, Lu 2001). Общий вывод состоит в том, что для большинства значений p, практически все графы имеют один и тот же диаметр. Это значит, что, когда мы рассматриваем все графы с N вершинами и вероятностью связности p, диаметры могут лишь незначительно отличаться, обычно находясь около значения

2.5 Кластерный коэффициент

Если мы рассмотрим вершину  случайного графа и ее ближние  соседние вершины, вероятность того, что две соседние вершины соединены, равна вероятности того, что две  случайно выбранных вершины соединены. В итоге, кластерный коэффициент случайного графа составляет:

 

3. Модель Эрдеша-Реньи

Этот раздел мы посвятим описанию модели случайного графа, которая  возникла исторически первой. На рубеже 50-ых и 60-ых годов ХХ века эту модель предложили классики современной комбинаторики и теории вероятностей П. Эрдеш и А. Реньи (см. [1], [2], [3]). Отметим, что Эрдеш –

это, пожалуй, одна из самых  ярких фигур в математике ХХ века. Ему принадлежат сотни статей и задач, которые оказали огромное влияние на развитие многих математических дисциплин. Реньи также сыграл значительную роль в формировании венгерской вероятностной школы, и его именем назван математический институт в Будапеште.

Зафиксируем натуральное число n и рассмотрим множество V ={1,…,n}. Таким образом мы задали множество вершин случайного графа. Зададим полный граф K_n    на множестве вершин V . Пронумеруем ребра K_n : e ₁…,e_N , где . Зададим некоторое  и будем выбирать ребра из множества e ₁…,e_N    согласно схеме Бернулли. Мы получили случайный граф G = (V,E) . Формально выражаясь, мы имеем вероятностное пространство , в котором:

 Таким образом, в модели Эрдеша-Реньи каждое ребро независимо от других ребер входит в случайный граф с вероятностью p. Модель Эрдеша-Реньи на данный момент является самой изученной моделью случайных графов. Приведем несколько наиболее значительных с нашей точки зрения фактов о ней. Будем далее говорить, что случайный граф обладает некоторым свойством почти наверное, если вероятность обладания этим свойством стремится к единице.

Треугольники в случайном графе. Обозначим через T_3,n  случайную величину на пространстве G(n, p) , равную количеству треугольников в случайном графе G . Тогда верны следующие три теоремы:

Теорема 1 Пусть при . Если , то почти

наверное T_3,n = 0 (т.е. граф не содержит треугольников).

Теорема 2 Пусть , где c > 0 – константа. Тогда T_3,n     имеет

 

 асимптотически пуассоновское распределение с параметром .

_{Теорема 3 Пусть при . Тогда если , то}

• Связность случайного графа. Одно из самых интересных свойств модели Эрдеша-Реньи – наличие фазового перехода:

Теорема 4 Пусть . Если c >1, то почти наверное случайный граф

связен. Если c <1, то почти наверное случайный граф связным не является.

Теорема 5 Пусть  . Тогда при любом c <1 существует такая

константа b = b(c) > 0, что почти наверное каждая компонента случайного графа имеет не более blnn вершин. При любом c >1 существует такая константа g = g(c) (0,1) , что почти наверное среди компонент случайного графа есть одна ( гигантская), число вершин которой не меньше gn .

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

 

4 Наблюдения Барабаши-Альберт

 

В своих статьях [5], [6] и [7] авторы заметили следующие закономерности в веб-графе (графе, вершинами которого являются сайты, а ребра соответствуют ссылкам):

• Веб-граф разрежен (на n вершинах у него mn ребер, m N )

 

• Веб-граф подчиняется феномену «малого мира» (его диаметр 5-7 )

• Он подчиняется степенному закону:

На основании своих наблюдений авторы ввели понятие предпочтительного присоединения (preferential attachment). Рассмотрим процесс генерации

графа. На n -ом шагу мы добавляем новую вершину n с m ребрами, инцидентыми ей, причем вероятность ребра к вершине i пропорциональна степени вершины i (см. Рисунок 1):

 

 

 

 

 

 

 

 

Рис. 1:Добавление вершины на n -ом шагу.

 

Основных проблем со спецификацией модели Барабаши-Альберт две.

 

Во-первых, результирующий граф зависит от начального параметра m . Например, при m =1 модель Барабаши-Альберт описывает генерацию дерева, если начальный граф – тоже дерево. Если начальный граф несвязный, то и все последующие тоже будут таковыми.

 

Во-вторых, трудность с предпочтительным присоединением заключается в случайном выборе вершин (если m ≥2 ), к которым присоединится новая вершина. Например, верна следующая теорема:

 

Теорема 1 Пусть f (n),n≥ 2 – произвольная целочисленная функция, такая что: f (2) = 0 , f (n)≤ f (n+1)≤ f (n)+1 для любых n≥ 2 и при . Тогда существует такой процесс генерации случайного графа T⁽ⁿ⁾ , удовлетвовряющий (1), что с вероятностью 1 в T⁽ⁿ⁾ ровно f (n) треугольников для достаточно больших n .

 

Говоря менее формально, теорема 1 говорит о том, что если вы хотите иметь в графе с n вершинами logn треугольников, есть модель Барабаши-Альберт,

 

которая выдаст такой результат.

 

5 Модель Боллобаша-Риордана

 

5.1. Генерация графа

 

Боллобаш и Риордан предложили следующую спецификацию модели Барабаши-Альберта. Построим последовательность случайных графов {Gⁿ}, в которой у графа с номером n число вершин и ребер равно n . Преобразуем ее в последовательность {Gⁿ}, в которой у графа с номером n число вершин ^{равно n , а число ребер равно kn,k N}

Пусть G¹ = ({1},{(1,1)}) . Предположим, что граф уже построен. Ребер и вершин у него по n-1. Добавим вершину n и ребро (n,i), у которого

 

i {1,…,n}. Ребро (n,n) появится с вероятностью , ребро (n,i) – с вероятностью , причем deg(i) – степень вершины i в графе .

 

Распределение вероятностей задано корректно, т.к.

 

Т.о., граф Gⁿ     построен, и он удовлетворяет принципу предпочтительного присоединения. Теперь перейдем к , у которого по kn вершин и ребер.

Делим множество его вершин на последовательные куски размера k : {1,…,k}, {k+1,…,2k},…,{k(n-1)++1,…,kn}.

 

Каждый кусок примем за новую вершину, а ребра сохраним (ребра внутри куска становятся кратными петлями, ребра между разными кусками – кратными ребрами).

5.2 Основные результаты

 

Оказалось, что модель Боллобаша-Риордана довольно хорошо сходится с эмпирическими данными. За время изучения этой модели было получено огромное множество полезных результатов, мы же приведем только некоторые из них.

Теорема 1. Для любого k ≥2 и любого e > 0

 

При n:10⁷ , что соответствует Интернету образца 1999 года, имеем в (2)

,что совпадает с наблюдениями Барабаши-Альберт.

Теорема 2. Для любого k ≥1 и для любого   

 

.

где     - количество ребер, имеющих вершину i своим левым концом в графе . Т.е мы получили степенной закон . От условия смогли избавиться сравнительно недавно, а для того чтобы получить степень 2.1 (соответствующую реальной степени веб-графа несколько лет назад) вместо 3, надо отойти от модели Боллобаша-Риордана.

Пусть H – фиксированный граф. Обозначим через случайную величину, равную количеству подграфов графа , изоморфных графу H . В работе [9] приведены результаты о математическом ожидании этой величины.

Теорема 2 Пусть k≥2 . Пусть также K₃ – полный граф на трех вершинах. Тогда

 

при .

 

Теорема 3 Пусть фиксированы k ≥2 и l ≥3. Пусть также C_l – цикл на l

 

вершинах. Тогда

при , где c_k,l – положительная константа. Более того, при имеем c_k,l = (k^l ) .

А. Рябченко и Е. Самосват из Яндекса в модели, близкой к модели Боллобаша-Риордана, установили следующий факт:

Теорема 4 Пусть задан граф H , степени вершин в котором равны

d₁ ,…,d_s . Обозначим через #(d_i = m) число вершин в H , степень каждой из которых равна m . Тогда

Зависимость от k занесена в константу .

 

По (6)

что согласуется с теоремой 2. А для K₄    теорема 4 говорит, что его средняя частота в веб-графе постоянна. Т.о., «тетраэдров» в веб-графе почти нет. Следует отметить, что последнее утверждение имеет мало общего со свойствами реального веба: в нем встречаются и тетраэдры, и клики большей мощности. Это связано с действием спамеров и агентств по раскрутке сайтов (групп в социальных сетях). Спам в модели Боллобаша-Риордана не учитывается.

6. Модель LCD [10]

Выделим в пространстве ось абсцисс и зафиксируем на ней 2n точек: 1, 2, 3,…, 2n . Разобьем эти точки на пары, и элементы каждой пары соединим дугой, лежащей в верхней полуплоскости. Полученный объект назовем линейной хордовой диаграммой (LCD). Дуги в LCD могут как пересекаться, так и лежать друг под другом, но не могут иметь общих вершин. Количество различных диаграмм равно

 

_{По каждой диаграмме построим граф с} n _{вершинами и} n _{ребрами. Процесс} построения описан в алгоритме 1 и показан на рис. 2.

 

 

 

 

 

_{Рис. 2: LCD модель}

 

 

 

 

 

 

 

 

Алгоритм 1

 

Теперь считаем LCD случайной, т.е. полагаем вероятность каждой диаграммы равной 1/l_n , где l_n      – общее число диаграмм из (7). Т.о. мы получаем случайные графы. В [7] показано, что такие графы по своим вероятностным характеристикам почти неотличимы от графов   (см. предыдущий пункт). Графы с n вершинами и kn ребрами получаются так же, как и в модели Боллобаша-Риордана.

7. Модель Buckley-Osthus

 

Buckley, Osthus и другие исследователи предложили модификацию модели Барабаши-Альберт,  в которой вершины обладают «изначальной привлекательностью» («initial attractiveness»): вероятность того, что старая вершина будет выбрана соседом новой вершины пропорциональна ее входящей     степени     (in-degree)    плюс     константе,     т.е.     «изначальной привлекательности», т.е. am , где m – число ребер, входящих в новую