{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "
\n", "\n", " \n", "## [mlcourse.ai](https://mlcourse.ai) – Open Machine Learning Course \n", "###
Author: Syrovatskiy Ilya, ODS Slack nickname : bokomaru\n", " \n", "##
Tutorial\n", " \n", "###
\"Epidemics on networks with NetworkX and EoN\"" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "With this tutorial, you'll tackle such an established problem in graph theory as **Epidemic dynamics models**.\n", "\n", "Firstly we'll have to deal with loading your own data from the **VKontakte network using it's API**, so we will go through some basic principles of requests and authentification. If you don't have account in this network - I'll give you already created graph on my own friends network (308 people), but with changed names and IDs. Probably, someone doesn't want to show his name and ID for OpenDataScience community (: . Also I will provide you the link to the graph based on social net with changed info for every person. Our main instrument for graph modeling will be the **NetworkX library** in Python.\n", "\n", "Since we get graph created, we are ready to start with somtething interesting. \n", "We'll go over the basic building blocks of graphs (nodes, edges, etc) and create **pseudo random graph** with the same depth and quantity of verteces. \n", "\n", "Then we are going to visualize created graphs - there will be some obvious differences between our graphs. \n", "\n", "Next point is to talk about main theme of this tutorial - Epidemic on Network. Thus, you'll know some new stuff about different models of epidemic's distributions.\n", "\n", "After you get to know basics it's time to go deeper into epidemic modeling. We'll explore the **most spread models** with code in two graphs (real and pseudo-random), and compare the results with python **library for epidemic modeling EoN** for each case. \n", "\n", "Since we have observed everything I planned in this tutorial, it'll be the time to look at results we got while getting in the world of network, and then - make a conclusion.\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "Here you can get familiarized with the content more properly:\n", "\n", ">> **TABLE OF CONTENTS** :\n", "\n", "0. **First meeting with graphs and libraries**\n", "\n", " 0.1 Intro \n", " 0.2 Packages installation\n", " 0.3 Packages importing\n", " \n", "> \n", "1. **Creation of a real Graph** :\n", " \n", " 1.1 Complex long start:\n", " \n", " 1.1.1 Fast (no) start with VK API \n", " 1.1.2 Loading your social net friends\n", " 1.1.3 Forming correct graph\n", " 1.1.4 (optional) Replacing real people's names and ID with random generated\n", "\n", " 1.2 Lazy fast start:\n", " \n", " 1.2.1 Uploading data for building graph\n", " 1.2.2 Building Graph with NetworkX\n", " 1.2.3 Saving created Graph \n", " \n", "> \n", "2. **Inspection of the Graph** \n", "\n", " 2.1 Loading graph from source\n", " \n", " 2.2 Creation of a pseudo-random Graph \n", "\n", " 2.3 Graph Visualization\n", "> \n", "3. **Introduction in Epidemics on Networks**\n", " \n", " 3.1 Basics of epidemic modeling\n", " \n", " 3.2 Connected components\n", "\n", "> \n", "4. **SI Model** \n", "\n", " 4.1. Statement of the model \n", " 4.2. Implementation in Real Graph\n", " 4.3. Implementation in Pseudo-random Graph\n", " 4.4. Compare with EoN modeling\n", " \n", "> \n", "5. **SIR Model** \n", " \n", " 5.1. Statement of the model \n", " 5.2. Implementation in Real Graph\n", " 5.3. Implementation in Pseudo-random Graph\n", " 5.4. Compare with EoN modeling \n", "\n", "> \n", "6. **SIS Model**\n", " \n", " 6.1. Statement of the model \n", " 6.2. Implementation in Real Graph\n", " 6.3. Implementation in Pseudo-random Graph\n", " 6.4. Compare with EoN modeling \n", "\n", "> \n", "7. **Conclusion**\n", "\n", "> \n", " \n", "> \n", "\n", "\n", "\n", "\n", "\n", "P.S. materials are based on :\n", "> Courses about networks in HSE(Higher School of Economics National Research University)\n", "\n", "> Couple of usefull ideas about EoN I got from the official EoN page https://media.readthedocs.org/pdf/epidemicsonnetworks/latest/epidemicsonnetworks.pdf\n", "\n", "> One example for SIR theory taken from :\n", "https://scipython.com/book/chapter-8-scipy/additional-examples/the-sir-epidemic-model/\n", "\n", "> One example for SIS theory taken from :\n", "https://chengjunwang.com/post/en/2013-03-14-learn-basic-epidemic-models-with-python/\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ ">>> ## 0. First meeting with graphs and libraries" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ ">> ### 0.1 Intro" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "\n", " Since we live in the 21th centure, almost all people have accounts in different networks, where they can be closer to their friends wherevere they are. \n", " As it plays significant part of our lives, analysis in this sphere is an amazing opportunity to know something interesting about ourselves and our friendship.\n", "\n", "\n", "\n", "The nice thing about graphs is that the concepts and terminology are generally intuitive. Nevertheless, here's some basic lingo:\n", "\n", "Graphs are structures that map relations between objects. The objects are referred to as nodes and the connections between them as edges in this tutorial. Note that edges and nodes are commonly referred to by several names that generally mean exactly the same thing:\n", "\n", "node == vertex == point\n", "edge == arc == link\n", "\n", " For implement graph in our analysis it's good idea to use some libraries. \n", "\n", "**Firstly**, it's NetworkX library. NetworkX is the most popular Python package for manipulating and analyzing graphs. Several packages offer the same basic level of graph manipulation, but, most likely, NetworkX is the best.\n", "\n", "**Secondly**, it's EoN library. EoN (Epidemics on Networks) is a Python module, that provides tools to study the spread of SIS and SIR diseases in networks (SIR and SIS definition I'll provide in the chapter 6). EoN is built on top of NetworkX.\n", "\n", "**Thirdly**, since we want to get our friendlist from VK, we have to use their API - that means we need some libraries for requests. If you are not VK user, you can change a bit code in this notebook to get your friends, for example, from Facebook. I am sure, that is pretty the same.\n", "\n", "**Finally**, we will need usual basic libraries you already know (I hope) such as matplotlib, Garbage Collector interface, pandas, etc. \n", "\n", "\n", "> Let's start from installing NetworkX and EoN and importing everything we will need : \n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ ">> ### 0.2 Packages installation" ] }, { "cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [], "source": [ "! pip install networkx\n", "! pip install EoN\n", "\n", "# for python3 use: python3 -m pip \n", "# instead of pip" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ ">> ### 0.3 Packages importing" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Now import all libraries that we will use in this tutorial:" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [], "source": [ "# System\n", "import os\n", "import sys\n", "import time\n", "import tqdm\n", "import gc\n", "\n", "\n", "# Basics \n", "import pandas as pd\n", "import random\n", "import numpy as np\n", "import copy\n", "\n", "\n", "# Graph analysis\n", "import networkx as nx\n", "import EoN\n", "\n", "\n", "# Usefull modules/functions\n", "import scipy as sp\n", "from numpy.linalg import eig\n", "from scipy.integrate import odeint\n", "\n", "\n", "# Get friends from network \n", "import requests\n", "import json\n", "\n", "\n", "# Visualization \n", "import matplotlib.pyplot as plt\n", "%matplotlib inline\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ ">>> ## 1. Creation of a real Graph \n", "\n", ">> ### 1.1 Complex start\n", "\n", "If you are NOT VK user, you can skip this part and jump to loading already created data for graph (**Lazy fast start**). But probably, you can get some new really interesing information in this part for your future researches. There will be not only work with API, but also random generating people with saving their relationships!\n", "\n", "\n", ">#### 1.1.1 Fast start with VK API\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "API stands for Application Programming Interface, or an interface for programming applications. In the case of web applications, the API can provide data in a format other than the standard HTML, which makes it convenient to use while writing different applications. Third-party public APIs most often provide data in one of two formats: XML or JSON.\n", "\n", "Based on the API: various mobile and desktop clients for Twitter and Vkontakte are built. APIs have high-quality and well documented APIs.\n", "\n", "The VKontakte API is described in the https://vk.com/dev documentation and, more specifically, https://vk.com/dev/api_requests.\n", "\n", "For example : \n", "https://api.vk.com/method/getProfiles?uid=59249080. \n", "\n", "We received the answer in json format: (I was authenticated. And yes, it's my ID)\n", "\n", "{\"response\":[{\"uid\":59249080,\"first_name\":\"Ilya\",\"last_name\":\"Syrovatskiy\",\"hidden\":1}]}\n", "\n", "Else you got an error also in json: \n", "\n", "{\"error\":{\"error_code\":5,\"error_msg\":\"User authorization failed: no access_token passed.\",\"request_params\":[{\"key\":\"oauth\",\"value\":\"1\"},{\"key\":\"method\",\"value\":\"getProfiles\"},{\"key\":\"uid\",\"value\":\"59249080\"}]}}" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "In order to use all the features of the VK API, you need to get an access token account. To do this you will need to [create a standalone application](https://vk.com/editapp?act=create).\n", "\n", "After we created the application you can find access token in the [Applications](https://vk.com/apps?act=manage) section." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Many VK API methods assume the presence of a private token that must be passed as a parameter when executing the request. The process of obtaining a token is described in the documentation: https://vk.com/dev/access_token\n", "\n", ">Attention! Token is called private for a reason. The person possessing it can perform a variety of actions on your behalf. Do not show it to anyone.\n", "\n", "In short, you will be given the ID of your application and the list of access rights, that you want to provide to the user of the API. Then you need to specify this data as parameters in the URL of the following format \n", "\n", "https://oauth.vk.com/authorize?client_id={APP_ID}&scope={APP_PERMISSIONS}&response_type=token\n", "\n", ", confirm your intention to provide access and copy the current token from the URL in the opened window.\n", "\n", "For example: " ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "'https://oauth.vk.com/authorize?client_id=8888888&scope=&response_type=token'" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# your app ID here : \n", "APP_ID = 8888888\n", "\n", "# your additional permissions: (here no additional permissions)\n", "PERMISSIONS = \"\"\n", "AUTH_URL = \"https://oauth.vk.com/authorize?client_id={}&scope={}&response_type=token\".format(APP_ID, PERMISSIONS)\n", "AUTH_URL" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Click on this link and you'll get to the page with address : \n", "\n", "https://oauth.vk.com/blank.html#access_token=5614afdcc2bcd42cea3d9c5edc130101dd4be6639b484131870dc12337e5b74b94411de69f0996379dd6b&expires_in=86400&user_id=59249080\n", "\n", "where string after access_token= \n", "\n", ">5614afdcc2bcd42cea3d9c5edc130101dd4be6639b484131870dc12337e5b74b94411de69f0996379dd6b \n", "\n", "your access token. \n", "\n", "Let's keep it." ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [], "source": [ "TOKEN = \"5614afdcc2bcd42cea3d9c5edc130101dd4be6639b484131870dc12337e5b74b94411de69f0996379dd6b\"" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Queryings to VK API**\n", "\n", "After receiving a private token, you can safely perform requests to the API using the methods you need (https://vk.com/dev/methods). The request format is as follows: \n", "\n", "https://api.vk.com/method/METHOD_NAME?PARAMETERS&access_token=ACCESS_TOKEN\n", "\n", "For example, to get information about a user with id 59249080, you need to run the following query:" ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [], "source": [ "# Paste here your user ID : \n", "uid = 59249080\n", "res = requests.get(\n", " \"https://api.vk.com/method/users.get\",\n", " params={\"user_ids\": uid,\n", " \"fields\": \"nickname, screen_name, sex, bdate, city, country, timezone, counters, photo_medium\",\n", " \"access_token\": TOKEN,\n", " \"version\": 5.85}).json()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "You can experiment here, just look into API documentation. Requests to API are really usefull: you can build your own web app (using Python and Django), then make correct Auth and connection to API server, and so you will be able to get almost all information you want automatically. For example, you can mining posts, people profiles, etc. with respect to your aims, and then do a research in something amazing in society.\n", "\n", "OK, let's continue:\n", "\n", "If token is not correct or it is already outdated, you will get an error : " ] }, { "cell_type": "code", "execution_count": 25, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "{'error': {'error_code': 5,\n", " 'error_msg': 'User authorization failed: invalid access_token (4).',\n", " 'request_params': [{'key': 'oauth', 'value': '1'},\n", " {'key': 'method', 'value': 'users.get'},\n", " {'key': 'version', 'value': '5.85'},\n", " {'key': 'fields',\n", " 'value': 'nickname, screen_name, sex, bdate, city, country, timezone, counters, photo_medium'},\n", " {'key': 'user_ids', 'value': '59249080'}]}}" ] }, "execution_count": 25, "metadata": {}, "output_type": "execute_result" } ], "source": [ "res" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**VK API Restrictions**\n", "\n", "There are limited number of requests via VK API - no more than three requests per second. \n", ">There can be maximum 3 requests to API methods per second from a client. \n", "\n", ">Maximum amount of server requests depends on the app's users amount. \n", "If an app has less than 10 000 users, 5 requests per second, up to 100 000 – 8 requests, up to 1 000 000 – 20 requests, 1 000 000+ – 35 requests. \n", "\n", ">If one of this limits is exceeded, the server will return the following error: 'Too many requests per second'. \n", "\n", ">If your app's logic implies many requests in a row, check the execute method. \n", "\n", ">Except the frequency limits there are quantitative limits on calling the methods of the same type. By obvious reasons we don't provide the exact limits info. \n", "\n", ">Excess of a quantitative limit access to a particular method will require captcha (see captcha_error). After that it may be temporarily limited (in this case the server doesn't answer on particular method's requests but easily processes any other requests).\n", "\n", "You can pause when performing any operation in Python using the sleep function from the time module. To do so you must pass the number of seconds for which the program will be suspended:" ] }, { "cell_type": "code", "execution_count": 26, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "0\n", "1\n", "2\n", "3\n", "4\n" ] } ], "source": [ "for i in range(5):\n", " time.sleep(.5)\n", " print(i)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We already saw that we can get response errors in JSON, so you have to check everything before and after querying to avoid getting false and incorrect information. \n", "\n", "Also, there are many different subtleties of usage API. For example, to get a list of friends of a user, you need to use the friends.get method, which can return both a simple friend list and detailed information about each friend, depending on whether the fields parameter is specified (if not specified, simply returns the ID list). And if the fields parameter is specified, then for one request you cannot get information about more than 5000 people.\n", "\n", "Since you've created your APP and got APP ID and token, you are ready to download your friends. \n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ ">#### 1.1.2 Loading your social net friends" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "Let's define function for it:" ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [], "source": [ "def get_friends_ids(user_id, fields = \"\"):\n", " res = requests.get(\n", " \"https://api.vk.com/method/friends.get\",\n", " params={\"user_id\": user_id,\n", " \"fields\": fields,\n", " \"access_token\": TOKEN,\n", " \"version\": 5.85}).json()\n", " # also you can add access token in the request, receiving it via OAuth 2.0\n", " if res.get('error'):\n", " print( res.get('error'))\n", " return list()\n", " return res[u'response']" ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [], "source": [ "# asking for friends and their gender \n", "# notice that gender is in the format 1=female, 2=male\n", "\n", "# uid supposed to be here your user ID to get YOUR friends\n", "full_friends = get_friends_ids(uid, [\"name\", \"sex\"])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ ">#### 1.1.3 Forming correct graph\n", "\n", "After we've downloaded friends, now it's time to download all friends of your friends. \n", "\n", "We will only make our research in graph of your friends only, but for getting correct links between each other we have to load graph of depth 2 (your friends and friends of your friends).\n", "\n", "Loading will take some time, something about 10 minutes (depends on total quantity of people, your system and internet connection), so you can make a tea/coffee in this pause :)" ] }, { "cell_type": "code", "execution_count": 30, "metadata": {}, "outputs": [], "source": [ "full_graph = {}\n", "for i in tqdm.tqdm_notebook(full_friends):\n", " full_graph[i[\"user_id\"]] = get_friends_ids(i[\"user_id\"])\n", " time.sleep(.3)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "I recommend you to save this data on your local storage to prevent repeating of loading and waiting : " ] }, { "cell_type": "code", "execution_count": 275, "metadata": {}, "outputs": [], "source": [ "with open(\"full_graph_depth2.txt\", \"w+\") as f:\n", " f.write(json.dumps(full_graph))\n", "\n", "with open(\"full_friends.txt\",\"w+\") as f:\n", " f.write(json.dumps(full_friends))\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Now we can continue. The next step is optional, you can just read what is happening there without running a code.\n", "\n", "So I will replace real people's names and ID with random generated. \n", "\n", "Here I provide for you links to 2 sets : names and surnames. These sets I will use for random generating people's names on already existing graph(!) - nodes and edges are kept unchanged:\n", "\n", "names : \n", ">go to https://www.ssa.gov/oact/babynames/limits.html\n", " \n", " then download National data \n", " in ZIP file take yob2017.txt\n", " \n", "surnames : \n", ">go to https://github.com/smashew/NameDatabases/blob/master/NamesDatabases/surnames/us.txt\n", " \n", " download surnames as us.txt\n", "\n", ">\n", "> Or you can load all needed data from my repo: https://github.com/Mercurialll/tutors_and_projs/tree/master/jupyter_english/tutorials\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ ">#### 1.1.4 (optional) Replacing real people's names and ID with random generated" ] }, { "cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [], "source": [ "names = pd.read_csv(\"yob2017.txt\", header=None)\n", "names.rename(columns={0: 'name', 1: 'sex', 2: 'Popularity'}, inplace=True)\n", "\n", "surnames = pd.read_table(\"us.txt\", header=None)\n", "surnames.rename(columns={0: 'surname'}, inplace=True)\n" ] }, { "cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [], "source": [ "def get_random_people(full_friends, names, surnames):\n", " n_people = len(full_friends)\n", " n_m = 0\n", " n_f = 0\n", " \n", " true_id_f = []\n", " true_id_m = []\n", " for friend in full_friends:\n", " if friend['sex'] == 2:\n", " n_m += 1\n", " true_id_m.append(friend['uid'])\n", " else:\n", " n_f += 1\n", " true_id_f.append(friend['uid'])\n", " print(\"people number: \", n_people, \", men: \", n_m, \", women: \", n_f)\n", "\n", " # take only top popular names for both Female and Male : \n", " names_f = names.query('sex == \"F\"')[:n_f].name.values\n", " names_m = names.query('sex == \"M\"')[:n_m].name.values\n", "\n", " # take random n_people surnames : \n", " random.seed(17)\n", " rand_indc = np.random.choice(a=range(len(surnames)), size=n_people, replace=False)\n", " s_names = surnames.surname.values[rand_indc]\n", " # separate on female/male\n", " s_names_f = s_names[:n_f]\n", " s_names_m = s_names[n_f:]\n", " \n", " # we will take from here random IDs of users:\n", " ids = np.random.choice(a=range(1001, 9999), size=n_people, replace=False)\n", " # separate on female/male\n", " id_f = ids[:n_f]\n", " id_m = ids[n_f:]\n", " \n", " random_f = pd.DataFrame(data={'uid': id_f, 'first_name': names_f, 'last_name': s_names_f, \n", " 'true_id': true_id_f, 'user_id': id_f, 'sex': 1})\n", " random_m = pd.DataFrame(data={'uid': id_m, 'first_name': names_m, 'last_name': s_names_m, \n", " 'true_id': true_id_m, 'user_id': id_m, 'sex': 2})\n", " \n", " # merge male and female random sets\n", " random_people = pd.concat([random_f, random_m])\n", " \n", " return(random_people)\n", " " ] }, { "cell_type": "code", "execution_count": 232, "metadata": { "scrolled": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "people number: 309 , men: 207 , women: 102\n" ] }, { "data": { "text/html": [ "
\n", "\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
first_namelast_namesexuiduser_id
0EmmaPlese194129412
1OliviaMckellan145034503
2AvaAbram186238623
3IsabellaBloomquist156585658
4SophiaBerkson180338033
\n", "
" ], "text/plain": [ " first_name last_name sex uid user_id\n", "0 Emma Plese 1 9412 9412\n", "1 Olivia Mckellan 1 4503 4503\n", "2 Ava Abram 1 8623 8623\n", "3 Isabella Bloomquist 1 5658 5658\n", "4 Sophia Berkson 1 8033 8033" ] }, "execution_count": 232, "metadata": {}, "output_type": "execute_result" } ], "source": [ "random_people = get_random_people(full_friends, names, surnames)\n", "random_people.drop(columns=['true_id']).head()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "So here everything is random except of true_id - which is a column of real users IDs (my friends). (I drop it just to show created dataset, but not real IDs).\n", "\n", "**Create new friend list according to the true_id column:**\n", "\n" ] }, { "cell_type": "code", "execution_count": 313, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "CPU times: user 407 ms, sys: 0 ns, total: 407 ms\n", "Wall time: 406 ms\n" ] } ], "source": [ "%%time\n", "full_friends_new = []\n", "for person in full_friends:\n", " #taking new ID from random_people data set according to current user ID: \n", " person_dict = {}\n", " person_data = random_people[random_people['true_id']==person['uid']]\n", "\n", " # keep all parameters from random_people according to current person\n", " person_dict['first_name'] = person_data.first_name.values[0]\n", " person_dict['last_name'] = person_data.last_name.values[0]\n", " # retyping here because of problem with JSON serialization numpy int64\n", " person_dict['sex'] = int(person_data.sex.values[0])\n", " person_dict['uid'] = int(person_data.uid.values[0])\n", " person_dict['user_id'] = int(person_data.user_id.values[0])\n", "\n", " full_friends_new.append(person_dict)\n" ] }, { "cell_type": "code", "execution_count": 243, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[{'first_name': 'Emma',\n", " 'last_name': 'Plese',\n", " 'sex': 1,\n", " 'uid': 9412,\n", " 'user_id': 9412},\n", " {'first_name': 'Liam',\n", " 'last_name': 'Lippy',\n", " 'sex': 2,\n", " 'uid': 9332,\n", " 'user_id': 9332}]" ] }, "execution_count": 243, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# just printed first 2 \"new\" friends: \n", "full_friends_new[:2]" ] }, { "cell_type": "code", "execution_count": 241, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "quantity of friends in my graph with real people : 309 \n", "quantity of friends in my graph with random people : 309\n" ] } ], "source": [ "print(\"quantity of friends in my graph with real people : \", len(full_friends), \n", " \"\\nquantity of friends in my graph with random people : \", len(full_friends_new))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Ok, everything is fine. Let's continue with updating full graph, where should be friends and friends of friends:" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Creating new graph according to random_people dataset:**\n", "\n", "Also here I will drop all people (just skip them), that are not in my friendlist, so this operation will reduce the size of dict. \n" ] }, { "cell_type": "code", "execution_count": 317, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "CPU times: user 15 s, sys: 0 ns, total: 15 s\n", "Wall time: 15 s\n" ] } ], "source": [ "%%time\n", "full_graph_new = {}\n", "\n", "for person in list(full_graph.keys()):\n", " #taking new ID from random_people data set according to current user ID: \n", " new_id = random_people[random_people['true_id']==int(person)].uid.values[0]\n", "\n", " list_com_friends = []\n", "\n", " for i in full_graph[person]:\n", " # if person have friends in my friendlist, append them from random_people data set:\n", " if i['uid'] in random_people.true_id.values:\n", " person_dict = {}\n", " \n", " person_data = random_people[random_people['true_id']==i['uid']]\n", "\n", " person_dict['first_name'] = person_data.first_name.values[0]\n", " person_dict['last_name'] = person_data.last_name.values[0]\n", " # retyping here because of problem with JSON serialization numpy int64\n", " person_dict['sex'] = int(person_data.sex.values[0])\n", " person_dict['uid'] = int(person_data.uid.values[0])\n", " person_dict['user_id'] = int(person_data.user_id.values[0])\n", " \n", " list_com_friends.append(person_dict)\n", " if list_com_friends != []:\n", " full_graph_new[\"{}\".format(new_id)] = list_com_friends\n" ] }, { "cell_type": "code", "execution_count": 257, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "quantity of people in full graph that have real friends from my list : 309 \n", "quantity of people in full graph that have random 'new' friends : 309\n" ] } ], "source": [ "print(\"quantity of people in full graph that have real friends from my list : \", len(full_graph), \n", " \"\\nquantity of people in full graph that have random 'new' friends : \", len(full_graph_new))" ] }, { "cell_type": "code", "execution_count": 255, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[{'first_name': 'Lucas',\n", " 'last_name': 'Tomei',\n", " 'sex': 2,\n", " 'uid': 3972,\n", " 'user_id': 3972}]" ] }, "execution_count": 255, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# let's see someone's connections : \n", "full_graph_new[list(full_graph_new.keys())[1]]" ] }, { "cell_type": "code", "execution_count": 318, "metadata": {}, "outputs": [], "source": [ "# also saving new data\n", "\n", "with open(\"full_graph_rand_people.txt\", \"w+\") as f:\n", " f.write(json.dumps(full_graph_new))\n", "\n", "with open(\"full_friends_rand_people.txt\",\"w+\") as f:\n", " f.write(json.dumps(full_friends_new))\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Yep! We went out from super private friendlist to super public - now you can generate people infinitly and save links between them! Nice.\n", "\n", " That was some kind of 'preprocessing' of our graph.\n", "\n", "The next step will be creating Python graph with NetworkX!\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ ">> ### 1.2 Lazy fast start\n", "\n", "\n", "\n", ">#### 1.2.1 Uploading data for building graph\n", "\n", "As we remember, we downloaded the data for our future graph to the local storage. So you can use it.\n", "\n", "I will give you a real graph, but with random generated names.\n", "\n", "If you wasn't with us in previous part, you can load the necessary data from here:\n", "\n", "> [full_friends_rand_people](https://github.com/Mercurialll/tutors_and_projs/blob/master/jupyter_english/tutorials/full_friends_rand_people.txt)\n", "\n", "> [full_graph_rand_people](https://github.com/Mercurialll/tutors_and_projs/blob/master/jupyter_english/tutorials/full_graph_rand_people.txt)\n", "\n", "Now it's time to load it back, or as I do, to continue with new generated : " ] }, { "cell_type": "code", "execution_count": 12, "metadata": {}, "outputs": [], "source": [ "# If you have constracted your own graph withour renaming, load it from your storage:\n", "\n", "with open(\"full_graph_depth2.txt\") as f:\n", " full_graph = json.loads(f.read())\n", "\n", "with open(\"full_friends.txt\") as f:\n", " full_friends = json.loads(f.read())" ] }, { "cell_type": "code", "execution_count": 15, "metadata": {}, "outputs": [], "source": [ "# If you've run every operation step by step with me. so load this :\n", "# pay attention that I will work with full_graph and full_friends, but meaning that sets,\n", "# that I generated in previous steps\n", "\n", "#or if you skipped everything, it's also for you:\n", "\n", "with open(\"full_graph_rand_people.txt\") as f:\n", " full_graph = json.loads(f.read())\n", "\n", "with open(\"full_friends_rand_people.txt\") as f:\n", " full_friends = json.loads(f.read())\n" ] }, { "cell_type": "code", "execution_count": 16, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "all friends: 309 , nodes for graph: 280\n" ] } ], "source": [ "print(\"all friends: \", len(full_friends), \", nodes for graph: \", len(full_graph))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Notice, that there are 29 'lost' people.\n", "\n", "Fortunetly, they are Ok, they are absent for the pretty obvious reason:\n", "\n", "> They don't have in their friendlists anyone from my friends. And I will not appear in my graph for sure, so they have no any connection with somebody - and they were eliminated several steps ago.\n", "\n", "So we have reasons to cut out our friendlist also : " ] }, { "cell_type": "code", "execution_count": 17, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "280" ] }, "execution_count": 17, "metadata": {}, "output_type": "execute_result" } ], "source": [ "full_friends_cutted = []\n", "\n", "connected_people = [int(i) for i in list(full_graph.keys())]\n", "\n", "for person in full_friends:\n", " if person['uid'] in connected_people:\n", " full_friends_cutted.append(person)\n", "\n", "full_friends = copy.copy(full_friends_cutted)\n", "\n", "del full_friends_cutted\n", "gc.collect()\n", "\n", "len(full_friends)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> #### 1.2.2 Building Graph with NetworkX\n", " " ] }, { "cell_type": "code", "execution_count": 18, "metadata": {}, "outputs": [], "source": [ "# calling base class for undirected graphs and create empty graph:\n", "\n", "G = nx.Graph()" ] }, { "cell_type": "code", "execution_count": 19, "metadata": {}, "outputs": [], "source": [ "# fullfil the nodes in graph : \n", "\n", "for i in full_friends:\n", " G.add_node(i[\"uid\"], name = i[\"first_name\"] + \" \" + i[\"last_name\"], sex = i['sex'])" ] }, { "cell_type": "code", "execution_count": 20, "metadata": {}, "outputs": [], "source": [ "# establish connections between people : \n", "\n", "my_friends = list(nx.nodes(G))\n", "for i in my_friends:\n", " for j in full_graph[\"{}\".format(int(i))]:\n", " if j['uid'] in my_friends:\n", " G.add_edge(i, j['uid'])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> #### 1.2.3 Saving created Graph\n", " " ] }, { "cell_type": "code", "execution_count": 21, "metadata": {}, "outputs": [], "source": [ "nx.write_gpickle(G, \"my_graph.gpickle\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Let's move to next part! We'll explore some easy attributes of graph, that we've created. And using that knowledgement - build pseudo-random graph. \n", " \n", "Then we are going to visualize both of them - we will see huge difference." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ ">>> ## 2. Inspection of the Graph\n", "\n", ">> ### 2.1 Loading graph from source\n", "\n", "You can get the created graph from this [link](https://github.com/Mercurialll/tutors_and_projs/blob/master/jupyter_english/tutorials/my_graph.gpickle)\n", "\n", "Or if you created it properly with me, read from storage:" ] }, { "cell_type": "code", "execution_count": 22, "metadata": {}, "outputs": [], "source": [ "G = nx.read_gpickle(\"my_graph.gpickle\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ ">> ### 2.2 Getting deeper in Graph theory" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Edges**\n", "\n", "Your graph edges are represented by a list of tuples of length 3. The first two elements are the node names linked by the edge. The third is the dictionary of edge attributes.\n" ] }, { "cell_type": "code", "execution_count": 23, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[(7680, 4202, {}),\n", " (7680, 7980, {}),\n", " (7680, 8586, {}),\n", " (5120, 3842, {}),\n", " (5609, 3842, {})]" ] }, "execution_count": 23, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Preview first 5 edges\n", "list(G.edges(data=True))[:5]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Since here are no edges attributes - the 3rd element is empty.\n", "\n", "**Nodes**\n", "\n", "Similarly, your nodes are represented by a list of tuples of length 2. The first element is the node ID, followed by the dictionary of node attributes." ] }, { "cell_type": "code", "execution_count": 24, "metadata": { "scrolled": true }, "outputs": [ { "data": { "text/plain": [ "[(7680, {'name': 'Axel Holgerson', 'sex': 2}),\n", " (5120, {'name': 'Alexa Galang', 'sex': 1}),\n", " (5609, {'name': 'Hannah Simeon', 'sex': 1}),\n", " (7172, {'name': 'Evelyn Goodheart', 'sex': 1}),\n", " (4613, {'name': 'Jayce Bunt', 'sex': 2}),\n", " (2102, {'name': 'Mateo Kesner', 'sex': 2}),\n", " (5633, {'name': 'Carlos Oxley', 'sex': 2}),\n", " (7689, {'name': 'Benjamin Manderscheid', 'sex': 2}),\n", " (9227, {'name': 'Beau Spotorno', 'sex': 2}),\n", " (2572, {'name': 'Messiah Siciliano', 'sex': 2})]" ] }, "execution_count": 24, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Preview first 10 nodes\n", "list(G.nodes(data=True))[:10]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Summary Stats**\n", "\n", "Print out some summary statistics before visualizing the graph.\n" ] }, { "cell_type": "code", "execution_count": 25, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "# of edges: 2774\n", "# of nodes: 280\n" ] } ], "source": [ "print('# of edges: {}'.format(G.number_of_edges()))\n", "print('# of nodes: {}'.format(G.number_of_nodes()))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The **degree (or valency) of a vertex** of a graph is the number of edges incident to the vertex, with loops counted twice. \n", "\n", "Look at degree of every vertex in Graph :" ] }, { "cell_type": "code", "execution_count": 56, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[(7680, 3),\n", " (5120, 1),\n", " (7172, 1),\n", " (2134, 39),\n", " (5633, 45),\n", " (7689, 2),\n", " (9227, 11),\n", " (2572, 2),\n", " (4092, 2),\n", " (2574, 14)]" ] }, "execution_count": 56, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Preview first 10 nodes\n", "# node : degree\n", "list(G.degree())[:10]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Pay attention to hist of a **distribution of the graph's degrees**:" ] }, { "cell_type": "code", "execution_count": 62, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "Text(0.5, 1.0, 'Degrees in th Graph')" ] }, "execution_count": 62, "metadata": {}, "output_type": "execute_result" }, { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXQAAAEICAYAAABPgw/pAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDMuMC4wLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvqOYd8AAAFRxJREFUeJzt3XuwpHV95/H3JwygIDKMHGfHGXBIQTCsJWBGxJK4yiUhhhWyZbG47u6sS3bilmwkUiWwVsyQjbtYlVLIarkiiFOu4RLUHUJlTcgEK6u7gcwIRC4SLgEZnGEGZMJFQwS++0c/o12Hc+g+t+k+P9+vqlP93PvbT3d/+te/fp7npKqQJC1+PzPqAiRJ88NAl6RGGOiS1AgDXZIaYaBLUiMMdElqhIGunypJ/keS357H7VWSw+dre/MtyequxiWjrkULz0DXlJI8mOSHSZ5KsivJ/03y/iSL+jVTVe+vqv8ym3WTfD3Jr8/l/pMckeTqJDuTPJnk3iT/PcmquWxXAgNdL+2fV9UBwGuBi4HzgSsW4o6S7LUQ2x0nXUv+ZuB7wLFV9UrgrcD9wAnTrGPLWkMz0DVQVf19VV0P/EtgbZLXAyTZN8nvJ/lukke77oyX714vyYeTbEvyvSS/3t89keQLST6T5E+SPAO8Y4jtnZbktr5vDG/om3d+kke6bxT3JDlpqsfS3e/vdcNvT7I1yXlJdnS1vm+a9T4G/CLwqSRPJ/lU3+yTu5b2riSfTpJpduV64JtV9aGq2trt2x1VdUlVXT2ppvOTbAeuTHJQkhu6Vv0T3fCPW/TdN4f/luSWrtW/McmySff93m6/PpbkI9PUp0XOQNfQquoWYCu9YINeq/3ngGOAw4GVwEcBkpwKfAg4uZv39ik2+a+AjwEHAN8YsL1jgc8DvwG8CvgscH33IXAkcA7wpu4bxS8DDw75sP4JcGB3X2cDn05y0BSP/SPA/wHOqapXVNU5fbNPA94EvAE4s7v/qZwMfHnImpbR+2a0jt779Mpu/FDgh8CnJq3zb4F/D6wAngP+YNL8E4AjgZOAjyb5+SHq0CJjoGumvgcs61qh64DfqqrvV9VTwH8FzuqWOxO4sqrurKof0GudTraxqr5ZVS8Azw7Y3jrgs1V1c1U9X1UbunWOB54H9gWOSrJ3VT1YVfcP+Xh+BPxuVf2oqv4EeJpe8M3ExVW1q6q+C9xE7wNpKgcD23ePJDmna9U/neRzfcu9APxOVT1bVT+sqser6stV9YNuv3wM+GeTtv3Fqrqjqp4Bfhs4c1I31kXdtm4HbgeOnuFj1CJgoGumVgLfByaA/YAtXSjtAr7WTQd4DfBw33oP82L90wZt77XAebvndfMPAV5TVfcB59L70NjR/ej4miEfz+NV9Vzf+A+AVwy57m7b+4Zfav3H6bWgAaiqT1XVUuASYO++5XZW1T/sHkmyX5LPJnkoyZPAXwJLJwV2/758qNvewbOoUYuYga6hJXkTvUD/BvAYva/+/7SqlnZ/B1bV7qDYBvQfuXHIFJvsv9TnoO09DHysb97Sqtqvqq4CqKo/rKoT6AV/AR+fp4c9Xb2zsQn4F7O4n/PofWt4c/dD6tu66f199f3791B63zwem2WdWqQMdA2U5JVJTgOuBv5nVX276yb5HPDJJK/ulluZZHf/8bXA+5L8fJL96HUDTGuI7X0OeH+SN6dn/yS/muSAJEcmOTHJvsA/0PtgeGF+9wIAjwI/O4f11wO/mOQTSVYCJDkYGNSffQC9x7Sr+7Hzd6ZY5l8nOarb178LXFdVz8+hVi1CBrpeyh8neYpe6/gjwCeA/qNAzgfuA/6q6wr4c7r+56r63/R+mLtp9zLdOs++xP291PY2A/+B3o+BT3TL/btuvX3p/aD6GL2uhVcDF87yMb+US4F3d0eaTP7RcaCq+lvgzfS+udze7dtv0vtd4qU+8C4BXk7v8f0Vva6oyb4IfIHe438Z8JszrU+LX/wHF9oTuqMq7gD2ndRnrTlK8nV635wuH3UtGi1b6FowSX6tO6zwIHp92n9smEsLx0DXQvoNYAe9MyGfB/7jaMuR2maXiyQ1wha6JDVij1745+CDD67Vq1fvybuUpEVvy5Ytj1XVxKDl9migr169ms2bN+/Ju5SkRS/JQ8MsZ5eLJDXCQJekRhjoktSIgYHeXSfjtr6/J5Ocm2RZkhu7C/vfONU1pCVJe87AQK+qe6rqmKo6BvgFepfe/CpwAbCpqo6gdxW5Cxa0UknSS5ppl8tJwP1V9RBwOrChm74BOGM+C5MkzcxMA/0s4KpueHlVbeuGtwPLp1ohybokm5Ns3rlz5yzLlCQNMnSgJ9kHeBfwR5PnVe/6AVNeQ6CqLquqNVW1ZmJi4HHxkqRZmkkL/VeAb1XVo934o0lWAHS3O+a7OEnS8GZypuh7+El3C8D1wFp6/1hgLbBxHut6kfXrR7OuJC0WQ7XQk+wPnAJ8pW/yxcApSe4FTu7GJUkjMlQLvaqeAV41adrj9I56kSSNAc8UlaRGGOiS1AgDXZIaYaBLUiMMdElqhIEuSY0w0CWpEQa6JDXCQJekRhjoktQIA12SGmGgS1IjDHRJaoSBLkmNMNAlqREGuiQ1wkCXpEYY6JLUCANdkhphoEtSIwx0SWrEUIGeZGmS65J8J8ndSd6SZFmSG5Pc290etNDFSpKmN2wL/VLga1X1OuBo4G7gAmBTVR0BbOrGJUkjMjDQkxwIvA24AqCq/rGqdgGnAxu6xTYAZyxUkZKkwYZpoR8G7ASuTHJrksuT7A8sr6pt3TLbgeVTrZxkXZLNSTbv3LlzfqqWJL3IMIG+BHgj8JmqOhZ4hkndK1VVQE21clVdVlVrqmrNxMTEXOuVJE1jmEDfCmytqpu78evoBfyjSVYAdLc7FqZESdIwBgZ6VW0HHk5yZDfpJOAu4HpgbTdtLbBxQSqUJA1lyZDL/SfgS0n2AR4A3kfvw+DaJGcDDwFnLkyJkqRhDBXoVXUbsGaKWSfNbzmSpNnyTFFJaoSBLkmNMNAlqREGuiQ1wkCXpEYY6JLUCANdkhphoEtSIwx0SWqEgS5JjTDQJakRBrokNcJAl6RGGOiS1AgDXZIaYaBLUiMMdElqhIEuSY0w0CWpEQa6JDXCQJekRiwZZqEkDwJPAc8Dz1XVmiTLgGuA1cCDwJlV9cTClClJGmQmLfR3VNUxVbWmG78A2FRVRwCbunFJ0ojMpcvldGBDN7wBOGPu5UiSZmvYQC/gz5JsSbKum7a8qrZ1w9uB5VOtmGRdks1JNu/cuXOO5UqSpjNUHzpwQlU9kuTVwI1JvtM/s6oqSU21YlVdBlwGsGbNmimXkSTN3VAt9Kp6pLvdAXwVOA54NMkKgO52x0IVKUkabGCgJ9k/yQG7h4FfAu4ArgfWdoutBTYuVJGSpMGG6XJZDnw1ye7l/7Cqvpbkr4Frk5wNPAScuXBlSpIGGRjoVfUAcPQU0x8HTlqIoiRJMzfsj6KL2vr1o1lXkvYkT/2XpEYY6JLUCANdkhphoEtSIwx0SWqEgS5JjTDQJakRBrokNcJAl6RGGOiS1AgDXZIaYaBLUiMMdElqhIEuSY0w0CWpEQa6JDXCQJekRhjoktQIA12SGmGgS1Ijhg70JHsluTXJDd34YUluTnJfkmuS7LNwZUqSBplJC/2DwN194x8HPllVhwNPAGfPZ2GSpJkZKtCTrAJ+Fbi8Gw9wInBdt8gG4IyFKFCSNJxhW+iXAB8GXujGXwXsqqrnuvGtwMqpVkyyLsnmJJt37tw5p2IlSdMbGOhJTgN2VNWW2dxBVV1WVWuqas3ExMRsNiFJGsKSIZZ5K/CuJO8EXga8ErgUWJpkSddKXwU8snBlSpIGGdhCr6oLq2pVVa0GzgL+oqreC9wEvLtbbC2wccGqlCQNNJfj0M8HPpTkPnp96lfMT0mSpNkYpsvlx6rq68DXu+EHgOPmvyRJ0mx4pqgkNcJAl6RGGOiS1AgDXZIaYaBLUiMMdElqhIEuSY0w0CWpEQa6JDXCQJekRhjoktQIA12SGmGgS1IjDHRJaoSBLkmNMNAlqREGuiQ1wkCXpEYY6JLUCANdkhphoEtSIwYGepKXJbklye1J7kxyUTf9sCQ3J7kvyTVJ9ln4ciVJ0xmmhf4scGJVHQ0cA5ya5Hjg48Anq+pw4Ang7IUrU5I0yMBAr56nu9G9u78CTgSu66ZvAM5YkAolSUNZMsxCSfYCtgCHA58G7gd2VdVz3SJbgZXTrLsOWAdw6KGHzrXePW79+tGuL0nDGupH0ap6vqqOAVYBxwGvG/YOquqyqlpTVWsmJiZmWaYkaZAZHeVSVbuAm4C3AEuT7G7hrwIemefaJEkzMMxRLhNJlnbDLwdOAe6mF+zv7hZbC2xcqCIlSYMN04e+AtjQ9aP/DHBtVd2Q5C7g6iS/B9wKXLGAdUqSBhgY6FX1N8CxU0x/gF5/uiRpDHimqCQ1wkCXpEYY6JLUCANdkhphoEtSIwx0SWqEgS5JjTDQJakRBrokNcJAl6RGGOiS1AgDXZIaYaBLUiMMdElqhIEuSY0w0CWpEQa6JDXCQJekRhjoktQIA12SGmGgS1IjBgZ6kkOS3JTkriR3JvlgN31ZkhuT3NvdHrTw5UqSpjNMC/054LyqOgo4HvhAkqOAC4BNVXUEsKkblySNyMBAr6ptVfWtbvgp4G5gJXA6sKFbbANwxkIVKUkabMlMFk6yGjgWuBlYXlXbulnbgeXTrLMOWAdw6KGHzrbORWv9+tGsK+mnz9A/iiZ5BfBl4NyqerJ/XlUVUFOtV1WXVdWaqlozMTExp2IlSdMbKtCT7E0vzL9UVV/pJj+aZEU3fwWwY2FKlCQNY5ijXAJcAdxdVZ/om3U9sLYbXgtsnP/yJEnDGqYP/a3AvwG+neS2btp/Bi4Grk1yNvAQcObClChJGsbAQK+qbwCZZvZJ81uOJGm2PFNUkhphoEtSIwx0SWqEgS5JjTDQJakRBrokNcJAl6RGGOiS1AgDXZIaYaBLUiMMdElqhIEuSY2Y0X8s0p41qv92NNf/lOR/WpJGwxa6JDXCQJekRhjoktQIA12SGmGgS1IjDHRJaoSBLkmNMNAlqREDTyxK8nngNGBHVb2+m7YMuAZYDTwInFlVTyxcmdLCGuWJWIuRJ5+Np2Fa6F8ATp007QJgU1UdAWzqxiVJIzQw0KvqL4HvT5p8OrChG94AnDHPdUmSZmi2fejLq2pbN7wdWD7dgknWJdmcZPPOnTtneXeSpEHm/KNoVRVQLzH/sqpaU1VrJiYm5np3kqRpzDbQH02yAqC73TF/JUmSZmO2l8+9HlgLXNzdbpy3iiTtER5p0p6BLfQkVwH/DzgyydYkZ9ML8lOS3Auc3I1LkkZoYAu9qt4zzayT5rkWSdIc+B+LNFY8wUeaPU/9l6RGGOiS1Ai7XKQ58romGhe20CWpEQa6JDXCLpdG+TV+8fDInplxf03PFrokNcJAl6RG2OWiedf619px4r5WP1voktQIA12SGmGXi5ph94N+2tlCl6RGGOiS1Ai7XCTtcYuxe2wxnNBkC12SGmGgS1IjDHRJaoSBLkmNMNAlqRFzOsolyanApcBewOVVdfG8VCVJC2AxHl0zE7NuoSfZC/g08CvAUcB7khw1X4VJkmZmLl0uxwH3VdUDVfWPwNXA6fNTliRppubS5bISeLhvfCvw5skLJVkHrOtGn05yzyzv72DgsVmuuyeMc33jXBuMd33jXBuMd33jXBvswfouumjGq0yu7bXDrLTgZ4pW1WXAZXPdTpLNVbVmHkpaEONc3zjXBuNd3zjXBuNd3zjXBuNd32xrm0uXyyPAIX3jq7ppkqQRmEug/zVwRJLDkuwDnAVcPz9lSZJmatZdLlX1XJJzgD+ld9ji56vqznmr7MXm3G2zwMa5vnGuDca7vnGuDca7vnGuDca7vlnVlqqa70IkSSPgmaKS1AgDXZIasSgCPcmpSe5Jcl+SC0Zcy+eT7EhyR9+0ZUluTHJvd3vQCOs7JMlNSe5KcmeSD45LjUleluSWJLd3tV3UTT8syc3d83tN9yP7SCTZK8mtSW4Yw9oeTPLtJLcl2dxNG/nz2lff0iTXJflOkruTvGUc6ktyZLfPdv89meTccaitr8bf6t4TdyS5qnuvzPi1N/aBPoaXGPgCcOqkaRcAm6rqCGBTNz4qzwHnVdVRwPHAB7r9NQ41PgucWFVHA8cApyY5Hvg48MmqOhx4Ajh7BLXt9kHg7r7xcaoN4B1VdUzfMcrj8Lzudinwtap6HXA0vf048vqq6p5unx0D/ALwA+Cr41AbQJKVwG8Ca6rq9fQOMjmL2bz2qmqs/4C3AH/aN34hcOGIa1oN3NE3fg+wohteAdwz6v3WV9tG4JRxqxHYD/gWvbOLHwOWTPV87+GaVtF7Y58I3ABkXGrr7v9B4OBJ08bieQUOBP6O7kCLcauvr55fAr45TrXxk7Pul9E78vAG4Jdn89ob+xY6U19iYOWIapnO8qra1g1vB5aPspjdkqwGjgVuZkxq7Lo0bgN2ADcC9wO7quq5bpFRPr+XAB8GXujGX8X41AZQwJ8l2dJdUgPG5HkFDgN2Ald2XVaXJ9l/jOrb7Szgqm54LGqrqkeA3we+C2wD/h7Ywixee4sh0BeV6n2cjvxY0CSvAL4MnFtVT/bPG2WNVfV89b76rqJ3gbfXjaKOyZKcBuyoqi2jruUlnFBVb6TX/fiBJG/rnzni194S4I3AZ6rqWOAZJnVhjPq90fVBvwv4o8nzRllb13d/Or0PxdcA+/Pibt2hLIZAXwyXGHg0yQqA7nbHKItJsje9MP9SVX2lmzxWNVbVLuAmel8llybZfZLbqJ7ftwLvSvIgvSuHnkivT3gcagN+3JKjqnbQ6wM+jvF5XrcCW6vq5m78OnoBPy71Qe+D8FtV9Wg3Pi61nQz8XVXtrKofAV+h93qc8WtvMQT6YrjEwPXA2m54Lb1+65FIEuAK4O6q+kTfrJHXmGQiydJu+OX0+vbvphfs7x5lbVV1YVWtqqrV9F5jf1FV7x2H2gCS7J/kgN3D9PqC72AMnleAqtoOPJzkyG7SScBdjEl9nffwk+4WGJ/avgscn2S/7v27e9/N/LU3yh8oZvCjwTuBv6XX3/qREddyFb1+rh/Ra5WcTa+vdRNwL/DnwLIR1ncCva+OfwPc1v29cxxqBN4A3NrVdgfw0W76zwK3APfR+zq874if47cDN4xTbV0dt3d/d+5+H4zD89pX4zHA5u75/V/AQeNSH71ujMeBA/umjUVtXS0XAd/p3hdfBPadzWvPU/8lqRGLoctFkjQEA12SGmGgS1IjDHRJaoSBLkmNMNAlqREGuiQ14v8DYa1l0EM32P4AAAAASUVORK5CYII=\n", "text/plain": [ "