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

вершину. Если a =1, то мы просто получаем модель Барабаши-Альберт, т.к.

_{там используется полная степень, а каждая исходящая степень равна} m_. Buckley и Osthus в работе [11] обобщили результат для произвольной привлекательности a .

Для произвольного фиксированного положительного целого a граф

определяется так же, как и    в модели Боллобаша-Риордана, но при этом вероятность выбора старой вершины   определяется по-другому (см. статью [11] или обзор [9]). Оказывается, в этой модели распределение степеней тоже   подчиняется степенному закону. Если обозначить через число вершин

графа с входящей степенью d , то при определенных условиях:

 

8. Модель копирования 

 

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

 

Фиксируем a (0,1) и . В качестве начального графа возьмем _{любой d -регулярный граф. Пусть построен граф с номером} t_{. Обозначим его} через    причем s отличается от t на число вершин начального графа, т.е. на константу, выражаемую через d . Добавим к G_t новую вершину u_s+1    и d ребер, выходящих из u_s+1.

Для этого сначала случайно выберем вершину . Затем строим ребра из u_s+1 в V_t . На шаге с номером i, 1≤i≤d , бросаем неоднородную монетку (падает решкой с вероятностью a, орлом – с вероятностью 1-a). Если выпала решка, то выпускаем ребро из u_s+1    в случайную вершину из V_t . Если выпал орел, то ^{берем i -го по номеру соседа p. Последнее действие всегда возможно, т.к.} исходный граф d -регулярен.

8.2 Основной результат

_{Теорема. Пусть Nt,r    – математическое ожидание числа вершин степени} r _в графе  G_t . Тогда

Если вероятность копирования близка к 1 (a близка к 0), то показатель степени в (8) близок к 2.1, что соответствует наблюдениям Барабаши-Альберт. Также в модели копирования есть плотные двудольные графы, которые соответствуют спамерским структурам, отсутствующим в модели Боллобаша-Риордана.

9. Ориентированные безмасштабные графы

Большинство безмасштабных моделей описывают только неориентированные графы. Но поскольку большинство реальных сетей ориентировано, то логично создать ориентированные модели, в которых предпочтительное присоединение зависит от входящих и исходящих степеней. Такая модель была предложена Боллобашем, Риорданом и др. в работе [12]. В этой модели тоже получается степенной закон для входящих и исходящих степеней вершин.

 

10 Модель Чунг-Лу

 

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

 

Пусть нам задано некоторое конечное множество вершин V ={v₁ ,…,v_n} и

 

степень каждой вершины Генерация графа G = (V,E) происходит

следующим образом:

 

• Формируем множество L, состоящее из d_i копий v_i для каждого i от 1 до n .

• Задаем случайные паросочетания на множестве L.

 

• Для вершин u и v из Vs количество ребер в графе G , соединяющее их, равно числу паросочетаний между копиями u и v в L.

 

Сгенерированный таким образом граф соответствует степенной модели , описывающей графы, для которых:

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

• Почти наверное при β <1 граф связен.

 

• При 1< β < 2 в графе есть гигантская компонента, при этом все остальные компоненты имеют размер O(1) .

 

• При 2 < β < β₀      в графе есть гигантская компонента, при этом все остальные компоненты имеют размер O(logn).   – решение уравнения z(b-2)-2z(b-1) = 0 .

 

• При β = 2 меньшие компоненты имеют размер O(logn / loglogn)

 

• При β > β₀ в графе почти наверное нет гигантской компоненты.

 

10.3. Сравнение с реальными сетями

 

Авторы проверяли гипотезу на графе звонков (максимальное число узлов 47·10⁶ ). Качественно, прогнозы авторов верны (см. иллюстрации к статье [3] и ее последний раздел).

 

11. Модель Янсона - Лучака

 

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

 

Рассмотрим упорядоченный набор [n]s из ns вершин. Каждой вершине i присваивается вес W_i . Для простоты и понятности положим их независимо и одинаково распределенными случайными величинами со степенным хвостом:

P(W > x) = ax^-a , x ≥ x₀ , (9)

с некоторыми константами a > 0 и a > 0 , и некоторым x₀ > 0. Мы обозначаем наибольший вес   W _max = _{maxi W i} . Из (9) следует:

Следует отметить, что EW^β < только если a > β . В частности, при a < 2 в случае распределения с экспоненциально неограниченным хвостом (heavy tail case) имеем EW² = .

 

