Graph Theory: Assignment 3

Graph Theory: Assignment 3 Due April 21^th

Submit clear and well explained answers. You can submit one answer per group. You can use the internet (but not pay wall sites like Chegg) to look for answers, but the final answer must be in your own words. Please cite all resources used.

1. Community Detection in Networks: (55 points)
   • Go to the social networks section of the network repository website (https://networkrepository.com/soc.php). (5 points)

Download the following graphs

• Soc-tribes
• Soc-karate
• Soc-dolphins

• Download the Louvain community detection algorithm (https://perso.uclouvain.be/vincent.blondel/research/louvain.html)

You can use any of the versions given in the website Download/or use online the infomap algorithm https://www.mapequation.org/infomap/

If your data is too large for the online version you can use the code given in the page.

Obtain the communities for each network using (i) the Louvain algorithm and (ii) the Infomap algorithm (3*2*5=30 points)

• Compare the similarity between the two sets of results for each network using (3*5

points)

• Write a short paragraph on your observations of how the two algorithms give similar/dissimilar

results. (5 points)

2. Laplacian Given an undirected and unweighted network G with N vertices, let A be the

adjacency matrix, and D =[d1, d2, d3, …,dN] the degree matrix, where degree of each vertex is given in the diagonal. The Laplacian matrix is given as L=D-A. The normalized Laplacian is given by Ln=D^-1/2L D^-1/2. (15 points)

1. Show that if x is an eigen vector of L then D^1/2x is an eigen vector of Ln (5)
2. Show that Ln has one eigen vector of the form D=[d1^1/2, d2^1/2, ….,

dN^1/2] whose corresponding eigen value is zero.(5)

1. For the figure given, find the Fiedler vector for L , and using that partition the Give the Laplacian graph, the Fiedler vector and the eigen value, as well as the partition. You can use this toll

to compute the eigenvectors (https://www.emathhelp.net/en/calculators/linear- algebra/eigenvalue-and-eigenvector-calculator/) (5)

3. Prove the following statements. Please write out the proof in detail, without skipping any vital You can use figures to illustrate your work if necessary (10*3=30 points)
4. Given that G is a graph with at least three vertices, where for any three distinct vertices u,v, and w, there is a path from u to v that does not contain Prove that G has no cut vertex (articulation points), i.e. there is no vertex is G whose removal would disconnect it into two separate subgraphs.
5. G is a simple graph with n vertices n>=2; and at least [(n-1)(n-2)/2 ]+1 edges. Prove that G is connected
6. Show that if v is an articulation point in a graph G, then it cannot be an articulation point in the complement graph of G.