Свойства случайных веб-графов, основанных на предпочтительном присоединении тема автореферата и диссертации по математике, 01.01.05 ВАК РФ

ФГБОУ ВО "Московский государственный университет имени М.В. Ломоносова"

На правах рукописи

Прохоренкова Людмила Александровна

СВОЙСТВА СЛУЧАЙНЫХ ВЕБ-ГРАФОВ, ОСНОВАННЫХ НА ПРЕДПОЧТИТЕЛЬНОМ ПРИСОЕДИНЕНИИ

Специальность 01.01.05 — теория вероятностей и математическая статистика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

2 7 МАП 2015

Москва — 2015

005569491

005569491

Работа выполнена на кафедре математической статистики и случайных процессов механико-математического факультета ФГБОУ ВО "Московский государственный университет имени М.В. Ломоносова".

Научный руководитель: Райгородский Андрей Михайлович

доктор физико-математических наук, профессор

Официальные оппоненты: Павлов Юрий Леонидович

доктор физико-математических наук, профессор заведующий лабораторией теории вероятностей и компьютерной статистики ФГ'БУН Института прикладных математических исследований Карельского научного центра РАН

Карпов Дмитрий Валерьевич кандидат физико-математических наук старший научный сотрудник Санкт-Петербургского отделения Математического института им. В.А. Стеклова РАН

Ведущая организация: Хабаровское отделение ФГБУН Института

прикладной математики ДВО РАН Защита состоится 24 июня 2015 года в 16 часов 45 минут на заседании диссертационного совета Д 501.001.85 на базе ФГБОУ ВО "Московский государственный университет имени М.В. Ломоносова", по адресу: 119991, Москва, ГСП-1, Ленинские горы, д. 1, МГУ, Механико-математический факультет, аудитория 16-24.

С диссертацией можно ознакомиться в Фундаментальной библиотеке ФГБОУ ВО "Московский государственный университет имени М.В. Ломоносова" по адресу: Москва, Ломоносовский проспект, д. 27, сектор А и на сайте механико-математического факультета http://mech.math.msu.Su/~E:nark/index.cgi.

Автореферат разослан мая 2015 года.

Ученый секретарь диссертационного совета Д 501.001.85 на базе МГУ доктор физико-математических наук, профессор

Общая характеристика работы

Актуальность

Диссертация посвящена изучению моделей сложных сетей и их свойств. Под сложными сетями понимают всевозможные сети, которые встречаются в природе: компьютерные, биологические, социальные, экономические, транспортные и тал далее. Классический пример такой сети — граф сети Интернет. Вершины графа — это веб-страницы, а ребра — ссылки между ними. С появлением сети Интернет началось интенсивное изучение сложных сетей. Было замечено, что все эти сети обладают некоторыми общими свойствами: малый диаметр, степенной закон распределения степеней вершин, кластерная структура и другие1,2,3,4,5,6. Возник естественный вопрос: почему сети столь различной природы обладают схожими свойствами? Возможно, в основе всех этих сетей лежит какой-то общий принцип формирования? Так стали появляться первые модели сложных сетей, в том числе вероятностные модели7,8,9,10,11,12,13. Вероятностная модель — это случайный элемент со значениями в множестве графов и некоторым вероятностным распределением на этом множестве.

В 1999 году A.-JI. Барабаши и Р. Альберт14 предложили моделировать сложные сети с помощью так называемого принципа предпочтительного присоедине-

3М. Girvan and М. Е. Newman. Community structure in social and biological networks. Proceedings of the National Academy of Sciences, 99(12):7821-7826, 2002.

2M.E.J. Newman. Assortative mixing in networks. Pkys. Rev. Letter, 89, 208701, 2002.

3M.E.J. Newman. Power laws, Pareto distributions and Zipf's law. Contemporary Physics, 46, N5, 323-351, 2005.

4M. E. Newman. The structure and function of complex networks. SIAM review, 4ó(2):167-2ó6, 2003.

5R. Pastor-Satorras, A. Vázquez, A. Vespignani. Dynamical and Correlation Properties of the Internet. Pkys. Rev. Lett., 87, N25, 258701, 2001.

6D. J. Watts and S. H. Strogatz. Collective dynamics of 'small-world' networks. Nature S9S, pages 440-442, 1998.

7W. Aiello, F. Chung, L. Lu. A random graph model for power law graphs. Experiment. Math., 10, 53-66, 2001.

8S. Boccaletti, V. Latora, Y. Moreno, M. Chavez, and D.-U. Hwang. Complex networks: Structure and dynamics. Physics reports, 424(4): 175-308, 2006.

9B. Bollobés, Ch. Borgs, J. Chayes, O. Riordan, Directed scale-free graphs. ACM-SIAM Symposium on Discrete Algorithms, 132-139, 2003.

