Last active
July 13, 2022 17:41
-
-
Save xvdp/de1055f34574e85bf838ea9bbfd8ddaf to your computer and use it in GitHub Desktop.
Page_Rank_Sketch.ipynb
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| { | |
| "cells": [ | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "view-in-github", | |
| "colab_type": "text" | |
| }, | |
| "source": [ | |
| "<a href=\"https://colab.research.google.com/gist/xvdp/de1055f34574e85bf838ea9bbfd8ddaf/page_rank_sketch.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "id": "d44593f6", | |
| "metadata": { | |
| "id": "d44593f6" | |
| }, | |
| "source": [ | |
| "# Page Rank\n", | |
| "\n", | |
| "https://networkx.github.io/documentation/networkx-1.10/reference/generated/networkx.algorithms.link_analysis.pagerank_alg.pagerank.html\n", | |
| "\n", | |
| "https://www.cs.princeton.edu/~chazelle/courses/BIB/pagerank.htm\n", | |
| "https://web.stanford.edu/class/cs54n/handouts/24-GooglePageRankAlgorithm.pdf\n", | |
| "\n", | |
| "\n", | |
| "**PR(A) = (1-d) + d (PR(T1)/C(T1) + ... + PR(Tn)/C(Tn))**\n", | |
| "\n", | |
| "* **PR(Tn)** page importance\n", | |
| "* **C(Tn)** spread evenly among out links\n", | |
| "* **d** dampening [ 0.85]\n", | |
| "* **(1-d)** minimum rank \n", | |
| "\n", | |
| "This sketchbook was done to undersatnd the relationship between graph laplacian, svd and page rank--the basic search algorithm for google search engine: The rank of a page is given by the rank of all the links that point to it, weighted.\n", | |
| "\n", | |
| "Scipy, NetworkX contain their own implementations. Caveat, this is only sketch code.\n", | |
| "\n", | |
| " \n", | |
| " Notes on einsums used here. Einsums are a compact way of expressing multiplications, sums, transposes\n", | |
| " # 2d to 2d, i is columns, j rows\n", | |
| " einsum(\"ij,ij->ij\", a, b) # is the Hammard Product a * b\n", | |
| " einsum(\"ij->ji\", a) # a.T\n", | |
| " \n", | |
| " # 2d to 1d\n", | |
| " einsum(\"ij,ij->i\", a, b) # is the Hammard summed over columns, np.sum(a * b, axis=1)\n", | |
| " einsum(\"ij,ij->j\", a, b) # idem summed over rows np.sum(a * b, axis=0)\n", | |
| " einsum('ij->i', a) # sum columns\n", | |
| "\n", | |
| " # 1d, 2d to 2d\n", | |
| " einsum('i,ij->ij', a, b) # (b.T * a).T # 1d, 2d to 2d " | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": null, | |
| "id": "81f2cd7d", | |
| "metadata": { | |
| "id": "81f2cd7d" | |
| }, | |
| "outputs": [], | |
| "source": [ | |
| "import numpy as np\n", | |
| "import matplotlib.pyplot as plt\n", | |
| "import networkx as nx\n" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": null, | |
| "id": "787920fa", | |
| "metadata": { | |
| "id": "787920fa" | |
| }, | |
| "outputs": [], | |
| "source": [ | |
| "class Graphene:\n", | |
| " \"\"\"\n", | |
| " data is an input output matrix\n", | |
| " i is outgoing connections\n", | |
| " j in incoming connections\n", | |
| " \"\"\"\n", | |
| " def __init__(self, data, datatype=np.ndarray, names=None, allow_self_references=False):\n", | |
| " \n", | |
| " self.data = data # io matrix\n", | |
| " self.names = self.set_names(names) # node names: default \n", | |
| " \n", | |
| " if not allow_self_references:\n", | |
| " self.data = self.to_selfless() # io matrix wo. self referential nodes\n", | |
| " \n", | |
| " self.degree = self.to_degree() # eye with number of connections\n", | |
| " self.sparse = self.to_sparse() # sparse selfress io matrix\n", | |
| " self.incidence = self.to_inicidence() # incidence matrix \n", | |
| " self.adjacency = self.to_adjacency() # undirected version of dag\n", | |
| " self.laplacian = self.degree - self.adjacency\n", | |
| " #self.laplacian = np.matmul(self.adjacency, self.adjacency.T)\n", | |
| " \n", | |
| " self.nxdag = self.to_nx()\n", | |
| " \n", | |
| "# self.values = np.ones(len(self.data))\n", | |
| " \n", | |
| " def set_names(self, names=None):\n", | |
| " if names is None:\n", | |
| " names = [i for i in range(len(self.data))]\n", | |
| " assert len(names) == len(self.data), \"number of nodes and number of names differs %d != %d\"%(len(names), len(self.data))\n", | |
| " return names\n", | |
| " \n", | |
| "# def weighted_data(self):\n", | |
| "# return np.divide(self.data, self.row_sum)\n", | |
| " \n", | |
| " def to_selfless(self):\n", | |
| " not_self = 1 - np.eye(len(self.data), dtype=self.data.dtype)\n", | |
| " return np.einsum(\"ij,ij->ij\", self.data, not_self)\n", | |
| " \n", | |
| " #def to_undirected(self):\n", | |
| "# return np.clip(self.data + self.data.T, 0, 1)\n", | |
| "\n", | |
| " def to_degree(self):\n", | |
| " \"\"\" node conectivity diagonal matrix with number of io connections per node\n", | |
| " \"\"\"\n", | |
| " rowsum = np.einsum('ij->i', np.clip(self.data + self.data.T, 0, 1))\n", | |
| "# rowsum = np.einsum('ij->i', np.clip(self.less_data + self.less_data.T, 0, 1))\n", | |
| " return np.einsum('i,ij->ij', rowsum, np.eye(len(rowsum), dtype=rowsum.dtype))\n", | |
| " \n", | |
| " def to_sparse(self, matrix=None):\n", | |
| " \"\"\" returns sparse array\n", | |
| " \"\"\"\n", | |
| " if matrix is None:\n", | |
| " matrix = self.data\n", | |
| "# matrix = self.less_data\n", | |
| " return np.array(np.where(matrix != 0))\n", | |
| "\n", | |
| " def flat_indices(self, arr, idcs):\n", | |
| " \"\"\" returns indices in flat array\n", | |
| " \"\"\" \n", | |
| " return np.sort(idcs[:,0]*arr.shape[1] + idcs[:,1])\n", | |
| "\n", | |
| " def to_inicidence(self, matrix=None):\n", | |
| " \"\"\" returns incidence matrix\n", | |
| " 1 : outgoing edges\n", | |
| " -1 : incoming edges\n", | |
| " 0 : otherwise\n", | |
| " i: nodes\n", | |
| " j: edges\n", | |
| " \"\"\"\n", | |
| " if matrix is None:\n", | |
| " matrix = self.data\n", | |
| " sparse = self.sparse\n", | |
| " else:\n", | |
| " sparse = self.to_sparse(matrix)\n", | |
| " incidence = np.zeros([len(matrix), matrix.sum()], dtype=matrix.dtype)\n", | |
| " edges = np.arange(len(sparse[0]))\n", | |
| " pos = self.flat_indices(incidence, np.vstack((sparse[0], edges)).T)\n", | |
| " neg = self.flat_indices(incidence, np.vstack((sparse[1], edges)).T)\n", | |
| " np.put(incidence, pos, 1)\n", | |
| " np.put(incidence, neg, -1)\n", | |
| " return incidence\n", | |
| "\n", | |
| " def to_adjacency(self):\n", | |
| " \"\"\" undirected make all connections mutual\n", | |
| " \"\"\"\n", | |
| " return np.clip(self.data + self.data.T, 0, 1)\n", | |
| " \n", | |
| " #\n", | |
| " # Network X\n", | |
| " #\n", | |
| " def to_nx(self, sparse=None):\n", | |
| " if sparse is None:\n", | |
| " sparse = self.sparse\n", | |
| " G = nx.DiGraph()\n", | |
| " G.add_nodes_from(self.names)\n", | |
| " G.add_edges_from(self.sparse.T)\n", | |
| " return G\n", | |
| " \n", | |
| " def page_rank_nx(self, damp=0.85):\n", | |
| " return nx.pagerank(self.nxdag, alpha=damp)\n", | |
| " \n", | |
| " def end_nodes(self):\n", | |
| " row_sum = np.einsum('ij->i', self.data).reshape(-1,1)\n", | |
| " return np.where(row_sum == 0)[0]\n", | |
| " \n", | |
| " def weighted_matrix(self, alpha=0.85):\n", | |
| " \"\"\" similar to networkx 'google_matrix'\n", | |
| " normalized matrix dampened by alpha\n", | |
| " no outputs distribute their weights evenly\n", | |
| " unconnected inputs add a token residual\n", | |
| " \"\"\"\n", | |
| " matrix = self.data.copy().astype(float)\n", | |
| " # output links per node\n", | |
| " row_sum = np.einsum('ij->i', self.data).reshape(-1,1)\n", | |
| " end_nodes = np.where(row_sum == 0)[0]\n", | |
| " \n", | |
| " # distribute end node values evenly \n", | |
| " for node in end_nodes:\n", | |
| " matrix[node] += 1.0/len(matrix) \n", | |
| " row_sum[node] = 1.0\n", | |
| "\n", | |
| " matrix *= alpha/row_sum # normalize\n", | |
| " matrix += (1 - alpha)/len(matrix) # dampen, add alpha residual to all nodes\n", | |
| " return matrix\n", | |
| "\n", | |
| " #\n", | |
| " # EigenVal PageRank\n", | |
| " #\n", | |
| " def page_rank_eigen(self, alpha=0.85):\n", | |
| " \"\"\" AE = EΛ \"\"\"\n", | |
| " weighted_matrix = self.weighted_matrix(alpha=alpha).T\n", | |
| " eigvals, eigvectors = np.linalg.eig(weighted_matrix)\n", | |
| " \n", | |
| " #print(eigvectors.real)\n", | |
| " #sort vectors by values\n", | |
| " vectors = eigvectors[:, eigvals.argsort()[-1]].flatten().real\n", | |
| " return vectors/vectors.sum()\n", | |
| " \n", | |
| " def page_rank_svd(self, alpha=0.85):\n", | |
| " \"\"\"U = E and S = Λ\n", | |
| " E: vectors Λ: values\n", | |
| " TODO: does not behave like eigen\n", | |
| " \"\"\"\n", | |
| " weighted_matrix = self.weighted_matrix(alpha=alpha).T\n", | |
| " U,S,V = np.linalg.svd(weighted_matrix)\n", | |
| "\n", | |
| " vectors = U[:, np.power(S, 2).argsort()[-1]].flatten().real\n", | |
| " return vectors/vectors.sum()\n", | |
| " \n", | |
| " #\n", | |
| " # Iterative PageRank\n", | |
| " #\n", | |
| " def page_rank_iterate(self, max_loops=1000, alpha=0.85, tolerance=1e-4, verbose=0):\n", | |
| " \"\"\" TODO does not include personalization.\n", | |
| " \n", | |
| " \"\"\"\n", | |
| " matrix = self.data.copy().astype(float)\n", | |
| " x = np.ones(len(matrix), dtype=float)/len(matrix)\n", | |
| " \n", | |
| " # output links per node\n", | |
| " row_sum = np.einsum('ij->i', self.data).reshape(-1,1)\n", | |
| " end_nodes = np.where(row_sum == 0)[0]\n", | |
| " damp = (1-alpha)/len(matrix)\n", | |
| " \n", | |
| " # end nodes have no output connections, force sum value = 1.0\n", | |
| " for node in end_nodes:\n", | |
| " row_sum[node] = 1.0\n", | |
| " \n", | |
| " end_weights = np.ones(len(matrix))/len(matrix)\n", | |
| " \n", | |
| " if verbose:\n", | |
| " print(\"input connectivity matrix\\n\", self.data)\n", | |
| " print(\"output links per node\", row_sum)\n", | |
| " print(\"end_nodes\", end_nodes)\n", | |
| " print(\"number of nodes\", len(matrix))\n", | |
| " \n", | |
| " matrix /= row_sum\n", | |
| " \n", | |
| " for i in range(max_loops):\n", | |
| " _x = x\n", | |
| " \n", | |
| " # project values to normalized matrix, add end node contributions + damping normalization\n", | |
| " x = alpha*(np.einsum('i,ij->j', x, matrix) + x[end_nodes].sum()*end_weights) + (1-alpha)*end_weights\n", | |
| " \n", | |
| " err = np.abs(_x - x).sum()\n", | |
| " \n", | |
| " if err < tolerance:\n", | |
| " return x\n", | |
| " return x" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "id": "19e2491d", | |
| "metadata": { | |
| "id": "19e2491d" | |
| }, | |
| "source": [ | |
| "## Given a Directed graph" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": null, | |
| "id": "6ed7e4a2", | |
| "metadata": { | |
| "id": "6ed7e4a2" | |
| }, | |
| "outputs": [], | |
| "source": [ | |
| "# Directed Graph with end nodes # i out, j: in\n", | |
| "# with end nodes\n", | |
| "M = np.array([[0,0,1,0,0,1,0],\n", | |
| " [0,0,0,0,0,0,0],\n", | |
| " [1,1,0,1,0,0,0],\n", | |
| " [0,0,0,0,1,0,1],\n", | |
| " [0,0,0,0,0,0,1],\n", | |
| " [0,0,0,0,0,0,0],\n", | |
| " [0,0,0,1,1,1,0]])" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": null, | |
| "id": "fcfe3e08", | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "id": "fcfe3e08", | |
| "outputId": "63d4b9bb-75c3-4497-d0e8-bc318393bb6f" | |
| }, | |
| "outputs": [ | |
| { | |
| "output_type": "execute_result", | |
| "data": { | |
| "text/plain": [ | |
| "array([[0, 0, 1, 0, 0, 1, 0],\n", | |
| " [0, 0, 1, 0, 0, 0, 0],\n", | |
| " [1, 1, 0, 1, 0, 0, 0],\n", | |
| " [0, 0, 1, 0, 1, 0, 1],\n", | |
| " [0, 0, 0, 1, 0, 0, 1],\n", | |
| " [1, 0, 0, 0, 0, 0, 1],\n", | |
| " [0, 0, 0, 1, 1, 1, 0]])" | |
| ] | |
| }, | |
| "metadata": {}, | |
| "execution_count": 4 | |
| } | |
| ], | |
| "source": [ | |
| "#undirected\n", | |
| "UG = np.clip((M+M.T), 0, 1)\n", | |
| "UG" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": null, | |
| "id": "5e676741", | |
| "metadata": { | |
| "id": "5e676741" | |
| }, | |
| "outputs": [], | |
| "source": [ | |
| "G = Graphene(M, allow_self_references=False)" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "id": "5d31843a", | |
| "metadata": { | |
| "id": "5d31843a" | |
| }, | |
| "source": [ | |
| "## Various implementations of pagerank" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": null, | |
| "id": "425d3acf", | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "id": "425d3acf", | |
| "outputId": "fde1c301-2722-46d7-ce81-7f9b6fa8007e" | |
| }, | |
| "outputs": [ | |
| { | |
| "output_type": "execute_result", | |
| "data": { | |
| "text/plain": [ | |
| "array([0.07104387, 0.07104387, 0.08821099, 0.10181143, 0.16972724,\n", | |
| " 0.11897854, 0.37918407])" | |
| ] | |
| }, | |
| "metadata": {}, | |
| "execution_count": 6 | |
| } | |
| ], | |
| "source": [ | |
| "G.page_rank_svd()" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": null, | |
| "id": "072dcffc", | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "id": "072dcffc", | |
| "outputId": "a400c0cd-b23b-4fe0-a7d7-3f74f42f8730" | |
| }, | |
| "outputs": [ | |
| { | |
| "output_type": "execute_result", | |
| "data": { | |
| "text/plain": [ | |
| "array([0.07206054, 0.07206054, 0.08001527, 0.15025156, 0.19143748,\n", | |
| " 0.1582063 , 0.27596832])" | |
| ] | |
| }, | |
| "metadata": {}, | |
| "execution_count": 7 | |
| } | |
| ], | |
| "source": [ | |
| "G.page_rank_eigen()" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": null, | |
| "id": "131ecea2", | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "id": "131ecea2", | |
| "outputId": "b146d5be-6ba6-4f90-d947-cf5bc5c8c6d2" | |
| }, | |
| "outputs": [ | |
| { | |
| "output_type": "execute_result", | |
| "data": { | |
| "text/plain": [ | |
| "array([0.07207178, 0.07207178, 0.08002893, 0.1502507 , 0.1914247 ,\n", | |
| " 0.15820785, 0.27594426])" | |
| ] | |
| }, | |
| "metadata": {}, | |
| "execution_count": 8 | |
| } | |
| ], | |
| "source": [ | |
| "G.page_rank_iterate()" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": null, | |
| "id": "3ad8015c", | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "id": "3ad8015c", | |
| "outputId": "87054e17-c81c-4b27-e23f-37738e13ef43" | |
| }, | |
| "outputs": [ | |
| { | |
| "output_type": "execute_result", | |
| "data": { | |
| "text/plain": [ | |
| "{0: 0.07206104876573148,\n", | |
| " 1: 0.07206104876573148,\n", | |
| " 2: 0.08001588904240155,\n", | |
| " 3: 0.1502514595698498,\n", | |
| " 4: 0.19143690928592935,\n", | |
| " 5: 0.15820629984651988,\n", | |
| " 6: 0.2759673447238362}" | |
| ] | |
| }, | |
| "metadata": {}, | |
| "execution_count": 9 | |
| } | |
| ], | |
| "source": [ | |
| "G.page_rank_nx()" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": null, | |
| "id": "b09f6a16", | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/", | |
| "height": 319 | |
| }, | |
| "id": "b09f6a16", | |
| "outputId": "df6200f6-a9e5-46c6-da4f-e5209b28bc56" | |
| }, | |
| "outputs": [ | |
| { | |
| "output_type": "display_data", | |
| "data": { | |
| "text/plain": [ | |
| "<Figure size 432x288 with 1 Axes>" | |
| ], | |
| "image/png": "iVBORw0KGgoAAAANSUhEUgAAAb4AAAEuCAYAAADx63eqAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4yLjIsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+WH4yJAAAgAElEQVR4nO3dd1RUd+IF8DtNhiKgKIiRqICIBXshahR7W8XYC4kpqzFqijFmo+Ka34ImurEkUWLbmESiUTGW2DEKiRpjQRGUIhALCgoqImWGKe/3B+tsCEWBYd4Mcz/n7Dm7M2/eXDTk7nvvWySCIAggIiKyElKxAxAREZkSi4+IiKwKi4+IiKwKi4+IiKwKi4+IiKwKi4+IiKwKi4+IiKwKi4+IiKwKi4+IiKwKi4+IiKwKi4+IiKwKi4+IiKwKi4+IiKwKi4+IiKwKi4+IiKwKi4+IiKwKi4+IiKwKi4+IiKwKi4+IiKwKi4+IiKwKi4+IiKwKi4+IiKyKXOwAZBzZeWpEXEhHYmYuclVaOCrl8G3kiHGdm8DFwUbseEREZkMiCIIgdgiquthbOVgblYLo5CwAgFqrN7ynlEshAAho2RAz+3ijvYezSCmJiMwHi8+ChZ+5jiUHE6HS6lDR36JEAijlMiwc5osg/2Ymy0dEZI54q9NCFZdeAgo1+qceKwhAoUaHJQcTAIDlR0RWjVd8Fij2Vg4mbjyDQo2uxOuZ338E9Z0kSKQyAICsrguem76+xDG2Chm2T/dHuya87UlE1olXfBZobVQKVFpdme/VHzQDddsPLvezKq0OYVEpWBfUpabiERGZNU5nsDDZeWpEJ2dV+EyvIoIAnEjKwv08tXGDERFZCBafhYm4kF7h+zlR3+LW55ORuWUeVDcul3mMBEBETMXnISKqrXir08IkZuaWmLLwZ/X6vgaFiwckMgXyE37BvV0hcH/tCyjquZc4TqXVIzHjsSniEhGZHV7xWZhclbbc92wat4TUxg4SuQIOfv1h81wrFKaeL+c8mpqKSERk1lh8FsZRWYmLdIkEQNkPAx2VCuMEIiKyMCw+C+PbyBE28tJ/bXpVHgrTLkDQFkHQ65B35QTUt+Jh69m51LFKuRS+7nVNEZeIyOzwGZ+FGdu5CVYdSy71uqDXIeeXcGgepAMSKRQuTdBwdDAU9Z8rfSyAsZ2amCAtEZH5YfFZmAYONujj0xCRCXdLTGmQ2TnB/dVVT/28RAL0bdmQC1cTkdXirU4LNCvAG0q5rEqfVcplmBngbeRERESWg8Vngdp7OGPhMF/YKir312erkGLhMF8uV0ZEVo3FZ6GG+TiiZcFV2CpkxYM3KyCRANAWQfXbNjTV3DJJPiIic8XiszB6vR6bNm1C48aNsW/lPGyf7o/Brd1gI5dC+ZfRnkq5FDZyKQa3dkOPwt9x/dgWDBo0CO3bt8fBgwfB9cmJyBpxdwYLcvHiRbz88sv4448/UFBQAFdXV9y9excAcD9PjYiYdCRmPEauSgNHpQK+7nUxtlPxDux79uzBlClTUFBQYDhfTEwMOnbsKNaPQ0QkCo7qtCAhISFISkqCVlu8esvzzz9veM/FwQZv9vYq97NdunSBXl+81JlUKkV4eDhLj4isEm91WpCdO3di4sSJkEgkkEgkaNas2TN/9rnnnoONjQ2ef/559OjRAxcuXKi5oEREZoxXfBYkJycHx44dw86dO/HFF1+gR48ez/xZiUSCI0eOoE2bNigqKkLnzp3RvXt3jBs3rgYTExGZHz7jsyCvvvoqnJyc8Pnnn1f7XDExMRgyZAiio6PRqlUrI6QjIrIMvOKzEJGRkYiKikJ8fLxRztepUyd8+umnGD16NM6ePYu6dbl2JxFZB17xWYD8/Hz4+fkhLCwMQ4YMMeq5p0+fjocPH2LHjh2QPG1CIBFRLcDiswBz587FvXv3sGXLFqOfW6VS4cUXX8SkSZPw/vvvG/38RETmhsVn5s6dO4cRI0YgPj4eDRo0qJHvuHHjBrp3744dO3agd+/eNfIdRETmgtMZzJhGo8Ebb7yBlStX1ljpAUDTpk3x3XffYdKkSbhz506NfQ8RkTlg8Zmx5cuXo0mTJpg0aVKNf9egQYPw1ltvYdy4cSgqKqrx7yMiEgtvdZqpxMRE9OrVCzExMSVWaKlJer0egYGB8PT0NMqUCSIic8QrPjOk1+sxbdo0LF682GSlBxQvZbZlyxYcOHAA27ZtM9n3EhGZEovPDG3YsAE6nQ4zZ840+Xc7Oztj165deOedd4w2Z5CIyJzwVqeZSU9PR8eOHREdHY3WrVuLluO7775DaGgozp07BycnJ9FyEBEZG4vPjAiCgMDAQHTu3BmLFy8WOw5mzZqFO3fu4Mcff+TkdiKqNXir04zs3LkTaWlpmD9/vthRAAArV65ERkYGli9fLnYUIiKj4RWfmbh//z7atm2LH3/8ES+88ILYcQzS09PRtWtXhIeHo3///mLHISKqNhafmXjttdfg6OholtMIjh8/jilTpuDs2bPw8PAQOw4RUbWw+MxAZGQkpk2bhri4OLPdJWHZsmXYvXs3oqOjYWNjI3YcIqIqY/GJrCZ3XjAmQRAwZswYuLu7Y+3atWLHISKqMhafyGpy5wVje/ToEbp27Yrg4GC88sorYschIqoSFp+ITLHzgrHFx8ejb9++OHbsGNq3by92HCKiSuN0BpGYaucFY2vbti2++OILjBkzBg8fPhQ7DhFRpfGKTyRLlizBqVOncODAAYucHP7uu+8iLS0Ne/fuhVTK//9ERJaDxScCMXZeMLaioiL069cPQ4YMQXBwsNhxiIieGYvPxPR6Pfr06YPx48fj7bffFjtOtdy5cwddu3bF5s2bMWjQILHjEBE9E96jMrH169eLtvOCsTVu3Bhbt27FK6+8ghs3bogdh4jomfCKz4Se7LwQFRWFNm3aiB3HaFauXIlt27bh119/hVKpFDsOEVGFWHwmYm47LxiTIAiYMGECnJycsHHjRrHjEBFViLc6TWTnzp1ITU3FRx99JHYUo5NIJPjPf/6DkydP4uuvvxY7DhFRhXjFZwLmuvOCsSUkJKBPnz44fPgwOnXqJHYcIqIysfhMwJx3XjC2iIgIzJs3D+fPn4eLi4vYcYiISmHx1bAnOy/Ex8fDwcFB7Dgm8cEHH+DKlSvYv38/ZDKZ2HGIiErgM74alJ+fjzfffBNfffWV1ZQeAHz66acoLCxESEiI2FGIiErhFV8Nmjt3Lu7evYvw8HCxo5hcZmYmunTpgvXr12P48OFixyEiMmDx1RBL3HnB2E6dOoXRo0fjt99+g6enp9hxiIgA8FZnjXiy88KKFSustvQAoGfPnggODsaYMWNQWFgodhwiIgC84quS7Dw1Ii6kIzEzF7kqLRyVcvg2csS4zk3g4mBj8TsvGJMgCJgyZQrq1KmDzZs3W/2fBxGJj8VXCbG3crA2KgXRyVkAALVWb3hPKZdCAND1OTscXf0Bzh2JQNOmTUVKal7y8/Ph7++P2bNn48033xQ7DhFZORbfMwo/cx1LDiZCpdWhoj8xCQCFFPjniDYI8m9mqnhmLzk5Gb169cL+/fvRrVs3seMQkRXjM75nUFx6CSjUVFx6ACAAKNIDSw4mIPzMdVPEswg+Pj5Yv349xo0bh6ysLLHjEJEV4xXfU8TeysHEjWdQqNGV+X7+1WjknNoGXW4WZPb14DL8PSg92gIAbBUybJ/uj3ZNnE0Z2azNnz8f586dw5EjRzi5nYhEwSu+p1gblQKVtuzSK/zjIh5GfYMGw96Dx/s74TblU8idGxneV2l1CItKMVVUixASEgJBELBo0SKxoxCRlWLxVSA7T43o5Kxyb28+Ovk9nHpOgs1zvpBIpJDXbQB53f9NXxAE4ERSFu7nqU2U2PzJ5XJs27YN4eHh2Lt3r9hxiMgKsfgqEHEhvdz3BL0O6owU6Ase4fa6aUhfOxUPjn4FvaZkyUkARMSUfx5r5Orqip07d2LatGm4du2a2HGIyMqw+CqQmJlbYsrCn+nycwC9FgVJp+AWtAzur32BortpeHR6e4njVFo9EjMemyKuRenevTv+7//+D6NHj0Z+fr7YcYjIirD4KpCr0pb7nkRhAwCo23kE5A71IbNzQt2uo1CYer6M82hqLKMlmzFjBjp16oTp06eDY6yIyFRYfBVwVMrLfU+mdICsbsnlyMpblcRRqTBqrtpCIpHgq6++wpUrV7B27Vqx4xCRlWDxVcC3kSNs5OX/ETn4DcDjC/uhy8+BTpWH3HN7YOfdtcQxSrkUvu51azqqxbKzs8OuXbvwr3/9C6dPnxY7DhFZARZfBcZ2blLh+049J6KOewvc3vAm7mycgTpuXnDqMaHEMQKAsZ0qPo+18/Lywtdff40JEybg7t27YscholqOE9ifYvqW84hMuPvUFVvKIpEAg1u7YV1QF+MHq4X++c9/4pdffsGxY8cgl5d/m5mIqDp4xfcUswK8UUdWtR0FlHIZZgZ4GzlR7bV48WLY2Nhg/vz5YkcholqMxVcOQRCQmJiIzxa8jeyjG6CQVu6Sz1YhxcJhvlyurBJkMhm2bt2KnTt3YteuXWLHIaJaisX3F1evXsXUqVPh6uqKdu3aITw8HN7IwOIRbWGrkOFp28lJJMVrdC4c1oq7M1SBi4sLIiIiMGPGDCQmJoodh4hqIT7j+4uIiAiMHz/eMK9MLpfj6tWraNGiBS6n5yAsKgUnkrKg0RRBL/nfc6gn+/H1bdkQMwO8eaVXTZs2bcLKlStx9uxZODg4iB2HiGoRFl8Z/Pz8EB8fDwDo0KEDLl68WOL9r77egn9uPoCg2R8hV6WBo1IBX/e6GNupeAd2Mo6///3vePz4MX744Qfu3E5ERsPi+xO9Xo9+/frh1KlTGDJkCPbv349vvvkGU6dONRxz//59NGnSBGq1GhqNhlvr1CCVSoVevXphypQpmDNnjthxiKiW4Jjx/yoqKkKnTp2QlpaGixcvonXr1tiwYQPGjx9vOEaj0WDYsGFQqVSQy+W4fPkyOnbsKGLq2k2pVCIiIgLdu3dH586d0bt3b7EjEVEtwOIDkJubi9atWyM/Px/Jyclo0qR4wvmMGTNKHPfWW28hLi7O8L+jo6NZfDWsWbNm+PbbbzFp0iScP38e7u7uAIq3jIq4kI7EzFzkqrRwVMrh28gR4zrzdjMRVczqb3Wmp6fDz88P9vb2uHLlCpycnMo8Tq/Xo3PnzoiPj4dWW7x49YABAxAZGWnKuFYrJCQEp0+fxqcbtmFtVAqik7MAoMTuGU8GGAW0bIiZfbzR3oMDjIioNKsuvvj4eHTr1g2enp6IiYlBnTp1nvqZOXPmYPPmzXjnnXegVCqxYMECEyQlvV6PTyNOYkt8AVRaXYUr6UgkxYsHLBzmyyklRFSK1RZfVFQUBg0ahJ49e+Lnn3+GVPpsUxq7dOkCZ2dnHDt2rIYT0p+Fn7mOJQcTUKgpe3/EshQvIsD5lERUklVOYN++fTv69++PMWPG4MSJE89cegCQlJSE4cOH12A6+qvYWzlYcjCxVOnpCh/j3q5Q3FwxBulhryH/SlSJ9ws1eiw5mIjL6TkmTEtE5s7qim/16tWYNGkS3nvvPWzbtq1Sn3348CHy8vIwZcqUGkpHZVkblQKVVlfq9QdHv4JEpkCTt8PRYMQHuH80DEVZN0oco9LqEBaVYqqoRGQBrKr4PvzwQ7z//vv497//jRUrVlT681u3boWdnR1cXV1rIB2VJTtPjejkrFLP9PRFKhQknYZz7yBI69hC6dEGdt7dkX/lRInjBAE4kZSF+3lqE6YmInNmNcUXFBSEFStWIDw8HHPnzq3SOfbv3w8fHx8jJ6OKRFxIL/N17YPbkEhlUNR/zvCawrU5NH+54gMACYCImLLPQ0TWp9bP49Pr9Rg4cCB++eUXHD16FP3796/yuS5evIjJkycbMR09TWJmbokpC0/oNYWQ2NiWeE1qYwd9UWGpY1VaPRIzHtdYRiKyLLXyiu/48ePQ6/XQaDTo0KEDTp8+jQsXLlSr9PR6Pe7du4egoCAjJqWnyVVpy3xdqrCFoC5ZcoK6ANI6tmUen6vSGD0bEVmmWld8V69eRf/+/fHaa6/B09MTN2/eRFJSEtq1a1et8x4+fBgymQydOnUyUlJ6Fo7Ksm9KyOs/B0Gvg+bBbcNrRff+gKJh03LOo6iRfERkeWpd8X311VeQyWT47rvvkJOTg+vXr+P555+v9nl37NhhWMqMTMe3kSNs5KX/MZXWUcKu5QvI+fV76ItUUKVfRUHK77Bv07fUsUq5FL7udU0Rl4gsgMVMYH+WtRmLiopQv3595OfnAyjeS2/dunV44403qv39Pj4+6NSpE3744Ydqn4ueXXaeGj2XHS/zOZ+u8DHuH/wcqusXIbV1RL0+U2HfJqDUcTZyKU7/ox/X8CQiABYwuCX2Vk4FazNmYtWxZMPajD99uwb5+fmQyWSQyWTw9PSErW3Zz3wq68aNGwgNDTXKuejZNXCwQR+fhohMuFtqSoPMti5cxwRX+HmJpHhzYJYeET1h1ld8xctUJT7T2ox1ZBJkH90A+4wYLF++HAMHDoSLi4tRciQlJcHX1xdqtfqZ1vMk44q9lYOJG8+gUFN6EvvT2Cpk2D7dH+2acMFqIipmts/4/rc2Y8WlBxRPUlZrBbgMmIalO37BxIkTjVZ6APDdd9/BxcWFpSeS9h7OWDjMF7aKyv3jWrxWpy9Lj4hKMMviK29txic0D27jxr9fQvZPn5V4vUiPGlmb8dixY9UeFUrVE+TfDAuHtYKtQgaJ5GlHC9BrVAhsqucC1URUilkWX3lrMz7x4Og62Li3KPO9mlibMSEhAUOHDjXqOanygvybYft0fwxu7QYbuRTKv4z2VMqlsJFL0d+nAe5+/xH+PX0kevfuXWLzYCIis3vGV9EoPgDIvxqNguTfoHDxgDYnAw1GfFDqGGOO4svNzYWTkxPu3Llj2P2bxHc/T42ImHQkZjxGrkoDR6UCvu51MbZT8ShfJycn5ObmQiKRQKFQYN68eRycREQAzHBUZ3lrMwKAXl2AnF+/h9ukpciLPVLucU/WZnyzt1e18/zwww+wtbVl6ZkZFwebCv9+vby8cPHiRQiCAKVSiT59+pgwHRGZM7O71Vne2owAkPPLFji0HwS5Y4MKz2HMtRn37dsHb29vo5yLTMfPzw9SqRR2dnaoX78+Bg4cKHYkIjITZld85a3NWHQ3DaobsXDsGviM5zHO2owxMTEICAgwyrnIdKZNm4avv/4aKSkpuH37NubNmyd2JCIyE2Z3q7O8tRlVN+OgfXQX6WGvAQCEIhUg6JGR/S7cX/u8jPNUb23Grl27wsbGBhkZGWjVqhUKCgpgZ2dXrXOS6fTq1Qu9evUCAISFheHNN9/E5MmT0bFjR5GTEZHYzG5wy7roVKw6llzqdqdeoyqxGn/u2R+hfXQX9QfPgszOqcSxSrkUcwb6VOsZn5+fH+Lj44vPp1TCx8cHsbGxVT4fiatPnz64evUq7t69C6nU7G50EJEJmd2/AcZ2LnshaKlCCZlDPcN/JAolJPI6pUoPAAQAYztVb0HpIUOGGP67RCLB6tWrq3U+EtehQ4dQWFiIiRMnih2FiERmdsX3ZG3Gp01Sdn5xSplTGSQA3IUHuHA6GnFxcbh//z6qclHbv39/SCQSyGQyLF++HH37ll71nyyHnZ0ddu3ahYiICBw4cEDsOEQkIrO71QlUb21GGXRI/2Yu8OAmbGxsoFKp0KFDB5w9e7ZS53kyf693796Ijo6udA4yT5MnT8aePXtw7949ODg4iB2HiERgdoNbgP+tzVi8VmfZUxvKYquQYv7Q1vh0rwIJmUUoKiqCUqnEjBkznvrZv257ZCPRw/mFcQjfub46PwqZmfDwcLi7u2Pw4ME4deqU2HGISARmecX3RGV2Z1DKZVg4zBdB/s1w6dIl9OjRAyqVCgqFAmPHjsWqVavg6upa6rMVbXsklwiQyWSGbY/ae3Cx49rg8uXL6NixI9asWYO33npL7DhEZGKyjz/++GOxQ5SnXRNn9G7RAA/zi3DrYSEUUgm0+v81oFIuhUwqwYBWrlg+ph0Gtm4EAGjUqBFu3ryJ2NhYnDt3Dn/88QdmzJiBBg0aoEOHDpD89wFi+JnreHf7JSTfewytXoBOX7Jd9ZBApxeQlp2PPZfuwNlWzpX+awE3Nzeo1WosWrQIr7/+OhwdHcWOREQmZNZXfH/2tLUZ/yo/Px9xcXHw9/cHAFy8eBHTpk2Do6Mj1q1bh7MP6lTpVurCYa244n8t0bJlSwiCgOTkZLGjEJEJWUzxGYNWq8WaNWuwdN33cBqzGBp9yaGj2T99BtX1WOg1Ksjs68HRfwzqth9c4hhubFp73LlzB02bNsWcOXOwfPlyseMQkYlYVfE98cqGX/HrH7n46w9elHUDinqNIZEroLl/C5lb58N13MewafS/tTolEmBwazesC+pi2tBUIzZs2IC33noLFy5cQIcOHcSOQ0QmYHbz+Gpadp4av9/KK1V6AFCnYVNI5E+WOpNAAgm0DzNKHCMIwImkLNzPU9d4Vqp506dPR48ePTBo0CDo9c9+25uILJfVFV9F2x4BwP0jYbj52Rjc2TgDMof6sPUqfWX3ZNsjqh2OHDmC/Px8TJ48WewoRGQCVld8FW17BAAug2fC4/0dcJuyDLY+L0AiK73YtTG3PSLx2dnZISIiAjt27MChQ4fEjkNENczqiq+8bY/+TCKVQenRBrrH2Xh88WA55zHOtkdkHoYOHYrx48dj7NixKCgoEDsOEdUgqyu+8rY9KpNeX+oZ3//OU71tj8j8bN26Ffb29hg8ePDTDyYii2V1xefbyBE28tI/ti4/B/lXo6EvKoSg16Ew7QLyE6KhbFZ6pJ9SLoW7rR6HDx/G6tWr8fLLL8PPz49D4i2cVCpFZGQkTp8+jfXruVQdUW1llmt11qSxnZtg1bEyJixLJHh88RDuHwkDBD3kTq6o138a7Fp0L3WoAOA/wdOQHBcDqVQKvV6POnXqwNmZc/ssXfv27TFv3jzMnj0bI0aMQOPGjcWORERGZpXz+KZvOY/IhLsVrv9Znifz+JaP9EGPHj2QlJQErbb4ueHQoUMxceJEDB8+HC4uLkZOTabk4+MDiUSCpKQksaMQkZFZ3a1OAJgV4A2lXFalzyrlMswM8IajoyN+//13dO3aFQqFAi1btsSECROwe/duNG/eHH379sXq1avxxx9/GDk9mUJUVBTS0tIwf/58saMQkZFZ5RUf8GTnh+qv1alSqTBmzBgMHToUs2fPBgAUFBTg2LFj2Lt3L3766Se4u7sjMDAQo0aNQseOHQ2LZJN5W7duHWbNmoWLFy+iXbt2YschIiOx2uIDqr7tUWXodDr89ttv2Lt3L/bs2QO1Wo3AwEAEBgaiT58+UCg4OtSc9ezZE9euXUNmZiakUqu8QUJU61h18QHA5fQchEWl4ERSFiQonpz+hFIuhQCgb8uGmBngXe2FqQVBQEJCAvbs2YO9e/fi2rVrGDZsGAIDAzFkyBDUrVu3ej8MGV1+fj5cXV0RGBiIrVu3ih2HiIzA6ovvicpue2QMt2/fxk8//YQ9e/bg9OnT6NWrFwIDAzFy5Ei4u7vXyHdS5R04cAAjRozAoUOHOMePqBZg8ZmJ3NxcHDp0CHv37sWhQ4fQsmVLjBo1CqNGjYKvr6/Y8aze+PHjcfDgQdy7dw92dnZixyGiamDxmaGioiJER0cbbona29sbBsd0794dMlnVRqRS1en1eri5uaF169aIjo4WOw4RVQOLz8wJgoALFy5g79692Lt3L+7evYuRI0ciMDAQAwYMgFKpFDui1bh06RI6d+6M9evX4+9//7vYcYioilh8FiYtLc0wQvTSpUsYMGAARo0aheHDh6N+/fpix6v1PvzwQ6xevRo3b95Eo0aNxI5DRFXA4rNg2dnZ2L9/P/bu3Yuff/4ZXbp0MUyVaNasmdjxaq0WLVpALpcjISFB7ChEVAUsvlriyaT5PXv2YP/+/WjcuDFGjRqFwMBAdOjQgZPmjSg9PR3NmzfHhx9+iCVLlogdh4gqicVXC+l0Opw+fdpwS1Sj0RgGx7z44oucNG8EYWFhePvttxEbG4u2bduKHYeIKoHFV8sJgoCrV68aRoimpqaWmDTv4OAgdkSL1aNHD6SmpiIjI4OruhBZEBaflbl9+zb27duHPXv24LfffsOLL76IUaNGYcSIERysUUl5eXlwdXXF6NGjER4eLnYcInpGLD4r9ujRI8Ok+cOHD6NVq1aGW6ItW7YUO55F2L9/P0aOHIkjR45g4MCBYschomfA4iMAxZPmo6KiDPMFHRwcDINjunfvzlt5FRg7diwOHz6M7OxszqsksgAsPipFr9eXmDSfnZ2NESNGYNSoUejXrx//5f4XWq0WjRo1gp+fH06cOCF2HCJ6ChYfPVVqaqphhOjly5cxcOBABAYGYvjw4ahXr57Y8cxCTEwMunTpgo0bN+KNN94QOw4RVYDFR5WSlZVlmDR//PhxdO3a1XBL9Pnnnxc7nqjmzp2LL7/8Erdu3YKbm5vYcYioHCw+qrKCggJERkYaJs17eHgYBse0a9fOKifNe3l5wcbGBlevXhU7ChGVg8VHRqHVaktMmtfr9Rg5cqRh0rxcLhc7okncvHkTXl5emD9/Pv71r3+JHYeIysDiI6MTBAFXrlwxlGBaWhqGDx+OUaNGYdCgQbV+0vyaNWvw7rvv4vLly2jTpo3YcYjoL1h8VOPS09MNk+bPnDmD3r17GybN19ZnYf7+/rh+/Tru3LnDqSBEZobFRyaVk5NjmDR/5MgRtG7d2vBc0MfHR+x4RvNkVZexY8fiu+++EzsOEf0Ji49Eo1arS0yad3R0NIwQ7datm8VfKe3duxcvvfQSIiMj0b9/f7HjENF/sfjILDyZNP9kMe379+8bBsf069cPNjY2YkesktGjRyMyMhJZWVmc+E9kJlh8ZJZSUlIMg2Pi4uIwaNAgBAYGYtiwYRY1aV6r1cLNzQ3t27fH8ePHxY5DRGDxkQW4d++eYdL8iRMn0K1bNwgM9nwAABHSSURBVMMtUQ8PD7HjPdX58+fRrVs3fP3113j11VfFjkNk9Vh8ZFHy8/NLTJpv2rSpYXCMn5+f2U6anzNnDtauXYv09HS4urqKHYfIqrH4yGJptVqcOnXKcEtUEATDlWCvXr3MbtK8p6cnbG1tceXKFbGjEFk1Fh/VCoIgID4+3jA45vr16yUmzdvb24sdETdv3oSnpyeCg4Px8ccfix2HyGqx+KhWunXrlmHS/O+//46AgAAEBgZixIgRot5q/Pzzz/H+++8jPj4erVq1Ei0HkTVj8VGtl5OTg4MHDxomzbdt29ZwS7RFixYmz9OtWzfcunULt2/fRlFREbRaba1fxo3InLD4yKqo1WqcOHECe/bswb59+1CvXj3D4JguXbqYZNJ8bm4u3Nzc0L9/f1y6dAkBAQEIDw+v8e8lomIsPrJaer0e58+fNzwXfPjwIQIDAxEYGIi+ffvW2KR5rVaLSZMmISIiAgDQtm1bxMXF1ch3EVFpLD6i/7p27ZphhOiVK1dKTJp3dnY22vd88MEHWLVqFfR6PQDA3t4eeXl5Rjs/EVWMxUdUhrt37xomzUdFRaF79+4YNWoURo4cWe1J8/fv38fixYuxadMmqNVqAMDDhw+NWq5EVD4WH9FT5Ofn4+jRo9izZw8OHDiAZs2aGZ4Ltm3btsqT5q9fv47XXnsNUVFRWLNmDWbNmoXsPDUiLqQjMTMXuSotHJVy+DZyxLjOTeDiYJnrlRKZGxYfUSVotVqcPHnScEtUIpEYRoj27NmzSpPmly5dip9OXYbfxA8QnZwFAFBr9Yb3lXIpBAABLRtiZh9vtPfglSFRdbD4iKpIEATExcUZBsfcvHmzxKR5Ozu7ZzpP+JnrCD2QALVOj4p+GyUSQCmXYeEwXwT5NzPOD0FkhVh8REZy8+ZNw6T5s2fPom/fvoZJ8w0bNizzM+FnrmPJwQQUavRlvl8WW4UUC4e1YvkRVRGLj6gGPHz40DBp/ujRo/Dz8zPcEvX29gYAxN7KwcSNZ1Co0Rk+J2g1uH80DKrrl6BX5UHu3Aj1+kyFrVeXEue3Vciwfbo/2jXhbU+iymLxEdUwtVqN48ePGybNu7i4IDAwEDebDsHJ67klbm/qi1TI/X0XHPwGQObUEIWp55G9799o/PoayJ3dDMdJJMDg1m5YF9SljG8kooqw+IhMSK/X4+zZs9i+9yB+knSH9hl+++78Zzacek6CvW/PEq/byKU4/Y9+HO1JVEk1vz4TERlIpVL4+/uj5ZCpkMme/uuny38IzYPbqNPw+VLvSQBExKTXQEqi2o3FRySCxMzcElMWyiLotMje9xkc/PpD4VJ60rxKq0dixuOaikhUa7H4iESQq9JW+L4g6JG9fwUgk6P+wBkVnEdj7GhEtR6Lj0gEjsryJ7oLgoD7B7+ALj8HDV9aAIms/GMdlYqaiEdUq7H4iETg28gRNvKyf/0eHFkLzf1bcB37T0gV5Q9cUcql8HWvW1MRiWqtyq+vRETVNrZzE6w6llzqde2je8i7dBiQKZD+5cuG1+sPmQWHNn1LHKtSqyG7eR46XTPIZLIaz0xUW3A6A5FIpm85j8iEuxUuU1YeiQRoXx+49+MSPHjwAAsWLMDkyZOrtFYokbXhrU4ikcwK8IZSXrUrNaVchn9N7IlTp04hLCwMmzdvRsuWLbFp0yYUFRUZOSlR7cLiIxJJew9nLBzmC1tF5X4Ni9fq9EW7Js6QSCTo168fTpw4gW+//RY7d+6Et7c31q5dC5VKVUPJiSwbi49IREH+zbBwWCvYKmR42rZ+EknxGp3lLVDdq1cvHDlyBBEREThy5Ag8PT2xcuVK5Ofn10x4IgvFZ3xEZuByeg7ColJwIikLEhRPTn/iyX58fVs2xMwA72demPrSpUsIDQ3FyZMn8d5772HWrFmoW5ejQIlYfERm5H6eGhEx6UjMeIxclQaOSgV83etibKeq78B+5coVLFmyBJGRkXj77bfxzjvvwNmZuzqQ9WLxEVmJ5ORkfPLJJ9i3bx9mzJiBOXPmoEGDBmLHIjI5PuMjshI+Pj7YvHkzzp8/j+zsbPj4+GDevHnIzMwUOxqRSbH4iKxM8+bNsX79esTGxkKlUqF169Z49913cfv2bbGjEZkEi4/ISnl4eODLL7/ElStXoFAo4OfnhxkzZuD69etiRyOqUSw+Iivn7u6Ozz77DElJSahfvz46d+6M119/HSkpKWJHI6oRLD4iAgA0bNgQS5cuxbVr19C0aVO88MILCAoKQkJCgtjRiIyKxUdEJdSvXx+LFy9Gamoq2rRpg4CAAIwbNw6xsbFiRyMyChYfEZXJ0dER8+fPR1paGvz9/TF06FAEBgbi/PnzYkcjqhYWHxFVyN7eHnPnzkVqaioGDhyIl156CUOHDsWpU6fEjkZUJZzATkSVolar8e233+KTTz5B8+bNsWjRIgQEBEDytMVGicwEi4+IqkSj0WDr1q1YsmQJXF1dERwcjMGDB7MAyeyx+IioWnQ6HXbs2IHQ0FDY29sjODgYI0aMYAGS2WLxEZFR6PV67N69G6GhoRAEAcHBwRg9ejSkUg4lIPPC4iMioxIEAQcOHEBISAgeP36MhQsXYsKECZDL5WJHIwLA4iOiGiIIAiIjIxESEoLMzEwsWLAAQUFBUCgUYkcjK8fiI6IaJQgCoqOjERISgrS0NHz00Ud49dVXYWNTtf0FiaqLxUdEJnP69GmEhoYiLi4O8+bNw7Rp02Brayt2LLIyfOpMRCbTo0cPHDx4ELt378bx48fh6emJzz77DHl5eWJHIyvC4iMik+vSpQv27NmDI0eO4Ny5c/Dy8sLSpUvx6NEjsaORFWDxEZFo2rVrh+3btyMqKgoJCQnw8vLC4sWL8eDBA7GjUS3G4iMi0bVq1QpbtmzBmTNncPv2bbRo0QLz589HVlaW2NGoFmLxEZHZ8Pb2xqZNmxATE4NHjx6hZcuWmDt3LjIyMsSORrUIi4+IzE7Tpk0RFhaGuLg46HQ6tGnTBrNnz8atW7fEjka1AIuPiMzWc889h9WrVyMhIQH29vbo0KEDpk2bhrS0NLGjkQVj8RGR2XNzc8OyZcuQnJyMRo0aoVu3bpg6dSqSkpLEjkYWiMVHRBbDxcUFISEhSElJgbe3N3r16oVJkyYhPj5e7GhkQVh8RGRxnJ2dsWjRIqSlpaFjx44YMGAARo8ejYsXL4odjSwAi4+ILFbdunXx4YcfIi0tDb1798bf/vY3/O1vf8Pvv/8udjQyYyw+IrJ4dnZ2eO+995Camophw4Zh/PjxGDRoEH799Vexo5EZ4iLVRFTrFBUVYcuWLVi6dCmaNGmCRYsWoX///twVngCw+IioFtNqtdi2bRuWLFmCevXqYdGiRRg6dCgL0Mqx+Iio1tPpdNi1axdCQ0NRp04dBAcHY+TIkZBK+bTHGrH4iMhq6PV67Nu3DyEhIdBoNFi4cCHGjh0LmUwmdjQyIRYfEVkdQRBw6NAhhISE4OHDh1iwYAEmT54MuVwudjQyARYfEVktQRBw/PhxhISE4NatW5g/fz5eeeUV1KlTR+xoVINYfEREAH799VeEhIQgKSkJ//jHP/D6669DqVSKHYtqAJ/sEhEBePHFF3H06FHs2LEDhw4dgpeXF1atWoWCggKxo5GRsfiIiP6ke/fu+Omnn7B//36cPHkSnp6eWLZsGR4/fix2NDISFh8RURk6duyIXbt24eeff0ZsbCy8vLwQEhKCnJwcsaNRNbH4iIgq0KZNG2zduhUnT55EamoqvL29ERwcjOzsbLGjURWx+IiInoGPjw+++eYbnD17Fvfu3YOPjw8+/PBD3L17V+xoVEksPiKiSvD09MSGDRsQGxuLwsJCtGrVCu+++y5u374tdjR6Riw+IqIq8PDwwJdffokrV65ALpfDz88Pb731Fm7cuCF2NHoKFh8RUTW4u7tjxYoVSEpKQr169dCpUye88cYbSElJETsalYPFR0RkBA0bNsTSpUtx7do1eHh44IUXXkBQUBASEhLEjkZ/weIjIjKi+vXr4+OPP0ZqairatGmDgIAAjBs3DrGxsWJHo/9i8RER1QBHR0fMnz8faWlp8Pf3x9ChQxEYGIjz58+LHc3qsfiIiGqQvb095s6di9TUVAwYMAAvvfQShg4ditOnT4sdzWpxkWoiIhNSq9X49ttv8cknn6B58+ZYtGgRAgICuCu8CbH4iIhEoNFo8P3332Pp0qVwdXXFokWLMGjQIBagCbD4iIhEpNPpsGPHDoSGhsLe3h7BwcEYMWIEC7AGsfiIiMyAXq/H7t27ERoaCkEQEBwcjNGjR0Mq5VAMY2PxERGZEUEQcODAAYSEhODx48dYuHAhJkyYALlcLna0WoPFR0RkhgRBQGRkJEJCQpCZmYkFCxYgKCgICoVC7GgWj8VHRGTGBEFAdHQ0QkNDkZqaio8++givvvoqbGxsxI5msVh8REQW4rfffkNISAji4uIwb948TJs2Dba2tmLHsjh8akpEZCFeeOEFHDx4ELt378aJEyfg6emJzz77DHl5eWJHsygsPiIiC9OlSxfs3r0bR44cwblz5+Dp6YklS5bg0aNHYkezCCw+IiIL1a5dO2zfvh3R0dFITEyEl5cXFi9ejAcPHogdzayx+IiILFyrVq2wZcsWnDlzBrdv30aLFi0wf/583Lt3T+xoZonFR0RUS3h7e2PTpk2IiYnBo0eP4Ovri/fffx8ZGRliRzMrLD4iolqmadOmCAsLQ3x8PARBQJs2bTB79mzcvHlT7GhmgcVHRFRLNW7cGKtWrUJCQgLs7e3RsWNHTJs2DWlpaWJHExWLj4iolnNzc8OyZcuQnJyMRo0aoVu3bpg6dSqSkpLEjiYKTmAnIrIyOTk5WLNmDb744gv069cPwcHBaNu2LQAgIyMDv//+O0aNGlXhObLz1Ii4kI7EzFzkqrRwVMrh28gR4zo3gYuDea8qw+IjIrJSjx8/xldffYWVK1eiR48eCA4OxooVK7Bt2zb8/PPP6Nu3b6nPxN7KwdqoFEQnZwEA1Fq94T2lXAoBQEDLhpjZxxvtPZxN9aNUCouPiMjKFRQUYOPGjfjkk0+QlZUFvV4PJycnXL16FY0bNzYcF37mOpYcTIRKq0NFzSGRAEq5DAuH+SLIv1nN/wCVxOIjIiIAwCuvvIKtW7dCp9NBIpHA29sbV69ehVwu/2/pJaBQo3/6if7LViHFwmGtzK78WHxERAQAqFu3LlQqFSQSCXQ6HfR6PZYsWYLhL8/ExI1nUKjRGY7NvfAT8uN+RlHWddi36oMGf5tT5jltFTJsn+6Pdk3M57YndzYkIiIAQGZmJrRaLWQyGaRSKWQyGWxsbDB9y3motLoSx8odXODUYwIK/4iBoCkq95wqrQ5hUSlYF9SlpuM/MxYfEREBAOzt7Uu9lp2nRnRyVqlnenYtewAA1Jkp0Gmyyz2nIAAnkrJwP09tNqM9OY+PiIjKFXEhvdrnkACIiKn+eYyFxUdEROVKzMwtMWWhKlRaPRIzHhspUfWx+IiIqFy5Kq2RzqMxynmMgcVHRETlclQaZyiIo1JhlPMYA4uPiIjK5dvIETby0lUh6HUQtEWAXgcIegjaIgh6XRlnKF7Rxde9bk1HfWacx0dEROXKzlOj57LjpZ7z5fz6PR6d2lbiNaeek+D84pRS57CRS3H6H/3MZlQni4+IiCo0fct5RCbcrXCZsvJIJMDg1m5mNY+PtzqJiKhCswK8oZTLqvRZpVyGmQHeRk5UPSw+IiKqUHsPZywc5gtbReUqo3itTl+zWq4M4MotRET0DJ4sNM3dGYiIyKpcTs9BWFQKTiRlQYLiyelPPNmPr2/LhpgZ4G12V3pPsPiIiKjS7uepERGTjsSMx8hVaeCoVMDXvS7GduIO7ERERGaFg1uIiMiqsPiIiMiqsPiIiMiqsPiIiMiqsPiIiMiqsPiIiMiqsPiIiMiqsPiIiMiqsPiIiMiqsPiIiMiqsPiIiMiqsPiIiMiqsPiIiMiqsPiIiMiqsPiIiMiqsPiIiMiqsPiIiMiqsPiIiMiqsPiIiMiqsPiIiMiqsPiIiMiq/D+fA9a7hBohSAAAAABJRU5ErkJggg==\n" | |
| }, | |
| "metadata": {} | |
| } | |
| ], | |
| "source": [ | |
| "nx.draw(G.nxdag, with_labels=True)\n", | |
| "# The highest ranked node receives links from other high rank nodes" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "id": "979ca571", | |
| "metadata": { | |
| "id": "979ca571" | |
| }, | |
| "source": [ | |
| "# Some graph info" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": null, | |
| "id": "6e932b1b", | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "id": "6e932b1b", | |
| "outputId": "b74cb8bd-5f57-429e-c653-d3f78ed41d86" | |
| }, | |
| "outputs": [ | |
| { | |
| "output_type": "execute_result", | |
| "data": { | |
| "text/plain": [ | |
| "array([[0, 0, 2, 2, 2, 3, 3, 4, 6, 6, 6],\n", | |
| " [2, 5, 0, 1, 3, 4, 6, 6, 3, 4, 5]])" | |
| ] | |
| }, | |
| "metadata": {}, | |
| "execution_count": 11 | |
| } | |
| ], | |
| "source": [ | |
| "G.sparse" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": null, | |
| "id": "a53302cb", | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "id": "a53302cb", | |
| "outputId": "bf2232a6-0361-427e-bdf5-08c5df8ad1a0" | |
| }, | |
| "outputs": [ | |
| { | |
| "output_type": "execute_result", | |
| "data": { | |
| "text/plain": [ | |
| "array([[0, 0, 1, 0, 0, 1, 0],\n", | |
| " [0, 0, 0, 0, 0, 0, 0],\n", | |
| " [1, 1, 0, 1, 0, 0, 0],\n", | |
| " [0, 0, 0, 0, 1, 0, 1],\n", | |
| " [0, 0, 0, 0, 0, 0, 1],\n", | |
| " [0, 0, 0, 0, 0, 0, 0],\n", | |
| " [0, 0, 0, 1, 1, 1, 0]])" | |
| ] | |
| }, | |
| "metadata": {}, | |
| "execution_count": 12 | |
| } | |
| ], | |
| "source": [ | |
| "G.data # i out, j: in" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": null, | |
| "id": "d357bc5f", | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "id": "d357bc5f", | |
| "outputId": "b885236e-e9bb-438d-ce57-daa797d753f4" | |
| }, | |
| "outputs": [ | |
| { | |
| "output_type": "execute_result", | |
| "data": { | |
| "text/plain": [ | |
| "array([1, 5])" | |
| ] | |
| }, | |
| "metadata": {}, | |
| "execution_count": 13 | |
| } | |
| ], | |
| "source": [ | |
| "G.end_nodes()" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": null, | |
| "id": "34dbc86a", | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "id": "34dbc86a", | |
| "outputId": "89ea8561-ba56-42e5-9eff-a65429876731" | |
| }, | |
| "outputs": [ | |
| { | |
| "output_type": "execute_result", | |
| "data": { | |
| "text/plain": [ | |
| "array([[0, 0, 1, 0, 0, 1, 0],\n", | |
| " [0, 0, 1, 0, 0, 0, 0],\n", | |
| " [1, 1, 0, 1, 0, 0, 0],\n", | |
| " [0, 0, 1, 0, 1, 0, 1],\n", | |
| " [0, 0, 0, 1, 0, 0, 1],\n", | |
| " [1, 0, 0, 0, 0, 0, 1],\n", | |
| " [0, 0, 0, 1, 1, 1, 0]])" | |
| ] | |
| }, | |
| "metadata": {}, | |
| "execution_count": 14 | |
| } | |
| ], | |
| "source": [ | |
| "G.adjacency" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": null, | |
| "id": "2169aaab", | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "id": "2169aaab", | |
| "outputId": "db085777-b9e6-4f6f-81ad-7a34ec020d7a" | |
| }, | |
| "outputs": [ | |
| { | |
| "output_type": "execute_result", | |
| "data": { | |
| "text/plain": [ | |
| "array([[2, 0, 0, 0, 0, 0, 0],\n", | |
| " [0, 1, 0, 0, 0, 0, 0],\n", | |
| " [0, 0, 3, 0, 0, 0, 0],\n", | |
| " [0, 0, 0, 3, 0, 0, 0],\n", | |
| " [0, 0, 0, 0, 2, 0, 0],\n", | |
| " [0, 0, 0, 0, 0, 2, 0],\n", | |
| " [0, 0, 0, 0, 0, 0, 3]])" | |
| ] | |
| }, | |
| "metadata": {}, | |
| "execution_count": 15 | |
| } | |
| ], | |
| "source": [ | |
| "G.degree" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": null, | |
| "id": "cd0dc341", | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "id": "cd0dc341", | |
| "outputId": "0ea810f5-c1a6-41cd-914c-a1532e9c7da1" | |
| }, | |
| "outputs": [ | |
| { | |
| "output_type": "execute_result", | |
| "data": { | |
| "text/plain": [ | |
| "array([[ 2, 0, -1, 0, 0, -1, 0],\n", | |
| " [ 0, 1, -1, 0, 0, 0, 0],\n", | |
| " [-1, -1, 3, -1, 0, 0, 0],\n", | |
| " [ 0, 0, -1, 3, -1, 0, -1],\n", | |
| " [ 0, 0, 0, -1, 2, 0, -1],\n", | |
| " [-1, 0, 0, 0, 0, 2, -1],\n", | |
| " [ 0, 0, 0, -1, -1, -1, 3]])" | |
| ] | |
| }, | |
| "metadata": {}, | |
| "execution_count": 16 | |
| } | |
| ], | |
| "source": [ | |
| "G.laplacian" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": null, | |
| "id": "5c2e507f", | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "id": "5c2e507f", | |
| "outputId": "c3a98bef-60a4-4962-eafb-5c688ef9d832" | |
| }, | |
| "outputs": [ | |
| { | |
| "output_type": "execute_result", | |
| "data": { | |
| "text/plain": [ | |
| "array([[ 1, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0],\n", | |
| " [ 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0],\n", | |
| " [-1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0],\n", | |
| " [ 0, 0, 0, 0, -1, 1, 1, 0, -1, 0, 0],\n", | |
| " [ 0, 0, 0, 0, 0, -1, 0, 1, 0, -1, 0],\n", | |
| " [ 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, -1],\n", | |
| " [ 0, 0, 0, 0, 0, 0, -1, -1, 1, 1, 1]])" | |
| ] | |
| }, | |
| "metadata": {}, | |
| "execution_count": 17 | |
| } | |
| ], | |
| "source": [ | |
| "G.incidence # i: nodes j: edges 1: input -1: output" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": null, | |
| "id": "aca3d8f0", | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "id": "aca3d8f0", | |
| "outputId": "8b7e1f75-cd6b-4028-fbd6-af1b0a9c5239" | |
| }, | |
| "outputs": [ | |
| { | |
| "output_type": "execute_result", | |
| "data": { | |
| "text/plain": [ | |
| "array([[ 3, 0, -2, 0, 0, -1, 0],\n", | |
| " [ 0, 1, -1, 0, 0, 0, 0],\n", | |
| " [-2, -1, 4, -1, 0, 0, 0],\n", | |
| " [ 0, 0, -1, 4, -1, 0, -2],\n", | |
| " [ 0, 0, 0, -1, 3, 0, -2],\n", | |
| " [-1, 0, 0, 0, 0, 2, -1],\n", | |
| " [ 0, 0, 0, -2, -2, -1, 5]])" | |
| ] | |
| }, | |
| "metadata": {}, | |
| "execution_count": 18 | |
| } | |
| ], | |
| "source": [ | |
| "BBT = np.matmul(G.incidence, G.incidence.T)\n", | |
| "BBT" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": null, | |
| "id": "affcbf85", | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "id": "affcbf85", | |
| "outputId": "aa1bdf2f-3e22-4933-df1e-4cb64332c061" | |
| }, | |
| "outputs": [ | |
| { | |
| "output_type": "execute_result", | |
| "data": { | |
| "text/plain": [ | |
| "(0, 0)" | |
| ] | |
| }, | |
| "metadata": {}, | |
| "execution_count": 19 | |
| } | |
| ], | |
| "source": [ | |
| "G.laplacian.sum(), BBT.sum()" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": null, | |
| "id": "39f12b0d", | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "id": "39f12b0d", | |
| "outputId": "c10ea20e-a286-46dd-c0da-c3af35793166" | |
| }, | |
| "outputs": [ | |
| { | |
| "output_type": "execute_result", | |
| "data": { | |
| "text/plain": [ | |
| "NodeView((0, 1, 2, 3, 4, 5, 6))" | |
| ] | |
| }, | |
| "metadata": {}, | |
| "execution_count": 20 | |
| } | |
| ], | |
| "source": [ | |
| "G.nxdag.nodes" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": null, | |
| "id": "59bcddde", | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "id": "59bcddde", | |
| "outputId": "31273761-35f5-427e-ceef-f5567c68350e" | |
| }, | |
| "outputs": [ | |
| { | |
| "output_type": "execute_result", | |
| "data": { | |
| "text/plain": [ | |
| "OutEdgeView([(0, 2), (0, 5), (2, 0), (2, 1), (2, 3), (3, 4), (3, 6), (4, 6), (6, 3), (6, 4), (6, 5)])" | |
| ] | |
| }, | |
| "metadata": {}, | |
| "execution_count": 21 | |
| } | |
| ], | |
| "source": [ | |
| "G.nxdag.edges" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": null, | |
| "id": "123eff04", | |
| "metadata": { | |
| "scrolled": false, | |
| "id": "123eff04" | |
| }, | |
| "outputs": [], | |
| "source": [ | |
| "# help(G.nxdag)" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": null, | |
| "id": "e4c765fe", | |
| "metadata": { | |
| "id": "e4c765fe" | |
| }, | |
| "outputs": [], | |
| "source": [ | |
| "" | |
| ] | |
| } | |
| ], | |
| "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.9.5" | |
| }, | |
| "colab": { | |
| "name": "Page_Rank_Sketch.ipynb", | |
| "provenance": [], | |
| "collapsed_sections": [], | |
| "include_colab_link": true | |
| } | |
| }, | |
| "nbformat": 4, | |
| "nbformat_minor": 5 | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment