Webgraph

The webgraph describes the directed links between pages of the World Wide Web. A graph, in general, consists of several vertices, some pairs connected by edges. In a directed graph, edges are directed lines or arcs. The webgraph is a directed graph, whose vertices correspond to the pages of the WWW, and a directed edge connects page X to page Y if there exists a hyperlink on page X, referring to page Y.

Properties

Applications

The webgraph is used for:

  • computing the PageRank[5] of the WWW-pages;
  • computing the personalized PageRank;[6]
  • detecting webpages of similar topics, through graph-theoretical properties only, like co-citation;[7]
  • and identifying hubs and authorities in the web for HITS algorithm.

References

  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:2434/372411.
  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. S2CID 9155618.
  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. S2CID 524106..
  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. S2CID 7069190.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.