10C. Cooper and A. Rieze. A general model of web graphs. Random Structures and Algorithms, 22(3):311—335, 2003.

nM. Deijfen, H. van den Esker, R. van der Hofstad, and G. Hooghiemstra. A preferential attachment model with random initial degrees. Ark. Mat., 47:41-72, 2009.

12N. Eggemann and S. D. Noble. The clustering coefficient of a scale-free random graph. Discrete Applied Mathematics, 159(10):953-965, 2011.

13P. Holme and B, Kim. Growing scale-free networks with tunable clustering. Physical Review E, 65(2), 2002.

14R. Albert and A.-L. Barabási. Statistical mechanics of complex networks. Reviews of modern physics, 74:47-97, 2002.

ния. Основная идея их подхода состоит в том, что новые страницы, появляющиеся в Интернете, скорее предпочтут сослаться на уже популярные страницы (то есть на те, на которые ведет много ссылок). Работа Барабаши и Альберт послужила толчком к развитию области вероятностного моделирования сложных сетей. Например, Р. Кумар, П. Рагхаван, С. Раджагопалан, Д. Сивакумар, А. Томкинс и Э. Упфал предложили так называемую модель копирования13, в которой некоторые ребра, проведенные из новой вершины, "копируют" ребра одной из предшествующих страниц. Еще изучалась конфигурационная модель15'17, которая позволяет построить граф с заданным распределением степеней вершин. Эта модель может применяться для моделирования графа Интернета, если взять подходящее распределение степеней. Обзор перечисленных и многих других моделей можно найти, например, в работах18'19,20. Модели сложных сетей применяются в различных областях: в математике, физике, биологии, области информационных технологий.

Вероятностное моделирование сложных сетей включает в себя две важные задачи. Первая задача — создание новых моделей, которые лучше моделируют свойства реальных сетей, вторая — изучение характеристик уже существующих моделей.

Наиболее распространенная характеристика сложных сетей — это распределение степеней вершин. А именно, если выбрать случайную вершину в сети и посмотреть на ее степень (количество примыкающих ребер), то получим случайную величину, распределение которой интересно изучать. Для большинства наблюдаемых сетей оказалось, что доля вершин степени d убывает как с некоторым параметром 7, который обычно лежит в интервале (2,3):;1'22'23. Таким образом, принято говорить, что в сложных сетях распределение степеней вершин подчиня-

1SR. Kumar, P. R&ghavan, S. Rajagopalan, D. Sivakumar, A. Tomkins, and E. Upl'al. Stochastic models for the web graph. Proc. 41st Symposium on Foundations of Computer Science, 2000.

,6M. Molloy and B. Reed. A critical point for random graphs with a given degree sequence. Random structures and algorithms, 1995.

17Ю. Л. Павлов. О предельных распределениях степеней вершин условного конфигурационного случайного графа. Труды Карельского научного центра РАН, 5, 2012.

18А. М. Райгородский. Модели случайных графов и их применение. Труды МФТИ, 2(4):130-140, 2010.

19А. М. Райгородский. Модели Интернета. Интеллект, 2013.

20В. Bollobás. Mathematical results on scale-free random graphs. Handbook of Graphs and Networks, pages 1-34 2003.

21A.-L. Barabási and R. Albert. Emergence of scaling in random network. Science, 286(5439):509-512, 1999.

"A. Broder, R. Kumar, F. Maghoul, P. Raghavan, S. Rajagopalan, R. Stata, A. Tomkins, and J. Wiener. Graph structure in the web. Computer Networks, 33(16) :309-320, 2000.

23M. Faloutsos, P. Faloutsos, and C. Faloutsos. On power-law relationships of the internet topology. SIGCOMM Conference, 1999.

ется (асимптотически) степенному закону.

Еще одной важной характеристикой сложных сетей является PageRank24'г5,г6. PageRank — это мера важности (популярности, качества) веб-страниц, он активно используется в информационном поиске. Основная идея Ра§е11апк заключается в том, что важность вершины определяется важностью (степенью, популярностью) ее соседей. Степень вершины является довольно грубым приближением ее Ра§е11апк. Более точное приближение можно получить, если рассматривать так называемую вторую степень вершины, то есть количество путей длины два, ведущих в данную вершину. В данной работе исследуется распределение вторых степеней вершин, а также анализируются к-е входящие степени вершин.

Другой важной характеристикой сети является ее диаметр, то есть максимальная по всем парам вершин длина кратчайшего пути между двумя вершинами. Сложные сети, встречающиеся в природе, имеют малый диаметр (теория б рукопожатий)27. Б. Боллобаш и О. Риордан доказали28, что диаметр графов в классической модели предпочтительного присоединения ведет себя асимптотически как где п — количество вершин в графе. В данной работе вводится обобщение понятия диаметра — г-диаметр. Для г-диаметра классических моделей предпочтительного присоединения тоже удается изучить асимптотическое поведение.

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

