Webgraph - Webgraph
В веб-граф описывает направленные ссылки между страницами Всемирная паутина. А график, в общем, состоит из нескольких вершин, пар соединенных ребрами. В ориентированный граф, ребра - это направленные прямые или дуги. Веб-граф - это ориентированный граф, вершины которого соответствуют страницам WWW, а направленное ребро соединяет страницу X со страницей Y, если существует гиперссылка на странице X, ссылаясь на страницу Y.
Характеристики
- В распределение степеней веб-графа сильно отличается от распределения степеней классической модели случайного графа, Модель Эрдеша – Реньи:[1] в модели Эрдеша – Реньи очень мало узлов с большой степенью по сравнению с распределением степеней веб-графа. Точное распределение неясно,[2] однако: это относительно хорошо описано логнормальный распространение, а также Модель Барабаши – Альберта за законы власти.[3][4]
- Веб-граф - это пример безмасштабная сеть.
Приложения
- Веб-граф используется для вычисления PageRank [5] веб-страниц.
- Веб-график используется для расчета персонализированного рейтинга страниц.[6]
- Веб-граф может использоваться для обнаружения веб-страниц схожей тематики только с помощью теоретико-графических свойств, таких как совместное цитирование. [7]
- Веб-граф применяется в Алгоритм HITS для определения узловых точек и органов власти в Интернете.
Рекомендации
- ^ П. Эрдеш, А. Реньи, Publ. Математика. Inst. Подвешенный. Акад. Sci. 5 (1960)
- ^ Meusel, R .; Vigna, S .; Lehmberg, O .; Бизер, К. (2015). «Структура графа в сети - анализируется на разных уровнях агрегирования» (PDF). Журнал веб-науки. 1 (1): 33–47. Дои:10.1561/106.00000003.
- ^ Clauset, A .; Shalizi, C.R .; Ньюман, М. Э. Дж. (2007). «Степенные распределения в эмпирических данных». SIAM Rev. 51 (4): 661–703. arXiv:0706.1062. Bibcode:2009SIAMR..51..661C. Дои:10.1137/070710111.
- ^ Барабаши, Альберт-Ласло; Альберт, Река (октябрь 1999 г.). «Появление масштабирования в случайных сетях» (PDF). Наука. 286 (5439): 509–512. arXiv:cond-mat / 9910332. Bibcode:1999Научный ... 286..509Б. Дои:10.1126 / science.286.5439.509. PMID 10521342..
- ^ С. Брин, Л. Пейдж, Компьютерные сети и системы 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.