{"nbformat_minor": 0, "worksheets": [{"cells": [{"source": ["# Matrices for graph traversal"], "cell_type": "markdown", "metadata": {}}, {"cell_type": "code", "language": "python", "input": ["import numpy as np"], "metadata": {}, "outputs": [], "prompt_number": 1, "collapsed": false}, {"cell_type": "code", "language": "python", "input": ["\n", "n = 5\n", "\n", "# Make a sparsely populated random matrix\n", "A = np.zeros((n, n))\n", "\n", "from random import randrange, uniform\n", "for i in range(n*n//2):\n", " i, j = randrange(n), randrange(n)\n", " w = round(uniform(0, 1), 1)\n", " A[i, j] = w\n", " \n", "A"], "metadata": {}, "outputs": [{"text": ["array([[ 0. , 0. , 0. , 0.5, 0.9],\n", " [ 0. , 0. , 0.8, 0. , 0.2],\n", " [ 0.3, 0. , 0.3, 0. , 0.4],\n", " [ 0. , 0. , 0.3, 0. , 0. ],\n", " [ 0. , 0. , 0. , 0. , 0. ]])"], "output_type": "pyout", "prompt_number": 182, "metadata": {}}], "prompt_number": 182, "collapsed": false}, {"source": ["For a reason that will become clear in a minute, we need the columns of $A$ to be normalized to sum to 1:"], "cell_type": "markdown", "metadata": {}}, {"cell_type": "code", "language": "python", "input": ["A_cols = np.sum(A, axis=0)\n", "A_cols[A_cols == 0] = 1\n", "A = A/A_cols\n", "\n", "print(A)\n", "print(np.sum(A, axis=0))"], "metadata": {}, "outputs": [{"text": ["[[ 0. 0. 0. 1. 0.6 ]\n", " [ 0. 0. 0.57142857 0. 0.13333333]\n", " [ 1. 0. 0.21428571 0. 0.26666667]\n", " [ 0. 0. 0.21428571 0. 0. ]\n", " [ 0. 0. 0. 0. 0. ]]\n", "[ 1. 0. 1. 1. 1.]\n"], "stream": "stdout", "output_type": "stream"}], "prompt_number": 183, "collapsed": false}, {"source": ["This short piece of code exports the matrix in a format that's readable to the [dot](http://graphviz.org) graph drawing tool."], "cell_type": "markdown", "metadata": {}}, {"cell_type": "code", "language": "python", "input": ["def to_dot(A, vec=None):\n", " lines = ['digraph mygraph { size=\"2,2\";']\n", " for i in range(n):\n", " for j in range(n):\n", " if A[i, j]:\n", " lines.append(\"%d -> %d [label=\\\"%0.1f\\\"];\" % (j, i, A[i, j]))\n", " if vec is not None:\n", " for i, vec_i in enumerate(vec):\n", " assert 0<=vec_i<=1\n", " lines.append(\n", " '%d [style=\"filled\", fillcolor=\"#ff%02xff\"];'\n", " % (i, int(255*(1-vec_i))))\n", " lines.append(\"}\")\n", " return \"\\n\".join(lines)"], "metadata": {}, "outputs": [], "prompt_number": 184, "collapsed": false}, {"source": ["See?"], "cell_type": "markdown", "metadata": {}}, {"cell_type": "code", "language": "python", "input": ["print(to_dot(A))"], "metadata": {}, "outputs": [{"text": ["digraph mygraph { size=\"2,2\";\n", "3 -> 0 [label=\"1.0\"];\n", "4 -> 0 [label=\"0.6\"];\n", "2 -> 1 [label=\"0.6\"];\n", "4 -> 1 [label=\"0.1\"];\n", "0 -> 2 [label=\"1.0\"];\n", "2 -> 2 [label=\"0.2\"];\n", "4 -> 2 [label=\"0.3\"];\n", "2 -> 3 [label=\"0.2\"];\n", "}\n"], "stream": "stdout", "output_type": "stream"}], "prompt_number": 185, "collapsed": false}, {"cell_type": "code", "language": "python", "input": ["%load_ext gvmagic"], "metadata": {}, "outputs": [{"text": ["The gvmagic extension is already loaded. To reload it, use:\n", " %reload_ext gvmagic\n"], "stream": "stdout", "output_type": "stream"}], "prompt_number": 186, "collapsed": false}, {"cell_type": "code", "language": "python", "input": ["%dotstr to_dot(A)"], "metadata": {}, "outputs": [{"svg": ["\n", "\n", "\n", "\n", "\n"], "output_type": "display_data", "metadata": {}}], "prompt_number": 187, "collapsed": false}, {"source": ["Another thing we can do is plot distributions on the graph:"], "cell_type": "markdown", "metadata": {}}, {"cell_type": "code", "language": "python", "input": ["d = np.zeros((n,))\n", "d[4] = 1\n", "%dotstr to_dot(A, d)"], "metadata": {}, "outputs": [{"svg": ["\n", "\n", "\n", "\n", "\n"], "output_type": "display_data", "metadata": {}}], "prompt_number": 188, "collapsed": false}, {"source": ["Now, how would we model the spread of this distribution across the graph?"], "cell_type": "markdown", "metadata": {}}, {"cell_type": "code", "language": "python", "input": ["d = np.dot(A, d)\n", "print(np.sum(d))\n", "%dotstr to_dot(A, d)"], "metadata": {}, "outputs": [{"text": ["1.0\n"], "stream": "stdout", "output_type": "stream"}, {"svg": ["\n", "\n", "\n", "\n", "\n"], "output_type": "display_data", "metadata": {}}], "prompt_number": 189, "collapsed": false}, {"source": ["More questions:\n", "\n", "* How would you find the steady state of this traversal?\n", "* Any predictions about `np.sum(d)`?"], "cell_type": "markdown", "metadata": {}}], "metadata": {}}], "nbformat": 3, "metadata": {"signature": "sha256:b14a6d671cd1d94a2d6a816f93630e22a26bba0bd808c9e31eaca54c4ef92223", "name": ""}}