Локальные свойства веб-графов в моделях предпочтительного присоединения Крот Александр Викторович

Введение к работе

Актуальность темы исследования

Диссертация посвящена изучению локальных свойств моделей сложных сетей. Под сложными сетями обычно имеют в виду сети, встречающиеся в природе — биологические, транспортные, или, например, сеть Интернет, вершинами в которой являются веб-страницы, а ребрами — ссылки между ними. Именно рост сети Интернет был одним из главных стимулов изучения сложных сетей. Изучение свойств таких сетей позволяет более точно описать их структуру, проверять гипотезы, искать спам, улучшать качество информационного поиска. Анализ сетей активно используется в термодинамической, статистической физике, где часто решаются задачи анализа фазовых переходов. В математике к изучению сложных сетей подходят более формально — сети представляют собой случайные графы, для анализа свойств которых используется аппарат случайных процессов, теории вероятностей и дискретной математики. С практической точки зрения задачи анализа сложных сетей больше всего встречаются в информационном поиске — например, эффективное вычисление PageRank, поиск сообществ и кластерных структур, оптимизация обхода сетей и др.

Степень разработанности темы

Эмпирическое исследование свойств веб-графов началось с работы А.-Л. Барабаши и Р. Альберт в 1999 году¹, где было показано, что граф сети Интернет, как и большинство других сетей, обладает следующими свойствами: малый диаметр, степенной закон распределения степеней вершин,

^arabasi A. L., Albert R. Emergence of scaling in random networks //science. - 1999. - T. 286. - №. 5439. - C. 509-512.

кластерная структура и другие²'³'⁴. Идея теоретического анализа таких сетей заключается в том, чтобы рассмотреть сеть как результат некоторого случайного процесса, построенного таким образом, чтобы получившиеся графы с высокой вероятностью обладали перечисленными свойствами.

В своей работе А.-Л. Барабаши и Р. Альберт¹ предложили общий подход к моделированию таких сетей, получивший название предпочтительное присоединение. Основная идея состоит в том, что новые страницы, появляющиеся в Интернете, скорее будут ссылаться на уже популярные страницы. С помощью этой идеи удалось впоследствии объяснить многие свойства реальных сетей, такие, как малый диаметр, степенной закон распределения степеней вершин, а также фазовый переход в размерах компонент связности. Стоит отметить, что сама идея предпочтительного присоединения не описывает конкретную модель. Различным образом формализуя понятие популярности, можно получить большое разнообразие моделей.

В данной работе изучаются локальные свойства в новом классе моделей сложных сетей — Generalized Preferential Attachment (обобщенное предпочтительное присоединение)⁵. Особенность данного подхода заключается в том, что, во-первых, большинство известных моделей предпочтительного присоединения принадлежат данному семейству, и, как следствие, доказанные результаты верны сразу для большинства моделей.

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

²Girvan M., Newman M. E. J. Community structure in social and biological networks //Proceedings of

the national academy of sciences. - 2002. - Т. 99. - №. 12. - С. 7821-7826.

³Newman M. E. J. The structure and function of complex networks //SIAM review. - 2003. - Т. 45. -

№. 2. - С. 167-256.

⁴Watts D. J., Strogatz S. H. Collective dynamics of’small-world’networks //nature. - 1998. - Т. 393. -

№. 6684. - С. 440.

⁵Ostroumova L., Ryabchenko A., Samosvat E. Generalized Preferential Attachment: Tunable Power-Law

Degree Distribution and Clustering Coefficient //WAW. - 2013. - С. 185-202.

коэффициентов: глобальный кластерный коэффициент C\{G) — отношение утроенного количества треугольников к числу пар смежных ребер в графе G и средний локальный кластерный коэффициент, который определяется как Co(G) = - У^7 і С (і), где С (і) — локальный кластерный ко-эффициент для вершины %: С (і) = |я, где Т^г — количество ребер между соседями вершины і и Рг, — количество пар смежных соседей.

Заметим, что кластерные коэффициенты определены для графов без кратных ребер. В данной работе мы также рассматриваем средний локальный кластерный коэффициент C2{n,d) среди вершин заданной степени d. Известно, что для многих реальных сетей оба коэффициента стремятся к нулю при росте размера сети. В реальных сетях C2{n,d) обычно убывает как d~^ для некоторого параметра ф > О⁶'⁷'⁸. Для некоторых сетей

„і. 1 9,10

