Jump to content

Webgraph

From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by Grolmusz (talk | contribs) at 15:32, 2 June 2011 (The page created.). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.
(diff) ← Previous revision | Latest revision (diff) | Newer revision → (diff)

Template:New unreviewed article

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 [2] of the WWW pages.
  • The webgraph is used for computing the personalized PageRank [3].
  • The webgraph can be used for detecting webpages of similar topics, through graph-theoretical properties only, like co-citation [4]
  • The webgraph is applied in the HITS algorithm for identifying hubs and authorities in the web.



References

  1. ^ P. Erdős, A. Renyi, Publ. Math. Inst. Hung. Acad. Sci. 5 (1960)
  2. ^ S. Brin, L. Page, Computer Networks and ISDN Systems 30, 107 (1998)
  3. ^ 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 http://doi.acm.org/10.1145/775152.775191
  4. ^ Ravi Kumar, Prabhakar Raghavan, Sridhar Rajagopalan, Andrew Tomkins, Trawling the Web for emerging cyber-communities, Computer Networks, Volume 31, Issues 11-16, 17 May 1999, Pages 1481-1493, ISSN 1389-1286, DOI: 10.1016/S1389-1286(99)00040-7.