The degree distribution of graphs generated using the classical, Erdos-Renyi random graph model (see Project 1 handout) is quite different. It is a bell-shaped curve that is symmetric about the average degree. Most of the vertices have the average degree and the number of vertices having degree less than the average is about the same as the number of vertices having degree greater than the average. For a plot of the degree distribution of the Erdos-Renyi random graph see Figure 3 in this Net Wiki page on the Erdos-Renyi model.

Your first experiment will seek to determine if the random network you generated in Project 1 has a power-law degree distribution. It is now known that even though the Watts-Strogatz model appropriately models high clustering coefficient and low average path length features of social networks, it fails to generate graphs with a power-law degree distribution. Here is quote from the Net Wiki page on the Watts-Strogatz model.

Despite producing a network that is both small-world and clustered, the Watts and Strogatz Model fails to be a good model for real networks. The WS Model is quite homogenous in degree, most nodes have about the same degree. Real networks such as the world wide web and metabolic networks are inhomogenous. There exist a significant number of nodes of very high degree called hubs.

So it is reasonable to expect that the random networks generated in Project 1, also, do not satisfy the power-law distribution. In fact, the starting hypothesis for your first experiment should be that the random graphs generated in Project 1 do not satisfy the power-law distribution. To perform this experiment, first add a method

int[] degreeDistribution()to the graph class. Then write a program called

Now we will "rewire" some of the edges in the unit disk graph constructed in Step (1). Suppose the vertices are labeled 1 through n. Consider vertices in the order 1 through n and suppose that we are currently considering a vertex v. Consider each edge {v, w} connecting v to a higher labeled vertex w. With probability p, replace edge {v, w} by an edge {v, z} where z is picked picked uniformly at random from the set of all vertices that are not neighbors of v (including w).

The change we make to the rewiring step is that instead of picking z uniformly at random,
it is picked in a manner that is proportional to the degrees.
In other words, the higher the degree of a non-neighbor of v, the more likely it is to be
picked as a vertex to connect v to.
This scheme is called *preferential attachment*, the idea being that a vertex is more
likely to connect to "popular" vertices.
Here is the idea in more detail.
Suppose we are considering edge {v, w} and have decided to rewire this edge.
Let Z be the set of all non-neighbors of v (including w).
Let D be the sum of the degrees of all vertices in Z.
Then the probability of picking a vertex z in Z to connect v to should be
degree(z)/D.
For example, suppose that Z = {a, b, c} and the degrees of a, b, and c are 5, 3, and 7 respectively.
Then the probability of picking a, b, and c should be 5/15, 3/15, and 7/15 respectively.

Create a new class called `prefAttachGraph` that is very similar to the `smallWorldGraph`
class from Project 1, except that it implements the preferential attachment scheme
described above, in the rewiring step.
Then implement a program called `experiment2.java` that determines if the graphs
generated by the `prefAttachGraph` class satisfy all three properties:
(i) high clustering coefficient, (ii) small average path length, and (iii) power-law distribution.
To verify the first two properties mentioned above, perform the experiments you performed for
Project 1. To verify the third property, repeat **Experiment 1**, but with the
`prefAttachGraph` class, rather than the `smallWorldGraph` class.

Start by implementing the following simple, greedy algorithm for routing a message from a given source vertex s to a given destination vertex t. The coordinates of the source vertex s and the coordinates of the destination vertex t are considered part of the message. This is analogous to how the "from address" and the "to address" usually appear on an envelope carried by the postal service.

**Algorithm:**
*Each node v that gets the message forwards the message to a neighbor
who is closest to the destination t.*

First, note that this algorithm does not always ensure that in each step the message gets closer to the destination. For example, the message may be at a node v which is fairly close to t, but all of v's neighbors may be further away from t. So when v forwards the message to a neighbor, the message moves away from t. This means that the algorithm may not always terminate and may cycle between nodes. Thus your implementation should have a way of detecting cycles and terminating the algorithm when a vertex is visited a second time. When the algorithm ends, successfully or unsuccessfully, you should record the following information:

- Whether the message reached t.
- The number of hops it took to go from s to t.
- The total Euclidean distance traveled by the message from s to t.

We would like to compare the hop-distance and the Euclidean-distance
travelled by message that reaches t successfully, with the actual
shortest path hop-distance between s and t and the shortest path
Euclidean-distance between s and t.
You can use the *breadth-first search* algorithm to compute the
shortest path hop-distance and *Dijkstra's shortest path*
algorithm to compute the shortest path Euclidean-distance.
A typical experiment you will perform will consist of the following
steps:

- Generate a random graph using the uniform rewiring model or the preferential rewiring model.
- For M randomly chosen pairs of source s and destination t, run the greedy algorithm to route a message from s to t. Record whether the message successfully reached t and if so, the number of hops and the Euclidean distance traveled by the message.
- For each of the M (s, t)-pairs chosen in the previous step, find the shortest path hop-distance and the shortest path Euclidean-distance between s and t.
- Output statistics including
- The fraction of the M pairs for which the message went from s to t successfully.
- The average ratio of hop-distance traveled by the message to the shortest path hop-distance between s and t.
- The average ratio of Euclidean-distance traveled by the message to the shortest path Euclidean-distance between s and t.

Here are some more instructions on running your experiment. Let us fix N, the number of vertices in our graphs, at 10,000. Let us also fix M, the number of (s, t) pairs to be 1 million. You should run your experiment for different values of p, the probability of rewiring, and different values of D, the average degree. You might try values of D = 15, 20, 25, 30, and 35. For each (p, D) pair, generate 10 graphs to run your experiments on. The size of these experiments may be too ambitious and we might scale these down a bit, depending on how long they take to run.