{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Matrices for Graph Traversal"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"import numpy as np"
]
},
{
"cell_type": "code",
"execution_count": 28,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"array([[ 0. , 0. , 0.8, 0.1, 1. ],\n",
" [ 0. , 0. , 0. , 0.8, 0. ],\n",
" [ 0. , 0.5, 0.8, 0.7, 0. ],\n",
" [ 0.7, 0. , 0. , 0. , 0. ],\n",
" [ 0. , 0. , 0.7, 0.6, 0. ]])"
]
},
"execution_count": 28,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"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"
]
},
{
"cell_type": "markdown",
"metadata": {},
"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": "code",
"execution_count": 29,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[[ 0. 0. 0.34782609 0.04545455 1. ]\n",
" [ 0. 0. 0. 0.36363636 0. ]\n",
" [ 0. 1. 0.34782609 0.31818182 0. ]\n",
" [ 1. 0. 0. 0. 0. ]\n",
" [ 0. 0. 0.30434783 0.27272727 0. ]]\n",
"[ 1. 1. 1. 1. 1.]\n"
]
}
],
"source": [
"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))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"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": "code",
"execution_count": 30,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"def to_dot(A, vec=None):\n",
" lines = ['digraph mygraph { size=\"4,4\";']\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)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"See?"
]
},
{
"cell_type": "code",
"execution_count": 31,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"digraph mygraph { size=\"4,4\";\n",
"2 -> 0 [label=\"0.3\"];\n",
"3 -> 0 [label=\"0.0\"];\n",
"4 -> 0 [label=\"1.0\"];\n",
"3 -> 1 [label=\"0.4\"];\n",
"1 -> 2 [label=\"1.0\"];\n",
"2 -> 2 [label=\"0.3\"];\n",
"3 -> 2 [label=\"0.3\"];\n",
"0 -> 3 [label=\"1.0\"];\n",
"2 -> 4 [label=\"0.3\"];\n",
"3 -> 4 [label=\"0.3\"];\n",
"}\n"
]
}
],
"source": [
"print(to_dot(A))"
]
},
{
"cell_type": "code",
"execution_count": 32,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"The gvmagic extension is already loaded. To reload it, use:\n",
" %reload_ext gvmagic\n"
]
}
],
"source": [
"%load_ext gvmagic"
]
},
{
"cell_type": "code",
"execution_count": 33,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"%dotstr to_dot(A)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Another thing we can do is plot distributions on the graph:"
]
},
{
"cell_type": "code",
"execution_count": 41,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"d = np.zeros((n,))\n",
"d[0] = 1\n",
"%dotstr to_dot(A, d)"
]
},
{
"cell_type": "code",
"execution_count": 42,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"array([ 1., 0., 0., 0., 0.])"
]
},
"execution_count": 42,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"d"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Now, how would we model the spread of this distribution across the graph?"
]
},
{
"cell_type": "code",
"execution_count": 45,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[ 0.38339921 0. 0.4743083 0.04545455 0.09683794]\n"
]
},
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"d = A.dot(d)\n",
"print(d)\n",
"%dotstr to_dot(A, d)"
]
},
{
"cell_type": "code",
"execution_count": 46,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"array([ 0.38339921, 0. , 0.4743083 , 0.04545455, 0.09683794])"
]
},
"execution_count": 46,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"d"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"* How would you find the steady state of this traversal?"
]
},
{
"cell_type": "code",
"execution_count": 47,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"# Just keep iterating until the distribution stabilizes."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"* Any predictions about `np.sum(d)`?"
]
},
{
"cell_type": "code",
"execution_count": 48,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"# Always stays 1."
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.5.2+"
}
},
"nbformat": 4,
"nbformat_minor": 0
}