"K. Avrachenkov, D. Lebedev. PageRank of Scale-Fi-ee Growing Networks. Internet Math., 3, N2, 207-232, 2006.

25L. Page, S. Brin, R. Motwani, and T. Winograd. The PageRank citation ranking: Bringing order to the Web. Technical report, Stanford University Database Group, 1998.

26G. Pandurangan, P. Raghavan, E. Upfal. Using PageRank to Characterize Web Structure. Internet Math., 3, N1, 1-20, 2006.

27R. Albert, H. Jeong, and L.-A. Barabäsi. Diameter of the world-wide web Nature, 401, 130-131, 1999.

28B. BollobiSs and O. M. Riordan. The diameter of a scale-free random graph. Combinatorica, 24(l):5-34, 2004. Lefortier, L. Ostroumova, and E. Samosvat. Evolution of the media web. In Algorithms and Models for the

Web Graph, pages 80-92. Springer International Publishing, 2013.

Цель работы

1. Обобщить понятие степени вершины и изучить распределение вторых степеней в классических моделях предпочтительного присоединения.

2. Обобщить понятие диаметра графа и изучить асимптотическое поведение г-диаметра в классической модели Боллобаша-Риордана.

3. Предложить вероятностную модель, которая отражает свойство устаревания реальных сетей, а также проанализировать ее свойства.

Научная новизна

Все результаты диссертации являются новыми. Перечислим основные из них:

1. Проанализировано распределение вторых степеней вершин в моделях Бакли-Остхуса и Боллобаша-Риордана. Показано, что это распределение подчиняется (асимптотически) степенному закону [3,4].

2. Введено понятие к-й входящей степени вершины, вычислено математическое ожидание этой величины для вершин графа и модели Боллобаша-Риордана [1].

3. Введено понятие г-диаметра и найдено его асимптотическое поведение в модели Боллобаша-Риордана [2].

4. Предложена модель, которая сочетает в себе идею предпочтительного присоединения и свойство устаревания. Для этой модели доказано, что при определенных условиях распределение степеней подчиняется степенному закону, а также показано, что доля ребер в графе, которые соединяют вершины с разницей "возрастов", большей чем Г, то есть вершины г и ] с |г — Л > Г, убывает экспоненциально с ростом Т [5].

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

Методы исследования

При доказательстве результатов использовалась разнообразная техника. Существенное место в данной работе занимают различные методы доказательства концентрации случайных величин около своего математического ожидания. Например. в задачах, которые возникают в данной работе, можно использовать неравенство Азумы30. Однако, в некоторых случаях оказывается полезнее использовать неравенство Талаграна31. Применение неравенства Талаграна неочевидно в случае моделей предпочтительного присоединения, в частности, нужно переопределить вероятностное пространство модели в терминах независимых случайных величин. Далее, проверка условий применения неравенства Талаграна является сложной комбинаторной задачей.

Теоретическая и практическая ценность

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

Апробация работы

Результаты диссертации докладывались на следующих научно-исследовательских семинарах:

— Неоднократные выступления на семинаре "Вероятностные и алгебраические методы в комбинаторике" под руководством профессора А.М. Райгородского (механико-математический факультет МГУ, 2011-2013 гг.).

-— Кафедральный семинар кафедры математической статистики под руководством профессора А.М. Зубкова (механико-математический факультет МГУ, 2014 г.).

S0K. Azuma. Weighted sums of certain dépendent variables. Tôhoku Math. ]., 19:357-367, 1967.

31M. Talagrand. Concentration of measures and isoperimetric Inequalities in product spaces. Publications Mathématiques de Vl.H.E.S., 81:73-205, 1996.

— Семинар "Динамические системы и статистическая физика" под руководством профессора Б.М. Гуревича и профессора В.И. Оселедца (механико-математический факультет МГУ, 2013 г.).

— Семинар "Дискретный анализ" под руководством профессора А. А. Сапожен-ко (факультет ВМК МГУ, 2013 г.)

— Неоднократные выступления на семинаре под руководством профессора A.M. Райгородского (ФИВТ МФТИ, 2011-2014 гг.).

Результаты диссертации докладывались на следующих международных научных конференциях:

— Международная конференция "Instabilities and Control of Excitable Networks" (Долгопрудный, Россия, май 2012 г.).

— Международная конференция "4th Polish Combinatorial Conference" (Бедлево, Польша, сентябрь 2012 г.).

— Международная конференция "Workshop on Internet Topology and Economics" (Атланта, США, ноябрь 2012 г.).

