Webgraph
From Wikipedia, the free encyclopedia
Template:Short description A webgraph is a set of 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.[1]
Properties
- The degree distribution of the webgraph strongly differs from the degree distribution of the classical random graph model, the Erdős–Rényi model:[2] in the Erdős–Rényi model, there are very few large degree nodes, relative to the webgraph's degree distribution. The precise distribution is unclear,[3] however: it is relatively well described by a lognormal distribution, as well as the Barabási–Albert model for power laws.[4][5]
- The webgraph is an example of a scale-free network.
Applications
The webgraph is used for:
- computing the PageRank[6] of the world wide web's pages;
- computing the personalized PageRank;[7]
- detecting webpages of similar topics, through graph-theoretical properties only, like co-citation;[8]
- and identifying hubs and authorities in the web for HITS algorithm.
References
Page Template:Reflist/styles.css has no content.
- ^ Page Module:Citation/CS1/styles.css has no content.Manning, Christopher D.; Raghavan, Prabhakar; Schütze, Hinrich (2008). "The web graph". Introduction to Information Retrieval. Cambridge University Press.
- ^ Page Module:Citation/CS1/styles.css has no content.Erdős, Paul; Rényi, Alfréd (1960). "On the evolution of random graphs" (PDF). Publication of the Mathematical Institute of the Hungarian Academy of Sciences. 5: 17–61.
- ^ Page Module:Citation/CS1/styles.css has no content.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.
- ^ Page Module:Citation/CS1/styles.css has no content.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.
- ^ Page Module:Citation/CS1/styles.css has no content.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..
- ^ Page Module:Citation/CS1/styles.css has no content.Brin, Sergey; Page, Lawrence (1998-04-01). "The anatomy of a large-scale hypertextual Web search engine". Computer Networks and ISDN Systems. Proceedings of the Seventh International World Wide Web Conference. 30 (1): 107–117. doi:10.1016/S0169-7552(98)00110-X. ISSN 0169-7552.
- ^ 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. Script error: No such module "CS1 identifiers".
- ^ Page Module:Citation/CS1/styles.css has no content.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.
