Вебграф

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

Вебграф описує спрямовані посилання між сторінками Всесвітнього павутиння. Загалом, граф складається з кількох вершин, деякі з них з'єднані ребрами. В орієнтованому графі ребра є спрямованими лініями або дугами. Вебграф — це орієнтований граф, вершини якого відповідають сторінкам 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.

Посилання

[ред. | ред. код]