Webwhompers

Conceived in 1735 by the fertile Leonhard Euler, graph theory developed over the next 200 years to include topics such as

• Shortest paths: Given a graph G=(V,E) and a pair of nodes x,y: How can we find a shortest path from x to y?
• Maximum cliques: A clique is a subset of nodes that are all adjacent to each other. Given a graph G=(V,E): How can we find large cliques in G? How can we find the largest clique in G? (Here is a more thorough definition of clique.)
• Graph coloring: Given a graph and the ability to assign a "color" to each of its nodes: How can we use the fewest possible number of distinct colors so that (1) every node has a color assigned to it, and (2) no two adjacent nodes are assigned the same color? 

In studying these and other questions, graph theorists usually made two important assumptions: (1) The graph is known, and (2) the graph does not change.

When we use graph theory to study the Web, we must acknowledge that these two assumptions are not realistic. For example:

• The Web graph is only partially known. Estimating the cardinality of the set of all Web pages is enough to stretch our powers of creative arithmetic; what if we actually had to name all 30-70 billion of them? Our knowledge of the set of all hyperlinks is rougher still.
• The Web graph is constantly changing. Even if all Web builders were to cease and desist immediately, the Web pages they have already created include many that automatically change their outgoing links each time a Web user visits. For example, Google, Facebook, Amazon, Delicious (etc., etc.) all present different links to different users at different times.