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

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

Властивості Редагувати

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

Додатки Редагувати

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

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

Примітки Редагувати

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. Journal of Web Science 1 (1): 33–47. doi:10.1561/106.00000003.
Clauset, A.; Shalizi, C. R.; Newman, M. E. J. (2009). Power-law distributions in empirical data. SIAM Rev. 51 (4): 661–703. Bibcode:2009SIAMR..51..661C. arXiv:0706.1062. doi:10.1137/070710111.
Barabási, Albert-László; Albert, Réka (October 1999). Emergence of scaling in random networks. Science 286 (5439): 509–512. Bibcode:1999Sci...286..509B. PMID 10521342. arXiv:cond-mat/9910332. doi:10.1126/science.286.5439.509. .
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. doi:10.1016/S1389-1286(99)00040-7. Проігноровано невідомий параметр |citeseerx= (довідка)

Посилання Редагувати

[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. Journal of Web Science 1 (1): 33–47. doi:10.1561/106.00000003.

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

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

[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. doi:10.1016/S1389-1286(99)00040-7. Проігноровано невідомий параметр |citeseerx= (довідка)