Веб- граф описывает направленные ссылки между страницами всемирной паутины . Граф , в общем, состоит из нескольких вершин, некоторые пары соединенных между собой ребрами. В ориентированном графе ребра представляют собой направленные прямые или дуги. Веб-граф - это ориентированный граф, вершины которого соответствуют страницам WWW, а направленное ребро соединяет страницу X со страницей Y, если на странице X существует гиперссылка , относящаяся к странице Y.
Характеристики
- Распределение степеней веб-графа сильно отличается от распределения степеней классической модели случайного графа, модели Эрдеша – Реньи : [1] в модели Эрдеша – Реньи очень мало узлов с высокой степенью по сравнению с распределением степеней веб-графа. Однако точное распределение неясно [2] : оно относительно хорошо описывается логнормальным распределением, а также моделью Барабаши – Альберта для степенных законов . [3] [4]
- Веб-граф - это пример безмасштабируемой сети .
Приложения
- Веб-граф используется для:
- вычисление PageRank [5] WWW-страниц;
- вычисление персонализированного PageRank; [6]
- обнаружение веб-страниц схожей тематики только с помощью теоретико-графических свойств, таких как совместное цитирование; [7]
- и определение узлов и органов власти в сети для алгоритма HITS .
Рекомендации
- ↑ P. Erds, A. Renyi, Publ. Математика. Inst. Повесили. Акад. Sci. 5 (1960)
- ^ Meusel, R .; Vigna, S .; Lehmberg, O .; Бизер, К. (2015). «Структура графа в сети - анализируется на разных уровнях агрегирования» (PDF) . Журнал веб-науки . 1 (1): 33–47. DOI : 10.1561 / 106.00000003 . hdl : 2434/372411 .
- ^ Clauset, A .; Шализи, ЧР; Ньюман, MEJ (2007). «Степенные распределения в эмпирических данных». SIAM Ред . 51 (4): 661–703. arXiv : 0706.1062 . Bibcode : 2009SIAMR..51..661C . DOI : 10.1137 / 070710111 .
- ^ Барабаши, Альберт-Ласло; Альберт, Река (октябрь 1999 г.). «Появление масштабирования в случайных сетях» (PDF) . Наука . 286 (5439): 509–512. arXiv : cond-mat / 9910332 . Bibcode : 1999Sci ... 286..509B . DOI : 10.1126 / science.286.5439.509 . PMID 10521342 ..
- ^ С. Брин , Л. Пейдж , Компьютерные сети исистемы ISDN 30, 107 (1998)
- ^ Глен Дже и Дженнифер Видом. 2003. Масштабирование персонализированного веб-поиска. В материалах 12-й международной конференции по всемирной паутине (WWW '03). ACM, Нью-Йорк, Нью-Йорк, США, 271–279. DOI : 10,1145 / 775152,775191
- ^ Кумар, Рави; Рагхаван, Прабхакар; Раджагопалан, Шридхар; Томкинс, Эндрю (1999). «Поиск в сети новых киберсообществ». Компьютерные сети . 31 (11–16): 1481–1493. CiteSeerX 10.1.1.89.4025 . DOI : 10.1016 / S1389-1286 (99) 00040-7 .
Внешние ссылки
- Веб-графики в Yahoo Sandbox
- Веб-графики в Миланском университете - Лаборатория веб-алгоритмов
- Веб-графики в Стэнфорде - SNAP
- Webgraph на сервере Erdős Webgraph
- Общие веб-данные - График гиперссылок