4.5 A Case Study: Small World Phenomenon
The mathematical model that we use for studying the nature of pairwise connections among entities is known as the graph. Graphs are important for studying the natural world and for helping us to better understand and refine the networks that we create.
Some graphs exhibit a specific property known as the smallworld phenomenon. You may be familiar with this property, which is sometimes known as six degrees of separation. It is the basic idea that, even though each of us has relatively few acquaintances, there is a relatively short chain of acquaintances (the six degrees of separation) separating us from one another. Scientists are interested in smallworld graphs because they model natural phenomena, and engineers are interested in building networks that take advantage of the natural properties of smallworld graphs.
In this section, we address basic computational questions surrounding the study of smallworld graphs.
Graph Data Type
We begin with some basic definitions. A graph is composed of a set of vertices and a set of edges. Each edge represents a connection between two vertices. Two vertices are neighbors if they are connected by an edge, and the degree of a vertex is its number of neighbors.
Graphprocessing algorithms generally first build an internal representation of a graph by adding edges, then process it by iterating through the vertices and through the edges that are adjacent to a vertex. This API supports such processing.
The program graph.py implements this API. Its internal representation is a symbol table of sets: the keys are vertices and the values are the sets of neighbors — the vertices adjacent to the key. A small example is illustrated at right. To implement this representation, we use the two builtin data types dict
and set
that we introduced in Section 4.4.
A natural way to write a Graph
is to put the vertices one per line, each followed by a list of its immediate neighbors. Accordingly, we support the builtin function str()
by implementing __str__()
as shown in graph.py.
The resulting string includes two representations of each edge, one for the case in which we discover that w
is a neighbor of v
and one for the case in which we discover that v
is a neighbor of w
. Many graph algorithms are based on this basic paradigm of processing each edge in the graph (twice). This implementation is intended for use only for small graphs, as the running time is quadratic in the string length on some systems.
The output format for str()
also defines a reasonable input file format. The __init__()
method supports creating a graph from a file in this format (each line is a vertex name followed by the names of neighbors of that vertex, separated by whitespace). For flexibility, we allow for the use of delimiters besides whitespace (so that, for example, vertex names may contain spaces), as shown in graph.py.
Graph Client Example
As a first graphprocessing client, we consider an example of social relationships — one that is certainly familiar to you and for which extensive data is readily available.
On this booksite you can find the file movies.txt which contains a list of movies and the performers who appeared in them. Each line gives the name of a movie followed by the cast (a list of the names of the performers who appeared in that movie). Since names have spaces and commas in them, we use the '/' character as a delimiter.
Using Graph
, we can compose a simple and convenient client for extracting information from movies.txt. We begin by building a Graph
to better structure the information. What should the vertices and edges model? We choose to have vertices for both the movies and the performers, with an edge connecting each movie to each performer in that movie. As you will see, programs that process this graph can answer a great variety of interesting questions for us.
The program invert.py is a first example. It is a Graph
client that takes a query, such as the name of a movie, and writes the list of performers who appear in that movie. A more interesting feature of invert.py is that you can type the name of a performer and get the list of movies in which that performer has appeared. Why does this work? Even though the database seems to connect movies to performers and not the other way around, the edges in the graph are connections that also connect performers to movies.
A graph in which connections all connect one kind of vertex to another kind of vertex is known as a bipartite graph. As this example illustrates, bipartite graphs have many natural properties that we can often exploit in interesting ways.
It is worth reflecting on the fact that building a bipartite graph provides a simple way to automatically invert any index! This invertedindex functionality is a direct benefit of the graph data structure. Next, we examine some of the added benefits to be derived from algorithms that process the data structure.
Shortest Paths in Graphs
Given two vertices in a graph, a path is a sequence of vertices connected by edges. A shortest path is one with the minimal number of edges over all such paths (there may be multiple shortest paths). Finding a shortest path connecting two vertices in a graph is a fundamental problem in computer science.
Depending on the application, clients have various needs with regard to shortest paths. Our choice is to start with the following API:
In huge graphs or for huge numbers of queries, we have to pay particular attention to API design because the cost of computing paths might prove to be prohibitive. With this design, clients can create a PathFinder
object for a given graph and a given vertex, and then use that object either to find the length of the shortest path or to iterate over the vertices on a shortest path to any other vertex in the graph. An implementation of these methods is known as a singlesource shortestpath algorithm. A classic algorithm known as breadthfirst search provides a direct and elegant solution where the constructor takes linear time, distanceTo()
takes constant time, and pathTo()
takes time proportional to the length of the path. Before examining our implementation, we will consider some clients.
Singlesource client.
Suppose that you have available to you the graph of vertices and connections for your nofrills airline's route map. Then, using your home city as a source, you can compose a client that writes your route anytime you want to go on a trip. The program separation.py is aPathFinder
client that provides this functionality for any graph. You are encouraged to explore the properties of shortest paths by running PathFinder
on our sample input routes.txt or any input model that you choose.
Degrees of separation.
One of the classic applications of shortestpaths algorithms is to find the degrees of separation of individuals in social networks. To fix ideas, we discuss this application in terms of a recently popularized pastime known as the Kevin Bacon game, which uses the movieperformer graph that we just considered. Kevin Bacon is a prolific actor who appeared in many movies. We assign every performer who has appeared in a movie a Bacon number: Bacon himself is 0, any performer who has been in the same cast as Bacon has a Kevin Bacon number of 1, any other performer (except Bacon) who has been in the same cast as a performer whose number is 1 has a Kevin Bacon number of 2, and so forth. For example, Meryl Streep has a Kevin Bacon number of 1 because she appeared in The River Wild with Kevin Bacon. Nicole Kidman's number is 2: although she did not appear in any movie with Kevin Bacon, she was in Cold Mountain with Donald Sutherland, and Sutherland appeared in Animal House with Kevin Bacon. Given the name of a performer, the simplest version of the game is to find some alternating sequence of movies and performers that lead back to Kevin Bacon. Remarkably, pathfinder.py is precisely the program that you need to find a shortest path that establishes the Bacon number of any performer in movies.txt: the Bacon number of any performer is precisely half the distance between Kevin Bacon and that performer.Shortestpath distances.
We define the distance between two vertices to be the length of the shortest path between them. The first step in understanding breadthfirst search is to consider the problem of computing distances between the source and each vertex (the implementation ofdistanceTo()
in PathFinder
). Our approach is to compute and store away all the distances in the constructor, and then just return the requested value when a client invokes distanceTo()
. To associate an integer distance with each vertex name, we use a symbol table:
_distTo = dict()
The purpose of this symbol table is to associate with each vertex the length of the shortest path (the distance) between that vertex and s
. To do that we consider the vertices in order of their distance from s
, ignoring vertices whose distance to s
is already known. To organize the computation, we use a FIFO queue. Starting with s
on the queue, we perform the following operations until the queue is empty:
 Dequeue a vertex v.
 Assign all of v's unknown neighbors a distance 1 greater than v's distance.
 Enqueue all of the unknown neighbors.
