автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Моделирование интернета с помощью случайных графов

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

САМОСВАТ Егор Александрович

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

05.13.18 — математическое моделирование, численные методы и комплексы программ

Автореферат

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

2 ь \Ш 2014

Москва — 2014

005549410

Работа выполнена на кафедре дискретной математики Федерального государственного автономного образовательного учреждения высшего профессионального образования "Московский физико-технический институт (государственный университет)".

Научный руководитель: доктор физико-математических наук, профессор Райгородский Андрей Михайлович. Место работы: Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования "Московский государственный университет имени М.В. Ломоносова". Официальные оппоненты:

• доктор физико-математических наук, Кабатянский Григорий Анатольевич. Место работы: Федеральное государственное бюджетное учреждение науки Институт проблем передачи информации им. A.A. Харкевича Российской академии наук (ИППИ РАН).

• кандидат физико-математических наук, доцент, Замараев Виктор Андреевич. Место работы: Национальный исследовательский университет «Высшая школа экономики».

Ведущая организация: Хабаровское отделение Федерального государственного бюджетного учреждения науки Института прикладной математики Дальневосточного отделения Российской академии наук.

Защита состоится 19 июня 2014 года в 14:30 на заседании диссертационного совета Д 002.017.04 при Федеральном государственном бюджетном учреждении науки «Вычислительный центр имени A.A. Дородницына Российской академии наук» по адресу 119991, г. Москва, ул. Вавилова, д. 40.

С диссертацией можно ознакомиться в библиотеке ВЦ РАН и на сайте http://www.ccas.ru/.

Автореферат разослан 2014 года.

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

профессор Н. М. Новикова

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

Актуальность проблемы. Современный этап изучения графовой структуры сложных сетей начался сравнительно недавно, в конце 1990-х годов. По всей видимости, главным толчком к активному развитию данной области послужило появление и рост сети Интернет. Под сложными сетями обычно понимают совершенно разные графы (сети), которые встречаются в природе и обладают нетривиальными топологическими свойствами, от компьютерных и социальных сетей до биологических и экономических. Удивительно, но несмотря на столь разные области происхождения, все эти сети обладают многими общими свойствами: малый диаметр (теория шести рукопожатий), степенной закон распределения степеней вершин, выраженная кластерная структура и др., что, с одной стороны, отличает их от сильно регулярных графов вроде решеток, а с другой стороны, от случайных графов в стиле Эрдеша-Реньи. А это значит, что можно пытаться построить общую теорию подобных сетей. В эту работу включились и физики, и математики, и исследователи в области информационных технологий (computer scientists).

Физики находят аналогии между сетями и термодинамическими системами, ищут фазовые переходы в сетях, применяют методы статистической физики. Математики подходят к вопросу более формально, строго доказывая гипотезы физиков: изучение сложных сетей оказалось хорошим полигоном для приложения теории вероятностей и случайных процессов, дискретного анализа и теории графов. Исследователи в области информационных технологий пытаются извлечь практическую пользу из изучения сетевых структур: разрабатывают алгоритмы поиска сообществ в сетях и их оптимального обхода, считают PageRank и подобные ему характеристики. Это свидетельствует о широком интересе научного сообщества к данной проблематике и необходимости междисциплинарного подхода к изучению сложных сетей.

В последние 10-15 лет было предложено множество моделей сетей. Идея состоит в том, чтобы с их помощью объяснять и предсказывать важные количественные и топологические характеристики растущих реальных сетей, от Интернета и социальных сетей до биологических и экономический сетей

[1,2,3,4,5,6,7] _ Один из естественных способов состоит в том, чтобы рассмотреть сеть как результат некоторого случайного процесса, определенного в терминах простых естественных правил, которые гарантируют желаемые свойства, наблюдаемые в реальных сетях. Видимо, наиболее широко изученной реализацией этого подхода является предпочтительное присоединение.

Механизм предпочтительного присоединения (preferential attachment) был положен в основу модели развития Интернета в 1999 году Барабаши и Альберт И. Их гипотеза состояла в том, что в Интернете новые страницы "предпочитают" цитировать более популярные страницы, т.е. с большей вероятностью ссылаются на те страницы, которые до этого уже много цитировались. С помощью идеи предпочтительного присоединения удалось объяснить малый диаметр Интернета, степенной закон распределения степеней вершин в нем, а также фазовый переход в размерах компонент связности.

Здесь надо отметить, что Барабаши и Альберт предложили именно идею предпочтительного присоединения, а не конкретную модель. Эта идея нашла выражение в целом множестве моделей с различными свойствами, например, в LCD и RAN t10I модели. К актуальным задачам анализа моделей предпочтительного присоединения можно отнести: иссле-

[1] R. Albert and A.-L. Barabdsi. Statistical mechanics of complex networks. Reviews of modern physics, 74:47-97, 2002.

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

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

[4] M. O. Jackson. Social and economic networks. Princeton University Press, 2010.

[5] M. O. Jackson and A. Watts. The evolution of social and economic networks. Journal of Economic Theory, 106(2):265-295, 2002.

[6] M. E. Newman. The structure and function of complex networks. SIAM review, 45(2):167-256, 2003.

[7] S. H. Strogatz. Exploring complex networks. Nature, 410(6825):268-276, 2001.

[8] A.-L. BaraMsi and R. Albert. Emergence of scaling in random network. Science, 286(5439) :509-512, 1999.

[9] B. BollobAs. Mathematical results on scale-free random graphs. Handbook of Graphs and Networks, pages 1-34, 2003.

[10] T. Zhou, G. Yan, and B.-H. Wang. Maximal planar networks with large clustering

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

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

