{"nbformat": 3, "worksheets": [{"cells": [{"source": ["# Matrices for graph traversal"], "metadata": {}, "cell_type": "markdown"}, {"outputs": [], "collapsed": false, "prompt_number": 1, "input": ["import numpy as np"], "language": "python", "metadata": {}, "cell_type": "code"}, {"outputs": [{"prompt_number": 2, "output_type": "pyout", "metadata": {}, "text": ["array([[ 0.5, 0.8, 0. , 0.5, 0.4],\n", " [ 0. , 0.7, 0.7, 0.3, 0. ],\n", " [ 0.5, 0. , 0. , 0. , 0. ],\n", " [ 0. , 0. , 0. , 0. , 0. ],\n", " [ 0. , 0. , 0.7, 0. , 0. ]])"]}], "collapsed": false, "prompt_number": 2, "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"], "language": "python", "metadata": {}, "cell_type": "code"}, {"source": ["For a reason that will become clear in a minute, we need the columns of $A$ to be normalized to sum to 1:"], "metadata": {}, "cell_type": "markdown"}, {"outputs": [{"stream": "stdout", "output_type": "stream", "text": ["[[ 0.5 0.53333333 0. 0.625 1. ]\n", " [ 0. 0.46666667 0.5 0.375 0. ]\n", " [ 0.5 0. 0. 0. 0. ]\n", " [ 0. 0. 0. 0. 0. ]\n", " [ 0. 0. 0.5 0. 0. ]]\n", "[ 1. 1. 1. 1. 1.]\n"]}], "collapsed": false, "prompt_number": 3, "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))"], "language": "python", "metadata": {}, "cell_type": "code"}, {"source": ["This short piece of code exports the matrix in a format that's readable to the [dot](http://graphviz.org) graph drawing tool."], "metadata": {}, "cell_type": "markdown"}, {"outputs": [], "collapsed": false, "prompt_number": 4, "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)"], "language": "python", "metadata": {}, "cell_type": "code"}, {"source": ["See?"], "metadata": {}, "cell_type": "markdown"}, {"outputs": [{"stream": "stdout", "output_type": "stream", "text": ["digraph mygraph { size=\"2,2\";\n", "0 -> 0 [label=\"0.5\"];\n", "1 -> 0 [label=\"0.5\"];\n", "3 -> 0 [label=\"0.6\"];\n", "4 -> 0 [label=\"1.0\"];\n", "1 -> 1 [label=\"0.5\"];\n", "2 -> 1 [label=\"0.5\"];\n", "3 -> 1 [label=\"0.4\"];\n", "0 -> 2 [label=\"0.5\"];\n", "2 -> 4 [label=\"0.5\"];\n", "}\n"]}], "collapsed": false, "prompt_number": 5, "input": ["print(to_dot(A))"], "language": "python", "metadata": {}, "cell_type": "code"}, {"outputs": [], "collapsed": false, "prompt_number": 6, "input": ["%load_ext gvmagic"], "language": "python", "metadata": {}, "cell_type": "code"}, {"outputs": [{"output_type": "display_data", "metadata": {}, "svg": ["\n", "\n", "\n", "\n", "\n"]}], "collapsed": false, "prompt_number": 7, "input": ["%dotstr to_dot(A)"], "language": "python", "metadata": {}, "cell_type": "code"}, {"source": ["Another thing we can do is plot distributions on the graph:"], "metadata": {}, "cell_type": "markdown"}, {"outputs": [{"output_type": "display_data", "metadata": {}, "svg": ["\n", "\n", "\n", "\n", "\n"]}], "collapsed": false, "prompt_number": 9, "input": ["d = np.zeros((n,))\n", "d[0] = 1\n", "%dotstr to_dot(A, d)"], "language": "python", "metadata": {}, "cell_type": "code"}, {"outputs": [{"prompt_number": 10, "output_type": "pyout", "metadata": {}, "text": ["array([ 1., 0., 0., 0., 0.])"]}], "collapsed": false, "prompt_number": 10, "input": ["d"], "language": "python", "metadata": {}, "cell_type": "code"}, {"source": ["Now, how would we model the spread of this distribution across the graph?"], "metadata": {}, "cell_type": "markdown"}, {"outputs": [{"stream": "stdout", "output_type": "stream", "text": ["[ 0.45070423 0.21126761 0.22535211 0. 0.11267606]\n"]}, {"output_type": "display_data", "metadata": {}, "svg": ["\n", "\n", "\n", "\n", "\n"]}], "collapsed": false, "prompt_number": 73, "input": ["d = A.dot(d)\n", "print(d)\n", "%dotstr to_dot(A, d)"], "language": "python", "metadata": {}, "cell_type": "code"}, {"outputs": [{"prompt_number": 47, "output_type": "pyout", "metadata": {}, "text": ["array([ 0.45070426, 0.2112676 , 0.2253521 , 0. , 0.11267604])"]}], "collapsed": false, "prompt_number": 47, "input": ["d"], "language": "python", "metadata": {}, "cell_type": "code"}, {"source": ["More questions:\n", "\n", "* How would you find the steady state of this traversal?\n", "* Any predictions about `np.sum(d)`?"], "metadata": {}, "cell_type": "markdown"}], "metadata": {}}], "metadata": {"signature": "sha256:256ae96cea4805fcbed0344844a99df92dccebc101c55056b9c08b4ff794e0ac", "name": ""}, "nbformat_minor": 0}