This method dequeues the vertices in nondecreasing order of their distance from the source s
.
Shortestpaths tree.
We need not only distances from the source, but also paths. To implementpathTo()
, we use a subgraph known as the shortestpaths tree, defined as follows:
 Put the source vertex s at the root of the tree.
 Put vertex v's neighbors in the tree if they are added to the queue, with an edge connecting each to v.
Since we enqueue each vertex only once, this structure is a proper tree: it consists of a root (the source) connected to one subtree for each neighbor of the source. Studying such a tree, you can see immediately that the distance from each vertex to the root in the tree is the same as the shortestpath distance to the source in the graph. More importantly, each path in the tree is a shortest path in the graph. This observation is important because it gives us an easy way to provide clients with the shortest paths themselves (implement pathTo() in PathFinder).
First, we maintain a symbol table associating each vertex with the vertex one step nearer to the source on the shortest path:
_edgeTo = dict()
To each vertex w
, we want to associate the previous stop on the shortest path from the source to w
. Augmenting the shortestdistances method to also compute this information is easy: when we enqueue w
because we first discover it as a neighbor of v
, we do so precisely because v
is the previous stop on the shortest path from the source to w
, so we can assign _edgeTo[w] = v
. The _edgeTo
data structure is nothing more than a representation of the shortestpaths tree: it provides a link from each node to its parent in the tree. Then, to respond to a client request for the path from the source to v
(a call to pathTo(v)
in PathFinder
), we follow these links up the tree from v
, which traverses the path in reverse order. We collect the vertices in an array as we encounter them, then reverse the array, so the client gets the path from s
to v
when using the iterator returned from pathTo()
.
Breadthfirst search.
This process is known as breadthfirst search because it searches broadly in the graph. By contrast, another important graphsearch method known as depthfirst search is based on a recursive method like the one we used in percolation.py from Section 2.4 and searches deeply into the graph. Depthfirst search tends to find long paths; breadthfirst search is guaranteed to find shortest paths.SmallWorld Graphs
Scientists have identified a particularly interesting class of graphs that arise in numerous applications in the natural and social sciences. Smallworld graphs are characterized by the following three properties:
 They are sparse: the number of vertices is much smaller than the number of edges.
 They have short average path lengths: if you pick two random vertices, the length of the shortest path between them is short.
 They exhibit local clustering: if two vertices are neighbors of a third vertex, then the two vertices are likely to be neighbors of each other.
