1.  [25 points] Note that the local clustering coefficient is defined by the following:

number of links between neighbors                C =

maximum possible number of links between neighbors

(a)  [15 points] Calculate the local clustering coefficient C for a node with degree k

in an Erdos-Renyi random graph Gn,p .

Hint:  For the denominator, think how many possible links you could have existing between  your neighbors  if you  have  k  neighbors .   Then, for the  numerator,  the number of links that will actually appear between them in the Gn,p  model is going to  be related to p (i. e ., the probability each edge will independently be formed) .

(b)  [10 points] Using the fact that the < k >= p(n − 1) ≈ pn, discuss why C → 0 as

n → ∞ using the result you obtained from 1(a) if the mean degree < k > stays fixed.

Hint:  The answer to part (a) will contain the value p .  After solving for p in the equality given here in  (b)  and plugging into your answer from  (a) .  Then, if you think of this value while n → ∞ it becomes clear why C → 0 with this condition of the mean degree remaining fixed.

2.  [30 points] In the lecture we discussed how we can use the powers of the adjacency matrix to calculate the number of paths of a given length between any pair of nodes. Specifically, A[i,j] told us whether there is a path of length one or not, A2[i,j] counted the number of paths of length two between nodes i and j, which generalizes to Ak [i,j] encoding the number of paths from i to j of length k . Here you will program this to visualize this relationship and observe the density increase.

(a)  [15 points] For this first part please use the graph we used as an example in class,

i.e., G = nx.Graph([(1,2),(1,3),(2,3),(2,4),(3,4),(4,5)])

First, you can obtain the adjacency matrix of this networkx graph with A = nx.adjacency matrix(G) and to better visualize the printing convert the default created SciPy sparse matrix to the dense form A.todense(). Then, you can obtain powers 2 and 3 of the adjacency by multiplying A with itself that many times. Please print the dense form of A, A2, and A3  to observe how generally this will become denser with increased powers of the adjacency.

Please see “networkx.linalg.graphmatrix.adjacency matrix” in NetworkX

(b)  [15 points] Now let us perform a similar calculation on a Gn,p  graph with 100

nodes and probability of 0.06 that two random nodes will be connected with an edge, i.e., G = nx.gnp random graph(100, 0.06). Please print the percentage of the matrices A, A2 , A3, and A4  that are non-zero.  To do this you can use the SciPy built in function count nonzero(), which will return the number of non- zero entries in the matrix and then divide by the total number of elements in the matrix (i.e., 1002 ). Note that since this is based on a random graph, please run this process on 5 graphs and report the average values as compared to reporting for a single graph.

Please see “scipy.sparse.csr matrix.count nonzero” in SciPy.

3.  [15 points] Remember that in the configuration model we were able to provide a degree sequence D = {k1 ,k2 , ··· ,kn} representing the degree for each of the n nodes in the graph to be constructed.  Assume that the degree sequence provided is the same for all nodes (i.e., k1 = k2 = ... = kn).

(a)  [5 points] Describe what the degree distribution would look like for this graph

along with a visualization (you’re welcome to include a visualization, e.g., rough hand drawn plot, of the degree distribution plot if that makes providing the description easier).

(b)  [10 points] What happens to the generated graph when k1  = k2  = ... = kn  = 1

(i.e., all nodes have degree equal to 1).  If each node only has degree one, this means that they are all required to only have one edge connected to them, since having zero edges or more than one edge would result in a degree lower or higher than 1, respectively.  Hence, in this setting, how many connected components will be in the generated graph?   Note that there is an exact answer since all possible graphs that can be constructed with this degree sequence will have the same number of connected components.

Hint:  Also,  note that here we  assume the  degree sequence k1  = k2  = k3 ··· kn  is a  valid  degree  sequence for the  configuration  model,  since  not  all sequences  are valid.  For example, if n = 1, then we have k1 = 1,  but it is impossible to have a graph with a single node having degree one, since even if that node has a self- loop, its degree would be 2.