[SOLVED] Cs550 problem set 3

In (Newman 2006, PNAS 103(23): 8577–8582)1 Mark Newman defines the modularity of
a network divided into two components as (see paper or course slides for specification on
notation):
Q =
1
4m
X
ij

Aij −
kikj
2m

sisj (1)We will now get a better intuition on what this quantity means. Consider the network in
the figure 1 below:
(a) [10pt] If we remove edge (A, G) and partition the graph into two communities, calculate
the modularity of this partition.(b) [10pt] Now, consider the original network from the figure and the groups identified
in (a). Add a link between nodes E and H and recalculate modularity Q. Did the
modularity Q go up or down? Why?(c) [10pt] Consider the original network from the figure and the groups identified in (a).
Now add a link between nodes F and A and recalculate modularity Q. Did Q go up or
down? Why?1Newman ME. Modularity and community structure in networks. Proceedings of the national academy of
sciences. 2006 Jun 6;103(23):8577-82.
1
Figure 1: Figure of problem 1 and problem 2Still consider the graph in Figure 1, assume that any edge in this graph has an equal
weight 1. We run spectral clustering to partition the graph into two communities.
(a) [10pt] Provide the adjacency matrix A, degree matrix D, and Laplacian matrix L of
the graph.(b) [10pt] Using Matlab or Python, compute the eigen values and the corresponding eigen
vectors of the Laplacian matrix. Rank the eigen values in ascending order. [You may refer
to the problem 1 in homework 2 for some hints of using Python to compute eigen values
and eigen vectors](c) [10pt] What is the eigen vector corresponding to the second smallest eigen values?
Using 0 as the boundary, partition the graph into two communities, what is the graph
partitioning result?What to submit:
i. The matrices A, D and L in (a).
ii. The eigen values and eigen vectors in (b), as well as the code for computing them.
iii. The graph partitioning result in (c).Imagine an undirected graph G with nodes 2, 3, 4, …, 1000000. (Note that there is no node
1.) There is an edge between nodes i and j if and only if i and j have a common factor
other than 1. Put another way, the only edges that are missing are those between nodes
that are relatively prime; e.g., there is no edge between 15 and 56.We want to find communities by starting with a clique (not a bi-clique) and growing it
by adding nodes. However, when we grow a clique, we want to keep the density of edges
2
at 1; i.e., the set of nodes remains a clique at all times. A maximal clique is a clique for
which it is impossible to add a node and still retain the property of being a clique; i.e., a
clique C is maximal if every node not in C is missing an edge to at least one member of
C.(a) [10pt] Prove that if i is any integer greater than 1, then the set Ci of nodes of G that
are divisible by i is a clique.(b) [10pt] Under what circumstances is Ci a maximal clique? Prove that your conditions
are both necessary and sufficient. (Trivial conditions, like “Ci
is a maximal clique if and
only if Ci
is a maximal clique”, will receive no credit.)(c) [10pt] Prove that C2 is the unique maximal clique. That is, it is larger than any other
clique.