Вебграф описує спрямовані посилання між сторінками Всесвітнього павутиння Загалом граф складається з кількох вершин деяк

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

Властивості

Розподіл степенів вебграфа дуже відрізняється від розподілу степенів класичної моделі випадкового графа, моделі Ердеша — Реньї: в моделі Ердеша — Реньї існує дуже мало великих степенів вузлів відносно розподілу степенів вебграфа. Однак точний розподіл неясний: він відносно добре описується логнормальним розподілом, а також моделлю Барабаші — Альберта для степеневих законів.
Вебграф є прикладом безмасштабної мережі.

Додатки

Вебграф використовують для:

обчислення PageRank вебсторінок;
обчислення персоналізованого PageRank;
виявлення вебсторінок подібної тематики лише за допомогою теоретико-графових властивостей, як-от спільне цитування;
а також визначення посредників і авторитетів в інтернеті для .

Примітки

P. Erdős, A. Renyi, Publ. Math. Inst. Hung. Acad. Sci. 5 (1960)
Meusel, R.; Vigna, S.; Lehmberg, O.; Bizer, C. (2015). The Graph Structure in the Web - Analyzed on Different Aggregation Levels (PDF). Journal of Web Science. 1 (1): 33—47. doi:10.1561/106.00000003. {{}}: |hdl-access= вимагає |hdl= ()
Clauset, A.; Shalizi, C. R.; Newman, M. E. J. (2009). Power-law distributions in empirical data. SIAM Rev. 51 (4): 661—703. arXiv:0706.1062. Bibcode:2009SIAMR..51..661C. doi:10.1137/070710111.
Barabási, Albert-László; Albert, Réka (October 1999). Emergence of scaling in random networks (PDF). Science. 286 (5439): 509—512. arXiv:cond-mat/9910332. Bibcode:1999Sci...286..509B. doi:10.1126/science.286.5439.509. PMID 10521342..
S. Brin, L. Page, Computer Networks and ISDN Systems 30, 107 (1998)
Glen Jeh and Jennifer Widom. 2003. Scaling personalized web search. In Proceedings of the 12th international conference on World Wide Web (WWW '03). ACM, New York, NY, USA, 271—279. DOI:10.1145/775152.775191
Kumar, Ravi; Raghavan, Prabhakar; Rajagopalan, Sridhar; Tomkins, Andrew (1999). Trawling the Web for emerging cyber-communities. Computer Networks. 31 (11–16): 1481—1493. CiteSeerX 10.1.1.89.4025. doi:10.1016/S1389-1286(99)00040-7.

Посилання

Вебграфи в Yahoo Sandbox
Вебграфи в Університеті Мілана — Лабораторія веб-алгоритміки
Вебграфи в Стенфорді — SNAP
Вебграф на сервері Erdős Webgraph
Web Data Commons — граф гіперпосилань

[1] P. Erdős, A. Renyi, Publ. Math. Inst. Hung. Acad. Sci. 5 (1960)

[2] Meusel, R.; Vigna, S.; Lehmberg, O.; Bizer, C. (2015). The Graph Structure in the Web - Analyzed on Different Aggregation Levels (PDF). Journal of Web Science. 1 (1): 33—47. doi:10.1561/106.00000003. {{}}: |hdl-access= вимагає |hdl= ()

[3] Clauset, A.; Shalizi, C. R.; Newman, M. E. J. (2009). Power-law distributions in empirical data. SIAM Rev. 51 (4): 661—703. arXiv:0706.1062. Bibcode:2009SIAMR..51..661C. doi:10.1137/070710111.

[4] Barabási, Albert-László; Albert, Réka (October 1999). Emergence of scaling in random networks (PDF). Science. 286 (5439): 509—512. arXiv:cond-mat/9910332. Bibcode:1999Sci...286..509B. doi:10.1126/science.286.5439.509. PMID 10521342..

[5] S. Brin, L. Page, Computer Networks and ISDN Systems 30, 107 (1998)

[6] Glen Jeh and Jennifer Widom. 2003. Scaling personalized web search. In Proceedings of the 12th international conference on World Wide Web (WWW '03). ACM, New York, NY, USA, 271—279. DOI:10.1145/775152.775191

[7] Kumar, Ravi; Raghavan, Prabhakar; Rajagopalan, Sridhar; Tomkins, Andrew (1999). Trawling the Web for emerging cyber-communities. Computer Networks. 31 (11–16): 1481—1493. CiteSeerX 10.1.1.89.4025. doi:10.1016/S1389-1286(99)00040-7.