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

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

МОДЕЛИРОВАНИЕ ИНТЕРНЕТА С ПОМОЩЬЮ

СЛУЧАЙНЫХ ГРАФОВ

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

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

Автореферат

диссертации на соискание ученой степени

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

Москва — 2014

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

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

Официальные оппоненты:

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

Харкевича Российской академии наук (ИППИ РАН).

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

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

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

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

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

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

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

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

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

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

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

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

Здесь надо отметить, что Барабаши и Альберт предложили именно идею предпочтительного присоединения, а не конкретную модель. Эта идея нашла выражение в целом множестве моделей с различными свойствами, например, в LCD [9] и RAN [10] модели. К актуальным задачам анализа моделей предпочтительного присоединения можно отнести: исслеR. Albert and A.-L. Barabsi. Statistical mechanics of complex networks.

a 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. Princeton University Press, 2010.

Social and economic networks.

[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. 410(6825):268–276, 2001.

[8] A.-L. Barabsi and R. Albert. Emergence of scaling in random network.

286(5439):509–512, 1999.

[9] B. Bollobs. Mathematical results on scale-free random graphs.

and Networks, pages 1–34, 2003.

[10] T. Zhou, G. Yan, and B.-H. Wang. Maximal planar networks with large clustering дование поведения различных характеристик в моделях и их сравнение с наблюдаемыми в реальных сетях, обобщение результатов, полученных для разных моделей, выяснение границ применимости этих моделей.

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

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

Цель работы:

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

2. Обобщение результатов о распределении степеней вершин и поведении кластерных коэффициентов в моделях предпочтительного приcoefficient and power-law degree distribution. 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. Для модифицированной LCD-модели доказаны теоремы, позволившие оценить распределение числа подграфов, изоморфных фиксированному графу, в этой модели.

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

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

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

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

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

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

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

8th French Combinatorial Conference, г. Париж, июнь 2010 года. Тема доклада: “On estimating the expected number of sub-graphs in Barabsi 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 powerlaw degree distribution and clustering coefficient”.

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

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

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

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

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

Рассмотрим последовательность вершин {1, 2,...}. Мы индуктивно определим процесс ( )1 так, что является графом на множестве вершин {1,..., } c ребрами. Начнем с 1 – графа с одной вершиной и петлями. Имея, мы построим, добавляя вершину вместе с ребрами, выходящими из нее. Ребра взаимно независимы, и каждое ребро соединяет вершину с вершиной, где {1,..., } выбирается случайно, причем Здесь, под 1 = () мы подразумеваем степень вершины в графе.

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

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

[9] B. Bollobs. Mathematical results on scale-free random graphs.

and Networks, pages 1–34, 2003.

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

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

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

Теорема 7 (о коротком спуске). Имеет место соотношение при и =( ) В этом соотношении зависимость от величины имеет вид 1 + и занесена в (1).

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

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

вершин которого равны 1,...,. Обозначим через #( = ) число вершин в 0, степень каждой из которых равна. Тогда Действительно, заметим, что количество копий фиксированного подграфа может быть записано с помощью величины. Рассмотрим, например, случай 0 = 2,2 (полный двудольный граф с долями размеров два и два), который мало отличается от случая произвольного 0.

В этом случае Мы приводим не строго математическое доказательство теоремы 14.

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

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

Preferential attachment (PA): провести ребро из вершины +1 в выбранного ребра Uniform (U): провести ребро из + 1 в вершины Triangle formation (TF): провести два ребра из вершины +1 в Определим теперь, как провести все ребер из вершины + 1. Рассмотрим набор таких неотрицательных параметров {, } для 0 / и 0 2, что,, = 1. Эти параметры полностью определяют модель. В начале ( + 1)-го шага с вероятностью, мы выбираем некоторые = 0 и = 0, затем проводим 0 ребер по правилу PA, 20 ребер по правилу TF и ( 0 20 ) ребер по правилу U. Полиномиальная модель построена. Из определения следует, что граф в такой модели может быть сгенерирован на компьютере за линейное время. Более того, эта модель принадлежит -классу. Действительно, посредством простых вычислений можно показать, что условия (1–4) выполняются.

Объясним, почему мы называем описанную модель полиномиальной.

Обозначим через = входящую степень вершины в графе.

Напомним, что через мы обозначаем количество ребер между вершинами и. Для любых,, таких, что 0 /2 и 0 2, положим Это моном, зависящий от и 2 21. Легко видеть, что P (ребра 1,..., идут в вершины 1,...,, соответственно) = Приведенная таблица резюмирует сравнение полиномиальной модели с остальными упомянутыми моделями предпочтительного присоединения:

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

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

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

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

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

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

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

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

Сначала выбирается целевой хост с вероятностью ( =1 = 1).

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

где контролирует скорость убывания привлекательности медиа-страниц Например, (,, ) = (т.е. = (0, 1, 0)) приводит к предпочтительному присоединению, тогда как (,, ) = · (т.е. = (1, 1, 0)) приводит к модели приспособления (fitness model). Мы изучаем разные варианты и показываем, какие из них лучшим образом отражают поведение медиавеба в разделах 2.4 и 2.5.

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

Теорема 15. Пусть — это страница с качеством и временем создания, тогда в приближении среднего поля мы имеем Здесь и — это некоторые константы, объяснение смысла которых можно найти в диссертации. Из теоремы 15 следует, что в первом случае, чтобы иметь степенной закон распределения случайной величины, качество должно быть распределено экспоненциально, при этом контролировать параметр степенного закона оказывается очень трудно. Во [15] G. Bianconi and A.-L. Barabsi. Bose–Einstein condensation in complex networks.

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

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

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

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

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

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

Результаты приведены в Таблице 1.

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

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

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

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

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

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

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

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

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

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

Предположим, что для каждой страницы мы знаем убывающую функцию (), которая есть “польза” от ее скачивания с задержкой секунд после ее появления (под пользой можно иметь в виду количество “кликов” или “показов”, которые страница соберет в поисковой выдаче). Если в итоге каждая страница была скачана с задержкой, мы можем опрединамическое качество Иными словами, динамическое качество — это средняя польза, которую приносит поисковый робот во временном окне размера. Динамическое качество может быть полезно для того, чтобы понять влияние недельных и суточных трендов на текущую полезность поискового робота.

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

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

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

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

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

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

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

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

Предположим, что нам дано множество источников контента 1,...,.

среднее количество ссылок на новые страницы, появляющихся в секунду.

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

В среднем количество страниц, найденных после переобхода на источнике, равняется. Поэтому каждые секунд нам приходится обходить 1 + страниц (сам источник и все новые страницы, найденные на нем).

Очевидно, что оптимальное решение потребует расходовать все имеющиеся ресурсы:

И мы хотим максимизировать среднее качество, т.е., Мы заменяем ( ) приближением и получаем:

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

где — это множитель Лагранжа.

Функция () = (1 (1 + ) ) монотонно возрастает для > 0, причем (0) = 0 и (+) = 1. Следовательно, для любого (0 < < ) существует единственное = 1 ( ), как показано на Рис. 2. Так как, монотонно возрастающая функция, то является монотонной функцией, и мы используем бинарный поиск для того, что удовлетворить условию Затем мы описываем конкретный практический алгоритм ECHO (от Ephemeral Content Holistic Ordering), основанный на нашем теоретическом анализе.

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

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

Это значит, что наш алгоритм эффективно расходует ресурсы и вначале Таблица 4: Среднее динамическое качество для временного окна в 1 неделю.

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

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

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

Рис. 3: Динамическое качество для временного окна в 5 часов.

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

:

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

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

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

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

Качество алгоритма экспериментально проанализировано на реальных данных. Алгоритм внедрен в компании Яндекс.

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

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

[1] A. Рябченко и E. Самосват. О числе подграфов в случайном графе [2] A. Рябченко и E. Самосват. О числе подграфов в случайном графе Известия Российской академии наук. Серия маБарабаши-Альберт.

тематическая, том 76, стр. 183–202, 2012.

[3] L. Ostroumova, A. Ryabchenko, and E. Samosvat. Generalized preferential attachment: tunable power-law degree distribution and 185–202. LNCS, vol. 8305, 2013.

[4] D. Lefortier, L. Ostroumova, and E. Samosvat. Evolution of the media web.

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

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