We refer to graphs having these three properties collectively as exhibiting the smallworld phenomenon. The term small world refers to the idea that the preponderance of vertices have both local clustering and short paths to other vertices. The modifier phenomenon refers to the unexpected fact that so many graphs that arise in practice are sparse, exhibit local clustering, and have short paths.
A key question in such research is the following: Given a graph, how can we tell whether it is a smallworld graph? To answer this question, we begin by imposing the conditions that the graph is not small (say, 1000 vertices or more) and that it is connected (there exists some path connecting each pair of vertices). Then, we need to settle on specific thresholds for each of the smallworld properties:
 By sparse, we mean the average vertex degree is less than 20 lg V.
 By short average path length, we mean the average length of the shortest path between two vertices is less than 10 lg V.
 By locally clustered, we mean that a certain quantity known as the clustering coefficient should be greater than 10%.
The definition of locally clustered is a bit more complicated than the definitions of sparsity and average path length. Intuitively, the clustering coefficient of a vertex represents the probability that if you pick two of its neighbors at random, they will also be connected by an edge. More precisely, if a vertex has t neighbors, then there are t(t1)/2 possible edges that connect those neighbors; its local clustering coefficient is the fraction of those edges that are in the graph (or 0 if the vertex has degree 0 or 1). The clustering coefficient of a graph is the average of the local clustering coefficients of its vertices. If that average is greater than 10%, we say that the graph is locally clustered. The diagram below calculates these three quantities for a tiny graph.
To better familiarize you with these definitions, we next define some simple graph models, and consider whether they describe smallworld graphs by checking whether they exhibit the three requisite properties.
Complete graphs.
A complete graph with V vertices has V (V1) / 2 edges, one connecting each pair of vertices. Complete graphs are not smallworld graphs. They have short average path length (every shortest path has length is 1) and they exhibit local clustering (the cluster coefficient is 1), but they are not sparse (the average vertex degree is V1, which is much greater than 20 lg V for large V).Ring graphs.
A ring graph is a set of V vertices equally spaced on the circumference of a circle, with each vertex connected to its neighbor on either side. In a kring graph, each vertex is connected to its k nearest neighbors on either side. The diagram at right illustrates a 2ring graph with 16 vertices. Ring graphs are also not smallworld graphs. For example, 2ring graphs are sparse (every vertex has degree 4) and exhibit local clustering (the cluster coefficient is 1/2), but their average path length is not short.Random graphs.
The ErdosRenyi model is a well studied model for generating random graphs. In this model, we build a random graph on V vertices by including each possible edge with probability p. Random graphs with a sufficient number of edges are very likely to be connected and have short average path lengths but they are not smallworld graphs, because they are not locally clustered.These examples illustrate that developing a graph model that satisfies all three properties simultaneously is a puzzling challenge. Take a moment to try to design a graph model that you think might do so. After you have thought about this problem, you will realize that you are likely to need a program to help with calculations. Also, you may agree that it is quite surprising that they are found so often in practice. Indeed, you might be wondering if any graph is a smallworld graph!
Choosing 10% for the clustering threshold instead of some other fixed percentage is somewhat arbitrary, as is the choice of 20 lg V for the sparsity threshold and 10 lg V for the short paths threshold, but we often do not come close to these borderline values. For example, consider the web graph, which has a vertex for each web page and an edge connecting two web pages if they are connected by a link. Scientists estimate that the number of clicks to get from one web page to another is rarely more than about 30. Since there are billions of web pages, this estimate implies that the average length of a path between two vertices is very short, much lower than our 10 lg V threshold (which would be about 300 for 1 billion vertices).
Having settled on the definitions, testing whether a graph is a smallworld graph can still be a significant computational burden. As you probably have suspected, the graphprocessing data types that we have been considering provide precisely the tools that we need. The program smallworld.py is a Graph
and PathFinder
client that implements these tests. Without the efficient data structures and algorithms that we have been considering, the cost of this computation would be prohibitive. Even so, for large graphs (such as movies.txt), we must resort to statistical sampling to estimate the average path length and the cluster coefficient in a reasonable amount of time because the functions averagePathLength()
and clusteringCoefficient()
take quadratic time.
A classic smallworld graph.
Our movieperformer graph is not a smallworld graph, because it is bipartite and therefore has a clustering coefficient of 0. Also, some pairs of performers are not connected to each other by any paths. However, the simpler performerperformer graph defined by connecting two performers by an edge if they appeared in the same movie is a classic example of a smallworld graph (after discarding performers not connected to Kevin Bacon). The diagram below illustrates the movieperformer and performerperformer graphs associated with a tiny moviecast file.The program performer.py is a script that creates a performerperformer graph from a file in our moviecast input format. Recall that each line in a moviecast file consists of a movie followed by all of the performers who appeared in that movie, delimited by slashes. The script connects all pairs of performers in that movie by adding an edge connecting each pair. Doing so for each movie in the input produces a graph that connects the performers, as desired.
Since a performerperformer graph typically has many more edges than the corresponding movieperformer graph, we will work for the moment with the smaller performerperformer graph derived from the file moviesg.txt, which contains 1261 Grated movies and 19044 performers (all of which are connected to Kevin Bacon). Now, performer.py tells us that the performerperformer graph associated with moviesg.txt has 19044 vertices and 1415808 edges, so the average vertex degree is 148.7 (about half of 20 lg V = 284.3), which means it is sparse; its average path length is 3.494 (much less than 10 lg V = 142.2), so it has short paths; and its clustering coefficient is 0.911, so it has local clustering. We have found a smallworld graph! These calculations validate the hypothesis that social relationship graphs of this sort exhibit the smallworld phenomenon.
This case study is an appropriate place to end the booksite because the programs that we have considered are a starting point, not a complete study. This booksite is a starting point, too, for your further study in science, mathematics, or engineering. The approach to programming and the tools that you have learned here should prepare you well for addressing any computational problem whatsoever.
Q & A
Q. How many different graphs are there with V given vertices?
A. With no selfloops or parallel edges, there are V(V1)/2 possible edges, each of which can be present or not present, so the grand total is 2^{V(V1)/2}. The number grows to be huge quite quickly, as shown in the following table:
V 1 2 3 4 5 6 7 8 9 2^{V(V1)/2} 1 2 8 64 1024 32768 2097152 268435456 68719476736
These huge numbers provide some insight into the complexities of social relationships. For example, if you just consider the next nine people that you see on the street, there are over 68 trillion mutualacquaintance possibilities!
Q. Can a graph have a vertex that is not connected to any other vertex by an edge?
A. Good question. Such vertices are known as isolated vertices. Our implementation disallows them. Another implementation might choose to allow isolated vertices by including an explicit addVertex()
method for the add a vertex operation.
Q. Why do the countV()
and countE()
query methods need to have constanttime implementations? Won't most clients would call such methods only once?
A. It might seem so, but code like this
while i < g.countE(): ... i += 1
would take quadratic time if you were to use a lazy implementation that counts the edges instead of maintaining an instance variable with the number of edges.
Q. Why are Graph
and PathFinder
in separate classes? Wouldn't it make more sense to include the PathFinder
methods in the Graph
API?
A. Finding shortest paths is just one of many graphprocessing algorithms. It would be poor software design to include all of them in a single interface. Please reread the discussion of wide interfaces in Section 3.3.
Exercises

