\n", "General Information" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Due Date:** 19.03.2015 23:59

\n", "**Late submission policy:** -0.2 points per day

\n", "\n", "\n", "Please send your reports to

**[HSE Networks 2015] *{LastName}* *{First Name}* HA*{Number}***\n", "\n", "Support your computations with figures and comments.

\n", "If you are using IPython Notebook you may use this file as a starting point of your report.

\n", "

\n", "

" ] }, { "cell_type": "heading", "level": 2, "metadata": {}, "source": [ "Problems" ] }, { "cell_type": "heading", "level": 3, "metadata": {}, "source": [ "Task 1* (For those who have not done that during the seminar)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On this seminar your are asked to implement simple community detection algorightm. It is called [Markov Cluster Algorithm](http://micans.org/mcl/) (MCL).\n", "\n", "Implement Markor Clustering Algorithm\n", "\n", "**Input:** Transition matrix $T = D^{-1}A$\n", "\n", "**Output:** Adjacency matrix $M^*$\n", "\n", "1. Set $M = T$\n", "2. **repeat:**\n", " 3. *Expansion Step:* $M = M^p$ (usually $p=2$)\n", " 4. *Inflation Step:* Raise every entry of $M$ to the power $\\alpha$ (usualy $\\alpha=2$)\n", " 5. *Renormalize:* Normalize each row by its sum\n", " 6. *Prunning:* Replace entries that are close to $0$ by pure $0$\n", "7. **until** $M$ converges\n", "8. $M^* = M$\n", "

\n", "

\n", "\n", "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. \n", "

\n", "* Run this method for network [1](https://www.dropbox.com/s/so0ly2ozh2pzxp6/network1.mat?dl=0), [2](https://www.dropbox.com/s/xcswyhoeehq95v2/network2.mat?dl=0) and [3](https://www.dropbox.com/s/cwshsfr2d8fn470/network3.mat?dl=0).\n", "* Play with the parameters ($p$, $\\alpha$, zero tolerance), analyse the results\n", "\n", "

\n" ] }, { "cell_type": "heading", "level": 3, "metadata": {}, "source": [ "Task 2" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Load [Yahoo Music network](https://www.dropbox.com/s/o3x14v4rznrh555/music_data.mat?dl=0). 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.\n", "\n", "* Implement *multilevel spectral recursive partitioning* algorithm that was described during the lecture\n", "* Visualize community structure of the network and output some of the dense clusters (with interpretation, if you can)\n", "\n", "You can load .mat files with the following commands:" ] }, { "cell_type": "code", "collapsed": false, "input": [ "import scipy.io\n", "\n", "data = scipy.io.loadmat('music_data.mat')" ], "language": "python", "metadata": {}, "outputs": [] } ], "metadata": {} } ] }