Другой областью, где анализ сложных сетей находит применение, является информационный поиск. Например, актуальной задачей в информационном поиске является эффективный обход Интернета поисковым роботом. Поисковый робот традиционно выполняет две задачи: обнаружение неизвестных качественных страниц и обновление обнаруженных ранее. Обе эти проблемы активно исследовались в течение последнего десятилетия I11!. Однако, в последнее время роль веба как средства массовой информации стала особенно важной. Благодаря этой тенденции на первый план выходит вопрос о скорости реакции поискового робота, т.е. задача уменьшения задержки между моментом создания новой страницы и моментом ее обнаружения поисковым роботом. Эта задача особенно актуальна для страниц, к которым интерес пользователей быстро пропадает (эфемерных страниц). Создание адекватных моделей эволюции Интернета может помочь в решении этой задачи.

Цель работы:

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

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

coefficient and power-law degree distribution. Phys. Rev. E, 71(4), 2005.

[11] C. Olston and M. Najork. Web crawling. Foundations and Trends in Information Retrieval, 4(3):175-246, 2010.

соединения.

3. Построение адекватной модели эволюции медиа-веба и ее валидация.

4. Разработка алгоритма эффективного обхода эфемерных страниц поисковым роботом.

Научная новизна. В диссертации получены следующие результаты, характеризующиеся научной новизной:

1. Для модифицированной ЬСБ-модели доказаны теоремы, позволившие оценить распределение числа подграфов, изоморфных фиксированному графу, в этой модели.

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

3. Построена адекватная модель эволюции медиа-веба, проведена ее теоретическая и эмпирическая (с помощью метода максимального правдоподобия) валидация.

4. На основе модели эволюции медиа-веба разработан алгоритм эффективного обхода эфемерных страниц поисковым роботом.

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

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

Публикации и апробация работы. По материалам диссертационной работы опубликовано 5 печатных работ из списка, рекомендованного ВАК.

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

• 8th French Combinatorial Conference, г. Париж, июнь 2010 года. Тема доклада: "On estimating the expected number of sub-graphs in Barabási and Albert model of random graph".

• 53-я научная конференция МФТИ, г. Долгопрудный, ноябрь 2010 года. Тема доклада: "О числе подграфов в случайном графе Бараба-ши-Альберт".

• 54-я научная конференция МФТИ, г. Долгопрудный, ноябрь 2011 года. Тема доклада: "О новой модели случайного веб-графа".

• 55-я научная конференция МФТИ, г. Долгопрудный, ноябрь 2012 года. Тема доклада: "Модели предпочтительного присоединения".

• Workshop on Random Graphs and their Applications, г. Москва, октябрь 2013 года. Тема доклада: "Evolution of the Media Web".

• 22nd ACM International Conference on Information and Knowledge Management, г. Сан-Франциско, октябрь 2013 года. Тема доклада: "Timely crawling of high-quality ephemeral new content".

• 56-я научная конференция МФТИ, г. Долгопрудный, ноябрь 2013 года. Тема доклада: "Об эволюции медиа-веба".

• 10th Workshop on Algorithms and Models for the Web Graph, Harvard University, г. Кембридж, декабрь 2013 года. Темы докладов: "Evolution of the Media Web" и "Generalized preferential attachment: tunable power-law degree distribution and clustering coefficient".

• Научные семинары Вычислительного центра имени А. А. Дородницына Российской академии наук, Московского физико-технического института, Московского государственного университета имени М. В. Ломоносова.

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

Результаты работы и их обсуждение

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

В первой главе исследуются модели предпочтительного присоединения. Эта глава соответствует математическому подходу к анализу сложных сетей и основана на статьях [1,2,3].

В разделе 1.1 дается краткий обзор результатов касательно моделей предпочтительного присоединения, определяется LCD-модель ^, а также следующая ее модификация Grrln.

Рассмотрим последовательность вершин {1,2,...}. Мы индуктивно определим процесс (GJn)t>1 так, что G\n является графом на множестве вершин {1, ...,£} с mi ребрами. Начнем с G^ - графа с одной вершиной и тп петлями. Имея Glm 1, мы построим G\n, добавляя вершину t вместе с ш ребрами, выходящими из нее. Ребра взаимно независимы, и каждое ребро соединяет вершину i с вершиной г, где i € {1,... ,i} выбирается случайно, причем

P(i-s)-i <Г7(т-(2£-1)) l<S<i-l ^ ~~ Sj " \ l/(2i - 1) 8 = t

Здесь, под = dGt-i (s) мы подразумеваем степень вершины s в граФе G^1.

В текущих обозначениях, в отличие от обозначений для LCD, нет скобок в верхнем индексе у Gbm. Мы используем это отличие для указания того, о какой модели идет речь. Главное отличие этой модели от LCD-модели состоит в том, что мы проводим сразу все т ребер из очередной вершины, а в LCD-модели ребра проводятся последовательно и после проведения каждого ребра степени вершин пересчитываются t9l.

В разделе 1.2 для модели G™ сначала доказывается новая теорема о распределении числа треугольников, которая затем обобщается на случай произвольного подграфа. В параграфе 1.2.1 доказывается теорема о распределении числа треугольников.

[9] В. Bollob&3. Mathematical results on scale-free random graphs. Handbook of Graphs and Networks, pages 1-34, 2003.

Обозначим через # (Со, число подграфов, изоморфных графу 6*0, в графе

Теорема 6 (о числе треугольников). Имеет место асимптотика

