This question asks you to write a spectral clustering algorithm using k $-$means clustering and test your

code on a test network. Consider the symmetric graph Laplacian $L_g=D-$A and the non$-$symmetric

random walk matrix $L_r=A{D}^{-1}.$

Construct an artificial network consisting of $4$ clearly defined communities, each with $10$ nodes,

where the probability of connecting within a community is $0\mathrm{.}9$ and the probability to connect to

nodes outside the community is $0\mathrm{.}05.$ Use the NetworkX command planted$\_$partition$\_$graph.

Plot the graph.

This is a good test case to test any community finding algorithm. You can play with changing the

inter$/$intra connectivity probabilities to consider less well$-$defined communities and to see how the

routines work.

Write a programme to do spectral clustering as we discussed in the lectures using k$-$means $($use

built$-$in routines for k$-$means; no need to write this routine yourself$).$

$[$Remarks: k$-$means requires real inputs. You will need a routine which sets all $($very small, but

non$-$zero$)$ imaginary parts of the eigenvectors to zero.$]$

Test your programme with the network you generated above in $(1).$ In k$-$means you need to specify

the number of clusters $k.$ Argue by using the spectrum of your respective matrices how you should

be choosing $k.$

What are the python codes for this question?