# Structural Analysis and Visualization of Networks¶

## Home Assignment #4: Community Detection Algorithms

#### 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

import scipy.io