Модели Интернета
Покупка
Тематика:
Основы высшей математики
Издательство:
Интеллект
Год издания: 2019
Кол-во страниц: 64
Дополнительно
Вид издания:
Учебное пособие
Уровень образования:
ВО - Бакалавриат
ISBN: 978-5-91559-260-4
Артикул: 477151.03.99
Доступ онлайн
В корзину
Учебное пособие посвящено моделированию Интернета, который был диковинкой для большинства из нас еше каких то 20 лет назад. Сейчас мы ежедневно пользуемся ресурсами Интернета поиском, электронной почтой, блогами и др. Сеть динамично развивается, растет и усложняется, а потому рядовому пользователю может казаться, что в Интернете царит полный хаос. Однако в реальности все устроено намного интереснее. Многочисленные статистические исследования показывают, что есть ряд за конов, которым подчиняется «всемирная паутина». В частности, эти законы связаны с интерпретацией Интернета как графа, вершины которого сайты, а ребра гиперссылки. В книге описаны основные законы такого типа и рассказано, как современная математика помогает их моделировать. Для понимания книги читателю понадобится знание основ комбинаторики, теории графов и теории вероятностей. Книга будет полезна студентам, аспирантам и преподавателям технических ВУЗов, а также всем, кто интересуется приложениями математики к моделированию «сложных сетей» Интернета, социальных, биологических, транспортных и других сетей. Первое издание книги широко используется в российских университетах и специалистами по информационным технологиям.
Тематика:
ББК:
УДК:
- 51: Математика
- 510: Фундаментальные и общие проблемы математики. Основания математики, математ. логика
ОКСО:
- ВО - Бакалавриат
- 01.03.02: Прикладная математика и информатика
- 02.03.01: Математика и компьютерные науки
- 02.03.02: Фундаментальная информатика и информационные технологии
- ВО - Магистратура
- 01.04.02: Прикладная математика и информатика
- 02.04.01: Математика и компьютерные науки
- 02.04.02: Фундаментальная информатика и информационные технологии
- 02.04.03: Математическое обеспечение и администрирование информационных систем
ГРНТИ:
Скопировать запись
Фрагмент текстового слоя документа размещен для индексирующих роботов.
Для полноценной работы с документом, пожалуйста, перейдите в
ридер.
А.М. РАЙГОРОДСКИЙ МОДЕЛИ ИНТЕРНЕТА Второе издание
À.Ì. Ðàéãîðîäñêèé Ìîäåëè Èíòåðíåòà: Ó÷åáíîå ïîñîáèå / À.Ì. Ðàéãîðîäñêèé – 2-å èçä. – Äîëãîïðóäíûé: Èçäàòåëüñêèé Äîì «Èíòåëëåêò», 2019. – 64 ñ. ISBN 978-5-91559-260-4 Ó÷åáíîå ïîñîáèå ïîñâÿùåíî ìîäåëèðîâàíèþ Èíòåðíåòà, êîòîðûé áûë äèêîâèíêîé äëÿ áîëüøèíñòâà èç íàñ åùå êàêèõòî 20 ëåò íàçàä. Ñåé÷àñ ìû åæåäíåâíî ïîëüçóåìñÿ ðåñóðñàìè Èíòåðíåòà ïîèñêîì, ýëåêòðîííîé ïî÷òîé, áëîãàìè è äð. Ñåòü äèíàìè÷íî ðàçâèâàåòñÿ, ðàñòåò è óñëîæíÿåòñÿ, à ïîòîìó ðÿäîâîìó ïîëüçîâàòåëþ ìîæåò êàçàòüñÿ, ÷òî â Èíòåðíåòå öàðèò ïîëíûé õàîñ. Îäíàêî â ðåàëüíîñòè âñå óñòðîåíî íàìíîãî èíòåðåñíåå. Ìíîãî÷èñëåííûå ñòàòèñòè÷åñêèå èññëåäîâàíèÿ ïîêàçûâàþò, ÷òî åñòü ðÿä çàêîíîâ, êîòîðûì ïîä÷èíÿåòñÿ «âñåìèðíàÿ ïàóòèíà».  ÷àñòíîñòè, ýòè çàêîíû ñâÿçàíû ñ èíòåðïðåòàöèåé Èíòåðíåòà êàê ãðàôà, âåðøèíû êîòîðîãî ñàéòû, à ðåáðà ãèïåðññûëêè.  êíèãå îïèñàíû îñíîâíûå çàêîíû òàêîãî òèïà è ðàññêàçàíî, êàê ñîâðåìåííàÿ ìàòåìàòèêà ïîìîãàåò èõ ìîäåëèðîâàòü. Äëÿ ïîíèìàíèÿ êíèãè ÷èòàòåëþ ïîíàäîáèòñÿ çíàíèå îñíîâ êîìáèíàòîðèêè, òåîðèè ãðàôîâ è òåîðèè âåðîÿòíîñòåé. Êíèãà áóäåò ïîëåçíà ñòóäåíòàì, àñïèðàíòàì è ïðåïîäàâàòåëÿì òåõíè÷åñêèõ ÂÓÇîâ, à òàêæå âñåì, êòî èíòåðåñóåòñÿ ïðèëîæåíèÿìè ìàòåìàòèêè ê ìîäåëèðîâàíèþ «ñëîæíûõ ñåòåé» Èíòåðíåòà, ñîöèàëüíûõ, áèîëîãè÷åñêèõ, òðàíñïîðòíûõ è äðóãèõ ñåòåé. Ïåðâîå èçäàíèå êíèãè øèðîêî èñïîëüçóåòñÿ â ðîññèéñêèõ óíèâåðñèòåòàõ è ñïåöèàëèñòàìè ïî èíôîðìàöèîííûì òåõíîëîãèÿì. © 2018, À.Ì. Ðàéãîðîäñêèé © 2019, ÎÎÎ Èçäàòåëüñêèé Äîì «Èíòåëëåêò», îðèãèíàë-ìàêåò, îôîðìëåíèå ISBN 978-5-91559-260-4 Êîìïüþòåðíàÿ âåðñòêà – ÈÄ «Èíòåëëåêò» Êîððåêòóðà – àâòîðà Îòâåòñòâåííûé çà âûïóñê – Ë.Ô. Ñîëîâåé÷èê Ôîðìàò 60õ90/16. Ïå÷àòü îôñåòíàÿ. Ãàðíèòóðà Íüþòîí. Ïå÷. ë. 4. Çàê. ¹ Áóìàãà îôñåòíàÿ ¹ 1, ïëîòíîñòü 80 ã/ì2 Èçäàòåëüñêèé Äîì «Èíòåëëåêò» 141700, Ìîñêîâñêàÿ îáë., ã. Äîëãîïðóäíûé, Ïðîìûøëåííûé ïð-ä, ä. 14, òåë. (495) 617-41-85 Îòïå÷àòàíî â òèïîãðàôèè ÎÎÎ «Áóêè Âåäè»
ОГЛАВЛЕНИЕ Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 Глава 1. Свойства Интернета . . . . . . . . . . . . . . . . . . . . . . . . 7 1.1. Основные объекты и общая идеология их изучения . . . . . . . . . . 7 1.2. Количество ребер . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.3. Гигантская компонента . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.4. Устойчивость и уязвимость . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.5. Диаметр . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.6. Степени вершин . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.7. Вторые степени вершин. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.8. Пейджранк . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.9. Количество ребер между вершинами заданных степеней . . . . . . 13 1.10. Корреляции степеней вершин . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.11. Кластерные коэффициенты . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.12. Число копий фиксированного графа . . . . . . . . . . . . . . . . . . . . 17 Глава 2. Модели хост-графов . . . . . . . . . . . . . . . . . . . . . . . . 19 2.1. Общая концепция. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.2. Модель Эрдеша–Реньи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.3. Модели Барабаши–Альберт . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.4. Модель Боллобаша–Риордана: определения . . . . . . . . . . . . . . . 24 2.4.1. Динамическое определение модели . . . . . . . . . . . . . . . . . 24 2.4.2. Статическое определение модели . . . . . . . . . . . . . . . . . . 26 2.5. Модель Боллобаша–Риордана: результаты . . . . . . . . . . . . . . . . 28 2.5.1. Гигантская компонента, устойчивость и уязвимость . . . . . . 28 2.5.2. Диаметр . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
Оглавление 2.5.3. Степени вершин . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 2.5.4. Вторые степени вершин . . . . . . . . . . . . . . . . . . . . . . . . 30 2.5.5. Пейджранк . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 2.5.6. Количество ребер между вершинами заданных степеней . . 33 2.5.7. Кластерные коэффициенты . . . . . . . . . . . . . . . . . . . . . . 34 2.5.8. Число копий фиксированного графа . . . . . . . . . . . . . . . . 34 2.6. Уточнения модели Боллобаша–Риордана: начальная притягательность вершины . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 2.6.1. Несколько вводных замечаний . . . . . . . . . . . . . . . . . . . . 36 2.6.2. Модель Бакли–Остгуса . . . . . . . . . . . . . . . . . . . . . . . . . 36 2.6.3. Модель Мори . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 2.6.4. Степени вершин . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 2.6.5. Вторые степени вершин . . . . . . . . . . . . . . . . . . . . . . . . 38 2.6.6. Количество ребер между вершинами заданных степеней . . 39 2.6.7. Кластерные коэффициенты . . . . . . . . . . . . . . . . . . . . . . 40 2.6.8. Число копий фиксированного графа . . . . . . . . . . . . . . . . 41 2.6.9. Удивительное соответствие модели Бакли–Остгуса реальному хост-графу . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 2.6.10. Классификация ссылочного спама . . . . . . . . . . . . . . . . . 44 2.7. Дальнейшие уточнения модели Боллобаша–Риордана. . . . . . . . . 44 2.7.1. Несколько вводных замечаний . . . . . . . . . . . . . . . . . . . . 44 2.7.2. Модель Боллобаша–Боргса–Риордана–Чайес . . . . . . . . . . 45 2.7.3. Модель копирования. . . . . . . . . . . . . . . . . . . . . . . . . . . 47 2.7.4. Модель Купера–Фриза . . . . . . . . . . . . . . . . . . . . . . . . . 49 2.7.5. Модель Холма–Кима . . . . . . . . . . . . . . . . . . . . . . . . . . 51 Глава 3. Схемы и идеи некоторых доказательств . . . . . . . . 53 3.1. Несколько вводных слов . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 3.2. Схема доказательства теоремы 9 . . . . . . . . . . . . . . . . . . . . . . 53 3.3. Схема доказательства теоремы 10 . . . . . . . . . . . . . . . . . . . . . . 56 3.4. Неравенства плотной концентрации и теоремы об асимптотическом распределении. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 3.4.1. Несколько вступительных слов . . . . . . . . . . . . . . . . . . . 57 3.4.2. Неравенство Чебышёва . . . . . . . . . . . . . . . . . . . . . . . . . 57 3.4.3. Неравенство Азумы–Хёффдинга . . . . . . . . . . . . . . . . . . . 58 3.4.4. Неравенство Талаграна . . . . . . . . . . . . . . . . . . . . . . . . . 59 Список литературы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
ВВЕДЕНИЕ Еще каких-то 20 лет назад про существование сети Интернет мало кто знал. Сейчас же Интернет прочно вошел в нашу жизнь, став для нас незаменимым инструментом получения и распространения информации, а также, конечно, общения. Поиск, электронная почта, блоги, социальные сети, скайп и пр., — без этого многие уже не могут обойтись. Всемирная паутина невероятно разрослась за эти годы. Может показаться даже, что в ней царит полный хаос: так велика она и, на первый взгляд, неконтролируема. И тем не менее, существуют законы, по которым развивается Интернет. Изучение этих законов так же увлекательно, как и изучение законов природы. Начато оно было практически одновременно с появлением сети. И к настоящему времени возникла целая научная дисциплина, лежащая на стыке физики, математики и социологии. Этой небольшой книгой мы открываем серию брошюр, посвященных исследованиям Интернета. Здесь мы сделаем акцент на интерпретации Интернета как графа, вершины которого, в зависимости от контекста, суть страницы или сайты (хосты), а ребра — (гипер)ссылки между ними. Об удивительных свойствах этого графа — графа, растущего с течением времени, — и о неожиданно простых моделях, в которых эти свойства реализуются, мы и поговорим в книге. Для понимания книги читателю потребуются начальные знания в области комбинаторики, теории графов и теории вероятностей. Структурно книга устроена следующим образом. В первой главе мы расскажем о многочисленных характеристиках Интернета, которые изучались и продолжают изучаться исследователями. Эти-то характеристики и покажут, насколько ошибочно первоначальное впечатление о полном хаосе, якобы царящем во всемирной паутине. Во второй главе мы опишем
Введение несколько вероятностных моделей веба и сформулируем теоретические результаты, которые выявят как сильные, так и слабые стороны моделей. При этом мы пройдем основные этапы того пути, который прошли исследователи Интернета: от простейших моделей конца 90-х годов ХХ века до значительно более точных моделей, возникших буквально в последние несколько лет. Правда, мы будем следовать лишь одному из важнейших направлений в идеологии построения моделей. А именно, мы обсудим только идею так называемого предпочтительного присоединения. Это уже огромный пласт современной Интернет-математики. Его мы и постараемся вскрыть в нашей первой книге. Наконец, в третьей главе мы приведем схемы доказательств некоторых теорем из второй главы.
Г Л А В А 1 СВОЙСТВА ИНТЕРНЕТА 1.1. ОСНОВНЫЕ ОБЪЕКТЫ И ОБЩАЯ ИДЕОЛОГИЯ ИХ ИЗУЧЕНИЯ Существуют два типа графов, возникающих при изучении всемирной паутины. С одной стороны, можно считать вершинами графа компьютеры, подключенные к Интернету, или серверы, через которые идет Интернет-коммуникация. В этом случае ребрами являются линии связи. Это такой граф «из железа». Он называется Интернет-графом, и он нас не будет интересовать. Нашим объектом послужит более «виртуальный» граф. Его вершины — это страницы или сайты в Интернете, а ребра — (гипер)ссылки между ними. Если вершины — страницы, граф называется веб-графом; если вершины — сайты (хосты), граф называется хост-графом. Хост-граф проще для статистического анализа, так как он гораздо меньше веб-графа. В хост-графе есть и кратные ребра (несколько различных ссылок с одного сайта на другой), и (кратные) петли (ссылки между страницами внутри сайта), и, конечно, хост-граф (как и веб-граф) ориентирован. Мы будем, как правило, говорить о хост-графах. Предположим, нас интересует какая-то статистика хост-графа. Например, число ребер в нем. Разумеется, желая узнать ее приблизительное значение, мы действуем так же, как и всегда в статистическом анализе. Мы берем достаточно репрезентативную (большую) выборку, состоящую из хост-графов, которые получены в результате взятия надлежащего количества «временн ´ых срезов». И для каждого из этих графов мы считаем число ребер xi. Получается выборка x1, . . . , xn. Пользуясь теми или иными статистическими инструментами, мы делаем те
Гл. 1. Свойства Интернета или иные заключения о природе числа ребер. Иными словами, если мы произносим фразу «хост-граф имеет такое-то количество ребер» или «степени вершин хост-графа распределены так-то», то мы подразумеваем не один хост-граф, но последовательность хост-графов — случайный процесс, статистики которого мы изучаем. В настоящей книге нас не будут интересовать конкретные инструменты статистического анализа, с помощью которых получены различные наблюдения об Интернете. С ними можно будет познакомиться при чтении исходных публикаций, ссылки на которые мы будем давать. Для нас важнее будет сама картина Интернета, и именно на ее основе мы будем строить модели веба. Итак, в следующих разделах мы опишем несколько весьма удивительных статистических закономерностей, которым подчиняются хост-графы. 1.2. КОЛИЧЕСТВО РЕБЕР Хост-граф, да и веб-граф тоже, — графы разреженные. Принято считать, что если у такого графа n вершин, то ребер у него mn, где m — некоторая константа, не меньшая единицы. Разумеется, это лишь допущение. Скорее, статистика такова, что число ребер — это Θ(n), т. е. оно зажато в пределах от m1n до m2n с постоянными m1, m2. Почему при таких характеристиках граф разрежен? Очень просто: даже если забыть о наличии в графе кратных ребер, за счет которых общее количество ребер могло бы быть сколь угодно большим, все равно на n вершинах бывает вплоть до Θ(n2) ребер, и эта функция растет существенно быстрее линейной функции mn. Наблюдение о разреженности графов страниц и хостов — одно из самых первых и простых (см., например, [1–3]). 1.3. ГИГАНТСКАЯ КОМПОНЕНТА Понятие гигантской компоненты является одним из центральных в теории графов. Как всегда, нелепо пытаться определить его для одного конкретного графа. Оно имеет смысл лишь для бесконечных последовательностей графов. Итак, пусть дана последовательность графов {Gn = (Vn, En)}, в которой lim n→+∞ |Vn| = +∞. Говорят, что графы Gn содержат гигантскую компоненту связности, если существует такая константа γ > 0, что для каждого n размер наибольшей связной компоненты в Gn не меньше γ|Vn|.
1.4. Устойчивость и уязвимость 9 Одно из важнейших наблюдений в науке о «реальных сетях» (т. е., в частности, о веб- и хост-графах) состоит в том, что гигантская компонента в этих сетях всегда есть. Исследователи, которые не очень склонны к черезмерной математической аккуратности (а таких в этой области большинство), подходят к понятию гигантской компоненты даже менее формально, чем это сделали мы. Обычно они просто говорят, что у графа (отдельного графа!) есть гигантская связная компонента, коль скоро «существенная доля его вершин» образует такую компоненту. Разумеется, совершенно не ясно, что такое «существенная» доля. Грубо говоря, одна сотая — это не существено, а девять десятых точно годится. Факт тот, что даже в этом нестрогом смысле принято считать, что и веб-, и хост-граф содержат гигантскую компоненту. Тем более они ее содержат в смысле данного выше аккуратного определения. И в строгом, и в нестрогом определении гигантская компонента, как правило, ровно одна. Интуиция за этим следующая. Трудно поверить, что, например, в хост-графе, у которого 1 000 000 000 (миллиард) вершин, может быть две связных компоненты размера 400 000 000 (четыреста миллионов) и ни одной ссылки между ними: слишком велика вероятность того, что хотя бы один владелец сайта из первой компоненты процитирует хотя бы один сайт из второй компоненты! Повторим, что все сказанное только что — это лишь способ осознать суть понятия гигантской компоненты. Строгое определение дано, и в дальнейшем мы предпочтем апеллировать только к нему. 1.4. УСТОЙЧИВОСТЬ И УЯЗВИМОСТЬ Исключительно важное для практики наблюдение о веби хост-графах состоит в том, что они устойчивы к случайным разрушениям (нарушениям функциональности) вершин, но уязвимы, коль скоро атакам целенаправленно подвергаются вершины максимальной степени — так называемые «хабы». Строго указанные статистические результаты можно сформулировать в следующих двух теоремах (см. [4]). Теорема 1. Пусть Gn — последовательность хост-графов, растущих с течением времени n. Пусть p ∈ (0, 1) и каждая вершина графа Gn уничтожается с вероятностью p независимо от всех остальных вершин. Тогда с вероятностью, стремящейся к единице при n → ∞, в последовательности случайных графов Gn,p есть гигантская компонента. Разумеется, размер гигантской компоненты (константа γ) тем меньше, чем ближе p к единице.
Гл. 1. Свойства Интернета Теорема 2. Пусть Gn = (Vn, En) — последовательность хост-графов, растущих с течением времени n. Пусть c ∈ (0, 1). Упорядочим вершины Gn по невозрастанию величины степени (имеется в виду сумма входящей и исходящей степеней). Удалим из Gn первые [c|Vn|] вершин (здесь [x] — целая часть числа x). Тогда существует такая константа c∗, что при c ⩽ c∗ в графе Gn,c есть гигантская компонента, а при c > c∗ в графе Gn,c гигантской компоненты нет. В последней теореме мы наблюдаем исключительно важное для физики явление — так называемый фазовый переход: уязвимость к атакам на хабы возникает скачкообразно; до c∗ ее нет, но, едва мы преодолеваем порог ∼ c∗|Vn|, и граф разваливается на мелкие компоненты — компоненты размера o(|Vn|) каждая. 1.5. ДИАМЕТР Как известно, диаметр графа — это максимальное расстояние между его вершинами, а расстояние в графе — это число ребер в кратчайшем реберном пути. Разумеется, у несвязного графа, каковым является веб-граф, диаметр не определен (или равен бесконечности). Однако вполне можно искать диаметр гигантской компоненты. И вот он все долгие годы исследований остается практически постоянным — не превосходящим 10–20, — и едва ли не уменьшается (см. [3]). Это при условии, что переходы осуществляются с учетом ориентации ребер. Если ориентацию убрать, то диаметр уменьшается и вовсе до 5–6. Примерно то же верно и для хост-графа. Это, по сути, знаменитый закон шести рукопожатий — статистическое наблюдение, состоящее в том, что любые два человека в мире знакомы друг с другом через не более чем пять посредников. Отметим, что в свете разреженности хост-графа столь малый диаметр весьма неожидан и замечателен. По-английски это свойство принято называть «small-world phenomenon», т. е. «мир тесен» (ср. [5]). 1.6. СТЕПЕНИ ВЕРШИН Обозначим indeg v, outdeg v, deg v — входящую, исходящую и полную степень вершины v соответственно (петля дает вклад 1 и в indeg v, и в outdeg v, т. е. вклад 2 в deg v). Замечательный статистический закон состоит в том, что каждая из этих степеней и в веб-графе, и в хост-графе, и во многих других реальных сетях (социальных,
1.7. Вторые степени вершин 11 биологических и пр.) подчиняется степенному закону распределения (см. [1,2]) с тем или иным показателем. Теорема 3. Пусть Gn = (Vn, En) — последовательность реальных сетей, растущих с течением времени n. Пусть dn ∈ N. Пусть adeg — одна из трех видов степеней. Тогда существуют константы γ и c, с которыми |{v ∈ Vn : adeg v = dn}| |Vn| ∼ c dγ n . Константа γ полностью задает распределение: она является степенью, определяющей скорость убывания доли вершин данной степени dn. Константу c можно найти из тех соображений, что сумма всех долей (вероятностей того, что степень вершины равна dn) есть 1. Степенные законы в сетях стали изучать задолго до появления Интернета (см., например, [6]). Как правило, γ ∈ (2, 3). Например, для adeg = deg и хост-графа γ ≈ 2,3 (см. [7]). 1.7. ВТОРЫЕ СТЕПЕНИ ВЕРШИН Степени вершин хост-графа, о которых мы писали в предыдущем разделе, свидетельствуют, в частности, об их популярности: чем больше ссылок на данный сайт, тем он, конечно, популярнее. Однако такую характеристику достаточно легко увеличить искусственно, создав множество фиктивных сайтов, которые будут цитировать сайт, подлежащий раскрутке. И, разумеется, спамеры и оптимизаторы этим активно пользуются. Поэтому важно не только количество ссылок на сайт, но и авторитетность тех сайтов, владельцы которых эти ссылки проставляют. В простейшем случае достаточно посмотреть на степени тех вершин, которые соединены ребром с данной вершиной v хостграфа. В частности, можно изучать вторую степень вершины v. Ее, в свою очередь, можно определять по-разному. Например, можно считать ее равной числу вершин, отстоящих на расстояние 2 от v, или числу вершин, отстоящих на расстояние ⩽ 2 от v, или сумме степеней вершин, отстоящих на расстояние 1 от v, и т. д. На рис. 1 показано, насколько разнятся данные определения. Можно показать, что вторые степени вершин подчиняются степенным законам, как и обычные степени. Разумеется, давались определения и k-х степеней с k > 2. Но нас такие степени в дальнейшем интересовать не будут. В следующем разделе
Гл. 1. Свойства Интернета Рис. 1 мы сразу дадим определение пейджранка, который в некотором роде содержит в себе информацию обо всех степенях всех вершин графа. 1.8. ПЕЙДЖРАНК Пейджранк — это, при всей своей простоте, одна из самых сильных характеристик вершины веб-графа, уточняющая в некотором смысле понятие степени, второй степени и т. д. Пусть Gn = (Vn, En) — веб-граф (пока именно веб-граф). Обозначим PR(v) пейджранк его вершины v. Тогда PR(i), где i ∈ {1, . . . , |Vn|}, определяется как решение системы линейных уравнений PR(i) = c j→i PR(j) outdeg j + c |Vn| j∈D PR(j) + 1 − c |Vn| , i = 1, . . . , |Vn|, где c ∈ (0, 1) — константа, а D — множество вершин, исходящие степени которых равны нулю. Смысл пейджранка очень простой. Мы хотим учесть не только количество ссылок на данную страницу веб-графа, но и качество ссылок. Пусть качество — это пейджранк. Тогда качество (пейджранк) страницы i и выражается, грубо говоря, как сумма качеств (пейджранков) страниц j, j → i, нормированных на величины outdeg j. При этом надо учитывать, что есть страницы нулевой исходящей степени. Величина 1 − c называется вероятностью телепортации. Идея в том, что мы можем представлять себе человека, который блуждает по сети: с вероятностью c он на очередном шаге переходит по ссылке, а с вероятностью 1 − c совершает «скачок» на случайную страницу.
Доступ онлайн
В корзину