Homework 3: Stat 4690: Statistical Analysis of Networks

Online submission through carmen due on Friday, March 22, at 11:59 PM

This assignment also uses the same football dataset that was used in homework 2.

library(igraph)

football  = read_graph("football. gml" ,  format="gml")

1.  (45 points) Fit the Stochastic Block Model using the Variational EM method imple- mented in R package "blockmodels" to this dataset and answer the following questions

(a)  (15) Obtain a plot of the ICL criterion with the number of communities (K) and

choose the optimal number of communities that maximizes the ICL criterion.

(b)  (15) Show the K × K matrix of block probabilities of connections and then also plot it. What patterns do you observe from this estimated matrix of probabilities?

(c)  (15)  Plot the observed and the estimated adjacency matrices ordered by the community assignments to visually compare how well the model fits the data and how well the community assignments partition the observed network.

2.  (60 points) Design and implement a simulation study to assess and compare the accuracy of Variational EM and spectral clustering for community detection in graphs generated from the Stochastic Block Model with increasing number of nodes. A possible setup could be to vary the number of nodes from 50 to 250 in increments of 50, keeping the number of communities fixed at 3, the block matrix of probabilities generated such that all intra-community probabilities are 0.2 and all inter community probabilities are 0.1. For variational EM method you may use the function implemented in the "blockmodels" package while for spectral clustering you may use the "Spectral" function from specfunctions.R code uploaded in carmen. You may use the MCrate() function from specfunctions.R uploaded to carmen to compute the correct clustering rate. Plot the correct clustering rate from the two methods againts the number of nodes.  On the basis of the plot comment how the methods perform with increasing node and how they compare against each other.

The total possible points are 105, while your grade will be recorded as out of 100. Therefore if you make no mistakes in the homework then you will receive 105/100. Therefore effectively the homework has 5 bonus points that everyone who submits on time receives.