We will study a political blog dataset first compiled for the paper Lada A$.$ Adamic and Natalie Glance,

$$The political blogosphere and the $2004$ US Election$,$ in Proceedings of the WWW$-2005$ Workshop on the

Weblogging Ecosystem $(2005).$ It is assumed that blog$-$site with the same political orientation are more

likely to link to each other, thus, forming a $$community$$ or $$cluster$$ in a graph. In this question, we will

see whether or not this hypothesis is likely to be true based on the data.

$$ The dataset nodes.txt contains a graph with n $=1490$ vertices $($nodes$)$ corresponding to political

blogs.

$$ The dataset edges.txt contains edges between the vertices. You may remove isolated nodes $($nodes

that are not connected to any other nodes$)$ in the pre$-$processing.

We will treat the network as an undirected graph; thus, when constructing the adjacency matrix, make

it symmetrical by$,$ e$.$g$.,$ set the entry in the adjacency matrix to be one whether there is an edge between

the two nodes $($in either direction$).$

In addition, each vertex has a $0-1$ label $($in the $3$rd column of the data file$)$ corresponding to the true

political orientation of that blog. We will consider this as the true label and check whether spectral clustering

will cluster nodes with the same political orientation as possible.

$1.(5$ points$)$ Use spectral clustering to find the k $=2,5,10,30,50$ clusters in the network of political blogs

$($each node is a blog, and their edges are defined in the file edges.txt$).$ Find majority labels $($Same as

purity score from the image compression problem$)$ in each cluster for different k values, respectively.

For example, if there are k $=2$ clusters, and their labels are $\{0,1,1,1\}$ and $\{0,0,1\}$ then the majority

label for the first cluster is $1$ and for the second cluster is $0.$ It is required you implement the

algorithms yourself rather than calling from a package.

$4$

Now compare the majority label with the individual labels in each cluster, and report the mismatch

rate $($Also known as misclassification rate$)$ for each cluster, when k $=2,5,10,30,50.$ For instance, in

the example above, the mismatch rate for the first cluster is $1/4($only the first node differs from the

majority$),$ and the second cluster is $1/3.$

$2.(5$ points$)$ Tune your k and find the number of clusters to achieve a reasonably small mismatch rate.

Please explain how you tune k and what is the achieved mismatch rate. Please explain intuitively what

this result tells about the network community structure.