— Международная конференция "Franco-Russian workshop on Algorithms, complexity and applications" (Москва, Россия, июнь 2013 г.).

— Международная конференция "International Conference on Random Structures and Algorithms" (Познань, Польша, август 2013 г.).

— Международная конференция "Palanga Conference in Combinatorics and Number Theory" (Паланга, Литва, сентябрь 2013 г.).

— Международная конференция "Workshop on Random Graphs and their Applications" (Москва, Россия, октябрь 2013 г.).

— Международная конференция "Workshop on Algorithms and Models for the Web Graph" (Кембридж, США, декабрь 2013 г.).

— Международная конференция "Moscow Workshop on Combinatorics and Number Theory" (Москва, Россия, январь 2014 г.).

— Международная конференция "11th International Vilnius Conference on Probability Theory and Mathematical Statistics" (Вильнюс, Литва, июль 2014 г.).

— Международная конференция "Sum(m)it240" (Будапешт, Венгрия, июль 2014 г.).

Работа автора поддержана грантом РФФИ N 12-01-00683 и грантом Президента МД-6277.2013.1.

Публикации

Результаты диссертации опубликованы в 5 работах автора (4 из них входят в перечень ВАК), список которых приведен в конце автореферата.

Структура диссертации

Диссертация состоит из введения, трех глав и списка литературы, насчитывающего 56 наименований. Общий объем диссертации составляет 119 страниц.

КРАТКОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИИ

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

Содержание главы 1

Первая глава посвящена анализу свойств классической модели Боллобаша-Риордана. Данная глава основана на статьях автора [1,2,4].

В разделе 1.1 приводится определение модели и известные результаты. Обычно для графов в модели Боллобаша-Риордана используется обозначение G™, где п — число вершин, т — фиксированное натуральное число. Граф G^ строится следующим образом. Сначала индуктивно строится G". Граф G\ состоит из одной вершины и одной петли. Граф G\ получается из Gj_1 посредством добавления вершины t и одного ребра между вершинами t и г, где i выбирается случайно

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

Р(г = а) =

dGt-i(s)/(2t - 1) если l^s^t-1, 1/(21 - 1) если s = t.

если s = t.

