Webgraph

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: 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, however: it is relatively well described by a lognormal distribution, as well as the Barabási–Albert model for power laws.
• The webgraph is an example of a scale-free network.

Applications

The webgraph is used for:

• computing the PageRank of the world wide web's pages;
• computing the personalized PageRank;
• detecting webpages of similar topics, through graph-theoretical properties only, like co-citation;
• and identifying hubs and authorities in the web for HITS algorithm.

References

References

1. (2008). "Introduction to Information Retrieval". Cambridge University Press.
2. Erdős, Paul. (1960). "On the evolution of random graphs". Publication of the Mathematical Institute of the Hungarian Academy of Sciences.
3. (2015). "The Graph Structure in the Web - Analyzed on Different Aggregation Levels". Journal of Web Science.
4. (October 1999). "Emergence of scaling in random networks". Science.
5. Brin, Sergey. (1998-04-01). "The anatomy of a large-scale hypertextual Web search engine". Computer Networks and ISDN Systems.
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. (1999). "Trawling the Web for emerging cyber-communities". Computer Networks.