При условии, что нам дан набор весов   соединим каждую пару вершин {i, j} посредством E_ij параллельных ребер, где E_ij – независимые пуассоновские случайные величины с ожиданием:

b > 0 – константа. В результате мы получим мультиграф Ĝ(n,a). Далее мы

 

можем стянуть параллельные ребра в одно, т.о. получив простой случайный граф G(n,a), в котором вершины i и j соединены с вероятностью

 

_Pij =1-exp(-λ_ij ), (12)

 

независимой для всех пар (i, j) таких, что 1≤i < j ≤n .

 

 

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

 

Обозначим за w(G(n,a)) размер максимальной клики в графе G(n,a). В этих

 

обозначениях в модели Янсона-Лучака получены следующие результаты:

Теорема 5

 

(i) Если 0 < a < 2, то

 

ω(G(n,α)) = (c++o_p (1))n^1-α/2 (logn)^--α/2, где

 

c = ab^a/2 (1-a / 2)^-a/2. (13)

 

(ii) Если a = 2 , то ω(G(n,a)) = O_p (1) .

 

(iii) Если a > 2 , то почти наверное ω(G(n,a)) {2,3}. Более того, при

 

Основной задачей при работе с веб-графом является поиск клик в нем. Опишем несколько разных типов клик в модели Янсона-Лучака:

 

• Жадная клика (greedy clique)

 

K_gr ={i:i ~ j для всех j с W_{j >} W_i и j K_gr}.

 

• Quasi top clique

K_qt ={i:i ~ j для всех j с W_{j >} W_i}

 

• Full top clique

 

K_ft ={i: j ~ k для всех различных j,k с W_j , W_k ≥ W_i}.

 

Имеем K _ft K_qt K_gr . Обозначим за K_max     максимальную клику в графе. Тогда

| K _ft |≤ | K_qt | ≤ | K_gr |≤| K_max |= ω (G(n,a)). (16)

Тогда верны следующие теоремы:

 

 

Теорема 6 Если 0 < a < 2, то K_gr и K_qt имеют размер

(1+o_p (1)) ω (G(n, a)) . С другой стороны,

| K_ft | / | K_max | ^p 2^{- α/2}.

_{Теорема 7 Для любого} a _{> 0 сушествует алгоритм, который почти}

наверное находит в G(n, a)    клику размером (1+o_p (1)) ω (G(n, ))  

 

за полиномиальное время.

11.3 Основные результаты для схожих моделей

 

11.3.1 Детерминированные веса

 

Вместо того, чтобы выбирать веса независимо согласно распределению W , можно выбрать их из подходящей детерменированной последовательности W_i (как в модели Чунг-Лу), например

 

В данной модели верными остаются все результаты для модели Янсона-Лучака.

 

12. Получение  и обработка экспериментальных данных из социальных сетей

 

Большие социальные сети (например, Facebook и MySpace) не публикают свой веб-граф, поэтому на текущий момент его характеристики приходится получать экспериментально. Наиболее популярный способ для этого – создание популярных приложений в социальной сети (с числом пользователей не менее нескольких миллионов) и последующий сбор данных их пользователей. Сотрудники центра RUBINET [17] написали три приложения для Facebook с общим числом пользователей около 8 миллионов. Анонимизированные данные, полученные с помощью этих приложений, доступны on-line. Проанализировав различные характеристики пользователей (их географическое расположение, связи друг с другом и другие) и как они различаются в зависимости от типа приложения, исследователи пришли к следующим выводам:

·  Граф отношений (interaction graph) пользователей обладает свойством «малого мира».

·  При этом пользователи неигровых приложений образуют более плотные сообщества, чем пользователи игр. При этом популярность приложений характеризуется степенным законом с экспоненциальным угасанием.

 

Генераторы синтетических веб-графов

 

Поскольку мы считаем разумным использование безмасштабных моделей типа Чунг-Лу [3] и Янсона-Лучака [4], то остановимся на генераторах, способных воспроизводить эти или похожие модели. В известных нам свободно распространяемых генераторах [13], [14], [15], [16] паросочетания реализуются не напрямую, а приближенно (например через введение понятия потенцтального соседа в [16]). Качество работы генератора определяется в сравнении некоторых параметров (например, размера плотных подграфов) получаемого графа с их теоретическими оценками. Наиболее полный отчет приведен авторами генератора DIGG [13].

 

 

Заключение

 

