Вебграф

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

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

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

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

Приложения

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

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

Ссылки

1. П. Эрдеш, А. Реньи, Publ. Математика. Инст. Хунг. акад. наук. 5 (1960)
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. С. Брин , Л. Пейдж , Компьютерные сети и системы ISDN 30, 107 (1998)
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 - График гиперссылок