Find the performer in movies.txt who has appeared in the most movies.

Modify the
__str__()
method inGraph
so that it returns the vertices in sorted order (assuming the vertices are comparable). Hint: Use the builtinsorted()
function. 
Modify the
__str__()
method inGraph
so that it runs in time linear in the number of vertices and the number of edges in the worst case. Hint: Use thejoin()
method in the str data type. 
Add to
Graph
a methodcopy()
that creates and return a new, independent copy of the graph. Any future changes to the original graph should not affect the newly created graph (and vice versa!). 
Compose a version of
Graph
that supports explicit vertex creation and allows selfloops, parallel edges, and isolated vertices (vertices of degree 0). 
Add to
Graph
a methodremoveEdge()
that takes two string arguments and deletes the specified edge from the graph, if present. 
Add to
Graph
a methodsubgraph()
that takes a set of strings as an argument and returns the induced subgraph (the graph consisting of only those vertices and only those edges from the original graph that connect any two of them). 
Describe the advantages and disadvantages of using an array or a linked list to represent the neighbors of a vertex instead of using a set.

Compose a
Graph
client that reads aGraph
from a file, then writes the edges in the graph, one per line. 
Modify
Graph
so that it supports vertices of any hashable type. 
Implement a
PathFinder
clientallshortestpaths.py
that takes the name of a graph file and a delimiter as commandline arguments, builds aPathFinder
for each vertex, and then repeatedly takes from standard input the names of two vertices (on one line, separated by the delimiter) and writes the shortest path connecting them. Note: For movies.txt, the vertex names may both be performers, both be movies, or be a performer and a movie. 
True or false: At some point during breadthfirst search, the queue can contain two vertices, one whose distance from the source is 7 and one whose distance from the source is 9.
Solution: False. The queue can contain vertices of at most two distinct distances d and d+1. Breadthfirst search examines the vertices in increasing order of distance from the source. When examining a vertex at distance d, only vertices of distance d+1 can be enqueued.