Существующие модели случайных безмасштабных графов можно условно разделить на три класса. В первый класс попадают модели со строгим математическим обоснованием выполнения степенного закона для порождаемых графов, для которых также доказан ряд важных свойств (подсчитан диаметр графа, коэффициент кластеризации, и т.п.), однако, показатель степени фиксирован и не может выбираться заранее. Типичным примером такой модели является модель Боллобаша-Риордана (степень равна 3) и ее обобщения (степень не меньше 2). Ко второму классу можно отнести модели, в которых показатель степенной зависимости может задаваться произвольно, что позволяет изучать эффекты фазовых переходов при его изменении. К числу таких моделей можно отнести модель Чунг-Лу и модель Лучака-Янсона. Доказательство наличия фазового перехода в них по свойству содержать большую клику при переходе степени через значение 2 представляет несомненный интерес и стимулирует исследование других свойств случайных графов с этой точки зрения. Наконец к третьему, самому многочисленному классу, относятся модели, в которых характеристики и свойства графов определяются эмпирически. Про такие модели не доказано никаких содержательных результатов (однако, возможно это дело недалекого будущего). Примерами таких моделей могут являться модель Forest Fire [18] и ряд других.

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

[1] Mark Newman, Albert-Lбszlу Barabбsi, Duncan J. Watts. The Structure and dynamics of networks. Princeton University Press, 2006.

[2] P. Erdцs and A. Rйnyi. On the evolution of random graphs // Publ. Math. Debrecen. 1959. V. 6. P. 290-297.

[3] W. Aiello, F. Chung, L. Lu. A Random Graph Model for Massive Graphs. STOC'2000. [4] S. Janson, T. Јuczak, I. Norros, (2010), Large cliques in a power-law random graph, J. Appl. Probab. V. 47, N. 4 1124-1135.

[5] L.-A. Barabбsi, R. Albert. Emergence of scaling in random networks. Science, 1999. V.286. P. 509-512

[6] L.-A. Barabбsi, R. Albert, H. Jeong. Scale-free characteristics of random networks: the topology of the world-wide web. Physica, 2000. V. A281. P. 69-77.

[7] L.-A. Barabбsi, R. Albert, H. Jeong. Diameter of the world-wide web. Nature, 1999. V. 401. P. 130-131.

[8] R. Kumar, P. Raghavan, S. Rajagopalan, D. Sivakumar, A. Tomkins, E. Upfal. Stochastic models for the web graph. Proc. 41st Symposium on Foundations of Computer Science. 2000.

[9] B. Bollobбs, O. Riordan. Mathematical results on scale-free random graphs. // Handbook of graphs and networks. Weinheim: Wiley-VCH, 2003. P. 1-34.

[10] А.М. Райгородский. Модели случайных графов. МЦНМО, 2011.

[11] P.G. Buckley, D. Osthus. Popularity based random graph models leading to scale-free degree sequence. Discrete Mathematics. Volume 282, Issues 1–3, 6 May 2004, Pages 53–68.

[12] B. Bollobбs, C. Borgs, T. Chayes, O.M. Riordan. Directed scale-free graphs. ProceedingSODA '03 Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms

[13] Arthur R. Brady. A compact routing scheme for power-law networks using empirical discoveries in power-law graph topology. http://digg.cs.tufts.edu/readings/pdf/021.pdf

[14] Deepayan Chakrabarti et al. R-MAT: A Recursive Model for Graph Mining. http://www.cs.cmu.edu/ christos/PUBLICATIONS/siam04.pdf

[15] A. Medina et al. BRITE: Universal Topology Generation from a User’s Perspective. http://www.cs.bu.edu/brite/publications/usermanual.pdf

[16] Joel C. Miller, Aric Hagberg. Efficient Generation of Networks with Given Expected Degrees. WAW, 2011.

[17] Atif Nazir, Saqib Raza, Chen-Nee Chuah. Unveiling Facebook: a measurement study of social network based applications. IMC'08.

[18] J. Leskovec, J. Kleinberg, and C. Faloutsos. Graph evolution: Densification and shrinking diameters. ACM Transact. on Knowledge Discovery from Data, 1(1), 2007.

[19] Колчин В. Ф. Случайные графы. 2-е изд. — М.: ФИЗМАТЛИТ, 2004.

[20]Сергей Косухин http://rain.ifmo.ru/cat/view.php/theory/graph-general/random-2005

[21] Берновский М.М., Кузюрин Н.Н. Случайные графы, модели и генераторы безмаштабных графов.