Здесь ^(в) — степень вершины в в графе С\. Иными словами, чем больше степень вершины в графе С?*-1, тем больше вероятность того, что следующая вершина будет соединена с ней. Граф (т > 1) получается из графа (т™" следующим образом. Первые т вершин С™" объединяются в первую вершину нового графа, следующие т — во вторую, и так далее. Ребра в некотором смысле сохраняются, а именно: если в С™71 ребро соединяло вершины г и то в полученном графе это ребро соединяет те группы вершин, в которые попали г и у. Тем самым в графе могут возникнуть кратные ребра и кратные петли. Построенные таким образом графы образуют вероятностное пространство (5^.

Известно, что граф обладает степенным распределением степеней вершин32.

ТЕОРЕМА 1. Пусть ш ^ 1. Тогда существует такая функция <р аргумента п, что ц> — о(п) при п -» оо, и для любой такой степени й, что то < й < п1/15, мы имеем

Здесь #m(d) — количество вершин степени d в графе

В разделе 1.2 рассматриваются вторые степени вершин в графе G". Сначала оценивается математическое ожидание количества вершин со второй степенью d, затем доказывается концентрация. Случай ш ^ 2 обсужде,ется в главе 2 данной работы.

Второй степенью вершины t 6 G" называем величину

Другими словами, вторая степень вершины I — это количество ребер, соединенных с соседями вершины Ь кроме тех, которые ведут в саму вершину t. Через Хп{й) обозначаем количество вершин второй степени d в С?". В разделе 1.2 доказаны следующие новые результаты.

d2(i) = \{ij :i^t,jyit,ite G", ij € G?}|.

"B. BollobSs, O. M. Riordan, J. Spencer, and G. Tusnady. The degree sequence of a scale-free random graph process. Random Structures and Algorithms, 18(3):279-290, 2001.

ТЕОРЕМА 2. Для любого к > 1 имеем

ТЕОРЕМА 3. Для любого е > 0 существует такая функция <р аргумента п, что кр = о(п) при п —» оо, и

Um Р (|X„(fc) - EXn(fc)| > = О

для любого такого к, что 1 ^ к ^ п1/6_е.

Эта теорема показывает, что для любого к, 1 ^ к ^ с вероятностью,

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

При доказательстве теоремы 3 о концентрации используется мартингальное неравенство Азумы33.

В разделе 1.3 изучаются к-е степени вершин. К определению к-й степени вершины можно подходить ио-разному. Первое возможное определение к-й степени вершины t в некотором графе — количество ребер, которые выходят из вершин, находящихся на расстоянии к — 1 от í, кроме тех, которые ведут в вершины, находящиеся на расстоянии к — 2 от í. Кроме того, можно определять к-ю степень вершины t как количество вершин, находящихся на расстоянии к от нее.

В графе предпочтительного присоединения вводится естественная ориентация ребер — от вершин с большими номерами к вершинам с меньшими. Таким образом, можно рассматривать "входящую" степень вершин. Определим ее сперва по аналогии с первым определением. Будем пока рассматривать только граф GПусть множества Dt(t) определяются индуктивно следующим образом: A)(í) = {t}, для

Dk{t) = {г : г g DQ(t) U D^t) U ... U Dfc_i(t), 3 j G Dk-i{t), ij € G"}.

Когда будем писать ij € G^, будем иметь в виду, что направленное ребро из вершины i в вершину j проведено в графе Таким образом, DyXt) — множество

33К. Azuma. Weighted sums of certain dependent variables. Tôhohu Math. J., 19:357-367, 1967.

вершин i, от которых можно добраться до вершины t самое меньшее за к шагов, двигаясь все время по направленным ребрам. Далее, пусть

Sk(t) = {ji : г 6 Dk-i(t), ji £ 6?"}, k^l.

Величина |5i(i)| = dk(t) и есть к-я входящая степень вершины. Считаем do(t) = 1. Кроме того, можно было бы назвать fc-й входящей степенью вершины t количество вершин, находящихся от t на "входящем" расстоянии к, то ость |Dfc(i)|. Заметим, что в графе G" при к > 1 оба определения совпадают.

В данном разделе для графа G" вычисляется величина Egk(t), где gk(t) = dfc(t) + dfc-i(i),

Для графа G^ вычислена немного другая величина. Пусть D'k(t) — множество таких вершин графа G^, из которых можно добраться до вершины t ровно за к шагов, двигаясь все время по направленным ребрам (но не по петлям). При этом возможность добраться за меньшее количество шагов допускается. Считаем D'0(t) = {t}. Положим d'k(t) = \D'k(t)\. Вычисляем величину Еg'k{t), где g'k(t) = d'bfy+md'j.^t). Для тп = 1 при к > 2 эта величина не отличается от определенной ранее, поскольку в графе G" между двумя вершинами не может быть больше одного направленного пути.

Сформулируем основные результаты раздела 1.3. Сначала рассматривается граф G?. Определим функцию fk(t,n). Пусть f0(t,n) = 1, а для к > О

ТЕОРЕМА 4. Для любого натурального к ^ 2 и любой вершины t <п в графе G"

%*(i) = fk(t, п) (1 + в(к, t, n)) (1 + 0Х(4))*, где |ö(fc,i,n)| sS G^^-^, |0i(i)| ^ Ci\, С и Ci - некоторые константы.

Посмотрим, при каких условиях на к и t мы получаем асимптотику. Чтобы получить 16(к, t, я)| = о( 1), надо взять к = o(y/t In2). Тогда при t ^ Inn имеем (l + 0i(i))fc = 1 + о(1). Чтобы

иметь возможность взять к ^ 2, надо наложить ограничение t < га — гп(п), где w(n) стремится к бесконечности с ростом п.

СЛЕДСТВИЕ 1. Пусть w(n) -> оо при тг -»• оо. Пусть, далее, Inn ^ £ < п - w(n) и к — о(у/Пnf), к ^ 2. Тогда

= (1+о(1))

при п —» 00.

Далее от графа G" переходим к графу G™ с тп ^ 2. Доказана следующая теорема.

ТЕОРЕМА 5. Пусть натуральные т ^ 2 и к ^ 1 фиксированы. Тогда для t <п

«^^('"(¡аи))-

В разделе 1.4 изучается некоторое обобщение понятия диаметра — г-диаметр:

diamr(G) = max min p(i,j).

ACV i,jeA И|=Г

Иными словами, здесь рассматриваются не пары вершин, как в обычном диаметре, а подмножества мощности г. В каждом таком подмножестве мы находим две вершины на наименьшем расстоянии друг от друга. И нас интересует максимум этого расстояния по всем подмножествам. Заметим, что при г = 2 имеем в точности обычный диаметр графа G.

В 2004 году Боллобаш и Риордан доказали следующую теорему34.

ТЕОРЕМА 6. Для любого г > 0 и любого натурального т ^ 2

lim Р ((1 - < diam(GJJj) < (1 + е)^-) = 1.

П-+00 lnlnn lnlnn/

В разделе 1.4 доказано подобное утверждение для r-диаметра. А именно

ТЕОРЕМА 7. Пусть е > 0 и натуральное т ^ 2 фиксированы. Пусть, далее, г(п) — произвольная последовательность целых чисел, лежащих в пределах от 2 доп. Тогда

У D fi1 -е) Inn-In г (l + e)lnn-lnr\

lim Р ^-f--sS diamr(GJ5,) s* --- = 1.

П-+00 ^ lnlnn lnlnn )

Как и ожидалось, чем больше вершин в рассматриваемых множествах, тем меньше г-диаметр. Отметим, что если для любого а > 0 выполнено г(п) = о (па), т.е. г(п) = то результаты теорем 6 и 7, по существу, идентичны. Если же,

МВ. Bollob&s and О. М. Riordan. The diameter of a scale-free random graph. Combinatorial, 24(l):5-34, 2004.

например, r(n) = па, а > 0, то константа в асимптотике из теоремы 7 принципиально другая: 1 ± е превращается в 1 — а ± е. Если, наконец, г(п) = п1-0'1', то асимптотики в теореме 7 нет.

Содержание главы 2

В данной главе рассмотрена модель, которая является обобщением модели Бол-лобаша и Риордана. С целью сделать модель более гибкой, две группы авторов35'36 предложили добавить в модель новый параметр — "привлекательность" вершины (константа, не зависящая от степени). Бакли и Остхус дали строгое определение этой модели37. Модель позволяет получить степенное распределение степеней вершин с любым параметром из (2;оо). В главе 2 проанализировано распределение вторых степеней вершин в модели Бакли-Остхуса. Глава основана на работе автора [3].

Дадим строгое определение рассматриваемой модели. Пусть п — количество вершин в графе, a m € N и а € ¡R+ — фиксированные параметры. Сначала рассмотрим случай т = 1 и индуктивно построим граф Граф Н\х состоит из одной вершины и одной петли. Предположим, что граф уже построен. На шаге t в граф добавляется одна вершина t и одно ребро между вершинами t и i, где i выбрана случайно следующим образом:

Здесь djjtJ^s) — степень вершины s в графе Нга1.

Граф Щт с m > 1 получается из графа Вершины 1 ,...,тп образуют первую вершину нового графа; вершины m + 1,..., 2т — вторую; и так далее. А ребра сохраняются: если ребро е соединяло вершины im + k и jm + l, 1 < к, I < m в графе H™", то в графе Щт будет проведено ребро е' между вершинами i + 1 и j + 1. Как и в случае графа Боллобаша-Риордана, в данном случае могут возникать петли и кратные ребра. Через f)" m обозначим полученное вероятностное пространство.

35S. N. Dorogovtsev, J. F. F. Mendes, and A. N. Samukhin. Structure of growing networks with preferential linking. Phys. Rev. Lett., 85, 4633, 2000.

36E. Drinea, M. Enachescu, and M. Mitzenmacher. Variations on random graph models for the web. technical report, Harvard University, Department of Computer Science, 2001.

37P. G. Buckley and D. Osthus. Popularity based random graph models leading to a scale-free degree sequence. Discrete Mathematics, 282:53-63, 2004.

P(t = s)=

d„t_i(s)-l+tt

если 1 ^ s ^ t — 1

a

если s — t.

(a+l)t-l

Бакли и Остхус доказали, что распределение степеней в графе #"т подчиняется степенному закону с параметром —2 — а, если а — натуральное число. Напомним, что второй степенью вершины t £ j мы называем

d2{t) = \{ij t,tt е Hiuij е ,

то есть количество ребер, смежных с соседями вершины i, кроме тех, кроме смежны с самой вершиной t. Вершину t назовем к-вершиной. если d^it) > к. Через Yn(k) обозначим количество fc-вершин в Н"д- Кроме того, рассматривается величина Хп(к), равная количеству вершин второй степени к в Щх- Очевидно, что

В главе 2 доказано, что Yn(k) убывает как к а. Это значит, что распределение вторых степеней также подчиняется степенному закону. Чтобы доказать это, сначала оценивается математическое ожидание величины Yn(k), а затем показывается концентрация этой величины около математического ожидания за счет неравенства Талаграна. Применение неравенства Талаграна в данном случае неочевидно, в частности, нужно переопределить вероятностное пространство модели Бакли-Остхуса в терминах независимых случайных величин. После этого, неравенство Талаграна применяется в его общей несимметричной форме. Далее, проверка условий применения неравенства Талаграна является сложной комбинаторной задачей.

Математическое ожидание Yn(k) удается оценить следующим образом.

ТЕОРЕМА 8. Для любого к > 1 имеем

Из теоремы 8 несложно получить следующее следствие.

СЛЕДСТВИЕ 2. ЕУ„(А;) = 6 (£) дляк = 0 (п^).

Используя ту же технику, что и в доказательстве теоремы 8, можно доказать следующий результат.

ТЕОРЕМА 9. Для любого к ^ 1 имеем

Из этой теоремы не сложно получить следующее следствие. СЛЕДСТВИЕ 3. КХп(к) = 0 (jfe) для к = 0 (тг^г).

Далее, доказана теорема о концентрации. ТЕОРЕМА 10. Пусть 6 > 0 и к — О (n^+s^j. Тогда для некоторого е > 0 имеем

Р (|ВД -Е(ВД)| > (Е(ВД))1-') = о(1).

Можно также доказать подобный результат для величины Хп(к). ТЕОРЕМА 11. Пусть 6 > 0 и к = О (п^+Ъз j. Тогда для некоторого е > 0 имеем

Р (|ад -E(X„(fc))| > (ЕСВД))1"') = о(1).

Содержание главы 3

Если предыдущие две главы посвящены анализу классических моделей, то в главе 3 вводится новый класс моделей, основанных на идее предпочтительного присоединения, а именно — модели с устареванием. Глава основана на статье автора [5].

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

В главе 3 рассматривается величина е(Т) — доля ребер в графе, которые соединяют вершины с разницей "возрастов", большей чем Т, то есть вершины inj с \i—j\ > Т. Известно38, что в некоторых реальных сетях е(!Г) убывает экспоненциально с ростом Т.

3SD. Lefortier, L. Ostromnova, and E. Samosvat. Evolution of the media web. In Algonthms and Models for the Web Graph, pages 80-92. Springer International Publishing, 2013.

Класс моделей, который обсуждается в данной главе, является обобщением модели Бианкони и Барабаши39, которая, в свою очередь, обобщает модели предпочтительного присоединения добавлением качества (fitness) вершин. В модели Бианкони и Барабаши, когда новая вершина добавляется в граф, она выбирает вершину, в которую проведет ребро, с вероятностью, пропорциональной произведению качества этой вершины и степени. В данной работе в функцию привлекательности вершины добавляется множитель, соответствующий устареванию вершины. Таким образом, вероятность того, что в данную вершину будет проведено новое ребро, определяется привлекательностью вершины, которая, в свою очередь, зависит от входящей степени вершины (текущая популярность), ее качества (некоторая константа) и возраста (новые страницы обладают большей привлекательностью).

В разделе 3.2 дано формальное определение модели с устареванием. А именно, рассматривается последовательность случайных графов {G„}. У этой последовательности есть следующие параметры: натуральное число т (количество ребер, добавляемых вместе с новой вершиной) и функция N(n), принимающая целочисленные значения. Нам также потребуется последовательность независимых положительных случайных величин Ci, Сг > • • • с некоторым распределением. Каждый граф G„ определяется в соответствии со своей собственной процедурой построения, которая основана на идее предпочтительного присоединения.

Случайный граф Gn определяется следующим образом. В начале процедуры построения имеем две вершины и одно ребро между ними (граф Gi?). Первые две вершины имеют качества q{ 1) и q(2) := £2- На шаге t + 1 (2 < t < п — 1) к графу G" добавляется одна вершина и т ребер. Новая вершина t + 1 имеет качество q(t 4- 1) := Ct+i- Новые ребра проводятся независимо друг от друга, и они соединяют новую вершину с одной из предыдущих вершин. Для каждого ребра вероятность того, что оно будет проведено в вершину г (1 ^ i ^ i), равна

attrt(z) E^iattr^j)'

где

attrt(i) = (1 or q(i)) • (1 or £¿¿00) • (l or I[i > t - AT(n)] or e"7^)

Bianconi and A.-L. Barab&si. Bose-Einstein condensation in complex networks. Physical Review Letters, 86(24):5632-5635, 2001.

и dt(i) — степени вершины i в G". Далее мы опускаем п в оэозначении N(n). Согласно определению, в графе нет петель, однако могут возникать кратные ребра.

Важно заметить, что, в отличие от стандартного определения предпочтительного присоединения, в нашем случае граф Gn не может быть получен из графа G„_i. Каждый граф строится в соответствии со своей собственной процедурой, которая, в свою очередь, основана на предпочтительном присоединении. Такое необычное определение позволяет теоретически исследовать распределение степеней и поведение функции е(Т) в графе.

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

В разделе 3.3 рассматривается модель с функцией привлекательности q(i)I[i > t — N]. Фактор устаревания в данном случае означает то, что вершина i может получить входящие ребра только в течение следующих N шагов после появления, и этот период называется жизнью вершины.

Мы также предполагаем, что случайные величины Ci> Cs> ■ • • имеют распределение Парето с плотностью f(x) = где 7 > 1, а > 0.

В итоге у случайного графа есть несколько параметроз: 1) количество вершин п, 2) исходящая степень вершин тп, 3) продолжительность жизни N, 4) параметр распределения качества 7, 5) минимальное качестве! а.