Е(#(*з, = (1 + О (¿)) (та~1)4ТО8(ш + 1) ЩЗ „.

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

В обеих теоремах - это степень вершины % в графе Сгг1п, е^ - это случайная величина, равная числу ребер между вершинами в графе С\1п, а - это произвольная функция от Скгг0 в частности, - любой многочлен от произвольного числа величин с?-, ерд, где г <1 < к, р < д < к.

Теорема 7 (о коротком спуске). Имеет место соотношение

= Е (е„-1 • ■■■■■ ■ ¿V ■■■■■ ¿Г) ■ ©(1)

при г < т и 0г ф ¡3^. В этом соотношении зависимость от величины т имеет вид 1 + 0 и занесена в 9(1).

Теорема 8 (о длинном спуске). Имеет место соотношение

Е (6-(^хГ =

= е (т)^-ад-

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

Из теорем о длинном и коротком спуске вытекает следующая теорема о произвольном подграфе.

Теорема 9 (о произвольном подграфе). Пусть задан граф во, степени вершин которого равны ,...,<13. Обозначим через = к) число вершин в С о, степень каждой из которых равна к. Тогда

Е (# (Со, Опт)) = в (п#<*=°> • (^)#№=1) • (1пп)#№=2> • .

Действительно, заметим, что количество копий фиксированного подграфа может быть записано с помощью величины е^д. Рассмотрим, например, случай Со = -^2,2 (полный двудольный граф с долями размеров два и два), который мало отличается от случая произвольного СоВ этом случае

#(^2,2,^)= ^ (е

1 <г<]<к<1<п

Далее требуется аккуратное применение теорем о длинном и коротком спуске. Доказательства теорем 7, 8, 9 приведены в параграфах 1.2.3-1.2.5.

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

В параграфе 1.3.1 вводится РА-класс моделей (РА от preferential attachment). Пусть (п > rig) — это граф с п вершинами {1,...,п} и тп ребрами, построенный в результате следующего случайного процесса. Мы стартуем в момент времени п() с произвольного графа с по вершинами и тппо ребрами. На (п + 1)-ом шаге (п > щ) мы строим граф из графа путем добавления новой вершины п + l и т ребер, соединяющих эту вершину и некоторые т вершин из множества {1,... , n, п + 1}. Обозначим через rf™ степень вершины v в графе G™г. Если для некоторых констант А и В выполняются следующие условия

Р «Г1 = < | = 1 - А^- - в\ + О (^jjpj , 1 <v<n, (1)

Р «+1 = dZ + 1 I = A^- + B^ + О

n

1 < V < n , (2)

P (d"+1=dS+j\G%l)=0 ,2<j<m,l<v<n, (3)

P(d^+\=m + j) = 0 , 1 <j<m

(4)

то мы говорим, что случайный граф G^ — это модель из РА-класса. Условие (4) означает, что вероятность образовать петлю мала. Как мы увидим далее, частные детали модели, вроде того, что разрешены ли петли и муль-тиребра или нет, являются не важными для многих свойств модели.

Здесь хочется подчеркнуть, что мы определили не одну модель, а целый класс моделей. Даже задание конкретных значений параметров Лит не определяет полностью процедуру построения графа. То, чего не хватает в определении, это конкретное вероятностное распределение на наборах из m вершин, с которыми будет соединена добавляемая вершина. Таким образом, существует множество моделей с разными свойствами, удовлетворяющих условиям (1-4). Например, LCD-модель, модель Холм-Кима t12' и RAN-модель принадлежат РА-классу с параметрами А = 1/2 и В = 0. Модели Бакли-Остуса '131 и Мори i14' также принадлежат РА-классу с параметрами А = и В = Заметим, что наш класс моделей шире класса Барабаши-Алберт, так как в нем мы имеем настраиваемый параметр степенного закона распределения степеней вершин.

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

[12] P. Holme and В. Kim. Growing scale-free networks with tunable clustering. Physical Review E, 65(2), 2002.

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

[14] T. F. M6ri. The maximum degree of the barabasi-albert random tree, combinatorics. Probability and Computing, 14:339-348, 2005.

Для всего класса получены результаты о распределении степеней вершин и поведении кластерных коэффициентов. Мы используем следующие обозначения. Под whp ("with high probability") мы имеем в виду, что для некоторой последовательности событий Лп выполнено Р(Ап) —> 1, когда п ->■ оо. Мы говорим, что ап ~ Ьп, если ап = (1 + о(1))6„, и ап « Ьп, если Сфп < ап < СгЬп для некоторых констант С0, С\ > 0. Мы говорим, что whp ап ~ Ьп, если Зф : ф = о(1) и Р(а„ = (1 + ф{п))Ьп) -> 1, когда поо.

В параграфе 1.3.2 сначала оценивается Nn{d) — количество вершин степени d в графе G^, а именно доказывается следующий результат о математическом ожидании ЕNn(d) случайной величины Nn(d).

Теорема 10. Пусть d> т. Тогда

ENn (d) = c(m, d) (n + О ,

где

<m'd>-Ar(d+S±A±l)r(m+%) ^r(m+f) '

а Г(а;) — это гамма-функция.

Затем доказывается, что количество вершин степени d плотно сконцентрировано около своего математического ожидания.

Теорема 11. Для каждой целочисленной ненулевой функции d = d(n) мы имеем

Р (|JVn(d) - ENn(d)\ > d V^ Inn) = О (n-lnn), откуда для любого S > 0 существует такая функция tр(п) = о(1), что

A — S

whp для любого d < п4А+2 выполнено

\Nn(d) - ENn(d)\ < <р(п) ЕNn(d) .

Эти две теоремы означают, что распределение степеней вершин подчиняется (асимптотически) степенному закону с параметром 1 +

В параграфе 1.3.3 исследуется поведение кластерного коэффициента в моделях из РЛ-класса. Существует два популярных определения кластерного коэффициента. Глобальный кластерный коэффициент С\{п) графа

С-т — это отношение утроенного числа треугольников к числу пар примыкающих ребер в графе <3^. Средний локальный кластерный коэффициент определяется следующим образом: С2(п) = ± ^27=1 С (г), где С {г) — это локальный кластерный коэффициент вершины г: С(г) = где Т* — это количество ребер между соседями вершины г и — это общее число разных пар соседей.

Наша цель — найти модели с постоянным кластерным коэффициентом. Давайте рассмотрим подкласс РА-класса со следующим свойством:

и а ' тп \ п2 )

(5)

Здесь еу — это количество ребер между вершинами i и j в графе а Б — положительная константа. Заметим, что это свойство по-прежнему полностью не определяет зависимости между добавляемым ребрами.

В некоторых предположениях мы получаем следующий результат о глобальном кластерном коэффициенте С 1(71) графа

Теорема 14. Пусть случайный граф С™ принадлежит РА-классу и удовлетворяет (5). Тогда

(1) Если 2А < 1, то whp С\{п) ~ у-3(1~2Л1? т ,

3 с

(2) Если 2А = 1, то \vlip Сх(гг) - 7-—^-,

(3) Если 2А > 1, ТО для любого е > 0 \vlip п1-2А~£ < С^п) < п1_2А+е .

Мы приводим не строго математическое доказательство теоремы 14. Однако используемые нами предположения точнее метода среднего поля, часто применяемого в физических статьях. Теорема 14 показывает, что в некоторых случаях (2А > 1) глобальный кластерный коэффициент (^(тг) стремится к нулю с ростом размера графа, даже если выполнено условие (5). Средний локальный кластерный коэффициент С2(п) в этом случае ведет себя по-другому. Действительно, из теорем 10 и 11 следует, что тоЪр количество вершин степени т в графе С^ больше сп для некоторой положительной константы с. Математическое ожидание числа треугольников, добавляемых на каждом шаге, равно Б + о(1). Поэтому \vlip

1 ^ 2сБ

С2{п) > - ^ С{г) >

п . т(т + 1) "

В параграфе 1.3.4 предложена полиномиальная модель, обладающая более реалистичным поведением глобального кластерного коэффициента и рядом других интересных свойств. Как обычно, мы строим граф G"n шаг за шагом. На (п + 1)-ом шаге граф образуется из графа G^

путем добавления вершины п +1 и последовательного проведения т ребер (кратные ребра и петли разрешаются).

Будем говорить, что ребро ij направлено от г к j, если г > j, таким образом исходящая степень каждой вершины равна т. Мы также будем говорить, что i и j — это соответственно начало и конец ребра ij. Рассмотрим три способа провести новые ребра из вершины n +1. Сначала мы случайно выбираем в графе G*"t ребро равномерно и независимо, и после этого возможны три варианта:

• Preferential attachment (РА): провести ребро из вершины п + 1 в конец выбранного ребра

• Uniform (U): провести ребро из п + 1 в вершины начало выбранного ребра

• Triangle formation (TF): провести два ребра из вершины п+1 в начало и конец выбранного ребра

Определим теперь, как провести все т ребер из вершины п+1. Рассмотрим набор таких неотрицательных параметров {а^,;} для 0 < к < т/2 и 0 < I < т - 2к, что i = 1- Эти параметры полностью определяют модель. В начале (п + 1)-го шага с вероятностью ctk,i мы выбираем некоторые к = к0 и I = 1о, затем проводим 10 ребер по правилу РА, 2ко ребер по правилу TF и (т — 10 — 2к0) ребер по правилу U. Полиномиальная модель построена. Из определения следует, что граф в такой модели может быть сгенерирован на компьютере за линейное время. Более того, эта модель принадлежит РА-классу. Действительно, посредством простых вычислений можно показать, что условия (1-4) выполняются.

Объясним, почему мы называем описанную модель полиномиальной. Обозначим через d? = df - т входящую степень вершины г в графе G"n. Напомним, что через eij мы обозначаем количество ребер между вершинами г и j. Для любых к,1, таких, что 0 < к < т/2 и 0 < I < т - 2к,

положим

^«..-.«-^Птйг1 п

х=1 у=2к+1

Это моном, зависящий от и Легко видеть, что

Р (ребра е1}..., ет идут в вершины ¿1,..., гт, соответственно) =

т/2т-2к

= (в)

к=0 1=0

Приведенная таблица резюмирует сравнение полиномиальной модели с остальными упомянутыми моделями предпочтительного присоединения:

А £> 7 СМп) С2(п)

ЬСБ 1/2 0 3 -)• 0

Мори 1/(2 + « 0 (2,оо) -> 0

Холм-Ким 1/2 гпг 3 ->• 0 0

IIА N 1/2 3 3 ->• 0 > 0

Полином. (2, оо) > 0 при А < 5 > 0

В параграфах 1.3.5 и 1.3.6 наши теоретические результаты демонстрируются с помощью компьютерного моделирования. В параграфе 1.3.7 обсуждаются полученные результаты, а параграф 1.3.8 посвящен доказательству теорем.

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

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

В разделе 2.2 мы подробно анализируем этот факт и вводим свойство устаревания медиа-страниц. Обозначим через е(Т) долю ребер, соединяющих страницы с разницей возрастов больше Т. Мы проанализировали

А

О 10 20 30 40 50

аде (¡п <1ау5)

Рис. 1: Свойство устаревания

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

В разделе 2.3 мы предлагаем новый класс моделей эволюции сетей, которые учитывают свойство устаревания страниц. Модели, обладающие таким свойством, мы называем моделями с устареванием.

Предположим, что мы имеем фиксированный набор хостов Н±,.Нп и каждый хост, т.е. множество страниц, Н^ характеризуется скоростью появления на нем новых страниц А;. Мы стартуем с пустого графа, т.е. в начале имеется п пустых множеств Н\,... ,Нп. Далее мы предполагаем, что новые страницы на хосте Щ появляются согласно пуассоновскому процессу с параметром А*. Пуассоновские процессы для разных хостов независимы.

Мы предполагаем, что каждая страница р при появлении получает качество др и исходящую степень тр. Случайные величины др и тр независимы в совокупности и одинаково распределены для р е Я;, т.е. распределение этих величин зависит только от хоста, которому принадлежит страница.

Когда новая страница р появляется на хосте Щ, она получает качество

qp и проводит взаимно независимо тр исходящих ссылок в уже существующие страницы. Цель каждой ссылки выбирается следующим образом. Сначала выбирается целевой хост к с вероятностью Pik (Sfc=i Pik — !)• Затем вероятность выбрать страницу г на хосте Нк полагается пропорциональной привлекательности f страницы г, которая является некоторой функцией dr (текущей степени страницы г), qr (качества страницы г) и аг (текущего возраста страницы г). Рассматривается следующее семейство функций привлекательности:

f7itTk(d,q,a) = qai-da*-e-^,

где тк контролирует скорость убывания привлекательности медиа-страниц на хосте Нк, а с^ = (а1,«2,«з) € {О, I}3.

Например, f(d,q,a) = d (т.е. ~се = (0,1,0)) приводит к предпочтительному присоединению, тогда как f(d, <7, а) — q-d (т.е. а = (1,1,0)) приводит к модели приспособления (fitness model) I15l. Мы изучаем разные варианты и показываем, какие из них лучшим образом отражают поведение медиа-веба в разделах 2.4 и 2.5.

В разделе 2.4 в приближении среднего поля мы доказываем теоремы о распределении степеней вершин для моделей с устареванием.

Теорема 15. Пусть р G Нк — это страница с качеством qp и временем создания tp, тогда в приближении среднего поля мы имеем

Nh'rk1p

a Wk

(1) Если / = q- d- е , то dp(qp, t, tp) = е

(2) Earn f = q-e~^, то dp(qp,t,tp) = ^^ (l-eVj.

Здесь Wk и Nk — это некоторые константы, объяснение смысла которых можно найти в диссертации. Из теоремы 15 следует, что в первом случае, чтобы иметь степенной закон распределения случайной величины dp, качество qp должно быть распределено экспоненциально, при этом контролировать параметр степенного закона оказывается очень трудно. Во

[15] G. Bianconi and A.-L. Barabäsi. Bose-Einstein condensation in complex networks.

Physical Review Letters, 86(24) :5632-5635, 2001.

Л_е "тк J

Таблица 1: Логарифм правдоподобия: средний логарифм правдоподобия ребра.

а ч — а е т ¿е т де т йце *

-6.il -5.56 -5.34 -6.08 -5.50 -5.17 -5.45

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

Также в этом разделе в приближении среднего поля мы доказываем теорему о свойстве устаревания для моделей с устареванием.

__ _ а _ а

Теорема 16 Для / = д ■ й ■ е т<= или / = д • е в приближении среднего поля мы имеем

е(Т) = (1+о(1))^2ккСке^ , к

где — это некоторые константы.

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

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

Таблица 2: Абсолютная победа: доля ребер, на которых модель побеждает все остальные.

а о. — о е dq ¿е г — а qe -г dqe

0.03 0.07 0.28 0.07 0.07 0.30 0.16

Таблица 3: Поединки: значение в (а,Ъ) — это доля ребер, на которых а побеждает Ь.

<г Я е т dq de -г qe -г dqe т

й - 0.22 0.30 0.43 0.18 0.22 0.19

Ч 0.78 - 0.38 0.76 0.41 0.23 0.40

— а е т 0.70 0.62 - 0.69 0.54 0.40 0.53

0.57 0.24 0.31 - 0.24 0.23 0.17

0.82 0.59 0.44 0.76 - 0.39 0.43

0.78 0.77 0.60 0.77 0.61 - 0.62

dqe~ 0.81 0.60 0.47 0.83 0.57 0.38 -

Согласно разным моделям ребра имеют разные вероятности, та из моделей, которая приписывает ребру наибольшую вероятность, называется побеждающей на этом ребре (см. Таблицу 2). Также для каждой пары моделей М\ и М2 мы вычислили процент ребер, имеющих большую вероятность согласно М\, чем согласно М2 (см. Таблицу 3). Из обеих таблиц ясно видно, что фактор устаревания играет очень важную роль.

Мы видим, что наиболее вероятная модель имеет функцию привлекательности / = . Это означает, что в медиа-вебе вероятность процитировать страницу определяется скорее качеством страницы, чем ее текущей популярностью.

Третья глава посвящена разработке алгоритмов эффективного обхода эфемерных страниц поисковым роботом. В этой главе существенно используются результаты главы 2 и она основана на статье [5].

Как уже обсуждалось, медиа-страницы интересны пользователям лишь несколько дней после своего появления. Чтобы подчеркнуть эту особен-

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

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

В разделе 3.1 мы формализуем проблему обхода эфемерных страниц поисковым роботом посредством введения подходящей метрики.

Предположим, что для каждой страницы i мы знаем убывающую функцию Pj(Ai), которая есть "польза" от ее скачивания с задержкой At секунд после ее появления U (под пользой можно иметь в виду количество "кликов" или "показов", которые страница соберет в поисковой выдаче). Если в итоге каждая страница г была скачана с задержкой Ati, мы можем определить динамическое качество поискового робота:

Qtü) = | Е (7)

i:ti+Ati€[t-T,t]

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

Определим теперь среднее качество поискового робота. Естественно ожидать, что, если выбрать временное окно Т достаточно большим, влияние временных трендов пользовательского интереса на динамическое качество поискового робота усреднится. Иными словами, функция Qr(t) стремится к константе, когда Т увеличивается. Таким образом, в предположении стационарности, мы можем рассмотреть среднее качество поискового робота:

Q = lim QT{t) (8)

которое не зависит от Ь.

Под пользой Рг(Д£) от скачивания страницы г в момент времени и + Д£ мы имеем в виду общее количество кликов пользователей, которое она получит в поисковой выдаче после момента скачивания (мы пренебрегаем временем индексации). Таким образом, мы можем оценить, насколько страница соответствует текущим интересам пользователей.

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

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

Для поиска оптимального расписания обхода источников контента и скачивания новых страниц мы используем следующую аппроксимацию Рг(АЬ) (т.е. количества будущих кликов):

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

Заметим, что используемая нами аппроксимация функции полезности фактически является лучшим вариантом функции привлекательности, который мы нашли во второй главе, а именно /((¿, д, а) = д ■ е~т.

Предположим, что нам дано множество источников контента 5^..., 5П. Пусть Аг — это скорость появления новых ссылок на источнике 5*, т.е. среднее количество ссылок на новые страницы, появляющихся в секунду.

Рассмотрим алгоритм, который обходит источник 5г каждые Ц секунд, находит ссылки на новые страницы, а затем скачивает все эти новые страницы. Мы хотим найти такое расписание обхода источников, которое максимизировало бы среднее качество <2, т.е., оптимальные значения /¿. Предположим, что наша инфраструктура позволяет обходить N страниц в секунду (./V может быть не целым). Это ограничение на ресурсы приводит к

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

г

В среднем количество страниц, найденных после переобхода на источнике 5г, равняется Поэтому каждые секунд нам приходится обходить 1 + А^ страниц (сам источник и все новые страницы, найденные на нем). Очевидно, что оптимальное решение потребует расходовать все имеющиеся ресурсы:

1г

г г

И мы хотим максимизировать среднее качество, т.е.,

Я = 12} £ ^(Л^)->тах.

Мы заменяем Р] (Д^-) приближением и получаем:

р А^Д 1

1г

1 0=0

Е?^^ = Ер« О

г 1 — в * 4 у

где рг = —¡и и XI = Без ограничения общности, предполагаем, что

1-е '

Р\ < • • • < Рп• Теперь для максимизации <5(^1,..., хп) при условии (9) мы используем метод множителей Лагранжа:

\Рг (1 - е-«/11) - =ш, г = 1,..., п,

где и> — это множитель Лагранжа. Вспоминая, что 1{ = получаем

(1 - = и, г = 1,..., тг,

Рис. 2: Оптимизация

Функция д{х) — (1 — (1 + х)е~х) монотонно возрастает для х > 0, причем д(0) = 0 и g(+oo) = 1. Следовательно, для любого и> (0 < ш < Pi) существует единственное ^Ji = как показано на Рис. 2. Так как, монотонно возрастающая функция w, то j- является монотонной функцией w, и мы используем бинарный поиск для того, что удовлетворить условию

Затем мы описываем конкретный практический алгоритм ECHO (от Ephemeral Content Holistic Ordering), основанный на нашем теоретическом анализе.

В разделе 3.4 мы экспериментально сравниваем качество работы ECHO алгоритма с некоторыми другими подходами для трех разных скоростей обхода N. В Таблице 4 показаны полученные средние значения общего качества и их стандартные отклонения, а на Рис. 3 показано динамическое качество для окна размером в 5 часов и N = 0.1.

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

Таблица 4: Среднее динамическое качество для временного окна в 1 неделю.

алгоритм N = 0.05 N = 0.10 N = 0.20

Frequency 0.014 ±0.004 0.39 ±0.04 0.61 ±0.06

BFS 0.24±0.04 0.46±0.03 0.62±0.03

Fixed-quota 0.43±0.04 0.59±0.03 0.69±0.03

ECHO-greedy 0.60±0.03 0.68±0.03 0.69±0.03

ECHO-schedule 0.52±0.02 0.69±0.03 0.71±0.03

ECHO-newpages 0.62±0.04 0.69±0.03 0.71±0.03

Оценка сверху 0.72 0.72 0.72

обходит наиболее качественные страницы и источники.

В разделе 3.5 мы обсуждаем полученные в этой главе результаты и их связь с предыдущими исследованиями других авторов.

В заключении сформулированы основные результаты работы, полученные в диссертации.

Результаты, выносимые на защиту:

1. Для модифицированной ЬСБ-модели доказаны теоремы, позволившие оценить распределение числа подграфов, изоморфных фиксированному графу.

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

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

4. Посредством введения подходящей метрики формализована проблема обхода эфемерных страниц поисковым роботом. Разработан алгоритм эффективного обхода эфемерных страниц поисковым роботом. Качество алгоритма экспериментально проанализировано на реальных данных. Алгоритм внедрен в компании Яндекс.

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

Основные результаты диссертации изложены в следующих публикациях:

[1] А. Рябченко и Е. Самосват. О числе подграфов в случайном графе Барабаши-Альберт. Доклады Академии наук, том 435, стр. 587-590, 2010.

[2] А. Рябченко и Е. Самосват. О числе подграфов в случайном графе Барабаши-Альберт. Известия Российской академии наук. Серия математическая, том 76, стр. 183-202, 2012.

[3] L. Ostroumova, A. Ryabchenko, and Е. Samosvat. Generalized preferential attachment: tunable power-law degree distribution and clustering coefficient. In Algorithms and Models for the Web Graph, pp. 185-202. LNCS, vol. 8305, 2013.

[4] D. Lefortier, L. Ostroumova, and E. Samosvat. Evolution of the media web. In Algorithms and Models for the Web Graph, pp. 80-92. LNCS, vol. 8305, 2013.

[5] D. Lefortier, L. Ostroumova, E. Samosvat, and P. Serdyukov. Timely crawling of high-quality ephemeral new content. In Proceedings of the 22nd ACM international conference on Conference on information & knowledge management, pp. 745-750. ACM, 2013.

В совместных работах Самосвату Е. принадлежат основные результаты, соавторы помогали в редактировании текста, проведении экспериментов и доказательстве некоторых теорем.

Подписано в печать 29.04.2014.

Формат А5. Тираж 100 Экз. Заказ № 17119. Типография ООО "Ай-клуб" (Печатный салон МДМ) 119146, г. Москва, Комсомольский проспект, д.28 Тел. 8-495-782-88-39

Федеральное государственное автономное образовательное учреждение высшего профессионального образования "Московский физико-технический институт

(государственный университет)" факультет инноваций и высоких технологий

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

Н укописи

Самосват Егор Александрович

05.13.18 — математическое моделирование, численные методы

и комплексы программ

Диссертация на соискание ученой степени кандидата физико-математических наук

Научный руководитель — д.ф.-м.н. А.М. Райгородский

Москва, 2014

Оглавление

Введение 4

Актуальность темы ........................................................4

Модели и основные характеристики сложных сетей....................5

Предпочтительное присоединение........................................6

Свойства медиа-веба и модели с устареванием..........................7

Приложение моделей к задаче обхода эфемерных страниц поисковым роботом ..........................................................8

1 Модели предпочтительного присоединения 11

1.1 Модель Барабаши-Альберт.....................11

1.1.1 Предпочтительное присоединение .............11

1.1.2 ЬСЭ-модель .......................13

1.1.3 Модификация ЬСЭ-модели: модель ..........15

1.2 О числе подграфов случайного графа в модели .......16

1.2.1 Подсчет количества треугольников.............16

1.2.2 Обобщение на случай произвольного подграфа......25

1.2.3 Доказательство теоремы о коротком спуске........28

1.2.4 Доказательство теоремы о длинном спуске........30

1.2.5 Доказательство теоремы о произвольном подграфе ... 35

1.3 Обобщенное предпочтительное присоединение..........38

1.3.1 Определение РА-класса...................38

1.3.2 Степенной закон распределения степеней вершин .... 39

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

1.3.4 Полиномиальная модель...................43

1.3.5 Описание модели, изученной эмпирически ........44

1.3.6 Эмпирические результаты..................45

1.3.7 Обсуждение..........................48

1.3.8 Доказательства теорем....................49

2 Свойства медиа-веба и модели с устареванием 56

2.1 Базовые модели............................56

2.2 Свойство устаревания медиа-веба..................57

2.2.1 Данные............................57

2.2.2 Свойство устаревания....................58

2.3 Модель медиа-веба..........................58

2.4 Теоретический анализ предложенной модели...........59

2.4.1 Распределение входящей степени..............59

2.4.2 Свойство устаревания....................62

2.5 Эмпирический анализ предложенной модели...........64

2.5.1 Оценивание параметров...................65

2.5.2 Правдоподобие........................65

3 Приложение моделей к задаче обхода эфемерных страниц поисковым роботом 70

3.1 Формализация проблемы......................70

3.2 Источники контента.........................73

3.3 Оптимальный обход источников..................76

3.3.1 Теоретический анализ....................76

3.3.2 Реализация..........................80

3.4 Эксперименты ............................82

3.4.1 Данные............................83

3.4.2 Упрощения предложенного алгоритма...........84

3.4.3 Результаты..........................85

3.5 Обсуждение..............................89

Заключение 92

Список литературы 94

Введение

Актуальность темы

Современный этап изучения графовой структуры сложных сетей начался сравнительно недавно, в конце 1990-х годов. По всей видимости, главным толчком к активному развитию данной области послужило появление и рост сети Интернет. Под сложными сетями обычно понимают совершенно разные графы (сети), которые встречаются в природе и обладают нетривиальными топологическими свойствами, от компьютерных и социальных сетей до биологических и экономических. Удивительно, но несмотря на столь разные области происхождения, все эти сети обладают многими общими свойствами: малый диаметр (теория шести рукопожатий), степенной закон распределения степеней вершин, выраженная кластерная структура и др., что, с одной стороны, отличает их от сильно регулярных графов вроде решеток, а с другой стороны, от случайных графов в стиле Эрдеша-Реньи. А это значит, что можно пытаться построить общую теорию подобных сетей. В эту работу включились и физики, и математики, и исследователи в области информационных технологий (computer scientists).

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

Модели и основные характеристики сложных сетей

В последние 10-15 лет было предложено множество моделей сетей на основе случайных графов. Идея состоит в том, чтобы с их помощью объяснять и предсказывать важные количественные и топологические характеристики растущих реальных сетей, от Интернета и социальных сетей до биологических и экономический сетей [3, 8, 28, 31, 32, 39, 48].

Простейшая характеристика вершины в сети — это ее степень, т.е. количество примыкающих к ней ребер. Поэтому не удивительно, что наиболее глубоко изученное свойство сетей — это распределение степеней вершин в них. Для большинства изученных реальных сетей оказалось, что доля вершин степени в, убывает как с£"7, причем обычно 2 < 7 < 3 [5, 8, 14, 26].

Другой важной характеристикой сети является ее кластерный коэффициент — величина, отражающая склонность сети формировать кластеры, т.е. густо соединенные множества вершин. В литературе встречаются разные подходы к определению кластерного коэффициента [9]. Мы будем использовать глобальный и средний локальный кластерные коэффициенты, точные определения которых будут даны в параграфе 1.3.3. Для большинства изученных реальных сетей средний локальный кластерный коэффициент варьируется в диапазоне от 0.01 до 0.08 и не меняется значительно с ростом сети [8]. Создание моделей сетей, которые реалистично отражают не только степенной закон распределения степеней вершин, но и поведение кластерного коэффициента, является непростой задачей.

Для того, чтобы совместить в одной модели и настраиваемое распределение степеней вершин, и кластеризацию, некоторые авторы [4, 45, 49] предложили стартовать с заданного априорного распределения степеней вершин и заданной кластеризации, а затем генерировать случайный граф, подчиненный этим ограничениям. Другими словами, среди всего множества графов с заданным количеством вершин они рассматривали подмножество графов с желаемыми свойствами, а затем равновероятно выбирали случайный граф из этого подмножества. Поступая таким образом, авторы автоматически получали желаемые характеристики случайного графа. Однако, такой подход не дает ответа на вопрос о происхождении и природе этих характеристик, более того, он кажется не достаточно общим и может быть заподозрен в "переобучении".

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

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

Предпочтительное присоединение

Механизм предпочтительного присоединения (preferential attachment) был положен в основу модели развития Интернета в 1999 году Барабаши и Альберт [5]. Их гипотеза состояла в том, что в Интернете новые страницы "предпочитают" цитировать более популярные страницы, т.е. с большей вероятностью ссылаются на те страницы, которые до этого уже много цитировались. С помощью идеи предпочтительного присоединения удалось объяснить малый диаметр Интернета, степенной закон распределения степеней вершин в нем, а также фазовый переход в размерах компонент связности.

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

Для определения глобального кластерного коэффициента необходимо знать распределение числа треугольников и пар примыкающих ребер в графе, такой анализ для LCD-модели был проведен в [9]. Мы в свою очередь провели этот анализ для модификации LCD-модели, которая также удобна для анализа распределения более сложных подграфов. Этому вопросу посвящен раздел 1.2. Интересный результат состоит в том, что асимптотическое поведение с ростом графа математического ожидания числа копий фиксированного подграфа определяется лишь количеством вершин степени ноль, один и два в этом подграфе. Так, если в фиксированном подграфе все степени вершин больше трех, то математическое ожидание числа его копий ограничено постоянной.

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

На основе этого подхода предложена модель с качественно более реалистичным поведением глобального кластерного коэффициента, чем в преды-

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

Первая глава этой работы соответствует математическому подходу к анализу сложных сетей и основана на статьях автора [51, 52, 53].

Свойства медиа-веба и модели с устареванием

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

Один из главных недостатков моделей предпочтительного присоединения состоит в том, что они уделяют слишком много внимания старым страницам и не реалистично объясняют, как появляются ссылки на вновь созданные страницы. В главе 2 мы изучаем медиа-веб, т.е. высокодинамическую часть веба, где ежедневно появляется множество новых страниц, связанных с медиа-контентом: новостями, постами в блогах и форумах. Отметим, что некоторые отдельные части веба уже изучались ранее, например, в [35] была предложена модель для социального веба.

Ясно, что предпочтительное присоединение плохо подходит для описания эволюции этой части веба. Действительно, в новостях и блогах редко цитируют сюжеты, потерявшие свою актуальность, какими бы популярными они ни были до этого. В разделе 2.2 мы подробно анализируем этот факт и вводим свойство устаревания медиа-страниц. Это наблюдение натолкнуло нас на мысль модифицировать предпочтительное присоединение, понижая вероятность ссылки на неактуальные страницы. Модели, обладающие таким свойством, мы называем моделями с устареванием. Мы предположили, что "качество" статьи тоже влияет на ее цитируемость. Это предположение близко к идее модели приспособления (fitness model) [7], в ней каждая страница имеет свою приспособленность, которая повышает вероятность того, что она будет процитирована.

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

В разделе 2.4 мы анализируем модели с устареванием теоретически и по-

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

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

Приложение моделей к задаче обхода эфемерных страниц поисковым роботом

В третьей главе мы рассматриваем приложение моделей с устареванием для одной из задач информационного поиска, эта глава основана на статье автора [55].

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

Поисковый робот традиционно выполняет две задачи: обнаружение неизвестных качественных страниц и обновление обнаруженных ранее. Обе эти проблемы активно исследовались в течение последнего десятилетия [40]. Однако, в последнее время роль веба как средства массовой информации стала особенно важной. Благодаря этой тенденции на первый план выходит вопрос о скорости реакции поискового робота, т.е. задача уменьшения задержки между моментом создания новой страницы и моментом ее обнаружения поисковым роботом.

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

Цена задержки между моментом создания эфемерной страницы и момен-

том ее скачивания поисковым роботом очень велика с точки зрения удовлетворения пользовательского интереса. Более того, если поисковый робот не сможет найти эфемерную страницу на пике пользовательского интереса, то, видимо, вообще нет необходимости ее скачивать. Таким образом, проблема быстрого обнаружения и скачивания новых эфемерных страниц является важной, но, насколько известно автору, слабо изученной в литературе. Действительно, множество метрик было предложено для измерения покрытия и свежести скачанного корпуса [17, 19, 40], но все они не берут в расчет особенности эфемерных страниц, т.е. деградацию полезности скачанных страниц для поисковой системы со временем. В разделе 3.1 мы формализуем задачу обхода эфемерных страниц путем введения подходящей метрики. Затем мы описываем предлагаемый алгоритм решения поставленной задачи.

Наш опыт использования Интернета подсказывает, что большинство публикуемого свежего контента (новости, посты в блогах, объявления) может быть найдено на сравнительно небольшом количестве "хабов" или источников контента. Собственно с таких хабов мы обычно и начинаем поиск нового — это главные страницы хостов, новостные рубрики или специальные страницы с новостями. Довольно естественная идея состоит в том, чтобы искать свежий контент путем мониторинга появления новых ссылок на хабах. В разделе 3.2 мы проверяем, что большинство интересных ссылок действительно могут быть найдены на небольшом множестве источников контента, а также предлагаем простую процедуру для поиска источников контента.

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

"Качество" страницы можно измерять разными способами, и оно, например, может быть основано на ссылочной структуре веба (входящая степень [33] или PageRank [2, 20] ) или на каких-то внешних сигналах (например, логе запросов [27, 41, 42] или количестве раз, которое страница была показана в поисковой выдаче [42]). В этой работе для оценки качества мы предлагаем использовать количество кликов на страницу в поисковой выдаче, которое наиболее достоверно с точки зрения поисковой системы отражает интерес

пользователей к содержанию страницы. Более того, выбор так