Erdös–Renyi random graph model. In the classic Erdös–Renyi random graph model, we build a...

Erdös–Renyi random graph model. In the classic Erdös–Renyi 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 < In V/V, the graph is disconnected with high probability; if p > In 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 adjacent 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 small-world graphs.

• Short path lengths: If p > In V/V, then the diameter of the graph (see Exercise 4.5.40) is logarithmic.

EXERCISE 4.5.40

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). Write a Graph client Diameter that can compute the eccentricity of a vertex and the diameter of a graph. Use it to find the diameter of the performer-performer graph associated with movies.txt.