Вебграф

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

Властивості

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

Додатки

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

обчислення PageRank^[5] вебсторінок;
обчислення персоналізованого PageRank^[6];
виявлення вебсторінок подібної тематики лише за допомогою теоретико-графових властивостей, як-от спільне цитування^[7];
а також визначення посредників і авторитетів в інтернеті для алгоритму 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 (PDF). Journal of Web Science. 1 (1): 33—47. doi:10.1561/106.00000003. {{cite journal}}: |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 (Жовтень 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.

Посилання

[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. {{cite journal}}: |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 (Жовтень 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.

[1]

[2]

[3]

[4]

[5]

[6]

[7]