CS 565, Spring 2023, Homework 4
Due Thur March 16, 11�59 pm ET (Boston time), via Gradescope
Submission guidelines
Please write your solutions inside of this .ipynb file, then convert it to a PDF before submitting
on Gradescope:
In Jupyter: File > Download as > PDF
In Google Colab: File > Print > Destination > Save as PDF
When you submit, please be sure to match the answers on your PDF to the outline on
Gradescope. In other words, if the answer to problem 2.1 is on pages 2 and 3 of your PDF,
please be sure to select those pages as the answer to problem 2.1 on Gradescope. Since it
takes significantly longer to grade homework that is not properly matched, we may deduct
points for noncompliant submissions.
Karan (the TF) will cover how to get started with the notebooks for writing problem solutions
and running experiments.
3/15/23, 8:14 PM homework4
localhost:8888/nbconvert/html/Desktop/CS565/homework/homework4.ipynb?download=false 2/3
1. Theoretical Questions (40 points)
1.1 (20 points)
Let be the laplacian matrix of an undirected weighted graph , where
. Show that for any vector :
1.2 Second eigenvalue of the Laplacian (20 points)
Assume an undirected graph with laplacian matrix . If is the second smallest
eigenvalue of show that: \emph{if and only if} is disconnected.
2. Experiments (60 points)
2.1 Implement the planted partition model (20 points)
The planted partition model is a graph-generation model that has four parameters :
corresponds to the nodes of the graph, which is an undirected and unweighted graph;
corresponds to the number of “clusters” in which the nodes of the graph are partitioned;
corresponds to the probability that two nodes in the same cluster are connected by an
corresponds to the probability that two nodes that belong in different clusters are
connected by an edge.
Note that the clusters have no overlap between them and also the partition of nodes into
clusters is random. Also, for the model to make sense it should be that .
Write a function that generates a graph according to the random partition model.
2.2 Implement spectral clustering (20 points)
In this part of the exercise you need to implement spectral clustering. Given a graph , form its
Laplacian matrix and compute its fiedler vector. Assign the nodes to clusters based on the their
sign in the fiedler vector.
2.3 Test Your Implementation (20 points)
Generate data using the random partition model for , and
. Report the value of graph expansion of the partition found by
L G(V , E, w)
w : E → R≥0 x ∈ R
w((i, j))(x(i) − x(j))
G(V , E) L λ2
L λ2 = 0 G
n, k, p, q
n = 5000 k = 2 p = 0.8
q ∈ {0.001, 0.01, 0.1, 0.2, 0.3}
3/15/23, 8:14 PM homework4
localhost:8888/nbconvert/html/Desktop/CS565/homework/homework4.ipynb?download=false 3/3
your clustering algorithm.
2.4 Visualization (20 points — extra credit)
Using the networkx package visualize the result of your clusterings and demonstrate through
these visualizations that the spectral algorithm works in practice.