Prove by induction on the set of vertices visited that
PathFinder
finds the shortestpath distances from the source to each vertex. 
Suppose you use a stack instead of a queue for breadthfirst search in
PathFinder
. Does it still find a path? Does it still correctly compute shortest paths? In each case, prove that it does or give a counterexample. 
Compose a program that plots average path length versus the number of random edges as random shortcuts are added to a 2ring graph on 1000 vertices.

Add an optional argument
k
toclusterCoefficient()
in the module smallworld.py so that it computes a local cluster coefficient for the graph based on the total edges present and the total edges possible among the set of vertices within distancek
of each vertex. Use the default valuek
=1 so that your function produces results identical to the function with the same name in smallworld.py. 
Show that the cluster coefficient in a kring graph is (2k2) / (2k1). Derive a formula for the average path length in a kring graph on V vertices as a function of both V and k.

Show that the diameter in a 2ring graph on V vertices is ~ V/4. Show that if you add one edge connecting two antipodal vertices, then the diameter decreases to ~ V/8.

Perform computational experiments to verify that the average path length in a ring graph on V vertices is ~ 1/4 V. Repeat, but add one random edge to the ring graph and verify that the average path length decreases to ~ 3/16 V.

Add to smallworld.py a function
isSmallWorld()
that takes a graph as an argument and returnsTrue
if the graph exhibits the smallworld phenomenon (as defined by the specific thresholds given in the text) andFalse
otherwise. 
Compose a smallworld.py and
Graph
client that generates kring graphs and tests whether they exhibit the smallworld phenomenon (first do the previous exercise). 
In a grid graph, vertices are arranged in an nbyn grid, with edges connecting each vertex to its neighbors above, below, to the left, and to the right in the grid. Compose a smallworld.py and
Graph
client that generates grid graphs and tests whether they exhibit the smallworld phenomenon (first add anisSmallWorld()
method to smallworld.py, as described in a previous exercise). 
Extend your solutions to the previous two exercises to also take a commandline argument m and to add m random edges to the graph. Experiment with your programs for graphs with approximately 1000 vertices to find smallworld graphs with relatively few edges.

Compose a
Graph
andPathFinder
client that takes the name of a moviecast file and a delimiter as arguments and writes a new moviecast file, but with all movies not connected to Kevin Bacon removed.
Creative Exercises

Large Bacon numbers. Find the performers in movies.txt with the largest, but finite, Kevin Bacon number.

Histogram. Compose a program
baconhistorgram.py
that writes a histogram of Kevin Bacon numbers, indicating how many performers from movies.txt have a Bacon number of 0, 1, 2, 3, ... Include a category for those who have an infinite number (not connected at all to Kevin Bacon). 
Performerperformer graph. An alternative way to compute Kevin Bacon numbers is to build a graph where there is a vertex for each performer (but not for each movie), and where two performers are connected by an edge if they appear in a movie together. Calculate Kevin Bacon numbers by running breadthfirst search on the performerperformer graph. Compare the running time with the running time on movies.txt. Explain why this approach is so much slower. Also explain what you would need to do to include the movies along the path, as happens automatically with our implementation.