В параграфе 3.3.1 показано, что степенное распределение качества ведет к степенному распределению степеней вершин в графе.

Через #(cZ) обозначим количество вершин степени d в графе G„. Доказана следующая теорема.

ТЕОРЕМА 12. Пусть d = d(n) растет с ростом nud= о ((77)^) • Если 7 > 2 ud = о или 1 < 7 < 2 ud = о для некоторого а, 1 < а < 7, то

Теорема 12 говорит о том, что математическое ожидание количества вершин степени d убывает как Однако, чтобы показать степенное распределение

степеней вершин, необходимо также доказать концентрацию количества вершин степени с? около своего математического ожидания.

ТЕОРЕМА 13. Для любого й выполнено:

Р (|#(с0 - Е#(<*)| ^ ^

Заметим, что для й = о имеем у/Ып 1п п = о (п/<Р+1), поэтому

теорема 13 действительно дает концентрацию.

В параграфе 3.3.2 изучается свойство устаревания. Напомним, что е(Т) — доля ребер в графе, которые соединяют вершины с разницей возрастов, большей чем Т, то есть такие вершины г и j, что |г — Л > Т. В этом параграфе показано, что в рассматриваемой модели е(Т) убывает линейно.

ТЕОРЕМА 14. Для любого натурального Т

1о, если Т > N.

ТЕОРЕМА 15.

Р||е(Т)-Ее(Г)|^ < 1

п I тп1пп

В разделе 3.4 изучается модель с экспоненциальным фактором устаревания. То есть функция привлекательности имеет вид д(г)е~~я\ Опять же, предполагаем, что случайные величины Сг, Сг, • • • имеют распределение Парето с плотностью

Дат) = где 7 > 1, о > о.

