Вебграф

График связанных веб-страниц

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

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

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

Приложения

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

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

Ссылки

1. Эрдёш, Пауль ; Реньи, Альфред (1960). «Об эволюции случайных графов» (PDF) . Издание Математического института Венгерской академии наук . 5 : 17–61.
2. Мейзель, Р.; Винья, С.; Лемберг, О.; Бизер, К. (2015). «Структура графа в Интернете — анализ на разных уровнях агрегации» (PDF) . Журнал Web Science . 1 (1): 33–47. doi :10.1561/106.00000003. hdl : 2434/372411 .
3. Clauset, A.; Shalizi, CR; Newman, MEJ (2009). «Степенные распределения в эмпирических данных». SIAM Rev. 51 ( 4): 661–703. arXiv : 0706.1062 . Bibcode :2009SIAMR..51..661C. doi :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. PMID  10521342. S2CID  524106..
5. Брин, Сергей ; Пейдж, Лоуренс (1998-04-01). «Анатомия крупномасштабной гипертекстовой поисковой системы в Интернете». Компьютерные сети и системы ISDN . Труды Седьмой международной конференции World Wide Web. 30 (1): 107–117. doi :10.1016/S0169-7552(98)00110-X. ISSN  0169-7552.
6. Глен Дже и Дженнифер Видом. 2003. Масштабирование персонализированного веб-поиска. В трудах 12-й международной конференции по Всемирной паутине (WWW '03). ACM, Нью-Йорк, США, 271–279. doi :10.1145/775152.775191
7. Кумар, Рави; Рагхаван, Прабхакар; Раджагопалан, Шридхар; Томкинс, Эндрю (1999). «Прочесывание Интернета в поисках новых киберсообществ». Компьютерные сети . 31 (11–16): 1481–1493. CiteSeerX 10.1.1.89.4025 . doi :10.1016/S1389-1286(99)00040-7. S2CID  7069190. 

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

• Веб-графы в Yahoo Sandbox
• Веб-графы в Миланском университете – Лаборатория веб-алгоритмики
• Вебграфы в Стэнфорде – SNAP
• Вебграф на сервере вебграфов Erdős
• Web Data Commons - График гиперссылок