Connected components. A connected component in an undirected graph is a maximal set of vertices that are mutually reachable. Compose a data type
ConnectedComponents
that computes the connected components of a graph. Include a constructor that takes aGraph
as an argument and computes all of the connected components using breadthfirst search. Include a methodareConnected(v, w)
that returnsTrue
ifv
andw
are in the same connected component andFalse
otherwise. Also add a methodcomponents()
that returns the number of connected components. 
Flood fill. A
Picture
is a twodimensional array ofColor
values (see Section 3.1) that represent pixels. A blob is a collection of neighboring pixels of the same color. Compose aGraph
client whose constructor builds a grid graph (see a previous exercise in this section) from a given image and supports the flood fill operation. Given pixel coordinatescol
androw
and a colorc
, change the color of that pixel and all the pixels in the same blob toc
. 
Word ladders. Compose a program
wordladder.py
that takes two 5letter strings from the command line, reads in a list of 5letter words from standard input, and writes a shortest word ladder using the words on standard input connecting the two strings (if it exists). Two words can be connected in a word ladder chain if they differ in exactly one letter. As an example, the following word ladder connects green and brown:green greet great groat groan grown brown
Compose a simple filter to get the 5letter words from a system dictionary for standard input, or download words5.txt. You can also try out your program on words6.txt, a list of 6 letter words. (This game, originally known as doublet, was invented by Lewis Carroll.)

All paths. Compose a
Graph
client classAllPaths
whose constructor takes aGraph
as an argument and supports operations to count or write all simple paths between two given verticess
andt
in the graph. A simple path does not revisit any vertex more than once. In twodimensional grids, such paths are referred to as selfavoiding walks (see Section 1.4). It is a fundamental problem in statistical physics and theoretical chemistry, for example, to model the spatial arrangement of linear polymer molecules in a solution. Warning: There might be exponentially many paths. 
Percolation threshold. Develop a graph model for percolation, and compose a
Graph
client that performs the same computation as percolation.py (from Section 2.4). Estimate the percolation threshold for triangular, square, and hexagonal grids. 
Subway graphs. In the Tokyo subway system, routes are labeled by letters and stops by numbers, such as G8 or A3. Stations allowing transfers are sets of stops. Find a Tokyo subway map on the web, develop a simple database format, and compose a
Graph
client that reads a file and can answer shortestpath queries for the Tokyo subway system. If you prefer, do the Paris subway system, where routes are sequences of names and transfers are possible when two stations have the same name. 
Center of the Hollywood universe. We can measure how good a center Kevin Bacon is by computing each performer's Hollywood number or average path length. The Hollywood number of Kevin Bacon is the average Bacon number of all the performers (in its connected component). The Hollywood number of another performer is computed the same way, making that performer the source instead of Kevin Bacon. Compute Kevin Bacon's Hollywood number and find a performer with a better Hollywood number than Kevin Bacon. Find the performers (in the same connected component as Kevin Bacon) with the best and worst Hollywood numbers.

Diameter. The eccentricity of a vertex is the greatest distance between it and any other vertex. The diameter of a graph is the greatest distance between any two vertices (the maximum eccentricity of any vertex). Compose a
Graph
clientdiameter.py
that can compute the eccentricity of a vertex and the diameter of a graph. Use it to find the diameter of the graph represented by movies.txt. 
Directed graphs. Implement a
Digraph
data type that represents directed graphs, where the direction of edges is significant:addEdge(v, w)
means to add an edge fromv
tow
but not fromw
tov
. ReplaceadjacentTo()
with two methods:adjacentFrom()
, to give the set of vertices having edges directed to them from the argument vertex, andadjacentTo()
, to give the set of vertices having edges directed from them to the argument vertex. Explain how to modifyPathFinder
to find shortest paths in directed graphs. 
Random surfer. Modify your
Digraph
class of the previous exercise to make aMultiDigraph
class that allows parallel edges. For a test client, run a random surfer simulation that matches randomsurfer.py (from Section 1.6). 
Transitive closure. Compose a
Digraph
client classTransitiveClosure
whose constructor takes aDigraph
as an argument and whose methodisReachable(v, w)
returnsTrue
ifw
is reachable fromv
along a directed path in the digraph andFalse
otherwise. Hint: Run breadthfirst search from each vertex, as inallshortestpaths.py
(from a previous exercise). 
Statistical sampling. Use statistical sampling to estimate the average path length and clustering coefficient of a graph. For example, to estimate the clustering coefficient, pick t random vertices and compute the average of the clustering coefficients of those vertices. The running time of your functions should be orders of magnitude faster than the corresponding functions from smallworld.py.