Наконец, еще одной важной характеристикой сложных сетей, отражающей локальные свойства, является средняя степень d_nn(d) соседа вершины заданной степени d. Данная величина тесно связана с понятием ассорта-тивности. Граф называется ассортативным, если d_nn(d) — возрастающая по d функция, и дисассортативным, если d_nn(d) — убывающая по d функция. В работе проанализирована величина d_nn(d) вместо подсчета корреляции Пирсона, т.к. полученная функция дает более глубокое представление об устройстве сети. В некоторых реальных сетях d_nn(d) ведет себя как d^v для некоторого z/, которое может быть положительно (для ассортативных

⁶Catanzaro M., Caldarelli G., Pietronero L. Assortative model for social networks //Physical Review E.

- 2004. - Т. 70. - №. 3. - С. 037101.

⁷Serrano M. A., Boguna M. Clustering in complex networks. I. General formalism //Physical Review E.

- 2006. - Т. 74. - №. 5. - С. 056114.

⁸Vazquez A., Pastor-Satorras R., Vespignani A. Large-scale topological and dynamical properties of the

Internet //Physical Review E. - 2002. - Т. 65. - №. 6. - С. 066130.

⁹Leskovec J. Dynamics of large networks. - Carnegie Mellon University, 2008. ¹⁰Ravasz E., Barabasi A. L. Hierarchical organization in complex networks //Physical Review E. - 2003.

- Т. 67. - №. 2. - С. 026112.

сетей) или отрицательно (для дисассортативных сетей)¹¹. Как мы покажем далее, в широком классе моделей предпочтительного присоединения d_nn{d) ~ log(rf) при d —> оо. Ассортативность имеет несколько приложений, например, в эпидемиологии. В социальных сетях мы обычно наблюдаем ассортативность, в то время как, например, биологические сети обычно дисассортативны. Цели и задачи

1. Исследование локальных свойств в моделях предпочтительного присоединения посредством получения оценок для локального кластерного коэффициента и средней степени соседа вершин среди вершин степени d.

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

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

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

Теоретическая и практическая значимость работы

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

ⁿEchenique P. et al. Distance-d covering problems in scale-free networks with degree correlations //Physical Review E. - 2005. - Т. 71. - №. 3. - С. 035102.

струировать графы с заданым поведением среднего локального кластерного коэффициента и средней степени соседа среди вершин степени d.

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

При доказательстве результатов использовалась разнообразная комбинаторная и вероятностная техники. Существенное место в работе занимают различные методы доказательства концентрации случайных величин около

своего математического ожидания. В частности, используется неравенство Азумы–Хефдинга¹².

Положения, выносимые на защиту

3. Найдена оценка математического ожидания среднего локального кластерного коэффициента соседа вершин среди вершин степени d в графах обобщенного предпочтительного присоединения. Доказана концентрация.

4. Получена оценка математического ожидания средней степени соседа вершины вершин степени d в графах обобщенного предпочтительного присоединения (Generalized Preferential Attachment).

5. Получены оценки для среднего локального кластерного коэффициента в моделях предпочтительного присоединения.

Степень достоверности результатов

Все результаты обоснованы в виде строгих математических доказательств.

Апробация результатов

¹²Azuma K. Weighted sums of certain dependent random variables //Tohoku Mathematical Journal, Second Series. – 1967. – Т. 19. – №. 3. – С. 357-367.

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

— Кафедральный семинар кафедры дискретной математики под руко
водством А.М. Райгородского (ФИВТ МФТИ, 2013-2016 гг.).

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

Международная конференция “The 12th Workshop on Algorithms and Models for the Web Graph” (Эйндховен, Нидерланды, декабрь 2015 г.),

Международная конференция “The 13th Workshop on Algorithms and Models for the Web Graph” (Монреаль, Канада, декабрь 2016 г.),

Международная конференция “Workshop on Extremal graph theory” (Москва, Россия, июнь 2014 г.),

Международная конференция “The 5th International Conference on Networks Analysis” (Нижний Новгород, Россия, май 2015 г.).

Публикации автора по теме диссертации

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

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

[1,2,4] - доказательство теорем о математическом ожидании и концентрации количества треугольников на вершинах заданной степени. Доказательство теоремы о среднем кластерном коэффициенте среди вершин заданной степени; [3] - доказательство теорем о математическом ожидании суммы степеней вершин среди вершин заданной степени. Отыскание математического ожидания средней степени вершин.

Структура и объем диссертации