1. Let G = (V, E) be an undirected (unweighted) graph and let S = (C1, C2,........Cl) be a community structure of G with I communities. Let A be the adjacency matrix of G, i.e., Aij =1 if (f,f) ∈ E and Aij = Or otherwise. Prove that the following two formulas to compute modularity of S are equivalent
where E(Ct) is the number of edges with both ends inside Ct; vol(Ct) is the total degree of nodes inside 4; in is the number of edges in G; and δ( Ci, Cj) = 1 if the two nudes . and j are in the same community and δ(ci, cj) = 0, otherwise.
2. Write a program in to find the largest value of k such that there exists a k-core in a given undirected graph G = (V, E). Also print out the nodes in the largest k-core.
Input: The file "graph.bit" includes multiples lines in which the first line contains two integersn and in that correspond to the number of nodes and edges in the graph. Each of the following in lines contain two integers u and ts, separated by one space, to denote an edge from u to tr. Nodes are numbered from 1 to n.
The output file itcorelsre contains exactly 2 lines in which the first line is the value of the largest k and the second line contains nodes in the largest k -tore, sorted in a nort-dtorearitig order.