В параграфе 3.4.1 проанализировано распределение степеней в этой модели. Полученные результаты похожи на результаты для модели с индикатором.

ТЕОРЕМА 16. Пусть й = й(п) растет с ростом п и в, — о ((туЩ/)^) • Если

7 > 2 и й = о ^У5^^ или 1<7<2 и — о для некоторого а,

1 < а < 7, то

п (Р+1 \ 7

Опять, математическое ожидание количества вершин степени <1 убывает как ¿-7-1 Следующая теорема показывает, что количество вершин степени <1 сконцентрировано около своего математического ожидания.

ТЕОРЕМА 17. Для любого й выполнено следующее неравенство:

Р (|#(<*) - Е#(й)| > = О (д-) .

и тео-

рема 17 дает концентрацию.

В параграфе 3.4.2 показано, что поведение е(Т) для модели с экспоненциальным убыванием популярности совпадает с реальностью, а именно, е(Т) убывает экспоненциально с ростом Т.

Вычислено математическое ожидание е(Т).

ТЕОРЕМА 18. Для любого натурального Т

Эти теоремы показывают, что е(Т) убывает экспоненциально, как и в наблюдаемых сетях.

Благодарности. Автор признателен научному руководителю, доктору физико-математических наук, профессору Андрею Михайловичу Райгородскому за неоценимую помощь в работе.

И показана концентрация. ТЕОРЕМА 19. Для любого натурального Т

Работы автора по теме диссертации

[1] JI.A. Остроумова, Математические ожидания k-x входящих степеней вершин в случайных графах в модели Боллобаша-Риордана, Труды МФТИ, 13:29-40, 2012.

[2] JI.A. Остроумова, Об т-диаметрах случайных графов в модели Боллобаша-Риордана, Труды МФТИ, 13:41-59, 2012.

[3] A. Kupavskii, L. Ostroumova, D. Shabanov, and P. Tetali, The distribution of second degrees in the Buckley-Osthus random graph model, Internet Mathematics, 9(4):297-335, 2013. [А. Купавский доказал лемму 5 в теореме о концентрации. Д. Шабанов и П. Тетали помогали в редактировании текста. Все основные результаты получены JI. Остроумовой. ]

[4] L. Ostroumova and Е. Grechnikov, The distribution of second degrees in the Bollobas-Riordan random graph model, Moscow Journal of Combinatorics and Number Theory, 2(2):85-110, 2012. [E. Гречников помог свернуть сумму в доказательстве теоремы 2. Л. Остроумовой были сформулированы и доказаны все основные результаты работы. ]

[5] Л. А. Прохоренкова и Е. А. Самосват, Модели предпочтительного присоединения с устареванием, Деп. в ВИНИТИ 20.11.14, № 319-В2014, 2014. Расширенная версия статьи находится в иечати в журнале Internet Mathematics. [Е. Самосват предложил идею устаревания. Л. Прохоренковой была формализована модель, а также сформулированы и доказаны все основные результаты работы. ]

Отпечатано в отделе оперативней печати Геологического ф-та МГУ Тираж ¡00 экз. Заказ № ¿2