{ "cells": [ { "cell_type": "markdown", "id": "988e4c4b", "metadata": {}, "source": [ "# PageRank using MapReduce" ] }, { "cell_type": "markdown", "id": "40d3e93f", "metadata": {}, "source": [ "In this section we will illustrate the computation of Taxed PageRank in a distributed way using MapReduce in **pyspark**. Note however that this only illustrated the case when the PageRank vector $v$ fits in memory. For cases where $v$ does not fit in memory, techniques like *striping* and *blocking* should be employed, as discussed in the previous section." ] }, { "cell_type": "code", "execution_count": 1, "id": "e254efe3", "metadata": {}, "outputs": [], "source": [ "from pyspark import SparkContext\n", "import numpy as np\n", "import matplotlib.pyplot as plt\n", "import networkx as nx\n", "import csv\n", "\n", "from alis import link_analysis # our Link Analysis module" ] }, { "cell_type": "markdown", "id": "4b6ba960", "metadata": {}, "source": [ "## Illustration of Matrix-Vector Multiplication via MapReduce" ] }, { "cell_type": "markdown", "id": "c9d985b9", "metadata": {}, "source": [ "First, let's demonstrate the implementation of a matrix-vector multiplication in MapReduce." ] }, { "cell_type": "code", "execution_count": 2, "id": "ffd6e516", "metadata": {}, "outputs": [ { "name": "stderr", "output_type": "stream", "text": [ "WARNING: An illegal reflective access operation has occurred\n", "WARNING: Illegal reflective access by org.apache.spark.unsafe.Platform (file:/usr/local/spark-3.1.2-bin-hadoop3.2/jars/spark-unsafe_2.12-3.1.2.jar) to constructor java.nio.DirectByteBuffer(long,int)\n", "WARNING: Please consider reporting this to the maintainers of org.apache.spark.unsafe.Platform\n", "WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations\n", "WARNING: All illegal access operations will be denied in a future release\n", "22/03/29 13:29:52 WARN NativeCodeLoader: Unable to load native-hadoop library for your platform... using builtin-java classes where applicable\n", "Using Spark's default log4j profile: org/apache/spark/log4j-defaults.properties\n", "Setting default log level to \"WARN\".\n", "To adjust logging level use sc.setLogLevel(newLevel). For SparkR, use setLogLevel(newLevel).\n", "22/03/29 13:29:54 WARN Utils: Service 'SparkUI' could not bind on port 4040. Attempting port 4041.\n" ] } ], "source": [ "sc = SparkContext('local[*]')" ] }, { "cell_type": "markdown", "id": "bd8aaee2", "metadata": {}, "source": [ "Let's load an ilustrative example from Leskovec et al. [*Mining of massive datasets*](http://www.mmds.org/) {cite:ps}`leskovec2020mining` and call it Graph 4." ] }, { "cell_type": "code", "execution_count": 3, "id": "3902a19e", "metadata": {}, "outputs": [ { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAagAAAEYCAYAAAAJeGK1AAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjQuMywgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/MnkTPAAAACXBIWXMAAAsTAAALEwEAmpwYAABG30lEQVR4nO3dd1hTZxsG8DskrASZMlQQBRVFUVTQ4sS9RxUXSnGvqriwKipOnLj3Z0Wtq9pWbcE9UOus1glUEQeKAwERGYGM9/sjJRVlEzhJeH7XlQtCzngSTnLnPec95+UxxhgIIYQQNaPDdQGEEEJIbiigCCGEqCUKKEIIIWqJAooQQohaooAihBCiliigCCGEqCWtD6j58+djyJAhXJehNsLDw2Fra8t1GfkaOnQo5syZw3UZKn+tgoKCMHLkyBIt4/nz5+DxeJBKpSqqqnwYO3YsFi1aVObr3bJlC6ytrWFkZITExMQCp9+1axdatGhRBpUVDtefF2UeUAcPHkTTpk0hEolgZWWFpk2bYvPmzVCX07Hmzp0LFxcXCAQCzJ8/v1jLGDp0KAQCAV6/fl3gtLdu3UL37t1hZmYGU1NTODs7IyAgAB8+fCjWuknx8Xg8PHnyRCXLyu2NPXv2bOzYsUMlyy9PivqFJbcP+a1bt2Lu3LmqLi1fEokEU6dOxenTp5GamgoLC4scj9OXjYKVaUAFBwfDz88P/v7+ePv2Ld69e4etW7fiypUryMrKynUemUxWliWiRo0aWLFiBbp161as+dPS0vDrr7/CxMQE+/bty3faq1evwtPTE82bN8c///yD5ORknDx5EgKBAPfu3ct1HtqYSWGpeluhba9o3r17B7FYjLp163JdiuZiZSQ5OZkJhUL2yy+/5Dudr68vGzt2LOvSpQsTCoXszJkzLDQ0lLm6urIKFSowW1tbFhgYqJz+2bNnDADbtm0bq1SpErOxsWGrVq1SPh4YGMj69evHfHx8mJGREXN2dmZ//fVXgfUOHjw4x3oKa/fu3czW1patXbuW1a1bN99pmzdvziZMmJDvNCEhIaxZs2Zs8uTJzMzMjAUEBLAnT56wNm3aMHNzc2ZhYcG8vb3Zhw8flPPY29uzoKAgVqdOHWZqasqGDh3KMjIyGGOMXbhwgVWpUoWtWrWKWVpaMhsbG7Zz5848179z505Wu3ZtZmRkxKpXr862bt2qfOz9+/esW7duzMTEhJmZmbEWLVowmUyW63ImTZrEbG1tWYUKFVijRo3YpUuX8lynr68vGz9+POvatSszMjJiTZo0YU+ePGGMMTZ+/Hg2derUHNN3796drVmzpsDnzhhj27dvZ46OjszMzIz16NGDxcXFMcYYa9myJQPAhEIhE4lE7ODBgwW+VmKxmE2bNo3Z2dkxKysrNmbMGJaens5SU1OZgYEB4/F4TCQSMZFIxOLi4lhgYCAbPHiwcv7Lly8zDw8PZmJiwmxtbVlISAhjjBVqe5dIJLm+dvb29mzZsmXMxcWF6enpMYlEwq5du6ZcT/369dmFCxeU07du3ZrNnDmTubu7M2NjY9azZ0+WmJiYY107duxgdnZ2rGXLlowxxn788UdWu3ZtZmpqyjp27MieP3/OGGNMLpezyZMnM0tLS2ZsbMxcXFzYgwcP8n2tGMt/m9y2bRsTCARMV1eXiUQi1r17d8YYY0uXLmUODg7MyMiI1alTh/3222+MMcYiIyOZvr4+09HRYSKRiJmYmCi3qYCAgAK3A8YYA8C2bNnCatSowUxNTdn48eOZXC7P9fUWi8XMz8+PVapUiVWqVIn5+fkxsVjMHj16xIRCIQPARCIRa9OmzVfz2tnZKR8XiUTs6tWrLCQkhDVv3pxNmzaNmZqasmrVqrHjx48r50lOTmbDhw9nNjY2rHLlyiwgIIBJpdKvlp2RkcEMDAzY+/fvGWOMLVq0iPH5fPbx40fGGGMBAQHMz8+v0P+bJUuWMAsLC2Zvb8/27t2b62tRGsosoE6cOMH4fH6eb6xsvr6+zNjYmP35559MJpOxjIwMduHCBXb//n0mk8nYvXv3mJWVFTty5Ahj7L830cCBA1lqaiq7f/8+q1ixIjtz5gxjTBFQ+vr6LCwsjEmlUjZz5kzWtGnTAustbkC1bduW+fv7s7dv3zI+n89u376d63SpqalMR0cnx4dFbkJCQhifz2fr169nEomEpaens+joaHb69GkmFotZfHw8a9mypXJjY0zxIVW3bl0WGxvLEhMTWbNmzZRvzgsXLjA+n8/mzp3LsrKyWFhYGDM0NGRJSUm5rj80NJQ9efKEyeVyFh4ezgwNDZXPaebMmWzMmDEsKyuLZWVlsUuXLuX5Rv7pp59YQkICk0gkbNWqVcza2jpHcHzO19eXmZmZsRs3bjCJRMK8vb3ZgAEDGGOM3bhxg1WqVEkZhO/fv2eGhobs7du3BT73c+fOMQsLC3b79m0mFovZhAkTlB+6jCk+mKKjo5X3C3qt/Pz8WI8ePVhiYiJLSUlh3bt3ZzNnzlTOW6VKlRzP6/OAevHiBTMyMmL79+9nWVlZLCEhgd25c0c5b0Hbe34B1aBBAxYbG8vS09PZq1evmLm5OQsLC2MymYydPn2amZubs/j4eMaYIqAqV67MHjx4wFJTU1mfPn2UNWavy8fHh6WmprL09HR25MgR5ujoyCIjI5lEImGLFi1iHh4ejDHGTp48yRo1asQ+fPjA5HI5i4yMZK9fvy7Ua5Xf6/xluDDG2KFDh1hcXByTyWTs4MGDTCgUKteV/SH/5TZVlO2gW7du7MOHD+zFixesYsWK7MSJE7m+3nPnzmVNmzZl7969Y/Hx8czDw4PNmTOnUP+r3B4PCQlhAoGAbd++nUmlUrZ582ZWqVIl5fuqV69ebPTo0Sw1NZW9e/eOubu75/jS+LmWLVsqGwQdOnRgDg4OyrBr2bKlMtQL87+ZMmUKE4vFLDw8nAmFQvbPP//kuk5VK7OA+umnn5i1tXWOv2V/qzMwMGAXL15kjCk2JB8fn3yX5efnxyZPnswY+++fHBUVpXzc39+fDR8+nDGm+FBo166d8rGIiAhmYGBQYL3FCagXL14wHo+n/KDp2LEjmzRpUq7Tvnz5Mte6TUxMmFAoZIsWLWKMKTZYOzu7fNd75MgR5urqqrxvb2/PtmzZorwfFhbGHBwcGGOKDc7AwCDHm8LS0pJdu3atUM+xV69ebO3atYwxxZuzZ8+eOT7UC8vU1JTdvXs318d8fX3ZiBEjctTv5OSkvF+7dm12+vRpxhhjGzZsYF26dFE+lt9zHz58OPP391c+9unTJyYQCNizZ88YY7kHVF6vlVwuZ0KhUNmyY4yxq1evsmrVqinnzS+ggoKCWO/evfN7iZRy297zC6gff/xReX/ZsmVsyJAhOabp2LEj27VrF2NMEVA//PCD8rGIiAimq6vLpFKpcl0xMTHKxzt37sx27NihvC+TyZihoSF7/vw5O3fuHKtZsya7du1ajpZ0YV6r/LbJ3ALqSw0aNGBHjx5ljBUcUIXZDi5fvqx8vF+/fmzp0qW5rtfBwYGFhYUp7588eZLZ29szxoofUI6Ojsr7aWlpDAB78+YNe/v2LdPT01O2bhhjbP/+/czT0zPX5c+ZM4dNnDiRSSQSZm1tzdauXct++OGHHK2rwvxv+Hw+S01NzfF6LFy4MNd1qlqZHYOysLBAQkJCjv3YV69eRXJyMiwsLCCXy5V/t7OzyzHvjRs30KZNG1haWsLExARbt25FQkJCjmk+n8fe3j5HBwUbGxvl70KhEGKxuFT2p//000+oU6cOXF1dAQCDBw/G/v37IZFIvprWzMwMOjo6ePPmjfJvK1asQHJyMr799tsc9X35esTHx2PgwIGoUqUKjI2NMWTIkCK9HhYWFhAIBMr7QqEQqampuT6nEydO4JtvvoG5uTlMTU1x/Phx5br8/f1Ro0YNdOzYEQ4ODli2bFmer01wcDDq1KkDExMTmJqa4uPHj1/V/Lkv/2ef1+fr64u9e/cCAPbu3QsfH59CPffXr1/D3t5e+ZiRkREsLCwQFxeXZx15vVbv379Heno6GjduDFNTU5iamqJz5854//59nsv63MuXL+Ho6JjrY4XZ3vPz+fN/8eIFDh8+rKzR1NQUf/75Z47t7svXSyKR5Fjfl8vz8/NTLsvc3ByMMcTFxaFt27aYMGECvv/+e1hbW2P06NFISUkp1GtVlG0SAPbs2QNXV1fl8h4+fFjo16gw20F+219+y/ryvVYcX64bAFJTU/HixQtIJBJUqlRJ+bzHjBmD+Pj4XJfTunVrhIeH4++//4aLiws6dOiAixcv4vr166hRowYqVqxYqP+NmZkZRCKRSp9jYZVZQHl4eEBfXx/Hjh0rcFoej5fjvre3N3r27ImXL1/i48ePGDt27Fe9/l6+fKn8PTY2FpUrV1ZN4UWwZ88ePH36FDY2NrCxscHUqVORkJCAEydOfDWtSCRC06ZN8dtvvxW43C9fj1mzZoHH4+H+/ftISUnB3r17S+X1yMzMRN++fTF9+nS8e/cOycnJ6Nq1q3JdFSpUQHBwMJ4+fYo//vgDq1evxrlz575azuXLl7F8+XIcOnQIHz58QHJyMkxMTIrdc3PIkCE4duwY7t27h6ioKPTu3TvH43k998qVK+PFixfKx9LS0pCYmIgqVaoUuYaKFSvC0NAQERERSE5ORnJyMj5+/Kj8IPvyf/YlOzs7xMTE5PpYYbb3/Hy+bjs7O/j4+ChrTE5ORlpaGmbOnKmc5svXS1dXFxUrVsxzedu2bcuxvIyMDDRr1gwAMGnSJNy+fRsRERF4/PgxVq5cWeBrVZTnAyhCctSoUdi4cSMSExORnJyMevXqKV+jgl57VW4HXy6rKO+1gur8kp2dHfT19ZGQkKB8HVNSUhAREZHr9M2aNcOjR49w5MgRtG7dGs7OzoiNjUVYWBhat24NoODtGAA+fPiAtLS0Yj3HkiqzgDI1NUVgYCDGjx+PX375BampqZDL5bh7926OJ5+bT58+wdzcHAYGBrh58yb279//1TSLFi1Ceno6IiIiEBISggEDBhSrTolEArFYDLlcDqlUCrFYXKiehNeuXUNMTAxu3ryJu3fv4u7du3j48CG8vb2xe/fuXOdZsWIFdu7ciWXLlim/Bb169QrPnj3Ld12fPn2CkZERTE1NERcXh5UrV341zaZNm/Dq1SskJSUhKCioWK9HVlYWMjMzYWlpCYFAgBMnTuD06dPKx0NDQ/HkyRMwxmBsbAw+nw8+n59rvQKBAJaWlpBKpVi4cCFSUlKKXE82W1tbuLu7w8fHB3379oWhoWGOx/N67t7e3ggJCcHdu3eRmZmJ2bNno2nTpqhWrRoAwNraGk+fPi1UDTo6Ohg1ahSmTJmi/N/FxcXh1KlTymUlJibi48ePuc4/ePBgnD17FocOHYJUKkViYiLu3r0LoHDbe2ENGTIEf/zxB06dOgWZTAaxWIzw8HC8evVKOc3evXsRGRmJ9PR0zJs3D15eXrn+HwHF+URLly5Vfih+/PgRhw8fBgD89ddfuHHjBiQSCUQiEQwMDMDn8wt8rQry5f8lLS0NPB4PlpaWAICQkBA8fPgwx/SvXr3Ks2dwQdtBUQwaNAiLFy/G+/fvkZCQgIULFxb6vEtLS0vo6OgUepurVKkSOnbsiGnTpiElJQVyuRwxMTG4ePFirtMLhUI0btwYmzZtUgZSs2bNsG3bNuX9wv5vAgMDkZWVhcuXLyM0NBT9+vUrVM0lVabdzGfMmIHVq1djxYoVsLKygrW1NcaMGYPly5crv4HlZvPmzZg3bx4qVKiAhQsXon///l9N07p1a9SoUQPt2rXD9OnT0bFjx2LVOGrUKBgaGuLAgQNYsmQJDA0N8dNPPwFQtASMjIxynW/37t3o1asXXFxclC0oGxsb+Pn5ITQ0FElJSV/N06JFC5w/fx6XLl1CrVq1lM1rT09PTJw4Mc8aAwMD8ffff8PExATdunVDnz59vprG29tbuevNwcGhWCe+VqhQAevXr0f//v1hZmaG/fv3o2fPnsrHo6Oj0b59exgZGcHDwwPjx4+Hp6fnV8vp1KkTunTpglq1asHe3h4GBgZf7bYsKl9fXzx48OCr3XtA3s+9Xbt2WLRoEfr27YtKlSohJiYGBw8eVM43f/58+Pr6wtTUFIcOHSqwhuXLl6NGjRr45ptvYGxsjPbt2+PRo0cAgNq1a2PQoEFwcHCAqanpV7tEqlatiuPHjyM4OBjm5uZwdXVVnlpQmO29sOzs7HDs2DEEBQXB0tISdnZ2WLlyZY5d6j4+Phg6dChsbGwgFouxfv36PJf37bff4ocffsDAgQNhbGyMevXqKfcQpKSkYNSoUTAzM4O9vT0sLCwwffr0Al+rgowYMQKRkZEwNTVF79694ezsjGnTpsHDwwPW1tZ48OABmjdvrpy+bdu2qFu3LmxsbHK0BLMVtB0UxZw5c+Dm5ob69evDxcUFjRo1KvR7TSgUIiAgAM2bN4epqSmuX79e4Dx79uxBVlYWnJ2dYWZmBi8vrxy7a7/UunVrSCQSNGnSRHn/06dPaNWqlXKagv43NjY2MDMzQ+XKlTF48GBs3boVtWvXLtRzLCkeK+5+FjXx/PlzVK9eHRKJJMc+7PKsWrVq2LFjB9q3b891KaXm0qVLGDJkCJ4/fw4dnf++Z5WH565Knp6eGDJkSImvcEFIadD6Sx0R7SORSLBu3TqMHDkyRzgRQrQLvbuJRomKioKpqSnevHmDyZMnc10OIaQUafwuPkIIIdqJWlCEEELUEgUUIYQQtUQBRQghRC1RQBFCCFFLFFCEEELUEgUUIYQQtUQBRQghRC1RQBFCCFFLFFCEEELUEgUUIYQQtUQBRQghRC1pxvgUcimQ9hyQiQG+ASCqBuhoRumEEEKKR30/5TMTgZidwNMQIDUG0NEFwAcgA+RZgFENwGEY4DgC0DfnulpCCCEqpn5XM5dlAQ8WAI9WA+ABsoy8p+UbAmCA01TAJRDg65VVlYQQQkqZegVUWixwvj2QHgfI0gs/H18ICKsAbc8CoqqlVx8hhJAyoz4BlRYLnHQDspIAJiv6/Dw+oGcOdL5FIUUIIVpAPXrxybIULafihhOgmC8rSbEcuUS19RFCCClz6hFQDxYodusVN5yyMZliOQ8WqKYuQgghnOF+F19mInDUVtGFPA9XHgHL/gCuRgNpmUAVM6CrKxA8GNDLrR8i3wDoHUe9+wghRINx34KK2QmAl+fDB68BrRcDoXcAO3PApzngYAVsPQekZ+Y1Fw+I+bE0qiWEEFJGuG9BhToDKVG5PpSeCdhNApJSgSHNgd1jAZ1/IzXmHWBnkUcLCgCMnYHuEaVTMyGEkFLH7Ym6cqniJNw8XHmsCCcAmNP7v3ACAEfrApad+kSxfLriBCGEaCRud/GlPf/3ChG5i0/573f7ikVcNk9XsXxCCCEaiduAkomhuHxR7qyM//v9RUIRl83j59vxghBCiHrjNqD4BgDy7lrerCZgJlL8vvgoIJf/99iL94BEms+ymezf5RNCCNFE3HaSkEuBQyLFxV/zsO8K8N0WQM6ABlWBJo7A6w/AmYfAu82AqSiPGXX0gP5pdAyKEEI0FLef3joCwMgxz158ADC4uaJ7+fJQ4Fo0EPUasDUHRrUBhPr5LNuoBoUTIYRoMO4/wR2GAQ8C871qeas6ilthyXUMoOMwTAXFEUII4Qr350FlJgFHq6i0Q0NGFmA/mQ8Z3wS6urrg8f47ETj7dwMDA1y4cAH29vYqWy8hhBDV4b4FpW+uGM/p0dqiDbGRF74QMXod8P7jMQBJeU5mZWWFypUrl3x9hBBCSgX3lzoCFIMNCqsouoaXBI8PCKug3sDDWLlyJQwMcu/FZ2RkhCVLlkBXN+9zsAghhHCL+1182VQ8HhRjDB07dsSlS5eQlZWzl6CFhQXevHlDAUUIIWpMPVpQgGKQwc63ACMHxQi5RcEXKub7bLBCHo+Hn3/+GSYmJjkm1dHRQWJiIjw8PPDw4UNVVU8IIUTF1CegAEW4dH0IOE1WnGTLN8x/er4QUqaLrReFiHM9/dVIuubm5vj9999haPjfcqysrHDz5k1IpVLUr18fbm5uiIigi8oSQoi6Ua+AAgC+HuC6RDGek8sCxVXJdfQAvggQGCt+6ugp/u6yAEd5GzFuSwJq1KqDjRs3Qv755SYAfPPNNwgMDIRQKIRIJEJQUBDc3d1x9+5d3Lx5ExKJBC4uLnB3d6egIoQQNaI+x6DyI5cqLvwqEytaVqJqypNwr1y5gg4dOiAjIwMikQg1atTA/v374ezsrJydMYb27dsjKioKsbGxEAhydl68desWhg8fjocPH8LNzQ27du3KMT8hhJCyp34tqNzoCIAKNQDTeoqfn10homLFisrASUtLw/379+Hm5oY5c+YgM1MxoiGPx8OxY8dw7dq1r8IJANzc3HD//n3cuHEDYrEY9erVQ9OmTREVlfcVLgghhJQuzQiofFhYWOTopccYQ0ZGBtasWYNatWrhypUrABRdyws6Kdfd3R3379/HtWvXkJ6ejrp16+Kbb77Bo0ePSvU5EEII+Zpm7OLLh0wmg66uLvJ6GgKBAAkJCV/15iuMGzduYMSIEYiMjETTpk2xa9cuODk5lbRkQgghhaDxLSg+n5+jl142kUiE+vXr46+//ipWOAFA06ZN8fDhQ1y5cgUpKSmoU6cOmjVrhujo6JKWTQghpAAaH1AAcgSQQCAAn8/HunXrcOfOHbi6upZ4+R4eHoiIiMDly5eRnJwMJycnNG/enIKKEEJKkVYElJmZGQDA0NAQw4YNg7u7O6RSKXR0VPv0mjdvjsjISFy+fBlJSUlwcnJCixYtEBMTo9L1EEII0ZKAcnBwQIMGDXD16lVs374d27Ztw7x585CQUNRx4gunefPmiIqKwqVLl5CYmIiaNWuiZcuWFFSEEKJCGt9JAgCkUin4fH6OYTX8/PyQkZGB7du3l/r6L126hNGjR+Px48do0aIFdu/ejerVq5f6egkhRJtpRQtKIBDkCCcAWLBgAUJDQ3Hz5s1SX3+rVq3wzz//4Pz583j37h0cHR3RunVrPHv2rNTXTQgh2korAio3pqamWLZsGb7//nvIZMW4OnoxeHp64tGjRzh//jzevHkDR0dHeHp64sWLF2WyfkII0SZaG1AA4OPjA319ffz4449lul5PT088fvwYZ8+exevXr1G9enW0adOGgooQQopAK45B5efevXvo2LEjIiMjYWFhwUkN586dw9ixYxETEwNPT0/s2rULVatWLXhGQggpx7S6BQUADRo0wIABAzB79mzOamjXrh2io6Nx5swZxMbGolq1amjbti1iY2M5q4kQQtSd1regACA5ORl16tTB77//Dnd3d67LwZkzZzB27Fg8e/YMbdq0we7du2Fra8t1WYQQola0vgUF5Oww8eV4UVzo0KEDYmJicOLECTx//hxVq1ZF+/bt8erVK65LI4QQtVEuAgpQdJjQ1dUt8w4T+enUqRNiYmIQFhaGp0+fomrVqujQoQMFFSGEoJzs4st29+5ddOrUidMOE/k5fvw4vv/+e7x48QLt27fHrl27ULlyZa7LIoQQTpSbFhQAuLq6on///ggICOC6lFx17doVz549Q2hoKB4/fgxbW1t06tQJr1+/5ro0Qggpc+WqBQX812Hijz/+gJubG9fl5Cs0NBQTJkxAbGwsOnbsiF27dsHGxobrsgghpEyUqxYUoOgwsXTpUrXpMJGf7t274/nz5zh27BiioqJQuXJldOnSBW/fvuW6NEIIKXXlLqAA4LvvvgOfz8fOnTu5LqVQevTogRcvXuDo0aOIiIhA5cqV0bVrV8THx3NdGiGElJpyt4sv2507d9ClSxdERkbC3Nyc63KK5OjRo5g0aRLi4uLQuXNnhISEwMrKiuuyCCFEpcplCwoAGjZsCC8vL7XtMJGf3r17IzY2Fr/88gvu37+PSpUqoXv37tSiIoRolXLbggKADx8+wNnZGaGhoWjcuDHX5RTbr7/+Cj8/P7x58wZdu3ZFSEgIKlasyHVZhBBSIuW2BQUohooPCgrSiA4T+enbty9evXqFQ4cO4c6dO7C2tkavXr1KbURhQggpC+U6oADA19cXPB4PISEhXJdSYtlBdfDgQdy6dQvW1tbo3bs3EhMTuS6NEEKKrFzv4sv2999/o2vXrhrZYSI/P//8M6ZMmYJ3796hZ8+e+PHHH7Xq+RFCtFu5b0EBQKNGjdC3b1/MmTOH61JUasCAAXj9+jX27duHGzduwNLSEn369EFSUhLXpRFCSIGoBfWvDx8+oE6dOggLC9PoDhP5OXDgAKZOnYr4+Hj07t0bO3bsgJmZGddlEUJIrqgF9S9t6TCRn0GDBuHNmzfYs2cPrl69iooVK8LLywvJyclcl0YIIV+hgPrM0KFDAQC7du3itI7SNnjwYLx58wa7d+/Gn3/+CQsLC/Tr14+CihCiVmgX3xeyO0xERUWVm91fP/30E6ZPn46EhAT07dsX27dvh6mpKddlEULKOQqoXIwfPx48Hg+bNm3iupQytXv3bsyYMQOJiYnw8vLC9u3bYWxszHVZhJByigIqF0lJSXB2dsbx48fRqFEjrsspc7t374a/vz+SkpLQr18/bNu2jYKKEFLm6BhULszNzbFkyRKt7jCRH19fX8THx+N///sfzp07B3Nzc3h7eyMlJYXr0ggh5QgFVB6GDRsGxhh2797NdSmcGTZsGOLj47Ft2zacOXMG5ubmGDx4MFJTU7kujRBSDtAuvnzcvn0b3bp1K1cdJvKzY8cOzJw5E8nJyRg4cCC2bt0KIyMjrssihGgpCqgCjBs3Dnw+Hxs3buS6FLWxfft2zJ49G8nJyfD29sbmzZspqAghKkcBVYDsDhMnTpxAw4YNuS5HrWzbtg2zZ89GSkoKvL29sWXLFgiFQq7LIoRoCToGVQBzc3MsXry43HaYyM+YMWOQmJiI9evXIzQ0FCYmJvD19UV6ejrXpRFCtAAFVCEMHz4cMpkMe/bs4boUtTRu3DgkJiZi3bp1yqAaNmwYBRUhpERoF18h3bp1Cz169EBUVBRdZaEAGzduxLx58/Dp0yf4+Phg48aNtOuPEFJkFFBFMHbsWOjq6mLDhg1cl6IRNmzYgHnz5iE1NRXfffcdNm3aBAMDA67LIoRoCAqoIkhMTISzszNOnToFV1dXrsvRGOvWrcP8+fORmpoKX19fbNy4kYKKEFIgOgZVBBYWFtRhohj8/Pzw4cMHrFy5Er/88guMjY0xevRoiMVirksjhKgxCqgiGjFiBCQSCX766SeuS9E4kydPRnJyMpYvX46ff/4ZxsbGGDNmDAUVISRXtIuvGP766y/07NmTOkyUgFwux9q1a7FgwQJkZGRg+PDhWLt2Le36I4QoUUAV05gxY6Cvr4/169dzXYpGk8vlWLNmDRYuXIiMjAyMGDEC69atg56eHtelEUI4RgFVTNkdJk6fPo0GDRpwXY7Gk8vlCA4OxqJFi5CZmYkRI0Zg7dq1FFSElGMUUCWwfft27NmzB5cvXwaPx+O6HK0gl8uxatUqLF68GJmZmRg5ciTWrFlDQUVIOUSdJEpgxIgRyMzMpA4TKqSjo4MZM2YgOTkZCxYswJ49e1ChQgVMnDgRWVlZXJdHCClD1IIqIeowUbrkcjmWL1+OoKAgZGVlYcyYMVi1ahW1qAgpByigVGD06NEwNDTEunXruC5Fa8nlcixduhRLly6FVCrFmDFjEBwcDIFAwHVphJBSQgGlAgkJCahbty51mCgDcrkcQUFBWLZsGaRSKcaNG4eVK1dSUBGihSigVGTbtm3Yu3cvLl26RB0myoBcLsfixYuxYsUKSKVSjB8/HitWrKCgIkSLUCcJFRk5ciQyMjKwd+9erkspF3R0dDBv3jykpKRg1qxZ2LZtG4yMjDBt2jRIpVKuyyOEqAC1oFTo5s2b6N27N6KiomBiYsJ1OeWKXC7HwoULsXLlSsjlckyYMAFLly6lFhUhGowCSsVGjRoFkUiEtWvXcl1KuSSXyzF//nwEBwdDLpdj4sSJCAoKoqAiRANRQKlYdoeJM2fOoH79+lyXU27J5XIEBgYiODgYjDFMmjQJS5cuhY4O7dUmRFNQQJWCrVu3Yt++fdRhQg3I5XLMnTsXa9asAaAY+mPJkiUUVIRoAHqXloJRo0YhPT0d+/bt47qUck9HRwdLlixBamoqJk+ejHXr1sHIyAizZ8+mMb0IUXPUgiolN27cwLfffksdJtSMXC5HQEAA1q5dCx6PhylTpmDRokXUoiJEDVFAlaKRI0eiQoUKyt1LRH1IpVIEBARg/fr14PF4mDZtGhYsWEBBRYgaoYAqRe/fv0fdunVx7tw5uLi4cF0OyYVUKsXs2bOxYcMG6OjoYNq0aZg/fz4FFSFqgAKqlG3ZsgUHDhzAxYsXqcOEGpNKpZg1axY2btwIHR0d+Pv7Y968eRRUhHCI3n2lbPTo0UhLS8P+/fu5LoXkQyAQYOXKlfj06RPGjh2LZcuWwdjYGAsWLKDOFIRwhFpQZeD69evo27cvoqKiYGxszHU5pBCkUilmzJiBzZs3QyAQYMaMGZgzZ06eLaro6GjI5XI4OTmVcaWEaC8KqDIyYsQImJiYYPXq1VyXQopAKpXC398fW7ZsgUAgwMyZMzF79uwcQcUYQ/369fH27Vs8evQI5ubmHFZMiPaggCoj2R0mzp8/j3r16nFdDikiqVSKadOmYevWrdDT08PMmTMxa9Ys6Ojo4NSpU+jbty8kEglatGiBs2fPFu14o1wKpD0HZGKAbwCIqgE6dGkmQiigytDmzZvx888/Izw8nDpMaKisrCz4+/srg2rWrFnYv38/IiIiAABCoRCBgYGYMWNG/gvKTARidgJPQ4DUGEBHFwAfgAyQZwFGNQCHYYDjCECfWmSkfKKAKkMymQzu7u6YPn06vL29uS6HlEBWVhamT5+OLVu2fDW8h6GhIS5cuICmTZt+PaMsC3iwAHi0GgAPkGXkvRK+IQAGOE0FXAIBPg1zT8oXCqgydu3aNXh5eVGHCS3AGEPdunURFRX11WOWlpZ49OgRzMzM/vtjWixwvj2QHgfI0gu/Ir4QEFYB2p4FRFVVUDkhmoG6mZcxDw8PdOrUCQsWLOC6FFJCJ0+eRGxsbK6PJSUloX///lB+/0uLBU66AalPixZOgGL61KeK+dNyXx8h2ohaUByIj49HvXr1qMOEBsuv9fS5Xr164cgvP4N3wkURMkxW/JXy+ICRA9At4t9jVoRoNwoojmzatAmHDx/GhQsXqMOEBpLJZOjRoweSkpIAAJ+/jRhjkMvliI2NRUpKCn6Z64TuNZ4UveWUG74QqD0FaLC45MsiRM1RQHFEJpPBzc0NM2bMwKBBg7guh5QSado78P+wB0+emec0jAHVJwMvEhT3I1cAdarks1C+AdA7jnr3Ea1Hx6A4wufzsWnTJkyfPh0pKSlcl0NKieDFHvB4+b/NLv3zXzgBwE9/FrRUHhDzY4lrI0TdUUBxqFmzZujYsSMWLlzIdSmktDwNyb8rOYC9/wZSw2qKn/uvKlpVeZJlAE93qaI6QtQaBRTHli9fjj179ihP9CRaRC5VnISbj0wJ8MtNxe/B3oCZSNGauvRPActOfaJYPiFajAKKY1ZWVpg3bx4mTJgAOhyoZdKeF9jbLvQOkJwOWBkDresA3Rsq/r63oN18PF3F8gnRYhRQamDs2LH48OEDfv75Z65LIaokE0Nx+aK87b2i+NmjEaCjA3zrprh/+KaidZUnHv/f5ROivagXn5q4cuUKBgwYgKioKFSoUIHrcogqfHoCnHAFpGm5PvwhDbAZD2Tlsafu8CTAK5erJQEA+CKg612gQg1VVEqIWqIWlJpo3rw52rdvTx0mtImoGiDPuxl06LoinIwNgV6N/7vVtFE8nm9vPiZRLJ8QLUYtKDXy7t071KtXDxcvXoSzszPX5RBVCHUGUnK/2kSrhcDlR4B/N2DFZ9cOvhgFeC4GdPnAm02ARW4NamNnoDt1rCHajQJKzWzYsAFHjhzBuXPn6AoT2iByJfAgsMCu5kXCNwRcFgLO01W3TELUEO3iUzPjxo1DUlISDh06xHUpRBUcRwBQ7XdAxhjgOFylyyREHVELSg1RhwktczcAeLRWJdfiy5DoYP1pPqJ0vdGmTRs4OTmhVq1aNMw80UoUUGrK19cX1tbWWLFiBdelkJKSZQHH66nkauZMVB0mg1/hU6oYurq6MDQ0hFgshp6eHuzt7VG3bl24urqiU6dOaNSokeqeAyEcoIBSU9kdJi5duoQ6depwXQ4pqezxoLKSihdSPD6gZw50voXzN56gS5cuyMrKynVSPp+P0aNHY/PmzSUsmhBuUUCpsfXr1+PYsWM4e/YsdZjQBv+OqCv9FAsB8r66+VdyGVG3RYsWuHr1aq5XH7G2tkZ0dDTtHiYajzpJqLHx48cjISGBOkxoC1FViNvdwubzepDz9BS98fLDFyqG1qg9RTFI4WfDvW/cuBEGBgZfzWJoaIjffvuNwoloBQooNSYQCJRDcqSmpnJdDlGBzVt34Nz7NtDp8wZwWaA4n0lHT3FlCIGx4qeOnuLvLgsU4z41WPzVNf2yjzPx+TkvpSSRSJCWlvuVKwjRNLSLTwN89913qFSpEpYvX851KaQEUlJSULNmTZw7dw716tX77wG5VHHhV5lY0WISVQN0BAUu7+nTp6hbty7EYjF4PB5q166N2rVr4+jRoxgyZAh27doFHR36Dko0FwWUBnj79i1cXFyow4SGCwwMxLNnz7Bnzx6VLXPMmDHYuXMn9PT0cOfOHdSqVQvHjh3DwIEDYWpqivPnz9M2QzQWBZSGWLduHf744w+cOXOGOkxooPj4eNSpUwe3bt1C9erVVbbc9+/fw97eHqtWrcL48eOVf09JSUGHDh1w69YtBAYGYt68eSpbJyFlhQJKQ0ilUjRq1Ahz585Fv379uC6HFNHkyZMhk8mwYcMGlS87MTER5ubmuX5xWbt2LaZPnw5nZ2ecP38eFStWVPn6CSktFFAa5PLly/D29kZUVBSMjIy4LocU0osXL9CoUSNERkbC2tqak/W3bt0ab968wc6dOzF48OAyr4GQ4qAjqBqkZcuW8PT0xOLFi7kuhRTB/PnzMW7cOE7CCQDs7e3x/PlzjBw5Ej4+Pvme5EuIOqEWlIbJ7jBx+fJl1K5dm+tySAEiIyPh6emJx48fw9TUlOtycOXKFXTr1g2MMYSFhaFFixZcl0RInqgFpWFsbGwQEBCAiRMn5noVAaJe5syZA39/f7UIJ0AxMGZ8fDyaN2+OVq1aYdy4cZDL5VyXRUiuqAWlgaRSKRo2bIjAwEB4eXlxXQ7Jw82bN9GnTx9ER0fD0LCAq0Zw4MCBAxg6dChsbGwQHh6u0t6FhKgCtaA0UPYVJqZOnUpXmFBjs2bNwrx589QynABg0KBBePPmDUxNTVGzZk0EBwdzXRIhOVBAaahWrVqhVatWWLJkCdelkFycPXsWL1++xLBhw7guJV/m5ua4d+8e5s+fjxkzZsDd3R0pKSlcl0UIANrFp9HevHmD+vXr488//4STkxPX5ZB/McbQpEkTTJ8+HQMGDOC6nEJ79OgR2rRpgw8fPmD//v349ttvuS6JlHPUgtJglSpVwuzZs6nDhJr57bffIJPJNO6EaicnJ7x69QoDBw5E37590adPH0ilUq7LIuUYtaA0nEQiQcOGDbFgwQL07duX63LKPalUinr16mHt2rXo3Lkz1+UU2/nz59GrVy/o6+vj9OnTNDov4QS1oDScrq4uNm3ahClTptAwC2pgz549sLGxQadOnbgupUTatm2L9+/fw8XFBW5ubvD39+e6JFIOUQtKSwwePBj29vYICgriupRySywWo1atWvj555/h4eHBdTkqs2PHDowbNw7VqlVDeHg4qlSpwnVJpJygFpSWWLlyJbZv345Hjx5xXUq5tXnzZjRs2FCrwgkARo4ciZcvX4LP56NatWrYunUr1yWRcoJaUFpk9erVOHXqFE6ePElDcpSxPAcj1DKzZs3CihUr0KxZM5w6dQpCoZDrkogWoxaUFpk4cSLi4uJw5MgRrkspd4KDg9GpUyetDicAWLp0KW7fvo1//vkHVlZWOHXqFNclES1GLSgtEx4eDl9fX0RGRkIkEnFdTrlQWoMRqjO5XI6BAwfil19+gbe3N/bs2UPDyxOVo4DSQt7e3qhevTpdZaKMlOZghOouNDQU/fv3h7GxMc6fPw9nZ2euSyJahAJKC71+/Rr169fH1atXUatWLa7L0WpcD0aoDlJTU9GhQwfcvHkTc+fOxfz587kuiWgJCigtFRwcjDNnzuDEiRPUYaIUDRs2DFWqVKFBJAFs2LABU6ZMQe3atREeHk7Dy5MSo53GWmrSpEl4+fIljh49ynUpWisyMhJhYWF0Euu/Jk6ciJiYGKSlpaFKlSrYu3cv1yURDUcBpaV0dXWxceNGTJ48Genp6VyXo5WyByM0MTHhuhS1YW9vj2fPnmH06NH47rvv0KlTJxpenhQb7eLTcoMGDYKjoyPtglIxdR+MUB1cv34dXbp0gVwup+HlSbFQQGm5uLg4NGjQANeuXUPNmjW5LkdrtGvXDgMGDMDo0aO5LkWtSaVS9O7dG8ePH8fo0aOxefNm6o5OCo22FC1XpUoVzJw5E5MmTaIhOVREUwYjVAcCgQChoaE4cOAAdu3ahWrVqiEmJobrsoiGoIAqB/z8/PDixQscO3aM61I0HmMMs2bNwqJFi6Crq8t1ORpjwIABeP36NSwsLODk5IRVq1ZxXRLRABRQ5QB1mFAdTR2MUB2Ym5vjzp07WLRoEX744Qe4ubnR8PIkX3QMqhwZOHAgatasiUWLFnFdikbKHoxw3bp1Gj/eE9eio6Ph6emJpKQk7Nu3D3369OG6JKKGqAVVjgQHB2PLli2Ijo7muhSNlD0YYceOHbkuRePVrFkTL1++xKBBg+Dl5YVvv/2WhpcnX6EWVDmzcuVKXLhwAWFhYXSFiSLQ1sEI1UH28PJ6eno4deoU3NzcuC6JqAlqQZUzfn5+ePbsGX7//XeuS9EoW7Zs0crBCNVB9vDyrq6uaNKkCaZNm8Z1SURNUAuqHDp37hxGjhyJiIgIGnCuEMrLYITqICQkBGPGjEHVqlURHh4OW1tbrksiHKIWVDnUrl07NGnSBMuWLeO6FI1QXgYjVAfDhg1DbGwsdHV1Ub16dWzevJnrkgiHqAVVTr169Qqurq64fv06atSowXU5aqs8DkaoLgICArBs2TJ4eHjg9OnT1NovhyigyrEVK1bg4sWLCA0NpQ4TeSjPgxGqg/v376N9+/ZIS0vDb7/9Rt37yxkKqHIsKysLDRo0wPLly9GzZ0+uy1E7NBihepDL5fD29sahQ4doePlyhgKqnDt79ixGjRqFyMhIuir3F4YNGwZbW1s6sVlNhIWFoV+/fjA2Nsa5c+dQt25drksipYy+hpRz7du3h7u7O3WY+EL2YITTp0/nuhTyr27duiE+Ph6Ojo6oX78+AgMDuS6JlDJqQRFlh4kbN27A0dGR63LUQp8+fdCsWTMKKDWVfW1JJycnXLhwAVZWVlyXREoBtaAIbG1t4e/vDz8/P65LUQs3b97EzZs38f3333NdCsnDhAkT8PTpU2RkZMDW1hZ79uzhuiRSCiigCABgypQpePLkCf744w+uS+HcrFmzEBgYSMfk1FzVqlXx9OlTjB8/HkOHDkWHDh1oeHktQ7v4iNKZM2cwZswYRERElNsP57Nnz2L8+PGIjIyEQCDguhxSSH/99Rc6deoEqVSK0NBQtGrViuuSiApQC4oodejQAY0bN8by5cu5LoUT2YMRLl68mMJJw7i7uyM+Ph6enp7w9PTE6NGjIZfLuS6LlBC1oEgOL1++hKurK27evFnuOkz8+uuvWLJkCW7dukXn2Wiww4cPw8fHB5aWlggPDy9327E2oXchycHOzg7+/v6YPHky16WUKalUioCAACxdupTCScP169cPb9++haWlJZycnLBixQquSyLFRO9E8pWpU6fi8ePH5arDBA1GqF1MTU3x999/Y8mSJZg9ezYaN26M5ORkrssiRUS7+EiuTp8+jbFjx5aLDhM0GKF2e/LkCTw9PZGQkIB9+/ahb9++XJdEColaUCRXHTt2RKNGjcrF7pHNmzejUaNGFE5aqkaNGoiNjcV3332Hfv36oVevXjS8vIagFhTJU2xsLBo2bIi//voLDg4OXJdTKmgwwvLl4sWL6NGjBwQCAU6dOgV3d3euSyL5oBYUyVPVqlUxffp0re4wERwcjM6dO1M4lROtW7dGfHw8GjdujKZNm2LKlClcl0TyQS0okq/MzEy4uLhg9erV6N69O9flqFT2YIS3b99GtWrVuC6HlLHdu3dj1KhRsLOzQ3h4OOzs7LguiXyBWlAkX/r6+tiwYQP8/PwgFou5LkelgoKCMHjwYAqncsrX1xevXr2CgYEBHBwcsGnTJq5LIl+gFhQplL59+6JBgwaYN28e16WoBA1GSD43d+5cBAUF4ZtvvsGpU6dgZGTEdUkEFFCkkLI7TNy6dQvVq1fnupwSo8EIyZcePnyIdu3aITU1FYcPH0bXrl25Lqnco4AihRYUFIQbN27g2LFjXJdSIpGRkfD09ER0dDRMTEy4LoeoEblcjiFDhuDgwYMYMGAA9u3bR1cW4RAFFCm07A4Ta9asQbdu3bgup9hoMEJSkBMnTsDLywtGRkZ0CgKH6KsBKTR9fX2sX79eoztM3LhxA3/99RcNRkjy1aVLF8THx6NmzZpo0KAB5s6dy3VJ5RK1oEiR9enTBw0bNtS4Ny1jDO3atcOgQYMwatQorsshGmLz5s3w8/NDzZo1ER4eTsPLlyEKKFJk2T3gNK3DxJkzZzBhwgRERETQeE+kSGJjY9GmTRu8fPkS//vf/+Dr68t1SeUC7eIjRWZvb4+pU6dq1Fn42YMRLlq0iMKJFFnVqlURExOD77//HsOGDUP79u01dje3JqGAIsUyffp0RERE4Pjx41yXUii//vorGGPw8vLiuhSiwdasWYMbN27g77//hpWVFcLDw7kuSatRQJFiyb7CxKRJk9T+m6RUKsWcOXMQFBREXYZJiWUPL9+2bVu0bdsWI0eOpOHlSwm9W0mxde7cGS4uLli1ahXXpeRr9+7dqFSpEg1GSFRGIBDg6NGjOHz4MPbu3YuqVasiOjqa67K0DnWSICXy/PlzNG7cWG0vuJo9GOGhQ4fwzTffcF0O0ULJyclo164d7t69i8WLF2PWrFlcl6Q1qAVFSqRatWqYMmWK2naYyB6MkMKJlBZTU1Pcvn0bS5cuxdy5c9GwYUMaXl5FqAVFSkwsFqNevXrYsGEDunTpwnU5StmDEZ4/fx5169bluhxSDsTExMDT0xPv37/Hnj170L9/f65L0mjUgiIlZmBgoOwwkZmZyXU5StmDEVI4kbLi6OiIFy9e4LvvvsPAgQPRo0cPGl6+BKgFRVSmd+/ecHd3R0BAANel0GCEhHOXLl1C9+7dwefzcfLkSTRt2pTrkjQOBRRRmewOE3///Tfs7e05rWXy5MmQy+VYv349p3WQ8i0zMxPdu3fHuXPnMHHiRKxbt47rkjQKBRRRqUWLFuHOnTv47bffOKuBBiMk6iZ7eHlbW1uEh4ejatWqXJekEegYFFEpf39/3L9/HydPnuSshvnz52P8+PEUTkRtZA8vb2hoCAcHB2zYsIHrkjQCtaCIyoWFhWHy5Ml4+PAh9PX1y3TdNBghUXeBgYFYvHgxmjRpgjNnztDw8vmgFhRRuW7dusHZ2RnBwcFlvu45c+ZgxowZFE5EbS1YsAD37t3Ds2fPYGVlhdDQUK5LUlvUgiKl4tmzZ3BzcyvTDhM3btyAl5cXHj9+DENDwzJZJyHFJZfL4ePjgwMHDsDLywsHDx6ka0V+gQKKlJqFCxfi3r17+PXXX0t9XdmDEXp7e2PkyJGlvj5CVCV7eHmRSISzZ8+ifv36XJekNiiuSamZMWMG7t69i1OnTpX6us6ePYu4uDgMHTq01NdFiCp16dIF79+/h5OTExo2bIjZs2dzXZLaoBYUKVVhYWGYMmUKHjx4UGodJhhjcHd3xw8//IB+/fqVyjoIKQtbtmzBpEmT4OjoiPDwcNjY2HBdEqeoBUVKVbdu3VC7dm2sXr261NaRPRhh3759S20dhJSFcePG4dmzZ5BKpahatSp+/PFHrkviFAUUKXVr167FqlWrEBsbW+JlvX37FhkZGcr72YMRLl26lA4wE61ga2uLJ0+eYOLEiRg1ahTatm371aCgGRkZaNmyJW7dusVRlWWD3tGk1Dk4OGDSpEmYOnVqiZfVv39/VKlSBVu3boVEIlEORtihQwcVVEqI+ggODsbNmzdx7949WFpa4vz588rH/Pz8cO3aNYwdOxbafJSGjkGRMpGRkYG6deti69atJRrZ1tXVFffu3YNIJEKFChWQmZmJ0NBQNGvWTIXVEqI+pFIp+vXrh2PHjsHX1xdeXl7o378/0tPTIRKJcPjwYbUa5kaVKKBImfnjjz8wffp03L9/v9gdJpydnREVFaW8z+fzUb16dWzYsAGdOnUCj8dTVbmEqJVff/0VgwcPRlZWVo5WU/Xq1REdHQ0+n89hdaWDdvGRMtOjRw/UqlWrRB0mJBJJjvsymQxPnjyBl5cX3NzcEBcXV9IyCVFLffr0gYeHx1e79OLj47F3797CLUQuBT49AZIfKn7K1XusKmpBkTL19OlTuLu7486dO8W6orO9vX2unS0MDAxgbW2NK1euoEqVKqoolRC18r///Q9TpkxBWlraV49ZWloiNjYWBgYGX8+YmQjE7ASehgCpMYCOLgA+ABkgzwKMagAOwwDHEYC+eak/j6KgFhQpUw4ODpg4cSKmTZtWrPlzG51UKBRi8ODBiIqKonAiWunZs2eYMGFCruEEAB8/fsTGjRtz/lGWBdwNAI7aAg8CgZQoRSBJ0wBpiuKnXKL4+4NA4GgVxfSyrDJ4RoVDLShS5rI7TGzbtq3Ive+srKzw/v17AIBAIIBQKMTevXvRo0eP0iiVELXw8OFDTJgwAdHR0YiPj4e+vj74fD4yMjKUu735fD7evn2LihUrAmmxwPn2QHocIEsv/Ir4QkBYBWh7FhBxP2YVBRThxO+//64cO6ooHSZMTEyQkpICoVCIRo0a4fDhw+X+bHtSvkgkEjx//hyPHj3CP//8g/v37+Pq1auIiYlB9erV8fflozC93h7ISgKYrOgr4PEBPXOg8y3OQ4oCinCCMYYePXqgRYsWmDlzZs4H5VIg7TkgEwN8A0BUDdARAAD09PQgl8uxbNkyTJ06lU7OJeRfMpkM/9u2CSNs1kA382Xxwikbjw8YOQDdIv49ZsUNCijCmZiYGDRp0gR3796FnZWwUAdyu0z8BQELgtGiRQuuyydE/dwNAB6tLdpuvbzwhUDtKUCDxSVfVjFRQBFOrVy+BG0qXoKb0SUAPECWkffEfEMADHCaCrgEAny9siqTEM4cP34crq6uqFy5cv4TZiYqOkTIxLk+XM0PeJGg+J2vA1SsAHjUBIIHAw5WeSyTbwD0juOsdx/tHyHcSYuFv/NuuBn9qXhT5RdOgOJxmVjxDfF4PcWBYEK03JAhQ1C9enX4+PggOjo67wljdgIo+ET17g2B8e0BEyFw9BYw8n/5Tc0DYri7YC0FFOFGWixw0g1IfVr03RGydMV8J90opIjW09HRQVZWFg4cOID69eujW7duuH379tcTPg0p+EsegBGewHpfYJW34v4/r/OZWJYBPN1VnLJVggKKlD1ZlqILbHF7GQGK+bKSFMuRSwqenhANpaur6KQgk8kgFotx4sQJtGrVCh4eHjh37pziyhJyqeLYbSH8GA5M2g3MOKC437dJATOkcnfFCQEnayXl24MFivMzStLLCFDMnx6nWB6HB3IJyYtUKkVqaio+ffqE1NRUpKamIi0tTfkzPT1decvIyFD+FIvFytvHjx9zLJMxhvT0dFy/fh0dOnSAQCCAb5/m2NZbAB0UfJJt6J3/ftfXBRpXK2AGnq6iV22FGkV+/iVFAUXKVmYi8Gh1rgdysw/i8niAUE9xELeJIzCtK9A0r/eGLB34JxioPTXPA7nXr1+Hn58fhg0bhrFjx6rwyRB1IJfLc4TAp0+fkJ6ejtTUVKSnpyMtLQ1paWnIyMhAWloaxGIxMjIycgRBZmYmxGIxsrKykJmZiczMTEgkEmRlZUEqlSp/Zt9kMhmkUinkcjlkMhnkcjnkcjkYY8rbl3g8Hng8HnR0dHLc+Hw++Hw+BAJBjpuenh50dXUhk+X+RU5HRwc8Hg/16tVDn15dwdO5DcgLfr2OTAF6NQZuxgAtFwIj/ge0rgNUz6ujBI+fZ8eL0kYBRcpWIQ7kdnMFLI2BK4+BwzeAI7eA/d8D/ZrmNce/B3Kd/XP8NTIyEpMnT8aVK1eQnp6Oli1bquIZlEtyuRzp6ek5WgLZt+wQyP4pFouVLYEvWwPZH/5ZWVk5bhKJBBKJRBkAEokEMplMecsOAsZYjiD4UnYIZAcBn8/PEQJ8Ph+6urrKn9m37DDQ19eHvr4+jI2Noa+vDwMDA+XN0NAQBgYGEAqFEAqFMDQ0hEgkglAohEgkgpGRkXIYGJFIBGNjYwiFwhKfq5fbFfx1dXUxaNAgLFmyBJUqVVJc+PXEgkIvk8cDGlcHRPpAcjoQE59PQDGZojcfByigSNkqxIHcEZ5AbzdAKgN8tgAHrwFjdyqCS5jbRSeyD+T+G1CxsbHw9/fH77//jqysLMjliq+V6ekqODekFMnlcojFYqSkpCAtLQ2fPn36anfQ5y2BzwPgy9ZAdgh83hLIDoHPgyC7NfB5K+DL1sCXvgyBgloCX4aAnp4e9PX1YWRkpAwBfX19GBoaKkPA0NBQGQSfh0D27fMQEIlEWjnURLbsK63weDwYGBigQ4cOWL16NRwdHf+bSFSt0MdifwwHLkQCfz9XhJNQH6hvl88MTKJYPgcooEjZKcKBXAAQ8IHAPoqASkpVtKg6uOQxceoTJMS/ReCCRQgJCVF+CH9OLBaDMYbMzMwcu4OyA+Dz2+fHA7J/z8zMREZGhnJ3UG4hkL0rKK8Q+DIIShIC2T91dXWVP/X09HLczMzMvmoJZAdA9i07AD4PASMjI+WtQoUKMDIygkBAHxdc0NfXh0AggIeHB9avXw9XV9evJ9IRAEaOigu/FiD7GJSpEGjhBCzoC1iZ5DODUQ3llVzKGm1xpOykPVdcIUJe+Ksl21f87/f4lLynSxdL8E39Soh5l/c0ISEhCAkJUd4vKAS+bA18uUsouyVgamqq3DWUWwhk7w4SCoUwMjL6apeQkZGRsiWgp0cnH5Oc5syZgwoVKqB169b5T+gwTHFV8jz2UDxfV4yV8w0Vy+UIBRQpOzIxFJcvKrzsM98BwMo47+l09QzQzrMhXh29DcYYsrK+DsGuXbviyJEjFAJEo3Tv3r1wEzqOAB7MU/HaGeA4XMXLLDw6D4qUHb4BgMJ3LZfKgAW/KX43NwKa18p7Wl2+Drb9bzeSkpKwYsUKVKxYEUZGRjmmkcvlFE5Ee+mbKy4DxheqZnl8IVB7GqeDGFJAkbJTyAO5P4YDw7cDdX9QHH8S8IGtw/PoIJHt3wO5QqEQfn5+eP36NTZv3gx7e3tlUGVmZqrkaRCitlwCFeM58UrYaYTHVyzHJVA1dRUTBRQpO9kHcgsQdhf4+TqQKQH6NwWuBObXxfxfXxzI1dXVhY+PD54+faq8RIyJSX5HggnRAnw9xWCDeubFD6ns8aDanuV0qA2ArmZOylrkynwP5BYL3xBwWQg4T1fdMgnRZFoyoi61oEjZchwBQNXfibg9kEuI2hFVBbo+BJwmK4798g3zn54vVExXe4pikEI1CCeAWlCEC1o2qBohai0zSXGllae7FBd+5ekqduMxmeLY7b+DgcJxOKcdInJDAUXKnixLMZ5T6lOtGJaaEI0hlyrOR5SJFS0mUTXOTsItDAoowo3s8aCKO+RG9oHczrfUZncEIUS16BgU4YaoqiJcjByKft4GX6iYj8KJEK1GAUW4oyUHcgkhpYN28RH1oMEHcgkhpYMCiqgfDTuQSwgpHRRQhBBC1BIdgyKEEKKWKKAIIYSoJQooQgghaokCihBCiFqigCKEEKKWKKAIIYSoJQooQgghaokCihBCiFqigCKEEKKWKKAIIYSoJQooQgghaokCihBCiFqigCKEEKKWKKAIIYSoJQooQgghaun/6V/yApJww7oAAAAASUVORK5CYII=\n", "text/plain": [ "
" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "G4 = nx.DiGraph()\n", "G4.add_nodes_from([\"A\",\"B\",\"C\",\"D\"])\n", "G4.add_edges_from([\n", " (\"A\",\"B\"), (\"A\",\"C\"), (\"A\",\"D\"), \n", " (\"B\",\"A\"), (\"B\",\"D\"),\n", " (\"C\",\"A\"), \n", " (\"D\",\"B\"), (\"D\",\"C\")\n", "])\n", "\n", "plt.figure() \n", "plt.title(\"Graph 1. A Graph as a hypothetical representation of the web\")\n", "nx.draw(G4, node_size=500, node_color='orange', with_labels=True, font_weight='bold', arrowsize=20)\n", "plt.tight_layout()\n", "plt.show()" ] }, { "cell_type": "markdown", "id": "0c59298b", "metadata": {}, "source": [ "Define the transition matrix $M$ using our `link_analysis` module." ] }, { "cell_type": "code", "execution_count": 4, "id": "95689ae5", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "array([[0. , 0.5 , 1. , 0. ],\n", " [0.33333333, 0. , 0. , 0.5 ],\n", " [0.33333333, 0. , 0. , 0.5 ],\n", " [0.33333333, 0.5 , 0. , 0. ]])" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "M = link_analysis.transition_matrix(G4)\n", "M" ] }, { "cell_type": "markdown", "id": "03c13dbb", "metadata": {}, "source": [ "Define the initial vector $v$" ] }, { "cell_type": "code", "execution_count": 5, "id": "a05dd78b", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(4, array([1., 1., 1., 1.]))" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "n = M.shape[0]\n", "v = np.ones(n) \n", "n, v" ] }, { "cell_type": "markdown", "id": "6f542ed8", "metadata": {}, "source": [ "Define list of triples ($i$, $j$, $m_{ij}$) to be used by the Map function. The first two element of the triple contains the indices to the transition matrix while the third element refers to the value. " ] }, { "cell_type": "code", "execution_count": 6, "id": "93693f7e", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[(0, 0, 0.0),\n", " (0, 1, 0.5),\n", " (0, 2, 1.0),\n", " (0, 3, 0.0),\n", " (1, 0, 0.3333333333333333),\n", " (1, 1, 0.0),\n", " (1, 2, 0.0),\n", " (1, 3, 0.5),\n", " (2, 0, 0.3333333333333333),\n", " (2, 1, 0.0),\n", " (2, 2, 0.0),\n", " (2, 3, 0.5),\n", " (3, 0, 0.3333333333333333),\n", " (3, 1, 0.5),\n", " (3, 2, 0.0),\n", " (3, 3, 0.0)]" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "M_elements = []\n", "for i in range(n):\n", " for j in range(n):\n", " M_elements.append( (i,j, M[i,j]))\n", "M_elements" ] }, { "cell_type": "markdown", "id": "06f784e5", "metadata": {}, "source": [ "Let's save this list as we will use it later when we illustrate the MapReduce reading from a file." ] }, { "cell_type": "code", "execution_count": 7, "id": "26850f6b", "metadata": {}, "outputs": [], "source": [ "with open(\"graph4.csv\", \"w\") as f:\n", " csv_writer = csv.writer(f)\n", " for row in M_elements:\n", " csv_writer.writerow(row)" ] }, { "cell_type": "markdown", "id": "e8aa9717", "metadata": {}, "source": [ "Parallelize the list of triples" ] }, { "cell_type": "code", "execution_count": 8, "id": "80002df8", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "ParallelCollectionRDD[0] at readRDDFromFile at PythonRDD.scala:274" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "M_elements = sc.parallelize(M_elements)\n", "M_elements" ] }, { "cell_type": "code", "execution_count": 9, "id": "aef1ce58", "metadata": { "scrolled": true }, "outputs": [ { "data": { "text/plain": [ "pyspark.rdd.RDD" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" } ], "source": [ "type(M_elements)" ] }, { "cell_type": "code", "execution_count": 10, "id": "6735094d", "metadata": {}, "outputs": [ { "name": "stderr", "output_type": "stream", "text": [ " \r" ] }, { "data": { "text/plain": [ "[(0, 0, 0.0), (0, 1, 0.5), (0, 2, 1.0), (0, 3, 0.0)]" ] }, "execution_count": 10, "metadata": {}, "output_type": "execute_result" } ], "source": [ "M_elements.take(4)" ] }, { "cell_type": "markdown", "id": "683ad9ec", "metadata": {}, "source": [ "**Map** " ] }, { "cell_type": "markdown", "id": "f63653a0", "metadata": {}, "source": [ "Apply Map function calculating ($i$, $m_{ij}v_j$)" ] }, { "cell_type": "code", "execution_count": 11, "id": "08e016e5", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[(0, 0.0),\n", " (0, 0.5),\n", " (0, 1.0),\n", " (0, 0.0),\n", " (1, 0.3333333333333333),\n", " (1, 0.0),\n", " (1, 0.0),\n", " (1, 0.5),\n", " (2, 0.3333333333333333),\n", " (2, 0.0),\n", " (2, 0.0),\n", " (2, 0.5),\n", " (3, 0.3333333333333333),\n", " (3, 0.5),\n", " (3, 0.0),\n", " (3, 0.0)]" ] }, "execution_count": 11, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Note that:\n", "# i = x[0]\n", "# j = x[1]\n", "# mij = x[2]\n", "M_elements.map(lambda x: (x[0], x[2]*v[x[1]])).collect()" ] }, { "cell_type": "markdown", "id": "3fe6d59e", "metadata": {}, "source": [ "**Reduce**" ] }, { "cell_type": "markdown", "id": "9f78d898", "metadata": {}, "source": [ "The Reduce function adds the values in the pairs produced by the Map function. We can chain the map function above with `reduceByKey`." ] }, { "cell_type": "code", "execution_count": 12, "id": "4472cca7", "metadata": {}, "outputs": [ { "name": "stderr", "output_type": "stream", "text": [ " \r" ] }, { "data": { "text/plain": [ "[(0, 1.5),\n", " (1, 0.8333333333333333),\n", " (2, 0.8333333333333333),\n", " (3, 0.8333333333333333)]" ] }, "execution_count": 12, "metadata": {}, "output_type": "execute_result" } ], "source": [ "M_elements.map(lambda x: (x[0], x[2]*v[x[1]])\n", " ).reduceByKey(lambda x, y: x+y\n", " ).collect()" ] }, { "cell_type": "markdown", "id": "6b31d8ee", "metadata": {}, "source": [ "The key-value pairs above are ($i$, $v'_i$) defining $v'=Mv$" ] }, { "cell_type": "markdown", "id": "eab91933", "metadata": {}, "source": [ "## Reading Graph Information from CSV file" ] }, { "cell_type": "markdown", "id": "5a5ecb1e", "metadata": {}, "source": [ "Here we implement the above steps while reading from a CSV file. Note that this still just represents Matrix-vector multiplication. Let's have a quick look at our CSV file." ] }, { "cell_type": "code", "execution_count": 13, "id": "f1ac4abe", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "0,0,0.0\r", "\r\n", "0,1,0.5\r", "\r\n", "0,2,1.0\r", "\r\n", "0,3,0.0\r", "\r\n", "1,0,0.3333333333333333\r", "\r\n", "1,1,0.0\r", "\r\n", "1,2,0.0\r", "\r\n", "1,3,0.5\r", "\r\n", "2,0,0.3333333333333333\r", "\r\n", "2,1,0.0\r", "\r\n", "2,2,0.0\r", "\r\n", "2,3,0.5\r", "\r\n", "3,0,0.3333333333333333\r", "\r\n", "3,1,0.5\r", "\r\n", "3,2,0.0\r", "\r\n", "3,3,0.0\r", "\r\n" ] } ], "source": [ "!cat graph4.csv" ] }, { "cell_type": "code", "execution_count": 14, "id": "e6cd3149", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[(0, 1.5),\n", " (2, 0.8333333333333333),\n", " (1, 0.8333333333333333),\n", " (3, 0.8333333333333333)]" ] }, "execution_count": 14, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# load data from a CSV file\n", "M_tuples= sc.textFile(\"graph4.csv\")\n", "\n", "# get the number of nodes of the graph \n", "n = round(np.sqrt(M_tuples.count()))\n", "\n", "# initialize our vector\n", "v = np.ones(n) \n", "\n", "# calculate M*v\n", "(M_tuples.map(lambda x: x.split(',')) # CSV file contains a string of triple per row; we split it by comma\n", " .map(lambda x: (int(x[0]), int(x[1]), float(x[2]))) # convert string to triple of (int, int, float)\n", " .map(lambda x: (x[0], x[2]*v[x[1]])) # (i, M_ij*v_j): equal to (i, Mv_ij)\n", " .reduceByKey(lambda x, y: x+y) # sum all values for a given key \n", " .collect())" ] }, { "cell_type": "markdown", "id": "cab9e530", "metadata": {}, "source": [ "We can check this quickly" ] }, { "cell_type": "code", "execution_count": 15, "id": "1fb2c814", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "array([1.5 , 0.83333333, 0.83333333, 0.83333333])" ] }, "execution_count": 15, "metadata": {}, "output_type": "execute_result" } ], "source": [ "M.dot(v)" ] }, { "cell_type": "markdown", "id": "d8eb3586", "metadata": {}, "source": [ "## Taxed PageRank Update" ] }, { "cell_type": "markdown", "id": "8f33e7d6", "metadata": {}, "source": [ "Here we illustrate how to do one update of the Taxed PageRank algorithm" ] }, { "cell_type": "code", "execution_count": 16, "id": "e2e40a73", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[(0, 1.2500000000000002),\n", " (2, 0.7166666666666666),\n", " (1, 0.7166666666666666),\n", " (3, 0.7166666666666666)]" ] }, "execution_count": 16, "metadata": {}, "output_type": "execute_result" } ], "source": [ "beta = 0.8\n", "M_tuples= sc.textFile(\"graph1.csv\")\n", "n = round(np.sqrt(M_tuples.count()))\n", "v = np.ones(n) \n", "Mv = (M_tuples.map(lambda x: x.split(','))\n", " .map(lambda x: (int(x[0]), int(x[1]), float(x[2])))\n", " .map(lambda x: (x[0], x[2]*v[x[1]]))\n", " .reduceByKey(lambda x, y: x+y) \n", " .map(lambda x: (x[0], beta*x[1]+(1-beta)/n)) # for each Mv_ij, compute beta*Mv_ij + (1-beta)/n\n", " .collect())\n", "Mv" ] }, { "cell_type": "markdown", "id": "f9504049", "metadata": {}, "source": [ "We can check this in the following way" ] }, { "cell_type": "code", "execution_count": 17, "id": "c44f48d3", "metadata": { "scrolled": true }, "outputs": [ { "data": { "text/plain": [ "array([1.25 , 0.71666667, 0.71666667, 0.71666667])" ] }, "execution_count": 17, "metadata": {}, "output_type": "execute_result" } ], "source": [ "beta * M.dot(v) + (1-beta)/n" ] }, { "cell_type": "markdown", "id": "8fcbbbef", "metadata": {}, "source": [ "Or, we can call our distributed_taxed_page_rank function, with one iteration." ] }, { "cell_type": "code", "execution_count": 18, "id": "814758c9", "metadata": { "scrolled": true }, "outputs": [ { "data": { "text/plain": [ "array([1.25 , 0.71666667, 0.71666667, 0.71666667])" ] }, "execution_count": 18, "metadata": {}, "output_type": "execute_result" } ], "source": [ "link_analysis.taxed_page_rank(link_analysis.transition_matrix(G4), max_iter=1)" ] }, { "cell_type": "markdown", "id": "a27d76ff", "metadata": {}, "source": [ "## Function for Computing PageRank using MapReduce" ] }, { "cell_type": "markdown", "id": "2da48dd7", "metadata": {}, "source": [ "Finally, we define a function which we can use to compute page rank in a distributed way, given a CSV file.Note that that this assumes that the vector of PageRanks fit in memory" ] }, { "cell_type": "code", "execution_count": 19, "id": "7d509f9f", "metadata": {}, "outputs": [], "source": [ "def distributed_taxed_page_rank(filename, beta=0.8, tol=10**-6, max_iter=100):\n", " \"\"\" Distributedly compute the Taxed PageRank of a given Transition Matrix using pyspark \n", " Note that that this assumes that the vector of PageRanks fit in memory\n", " \n", " Parameters\n", " ----------\n", " filename : string\n", " CSV file containing triples of (i, j, M_ij) representing the (i,j) index to the transition matrix M\n", " tol : float\n", " Tolerance: Iteration stops if the distance between previous and updated PageRank vectors \n", " goes below this value\n", " max_iter : integer\n", " Maximum number of iterations\n", " Returns\n", " -------\n", " v : numpy array\n", " Vector of size n containing the ordinary PageRank values \n", " \"\"\" \n", "\n", " M_tuples= sc.textFile(\"graph1.csv\")\n", " n = round(np.sqrt(M_tuples.count()))\n", " v = np.ones(n) \n", " delta = 1/tol # initialize vector difference to a large number\n", " i = 0\n", " while delta > tol:\n", " i += 1\n", " prev_v = v \n", " v = (M_tuples.map(lambda x: x.split(','))\n", " .map(lambda x: (int(x[0]), int(x[1]), float(x[2])))\n", " .map(lambda x: (x[0], x[2]*v[x[1]]))\n", " .reduceByKey(lambda x, y: x+y) \n", " .map(lambda x: (x[0], beta*x[1]+(1-beta)/n))\n", " .collect())\n", " v = np.array([v[j][1] for j in range(n)])\n", " delta = np.sum(np.abs(v-prev_v)) # compute L1 norm \n", " if i >= max_iter:\n", " break\n", " return v " ] }, { "cell_type": "markdown", "id": "593d44d6", "metadata": {}, "source": [ "Let's run it for one iteration to check if we are getting the correct answer." ] }, { "cell_type": "code", "execution_count": 20, "id": "c8a904fa", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "array([1.25 , 0.71666667, 0.71666667, 0.71666667])" ] }, "execution_count": 20, "metadata": {}, "output_type": "execute_result" } ], "source": [ "distributed_taxed_page_rank(\"graph1.csv\", max_iter=1)" ] }, { "cell_type": "markdown", "id": "cb3c6041", "metadata": {}, "source": [ "Let's now run it to convergence" ] }, { "cell_type": "code", "execution_count": 21, "id": "f966f4e3", "metadata": { "scrolled": true }, "outputs": [ { "data": { "text/plain": [ "array([0.3214298 , 0.22619129, 0.22619129, 0.22619129])" ] }, "execution_count": 21, "metadata": {}, "output_type": "execute_result" } ], "source": [ "distributed_taxed_page_rank(\"graph1.csv\")" ] }, { "cell_type": "markdown", "id": "861f7169", "metadata": {}, "source": [ "Again, we can compare this to the non-distributed procedure" ] }, { "cell_type": "code", "execution_count": 22, "id": "255ea220", "metadata": { "scrolled": true }, "outputs": [ { "data": { "text/plain": [ "array([0.3214298 , 0.22619129, 0.22619129, 0.22619129])" ] }, "execution_count": 22, "metadata": {}, "output_type": "execute_result" } ], "source": [ "link_analysis.taxed_page_rank(link_analysis.transition_matrix(G4))" ] }, { "cell_type": "markdown", "id": "85666368", "metadata": {}, "source": [ "**EXERCISES**\n", "\n", "1. Give Graph 1 in the previous section, create a CSV file containing the triples that could be used to be fed to a distributed computation of PageRank.\n", "2. Given the CSV file in no.1 above, read the CSV file and perform 1 round of the matrix-vector multiplication $Mv$ using MapReduce.\n", "3. Using again the CSV file in no.1, compute the PageRank using `distributed_taxed_page_rank` then compare the answer to `link_analysis.taxed_page_rank`.\n" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3 (ipykernel)", "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.8.12" }, "toc": { "base_numbering": 1, "nav_menu": {}, "number_sections": true, "sideBar": true, "skip_h1_title": false, "title_cell": "Table of Contents", "title_sidebar": "Contents", "toc_cell": false, "toc_position": { "height": "calc(100% - 180px)", "left": "10px", "top": "150px", "width": "318.188px" }, "toc_section_display": true, "toc_window_display": true } }, "nbformat": 4, "nbformat_minor": 5 }