Вебграф

орієнтований граф, який описує спрямовані посилання між сторінками Всесвітнього павутиння

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

Властивості

ред.

Додатки

ред.

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

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

Примітки

ред.
  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 (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.

Посилання

ред.