C.5.1 - Describe how the web can be represented as a directed graph.

Note: The vertices (nodes) represent web pages and the edges represent hyperlinks. It is not a complete graph. The directed graph formed by the web is known as the web graph. Link: mathematics - Graph theory.

• The Web as a directed graph - CS wiki

C.5.2 - Outline the difference between the web graph and sub-graphs.

Note: A sub-graph will be assumed to be a set of pages linked to one specific topic.

A sub-graph is just part of a graph - e.g. the Autobahns in Germany are a subset of the entire road system.

C.5.3 - Describe the main features of the web graph such as bowtie structure, strongly connected core (SCC), diameter.

Note: Students must be aware the web has a structure that has emerged from the behaviour of web users.

C.5.4 - Explain the role of graph theory in determining the connectivity of the web.

• • Brief Intro to Graph Theory

  • Another Intro to Graph Theory

C.5.5 - Explain that search engines and web crawling use the web graph to access information.

Note: Students should be aware of the Page Rank algorithm and explain how it works. No calculations are required.

• Matt Cutts Explains Pagerank

• Page rank algorithm - Udacity

• The PageRank algorithm - MajorPrep - Sept 2019

C.5.6 - Discuss whether power laws are appropriate to predict the development of the web.

• • Power Laws Chapter - especially section 18.5 - The Long Tail

  • Power law distribution of the www

  • Video about the Long Tail

  • Random and scale-free networks