Cover time. A random walk in a connected undirected graph moves from a vertex to one of its neighbors, each chosen with equal probability. (This process is the random surfer analog for undirected graphs.) Compose programs to run experiments that support the development of hypotheses on the number of steps used to visit every vertex in the graph. What is the cover time for a complete graph with V vertices? Can you find a family of graphs where the cover time grows proportionally to V^{3} or 2^{V}?

ErdosRenyi random graph model. In the classical random graph model, we build a random graph on V vertices by including each possible edge with probability p, independently of the other edges. Compose a
Graph
client to verify the following properties: Connectivity thresholds: If p < 1/V and V is large, then most of the connected components are small, with the largest being logarithmic in size. If p > 1/V, then there is almost surely a giant component containing almost all vertices. If p < ln V / V, the graph is disconnected with high probability; if p > ln V / V, the graph is connected with high probability.
 Distribution of degrees: The distribution of degrees follows a binomial distribution, centered on the average, so most vertices have similar degrees. The probability that a vertex is connected to k other vertices decreases exponentially in k.
 No hubs: The maximum vertex degree when p is a constant is at most logarithmic in V.
 No local clustering: The cluster coefficient is close to 0 if the graph is sparse and connected. Random graphs are not smallworld graphs.
 Short path lengths: If p > ln V / V, then the diameter of the graph (see the Diameter creative exercise earlier in this section) is logarithmic.

Power law of web links. The indegrees and outdegrees of pages in the web obey a power law that can be modeled by a preferred attachment process. Suppose that each web page has exactly one outgoing link. Each page is created one at a time, starting with a single page that points to itself. With probability p < 1, it links to one of the existing pages, chosen uniformly at random. With probability 1p, it links to an existing page with probability proportional to the number of incoming links of that page. This rule reflects the common tendency for new web pages to point to popular pages. Compose a program to simulate this process and plot a histogram of the number of incoming links.
Partial solution: The fraction of pages with indegree k is proportional to k^{1/(1p)}.

Global clustering coefficient. Add a function to smallworld.py that computes the global clustering coefficient of a graph. The global clustering coefficient is the conditional probability that two random vertices that are neighbors of a common vertex are neighbors of each other. Find graphs for which the local and global clustering coefficients are different.

WattsStrogatz graph model. (See Exercises 4.5.24 and 4.5.25.) Watts and Strogatz proposed a hybrid model that contains typical links of vertices near each other (people know their geographic neighbors), plus some random longrange connection links. Plot the effect of adding random edges to an nbyn grid graph (as described in previous exercises in this section) on the average path length and on the cluster coefficient, for n = 100. Do the same for kring graphs on V vertices, for V = 10000 and various values of k up to 10 log V.

BollobasChung graph model. Bollobas and Chung proposed a hybrid model that combines a 2ring on V vertices (V is even), plus a random matching. A matching is a graph in which every vertex has degree 1. To generate a random matching, shuffle the V vertices and add an edge between vertex i and vertex i+1 in the shuffled order. Determine the degree of each vertex for graphs in this model. Using smallworld.py, estimate the average path length and cluster coefficient for random graphs generated according to this model for V = 1000.

Kleinberg graph model. There is no way for participants in the WattsStrogatz model to find short paths in a decentralized network. But Milgram's experiment also had a striking algorithmic component — individuals can find short paths! Jon Kleinberg proposed making the distribution of shortcuts obey a power law, with probability proportional to the dth power of the distance (in d dimensions). Each vertex has one longrange neighbor. Compose a program to generate graphs according to this model, with a test client that uses smallworld.py to test whether they exhibit the smallworld phenomenon. Plot histograms to show that the graphs are uniform over all distance scales (same number of links at distances 110 as at distances 10100 or 1001000). Compose a program to compute the average lengths of paths obtained by taking the edge that brings the path as close to the target as possible in terms of lattice distance, and test the hypothesis that this average is proportional to (log V)^{2}.