Вебграф

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

Характеристики

Распределение степеней веб-графа сильно отличается от распределения степеней классической модели случайного графа, модели Эрдеша – Реньи : ^[1] в модели Эрдеша-Реньи очень мало узлов большой степени по сравнению с распределением степеней веб-графа. Точное распределение неясно, ^[2] однако: оно относительно хорошо описывается логнормальным распределением, а также моделью Барабаши-Альберта для степенных законов . ^[3]^[4]
Вебграф является примером безмасштабной сети .

Приложения

Вебграф используется для:

вычисление PageRank ^[5] WWW-страниц;
расчет персонализированного PageRank; ^[6]
обнаружение веб-страниц схожих тем только с помощью теоретико-графовых свойств, таких как совместное цитирование; ^[7]
и определение узлов и органов в сети для алгоритма HITS .

Ссылки

^ П. Эрдеш, А. Реньи, Publ. Математика. Инст. Хунг. акад. Наука 5 (1960)
^ Мейзель, Р.; Винья, С.; Лемберг, О.; Бизер, К. (2015). «Структура графа в Интернете — анализ на разных уровнях агрегации» (PDF) . Журнал веб-науки . 1 (1): 33–47. дои : 10.1561/106.00000003 . HDL : 2434/372411 .
^ Клозе, А.; Шализи, ЧР; Ньюман, МЭД (2009). «Степенное распределение в эмпирических данных». СИАМ преп . 51 (4): 661–703. arXiv : 0706.1062 . Бибкод : 2009SIAMR..51..661C . дои : 10.1137/070710111 . S2CID 9155618 .
^ Барабаши, Альберт-Ласло; Альберт, Река (октябрь 1999 г.). «Появление масштабирования в случайных сетях» (PDF) . Наука . 286 (5439): 509–512. arXiv : cond-mat/9910332 . Бибкод : 1999Sci...286..509B . дои : 10.1126/science.286.5439.509 . ПМИД 10521342 . S2CID 524106 . .
^ С. Брин , Л. Пейдж , Компьютерные сети и ISDN системы 30, 107 (1998)
^ Глен Дже и Дженнифер Уидом. 2003. Масштабирование персонализированного веб-поиска. В материалах 12-й международной конференции по Всемирной паутине (WWW '03). ACM, Нью-Йорк, штат Нью-Йорк, США, 271–279. дои : 10.1145/775152.775191
^ Кумар, Рави; Рагхаван, Прабхакар; Раджагопалан, Шридхар; Томкинс, Эндрю (1999). «Исследование Интернета в поисках новых киберсообществ». Компьютерные сети . 31 (11–16): 1481–1493. CiteSeerX 10.1.1.89.4025 . дои : 10.1016/S1389-1286(99)00040-7 . S2CID 7069190 .

Внешние ссылки

[1] П. Эрдеш, А. Реньи, Publ. Математика. Инст. Хунг. акад. Наука 5 (1960)

[2] Мейзель, Р.; Винья, С.; Лемберг, О.; Бизер, К. (2015). «Структура графа в Интернете — анализ на разных уровнях агрегации» (PDF) . Журнал веб-науки . 1 (1): 33–47. дои : 10.1561/106.00000003 . HDL : 2434/372411 .

[3] Клозе, А.; Шализи, ЧР; Ньюман, МЭД (2009). «Степенное распределение в эмпирических данных». СИАМ преп . 51 (4): 661–703. arXiv : 0706.1062 . Бибкод : 2009SIAMR..51..661C . дои : 10.1137/070710111 . S2CID 9155618 .

[4] Барабаши, Альберт-Ласло; Альберт, Река (октябрь 1999 г.). «Появление масштабирования в случайных сетях» (PDF) . Наука . 286 (5439): 509–512. arXiv : cond-mat/9910332 . Бибкод : 1999Sci...286..509B . дои : 10.1126/science.286.5439.509 . ПМИД 10521342 . S2CID 524106 . .

[5] С. Брин , Л. Пейдж , Компьютерные сети и ISDN системы 30, 107 (1998)

[6] Глен Дже и Дженнифер Уидом. 2003. Масштабирование персонализированного веб-поиска. В материалах 12-й международной конференции по Всемирной паутине (WWW '03). ACM, Нью-Йорк, штат Нью-Йорк, США, 271–279. дои : 10.1145/775152.775191

[7] Кумар, Рави; Рагхаван, Прабхакар; Раджагопалан, Шридхар; Томкинс, Эндрю (1999). «Исследование Интернета в поисках новых киберсообществ». Компьютерные сети . 31 (11–16): 1481–1493. CiteSeerX 10.1.1.89.4025 . дои : 10.1016/S1389-1286(99)00040-7 . S2CID 7069190 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]