Structural Analysis and Visualization of Networks

Home Assignment #4: Community Detection Algorithms

Student: *{Your Name}*


General Information

Due Date: 19.03.2015 23:59 <br > Late submission policy: -0.2 points per day <br >

Please send your reports to mailto:leonid.e.zhuk[email protected] and mailto:[email protected] with message subject of the following structure:<br > [HSE Networks 2015] {LastName} {First Name} HA{Number}

Support your computations with figures and comments. <br > If you are using IPython Notebook you may use this file as a starting point of your report.<br > <br >

<hr >

Problems

Task 1* (For those who have not done that during the seminar)

On this seminar your are asked to implement simple community detection algorightm. It is called Markov Cluster Algorithm (MCL).

Implement Markor Clustering Algorithm

Input: Transition matrix $T = D^{-1}A$

Output: Adjacency matrix $M^*$

  1. Set $M = T$
  2. repeat:
    1. Expansion Step: $M = M^p$ (usually $p=2$)
    2. Inflation Step: Raise every entry of $M$ to the power $\alpha$ (usualy $\alpha=2$)
    3. Renormalize: Normalize each row by its sum
    4. Prunning: Replace entries that are close to $0$ by pure $0$
  3. until $M$ converges
  4. $M^* = M$ <br> <br>

As a result you should get a cluster matrix s.t. elements of the cluster correspont to nonzero elements of the columns of the matrix. <br>

  • Run this method for network 1, 2 and 3.
  • Play with the parameters ($p$, $\alpha$, zero tolerance), analyse the results

Task 2

Load Yahoo Music network. Edges in this network appear if enough number of users have given ratings to both music bands. Note, that edges are weighted with similarity of the ratings.

  • Implement multilevel spectral recursive partitioning algorithm that was described during the lecture
  • Visualize community structure of the network and output some of the dense clusters (with interpretation, if you can)

You can load .mat files with the following commands:

In [ ]:
import scipy.io

data = scipy.io.loadmat('music_data.mat')