{ "nbformat": 4, "nbformat_minor": 0, "metadata": { "colab": { "provenance": [], "toc_visible": true, "private_outputs": true }, "kernelspec": { "name": "python3", "display_name": "Python 3" }, "language_info": { "name": "python" }, "gpuClass": "standard" }, "cells": [ { "cell_type": "markdown", "source": [ "# Aprendizaje Automático para Datos en Grafos - Laboratorio 2\n", "La idea de este Laboratorio es ver que algunas propiedades de la estructura de grandes redes que vimos en clase efectivamente aparecen en una red real. Además, implementaremos un par de algoritmos para hacer partición de un grafo, y los aplicaremos a un dataset real." ], "metadata": { "id": "r_70W1d-wTg1" } }, { "cell_type": "code", "source": [ "# Importo PyTorch\n", "import torch" ], "metadata": { "id": "uhm7zOFEwhNa" }, "execution_count": null, "outputs": [] }, { "cell_type": "code", "source": [ "# Instalo versión de PyTorch Geometric según instalación de PyTorch\n", "!pip install torch-scatter -f https://data.pyg.org/whl/torch-{torch.__version__}.html\n", "!pip install torch-sparse -f https://data.pyg.org/whl/torch-{torch.__version__}.html\n", "!pip install torch-geometric" ], "metadata": { "id": "2c9aotr_wkgl" }, "execution_count": null, "outputs": [] }, { "cell_type": "code", "source": [ "# Instalo graspologic. Es una biblioteca que nos va a servir para más adelante,\n", "# ahora solo vamos a utilizar un método muy útil que tiene (es como matar una\n", "# mosca con un cañón, pero bueno)\n", "!pip install graspologic" ], "metadata": { "id": "T03cr7brwNrQ" }, "execution_count": null, "outputs": [] }, { "cell_type": "code", "source": [ "# Importo bibliotecas\n", "import networkx as nx\n", "import numpy as np\n", "import matplotlib.pyplot as plt\n", "import torch\n", "# Importo la función de graspologic que quiero usar\n", "from graspologic.utils import remap_labels" ], "metadata": { "id": "di83Ec6nR9EV" }, "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "source": [ "## Estructura de grandes redes" ], "metadata": { "id": "Bpdq4JmxL4HU" } }, { "cell_type": "markdown", "source": [ "### Distribución de grados\n", "En esta sección vamos a trabajar con la distribución de grados de un grafo real, que proviene de datos de citaciones entre papers de machine learning. Dado un grafo $G$, llamamos $p_k$ a la fracción de los vértices del grafo que tienen grado $k$. El conjunto $\\{p_k\\}_{k\\geq 0}$ es la *distribución de grados del grafo $G$*. Por ejemplo, en el grafo de la figura:\n", "\n", "![grafo_ejemplo.png](data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAV0AAADnCAYAAAC9roUQAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4yLjIsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+WH4yJAAAgAElEQVR4nO3deVhUZfsH8O8sgIA76OurJirDYqTiEv5SSUXTNF9cyi3TNCJf0VREQYHZRSA3zF3ccsFcUdM084VMyyXEfUFRw0zNQHEBFGbm/P4o2lQEnDnPnHPuz3X5TwznfL0bb+7zMOc8Mo7jQAghhB9y1gEIIURKqOkSQgiPqOkSQgiPqOkSQgiPqOkSQgiPlGV90d3dnWvcuDFPUQghRByOHTuWy3Fcnad9rcym27hxY2RkZNgmFSGEiJRMJst51tdoeYEQQnhETZcQQnhETZcQQnhETZcQQnhETZcQQnhETZcQQnhETZcQQnhETZcQQnhETZcQQnhETZcQQnhETZcQQnhETZcQQnhU5gNvSNly8gqQfOAKtp24gYLHJrg6KdHXvz5CA5vCw82VdTxRoprzi+ptfbKyNqZs27YtR08Ze7r0rNsIW5eJErMFJsufNVTKZXBQyLFwaGt08anLMKH4UM35RfWuPJlMdozjuLZP+xotL1RCTl4BwtZloqjE/Lc3IwCYLByKSswIW5eJnLwCRgnFh2rOL6q37VDTrYTkA1dQYraU+ZoSswXLDl7lKZH4Uc35RfW2HWq6lbDtxI0nfvr/k8nCIfX4zzwlEj+qOb+o3rZDTbcSCh6byve64vK9jjwf1ZxfVG/boaZbCa5O5fvQh6sjfTjEWqjm/KJ62w413Uro618fSrmszNco5TL0a9WAp0TiRzXnF9XbdqjpVkJoYFM4KMounYNCjg87NuEpkfhRzflF9bYdarqV4OHmioVDW8PZQfHENMCZTXBSyrBwaGv68LgVlVVzpVwGZwcF1dyKPNxckfTOK+BKHkPxj4FXxlmo3i+Amm4ldfGpiz3jAzEkoBGqOikhkwFVnZRo5ngHLa5/QR8at4Fn1XxIQCPsGR9INbey82mb8XJOKt5t54GqTkpwnAWujgo8Pvs/LHu7KdW7kuiONCu7f/8+VCoV9u/fj2bNmrGOQ0ilFBQUwNPTE3v37kWLFi0AADKZDBzHITY2Fjdv3sTy5csZp7RfdEcaj6pXr46IiAjodDrWUQiptPnz56NTp05/NNy/ioiIwPbt23Hp0iUGyYSPJl0bKJ0SvvrqK7Rs2ZJ1HEIq5FlXa6WTLgAYjUZkZWVh7dq1rGLaNZp0eebq6oqoqChotVrWUQipsKSkJPTo0aPM5bHx48dj7969OHfuHI/JxIGaro3897//RUZGBuhKgQjJnTt38Omnnz53YKhevTomTZpEy2iVQE3XRpydnREdHQ21Ws06CiHlNmvWLPTt2xcqleq5rx0zZgwOHDiAEydO8JBMPKjp2lBISAjOnz+P7777jnUUQp7r119/xeLFi8s9KLi6umLKlCm0jFZB1HRtyMnJCWq1mqZdIgiJiYkYPHgwPDw8yv09o0aNQmZmJn744QcbJhMXaro2Nnz4cFy7dg3p6emsoxDyTDdv3sSKFSsQHR1doe+rUqUKLaNVEDVdG3NwcIBOp4NarUZZH88jhKX4+HiMGDECDRpU/AE2ISEhyMrKwsGDB22QTHyo6fJgyJAhuHPnDr766ivWUQh5wrVr17B27VpMmTKlUt/v6OhIy2gVQE2XBwqFAnq9nqZdYpfi4uIwatQo1K1b+WcpDB8+HNevX0daWpoVk4kTNV2evP322yguLsaOHTtYRyHkD1euXMHmzZsxadKkFzqOUqmkZbRyoqbLE7lcDoPBAI1GA4ul7A3/COGLwWDA2LFj4ebm9sLHGjx4MPLz87Fnzx4rJBMvaro8Cg4OhqOjI7Zs2cI6CiHIysrCrl27EB4ebpXj0TJa+VDT5ZFMJoPRaIRWq4XZbGYdh0icTqdDeHg4atasabVj9u/fHyaTCdu3b7faMcWGmi7PevTogdq1a2P9+vWsoxAJO336NNLT0zFu3DirHlcul8NoNNIyWhmo6fKsdNrV6XQoKSlhHYdIlFarxeTJk1G1alWrH7t3795wdnbG5s2brX5sMaCmy0CXLl3QqFEjrF69mnUUIkGZmZk4fPgwRo8ebZPjy2QyGAwGWkZ7Bmq6jBiNRhiNRjx+/Jh1FCIxGo0G0dHRcHFxsdk5unfvDnd3d6SkpNjsHEJFTZeRDh06oFmzZrTPFOHVoUOHcOrUKYSGhtr0PKXLaHq9npbR/oGaLkMGgwFxcXEoKipiHYVIhEajQWxsLJycnGx+rs6dO8PDwwOfffaZzc8lJNR0GXr11Vfx6quvYvHixayjEAnYv38/rly5gpEjR/J2TlpGexI1XcYMBgMSExNRUFDAOgoRMY7joFarodFo4ODgwNt527dvDz8/Pyxbtoy3c9o7arqMtWjRAp06dcL8+fNZRyEitm/fPty+fRtDhw7l/dxGoxHTp0+nZbTfUdO1AzqdDrNmzcL9+/dZRyEixHEcYmNjodPpoFQqeT9/mzZtEBAQQMtov6OmaweaNWuGHj16ICkpiXUUIkK7du1CYWEhBg4cyCyDXq9HYmIiHj58yCyDvaCmaye0Wi0+/fRT3Llzh3UUIiIWiwVqtRoGgwFyObt/7i1atEDnzp1pGQ3UdO2GSqVC3759MWvWLNZRiIikpqZCLpejb9++rKP8sYx279491lGYoqZrR9RqNRYvXoxff/2VdRQiAmazGVqtFkajETKZjHUc+Pr6olevXpJfRqOma0c8PDwwePBgJCYmso5CRGDDhg2oVq0aevbsyTrKHzQaDebNmyfpZTRqunYmOjoaK1aswM2bN1lHIQJmMpmg0+nsZsot5enpiX79+mHmzJmsozBDTdfONGjQACNGjEB8fDzrKETA1q5di/r166Nr166sozxBrVZjyZIlkl1Gk5W1rUbbtm25jIwMHuMQALh9+zZ8fX1x4sQJNGrUiHUcIjDFxcXw8fHB6tWrERgYaLXjymQyq23DM3bsWFSpUkW0E69MJjvGcVzbp32NJl07VLduXYwaNQpxcXGsoxABWrlyJby9va3acK2tdBntxo0brKPwjiZdO5WXlwdvb2/88MMPaNq0Kes4RCAePXoELy8vbNmyBQEBAVY9tjUnXQCIiIhAcXEx5s2bZ7Vj2guadAXIzc0NY8eOhcFgYB2FCMjSpUvh7+9v9YZrC1FRUUhJScG1a9dYR+EVTbp2LD8/H15eXjh48CB8fHxYxyF2rrCwECqVCrt27UKrVq2sfnxrT7rAb8sMubm5WLp0qVWPyxpNugJVs2ZNhIeHQ6fTsY5CBGDBggVo3769TRqurUyaNAlbt27F5cuXWUfhDU26du7hw4dQqVT4+uuv0bx5c9ZxiJ168OABVCoV0tLS4OfnZ5Nz2GLSBX57GM6VK1dEtcMETboCVrVqVUyePBlarZZ1FGLH5s6di27dutms4drShAkTsHv3bly4cIF1FF7QpCsApWt1O3fuROvWrVnHIXYmPz8fKpUK33//Pby9vW12HltNugAQHx+PkydP4vPPP7fJ8flGk67Aubi4IDo6GhqNhnUUYodmz56N4OBgmzZcW/v444/xzTff4PTp06yj2Bw1XYEIDQ3FqVOncOjQIdZRiB3Jzc3FggULoFarWUd5IVWrVkVkZKQkltGo6QqEk5PTHxsLElJqxowZGDhwIJo0acI6ygsbPXo0jhw5gmPHjrGOYlPUdAVkxIgRuHLlCvbv3886CrEDt27dQnJyMmJiYlhHsQpnZ2dJLKNR0xUQBwcHaDQaqNVqm/1CgwhHQkIChg0bhoYNG7KOYjUffvghzpw5I+plNGq6AjN06FDcvn0b+/btYx2FMHT9+nWsWbMGU6dOZR3FqkqX0YS+Rl0WaroCo1QqodPpEBsbS9OuhMXFxSEkJAT16tVjHcXq3n//ffz444/45ptvWEexCWq6AjRw4EAUFhZi165drKMQBq5evYqNGzciMjKSdRSbcHBwgFarFe0yGjVdAZLL5TAYDFCr1bBYLKzjEJ4ZjUaEhYXB3d2ddRSbeffdd5Gbm4uvv/6adRSro6YrUH379oVcLkdqairrKIRHly5dwo4dOzBx4kTWUWxKoVBAp9OJctqlpitQMpkMRqMRWq0WZrOZdRzCE71ejwkTJqBWrVqso9jcgAEDUFRUhJ07d7KOYlXUdAWsZ8+eqFatGjZs2MA6CuHB2bNnsXfvXowfP551FF6ULqNpNBpRLaNR0xUwmUyGadOmQafTwWQysY5DbEyn02Hy5MmoVq0a6yi86dOnDxQKBbZu3co6itVQ0xW4oKAg1K9fH2vWrGEdhdjQiRMncPDgQYwZM4Z1FF6JcRmNmq7Alb4pDQYDiouLWcchNqLRaDBlyhS4uLiwjsK7N998EzVq1BDNMho1XREIDAyEt7c3Vq5cyToKsYGjR4/i+PHjGDVqFOsoTIhtGY2arkgYjUZMmzYNjx49Yh2FWJlarUZMTAyqVKnCOgozQUFBaNCggSiW0ajpikRAQAD8/f1Ft6uq1B04cAAXL17EBx98wDoKc2JZRqOmKyIGgwHx8fEoLCxkHYVYAcdxfzxD2dHRkXUc5jp27AgfHx+sWLGCdZQXQk1XRFq1aoUOHTpgwYIFrKMQK0hLS8ONGzcwbNgw1lHshsFgQFxcnKCX0ajpioxer8fMmTPx4MED1lHICyidcnU6HZRKJes4diMgIACtW7fGkiVLWEepNGq6IuPn54du3bph7ty5rKOQF7B7927cu3cPgwYNYh3F7hgMBiQkJAh2GY2arghptVokJSXh7t27rKOQSiidcvV6PRQKBes4dqdly5bo2LGjYJfRqOmKkLe3N4KDgzF79mzWUUglbNu2DRaLBf3792cdxW4JeRmNmq5IqdVqLFy4ELm5uayjkAqwWCzQaDQwGAyQy+mf57O8/PLLeOONNwS5jEb/V0WqSZMmGDhwIGbMmME6CqmATZs2wcXFBb1792Ydxe5ptVrMnTtXcMto1HRFLCYmBsnJybh16xbrKKQcTCYTtFotjEYjZDIZ6zh2z8vLS5DLaNR0Raxhw4YYNmwYEhISWEch5ZCSkoI6dergjTfeYB1FMIS4jCYrayuMtm3bchkZGTzGIdZ269Yt+Pn54eTJk2jYsCHrOOQZSkpK4OvrixUrVqBTp06s4zyVTCazy61zwsLCULVqVXzyySeso/xBJpMd4ziu7dO+RpOuyNWrVw8hISGIi4tjHYWUYdWqVWjSpIndNlx7FhMTg+XLlwtmGY0mXQnIzc2Fj48PMjIy0KRJE9ZxyD88fvwYXl5e2LBhA1577TXWcZ7JXiddAAgPDwfHcUhKSmIdBQBNupLn7u6OsLAwGI1G1lHIUyQnJ6N58+Z23XDt3ZQpU7BmzRpcv36ddZTnoklXIu7evQsvLy8cOnQIXl5erOOQ3xUVFUGlUmHHjh1o06YN6zhlsudJFwCioqJw//59LFq0iHUUmnQJUKtWLUyYMAF6vZ51FPIXixYtQrt27ey+4QpBZGQkNm7ciKtXr7KOUiaadCXkwYMH8PT0RHp6Ovz8/FjHkbyHDx/C09MT+/btQ/PmzVnHeS57n3SB3/aSu379OvNn7tKkSwAA1apVw+TJk6HT6VhHIQDmzZuHoKAgQTRcoZg4cSK++OILXLx4kXWUZ6JJV2IKCwvh6emJ3bt3w9/fn3Ucybp37x5UKhUOHjwIHx8f1nHKRQiTLgDExcXh3LlzWLduHbMMZU26dvF05Jy8AiQfuIJtJ26g4LEJrk5K9PWvj9DApvBwc2UdT1RcXFzw30mx+GDhXhTX/4XqzZN/vseVMEM1OBZV3OmGFWsbN24cvFq9hrAV3+Lba0V29x5nPummZ91G2LpMlJgtMFn+zKKUy+CgkGPh0Nbo4lPXphmk5Ld6H0Pho2LIFH/+zKV6286z3uMKGeCoVAim5kKZdNOzbiN01RGYOA6Q/fk8Yj7f43a7ppuTV4CwdZkoKjH/7c0IACYLh6ISM8LWZSInr4BRQnH5s96WvzVcgOptK2W9x80cqOZWVlpvE+R/a7iA/bzHmTbd5ANXUGK2lPmaErMFyw7a90dAhILqzT+qOb+EUG+mTXfbiRtP/PT/J5OFQ+rxn3lKJG5Ub/5RzfklhHoz/UVawWNTuV734FExPV/UChpF7YBM9vyfs1Rv6ylvzQuKy/dvgZStvD2FZb2ZTrquTuXr+dWqOILjOPrzgn+qVXGkettpzV0d7eKDRIJX3p7Cst5Mm25f//pQysueqJRyGfq1asBTInGjevOPas4vIdSbadMNDWwKB0XZERwUcnzYkR5HaA1Ub/5RzfklhHozbboebq5YOLQ1nB0UT/x04swmVFHKsHBoa+YfZhaL0no7yDjAYv7b15RyGZwdFFRvK/Nwc4W6Sz1wJY+h/Me/Nqq59Xm4uWLeoBaA6TEU/xh47aXezJ+90MWnLvaMD8SQgEao6qSETAZUdVLCS34br+Z+LYgPjQtJoGdtYHccurzk8Ld6DwlohD3jA6neNrBn5Wy843oRQwI8qOY8uPLdTjQ+vx7vtrPPejO/I+1Z8vLy4OPjg6NHj6Jp06ZMMojRqlWrsGrVKqSnp9MnFHhw/vx5dOrUCZcuXUKNGjVYx3khQrgj7dGjR/D29samTZvQrl07Zjns9o60sri5uWHMmDEwGAyso4hGcXEx9Ho9bfHNI51Oh4kTJwq+4QpFcnIyWrZsybThPo9df04lPDwcXl5eyMrKEsyTmOzZypUr4e3tjcDAQNZRJOHUqVPYv38/82e7SkVhYSHi4+Oxa9cu1lHKZLeTLgDUrFkT4eHhtNuBFTx69AjTpk2jfdJ4pNVqERUVBVdX+iUZHxYuXIj27dujVatWrKOUya4nXeC3x7R5enrizJkzeOWVV1jHEaylS5fC398fAQEBrKNIQkZGBo4ePYqUlBTWUSThwYMHmDFjBtLS0lhHeS67nnQBoGrVqoiMjIRWq2UdRbAKCwuRkJBA6+M80mg0iImJgbOzM+sokjBv3jx069ZNENtQ2X3TBYDRo0fj0KFDyMzMZB1FkBYsWCCIyy6x+P7773H27FmEhISwjiIJ+fn5mDNnjmAGM0E0XRcXF0ydOhUajYZ1FMF58OABZs6cSeviPFKr1VCr1XBycmIdRRLmzJmD3r17w9vbm3WUchFE0wWAjz76CKdOncLhw4dZRxGUuXPnCuaySwzS09ORk5OD999/n3UUScjLy8P8+fMFNZAJpuk6OTkhNjYWarWadRTByM/PR1JSkmAuu4SO4zio1WpotVo4ODiwjiMJM2bMwIABA9CkiXCeXSGYpgsAI0eOxOXLl7F//37WUQRh9uzZCA4OFsxll9Dt3bsXeXl5ePfdd1lHkYRffvkFycnJiImJYR2lQuz+I2N/5eDgAK1WC7Vajf3799NdVWXIzc3FggULwOo2bqnhOA6xsbHQ6/VQKBTP/wbywhISEvDee+/hpZdeYh2lQgQ16QLA0KFD8csvv2Dfvn2so9g1IV52CdkXX3yB4uJivPPOO6yjSMLPP/+M1atXY+rUqayjVJigJl0AUCqV0Ov1UKvV6NatG027T3Hr1i0sW7YMJ0+eZB1FEiwWCzQaDQwGA+Rywc0xgjR9+nSEhISgXr16rKNUmCDfIQMHDkRBQYHd32PNSullV8OGDVlHkYQtW7bAwcEBwcHBrKNIQk5ODj7//HNERkayjlIpgpt0AUAul0Ov10Oj0eCtt96iafcvrl+/jjVr1uDs2bOso0iC2WyGVqvF7Nmz6X3IE6PRiNGjR8Pd3Z11lEoR5KQLAP369QMApKamMk5iX+Li4gR72SVEn3/+OWrVqoUePXqwjiIJ2dnZ2LZtGyIiIlhHqTRBTrrAbw9UNhqNiIqKQp8+feg3xgB+/PFHbNy4EVlZWayjSILJZIJOp8OSJUtoyuWJXq/H+PHjUatWLdZRKk2wky4A9OrVC9WqVcPGjRtZR7ELRqMRYWFhgr3sEprVq1fjpZdeQlBQEOsoknDu3Dns3bsX48ePZx3lhQh20gX+nHbDwsIwYMAAKJWC/uu8kEuXLmH79u24dOkS6yiSUFxcDIPBgHXr1rGOIhk6nQ4RERGoXr066ygvRNCTLgB07doV//73v7F27VrWUZjS6/WYMGGCoC+7hGT58uVo1qwZOnTowDqKJJw8eRIHDhzAmDFjWEd5YXa7MWVFfPvttxgxYgQuXLgAR0dH1nF4d/bsWXTp0gWXL19GtWrVWMcRvaKiInh5eSE1NRWvvvoq6zi8YbkxZZ8+fRAUFCSYpQVBbkxZEa+//jpUKhVWrlzJOgoTOp0OkyZNoobLkyVLlqBNmzaSargs/fDDD8jMzMSoUaNYR7EKUUy6AHDkyBG88847uHTpEqpUqcI6Dm9OnDiBnj17Ijs7m/bi4kFBQQFUKhX27NmDli1bso7DK1aTbs+ePREcHIzRo0fzfu7KEv2kCwDt2rWDv78/li5dyjoKrzQaDaZMmUINlyfz589HYGCg5BouK9999x0uXLggql04RDPpAsDx48fx1ltvITs7Gy4uLqzj2NzRo0fx9ttvS266Z+X+/ftQqVTYv38/mjVrxjoO71hMukFBQXjvvffwwQcf8HreFyWJSRcAWrVqhfbt22PhwoWso/BCrVYjJiaGGi5P5s6dix49ekiy4bKQlpaGn376CcOHD2cdxapENekCv/0mPygoCNnZ2aL+xdLBgwcxbNgwZGVlSfITG3y7e/cuvLy8cPjwYahUKtZxmOBz0uU4Dh07dkRYWBiGDh3KyzmtSTKTLgD4+fmha9eu+PTTT1lHsZnSB2ZrNBpquDyZNWsW+vbtK9mGy7evvvoK+fn5GDx4MOso1sdx3DP/tGnThhOirKwszt3dnbt79y7rKDaxb98+zsvLiyspKWEdRRJu377N1a5dm/vxxx9ZR2Hqt3ZhexaLhWvbti23adMmXs5nCwAyuGf0VdFNugDg7e2N3r17Y/bs2ayjWB33++aHOp1O0rc98+mTTz7B4MGD4eHhwTqKJOzYsQMlJSXo378/6yg2Idp/tRqNBm3btsW4ceNE9QCY3bt34969exg0aBDrKJJw8+ZNLF++HKdPn2YdRRIsFgvUajXi4uJEuwuHOP9WAJo0aYIBAwZgxowZrKNYDcdx0Gg0tPkhj+Lj4/H++++jQYMGrKNIwubNm+Hs7IzevXuzjmIzop10ASAmJgYtW7bExIkT8a9//Yt1nBe2fft2mM1m0V522ZuffvoJ69atw7lz51hHkYTSXTiSkpJE/Xxi0U66APDSSy9h2LBhSEhIYB3lhZVedtHmh/yJi4tDaGioKH5gC0FKSgrc3d3RvXt31lFsStSTLgBMnToVL7/8MiIiIgS9UeOmTZvg4uIi6ssue3LlyhVs3ryZduHgSUlJCfR6PZYtWybqKRcQ+aQLAPXq1UNISAimT5/OOkqlmUwmaLVaGI1G0b8h7YXRaMSYMWPg5ubGOookfPbZZ/Dw8EDnzp1ZR7E50U+6ABAZGQlfX19ERkaicePGrONUWEpKCurUqYM33niDdRRJuHjxInbu3Em7cPDk8ePHMBqNWL9+PesovBD9pAsAderUwejRo2E0GllHqbDSy65p06bRlMsTnU6H8PBw1KxZk3UUSVi+fDn8/PzQvn171lF4IbpnLzxL6b3zhw4dgpeXF+s45ZacnIwNGzZg3759rKNIwpkzZ9C1a1dcvnwZVatWZR3Hrtji2QtFRUVQqVTYsWMH2rRpY9VjsySpZy88S61atTB+/Hjo9XrWUcqt9LJLiBO6UGm1WkyePJkaLk8WL16MgIAAUTXc55HEmm6p8ePHQ6VS4dy5c3j55ZdZx3mu5ORkNG/eHK+99hrrKJJw/PhxHDp0CGvWrGEdRRIePnyIxMRE7N27l3UUXklm0gWA6tWrY9KkSdDpdKyjPFdRURHi4+NhMBhYR5EMjUaDqVOnSuIB+PZg/vz56Ny5M1q0aME6Cq8kNekCwJgxY6BSqXDixAn4+/uzjvNMixYtQrt27SR12cXS4cOHcfLkSWzevJl1FEm4d+8eZs+ejW+//ZZ1FN5JatIFAFdXV0yZMgVarZZ1lGcqvewS0vqz0Gk0GsTGxsLJyYl1FElISkpCz5494evryzoK7yTXdAFg1KhRyMzMxNGjR1lHeap58+ahS5cuaN68OesokvDtt98iOzsbI0eOZB1FEu7cuYN58+ZBo9GwjsKEJJtulSpVEB0dbZf/00svu4Sw7iwGpc8n1mq1cHBwYB1HEmbOnIl+/frB09OTdRQmJNl0ASAkJARZWVk4ePAg6yh/M2fOHPTq1UuSl10s/O9//8OtW7cEuQ+XEP36669YsmQJ1Go16yjMSO4XaaUcHR2hVquhVquRnp7OOg4AIC8vD/Pnz8eRI0dYR5EE7ve95vR6Pe3CwZPExEQMGTIEjRo1Yh2FGclOugAwfPhwXL9+HWlpaayjAPjtsqt///6Svezi25dffomCggIMHDiQdRRJuHHjBlasWIHo6GjWUZiS9I93pVIJnU4HtVqNLl26MH22we3bt7F06VIcP36cWQYpKV3L1ev19HxinsTHx2PkyJGoX78+6yhMSf7dNnjwYOTn52PPnj1McyQmJuLdd9+V9GUXn1JTUwEA/fr1Y5xEGq5du4aUlBRERUWxjsKcpCddAFAoFNDr9VCr1XjzzTeZTLs3btzAypUrcfbsWd7PLUVmsxkajQaJiYn05DaeTJs2DaNGjULdunVZR2FO8pMuAPTv3x8mkwnbt29ncv7p06fjgw8+wL///W8m55eajRs3olq1aujVqxfrKJJw+fJlbN26FZMmTWIdxS5IftIFALlcDoPBgNjYWAQHB/O6xpeTk4P169fjwoULvJ1TykwmE3Q6HRYsWEBTLk8MBgPGjh2L2rVrs45iF2jS/d1//vMfVKlShfd770svu+rUqcPreaVq3bp1qFevHrp27co6iiRcuHABX375JcLDw1lHsRs06f5OJiwgz8QAAAeESURBVJPBaDRiwoQJePvtt6FQKGx+zuzsbKSmpuLixYs2Pxf5cxeOVatW0ZTLE71ej4kTJ6JGjRqso9gNmnT/onv37nBzc0NKSgov5zMYDPj444/psosnK1euhEqlwuuvv846iiScPn0a6enp+Pjjj1lHsSs06f6FTCbDtGnTEBISgsGDB9v0Xvzz589jz549tPkhTx49egSj0UiPbuSRVqtFZGQk7cLxDzTp/kPnzp3RuHFjfPbZZzY9j06no8suHiUnJ8Pf3x/t2rVjHUUSjh07hiNHjmD06NGso9gdyWxMWRHff/89hgwZgosXL9rk+aqnTp1C9+7dkZ2dTVMADwoLC6FSqbBr1y60atWKdRzBqsjGlG+99RZ69eqFMWPG2DiVfaKNKSuoffv28PPzw7Jly2xyfK1Wi6ioKGq4PFm4cCHat29PDZcnhw4dwpkzZ/Dhhx+yjmKXaNJ9hoyMDPTp0wfZ2dlwdna2++OSp3vw4AFUKhXS0tLg5+fHOo6glXfS7datGwYNGoTQ0FAeUtknmnQroW3btggICMDixYutelyNRoOYmBhquDyZN28eunXrRg2XJ9988w2uXr2KESNGsI5it2jSLYO1115tvVZM/i4/Px9eXl747rvv4O3tzTqO4D1v0uU4Dq+//jpCQ0MxfPhwHpPZH5p0K6lFixbo3Lkz5s+fb5XjlT40nRouP+bMmYPevXtTw+XJ119/jdzcXNqF4zlo0n2OCxcuIDAwENnZ2S/08a709HSEhobi/PnztBcXD/Ly8uDt7Y2MjAw0adKEdRxRKGvS5TgO//d//4eJEydi0KBBPCezPzTpvgBfX1/07NkTSUlJlT4GbX7IvxkzZmDAgAHUcHmyc+dOFBUVYcCAAayj2D+O4575p02bNhzhuOzsbM7NzY3Ly8ur1Pfv2bOH8/X15Uwmk5WTkae5desWV7t2be6nn35iHUVUfmsXTzKbzZy/vz+XmprKcyL7BSCDe0ZfpUm3HDw9PdGvXz/MnDmzwt/L/WXzQz4eokOAhIQEvPfee2jYsCHrKJKwdetWKBQK9OnTh3UUQaBnL5RTbGwsWrdujQkTJlTo6fdffPEFiouL8c4779gwHSn1888/Y/Xq1bQLB0/MZjO0Wi1mzJhBT24rJ5p0y8nDwwNDhgxBYmJiub/HYrFAo9HAYDDQ5oc8iYuLQ0hICOrVq8c6iiRs2LABNWrUQM+ePVlHEQyadCsgOjoar7zyCiIiIsq1o+mWLVvg4OCA4OBgHtKRnJwcbNiwAVlZWayjSELpLhyLFi2iKbcCaPyqgPr162PkyJGIj49/7mtLL7uMRiO9IXliNBoRFhYGd3d31lEkYc2aNWjQoAGCgoJYRxEUmnQrKCoqCs2aNcPkyZPL3C59/fr1qFWrFnr06MFjOunKzs7G9u3baRcOnhQXF8NgMGDNmjU0VFQQTboVVLduXXz00UeYNm3aM19jMpmg1+tpyuWRXq/HuHHjUKtWLdZRJGHFihXw9vZGx44dWUcRHLojrRLu3LkDb29vHDlyBJ6enk98fcWKFVi7di3S0tIYpJOec+fOoUuXLrh06RKqV6/OOo5old6R9ujRI3h5eWHLli0ICAhgHcsu0R1pVla7dm2MHTsWBoPhia+VXnYZjUYGyaRJp9MhIiKCGi5PlixZglatWlHDrSRa062k8PBwqFQqXLhwAb6+vn/89+XLl8PX1xcdOnRgmE46Tp48iQMHDmDlypWso0hCQUEBEhISsHv3btZRBIuabiXVqFEDIROmYPinX6Kwbg4KHpvg4qjAg9NXsCBKyzqeaOXkFSD5wBVsO3EDBY9NkJmL8eroWch9BLi6sk4nPn+td6OoHfCf9j807BeBWi95sY4mWLSmW0npWbcxet0xFD0qhkzxl59dnBnOjo5YOLQ1uviU/8418nzpWbcRti4TJWYLTJY/37dKuQwOCjnV3MqeVW+FDHBUKqjeZaA1XSvLyStA2LpMPCqx/L3hAoBMgaISM8LWZSInr4BNQBEqrXlRiflvDQAATBaOam5lZdXbzIHq/QKo6VZC8oErKDFbynxNidmCZQev8pRI/Kjm/KJ62w413UrYduLGEz/9/8lk4ZB6/GeeEokf1ZxfVG/boaZbCQWPTeV7XXH5Xkeej2rOL6q37VDTrQRXp/J96MPVkT4cYi1Uc35RvW2Hmm4l9PWvD6W87Nt7lXIZ+rVqwFMi8aOa84vqbTvUdCshNLApHBRll85BIceHHWl/LmuhmvOL6m071HQrwcPNFQuHtoazg+KJaUApl8HZ4bfPMHq40af1rYVqzi+qt+3QzREvICevAMsOXkXq8Z9RUGyCq6MS/Vo1wIcdm9Cb0Uao5vyieldOWTdHUNMlhBArozvSCCHETlDTJYQQHlHTJYQQHlHTJYQQHlHTJYQQHlHTJYQQHlHTJYQQHlHTJYQQHlHTJYQQHlHTJYQQHlHTJYQQHlHTJYQQHpX5wBuZTPYrgBz+4hBCiCh4cBxX52lfKLPpEkIIsS5aXiCEEB5R0yWEEB5R0yWEEB5R0yWEEB5R0yWEEB79PzUuiBLXMIALAAAAAElFTkSuQmCC)\n", "\n", "la distribución de grados es $p_0 = 1/10$, $p_1 = 2/10$, $p_2 = 4/10$, $p_3 = 2/10$, $p_4 = 1/10$ y $p_k = 0$ para todo $k>4$. Del ejemplo debería ser claro que la distribución de grados de un grafo finito cumple $p_k=0$ para todo $k$ suficientemente grande.\n", "\n", "Notar que la distribución de grados se puede calcular simplemente como el histograma (normalizado) de la secuencia de grados del grafo, con *bins* de tamaño 1 centrados en los enteros no negativos." ], "metadata": { "id": "XHV0WQzYwqY0" } }, { "cell_type": "markdown", "source": [ "1. Escribir una función que permita calcular la distribución de grados de un grafo a partir de una lista de los grados de los nodos del grafo. La función [`numpy.histogram`](https://numpy.org/doc/stable/reference/generated/numpy.histogram.html) puede ser de utilidad." ], "metadata": { "id": "hNeWIkUY3iEf" } }, { "cell_type": "code", "source": [ "def degree_distribution(degree_list):\n", " # TODO: Implementar esta función que acepta como argumento una lista de los\n", " # grados de un grafo y devuelve la distribución de grados del grafo\n", "\n", " degree_distribution = []\n", "\n", " ############# Tu código acá #############\n", "\n", " #########################################\n", "\n", " return degree_distribution" ], "metadata": { "id": "yJ4gI3-r3vp8" }, "execution_count": null, "outputs": [] }, { "cell_type": "code", "source": [ "# Chequeemos que la función devuelva lo correcto en el grafo de ejemplo\n", "# Armo el grafo a partir de la lista de aristas\n", "G = nx.Graph()\n", "nodelist = np.arange(1,11)\n", "G.add_nodes_from(nodelist)\n", "edgelist = [(1,2), (1,3), (2,3), (3,4), (3,6), (6,7), (6,8), (8,9), (8,10), (9,10)]\n", "G.add_edges_from(edgelist)\n", "\n", "# Fijo posiciones de nodos\n", "dx = 0.5\n", "dy = 0.5\n", "pos = {1:(0,0),2:(dx,-dy),3:(2*dx,0),4:(dx,dx),5:(3*dx,dy),6:(4*dx,0),7:(3*dx,-dy),8:(5*dx,dy),9:(5*dx,-dy),10:(6*dx,0)}\n", "# Dibujo el grafo\n", "plt.figure()\n", "plt.title('Grafo de ejemplo')\n", "nx.draw_networkx(G,pos=pos,with_labels=False,node_size=100)\n", "\n", "# Armo lista de grados de nodos.\n", "degree_list = [deg for (node,deg) in G.degree()]\n", "degree_dist = degree_distribution(degree_list)\n", "print(f'Distribución de grados del grafo de ejemplo es {degree_dist}')" ], "metadata": { "id": "Z4CuUqXQ5DSE" }, "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "source": [ "### Power-law y redes scale-free\n", "Decimos que la distribución de grados tiene *power-law* si $p_k = Ck^{-\\alpha}$. En la práctica, se observa que la distribución de grados de muchas redes del mundo real siguen una distribución power-law. En esta parte trabajaremos con una construida a partir de datos de citaciones entre papers de machine learning. Los datos provienen del paper [Automating the Construction of Internet Portals with Machine Learning](https://link.springer.com/article/10.1023/A:1009953814988). Es un grafo no dirigido, donde los nodos se corresponden a papers y si el paper $i$ cita al paper $j$ entonces hay una arista entre los nodos $i$ y $j$." ], "metadata": { "id": "KcMYQsWwC3PN" } }, { "cell_type": "code", "source": [ "# Importo el dataset, que convenientemente forma parte de Torch-Geometric\n", "from torch_geometric.datasets import Planetoid\n", "\n", "cora_dataset = Planetoid(root='/tmp/cora', name='Cora')" ], "metadata": { "id": "C8Q4j_-pwula" }, "execution_count": null, "outputs": [] }, { "cell_type": "code", "source": [ "# Algunos datos del grafo\n", "print(f'Dataset: {cora_dataset}:')\n", "print('======================')\n", "print(f'Cantidad de grafos: {len(cora_dataset)}')\n", "print(f'Cantidad de clases: {cora_dataset.num_classes}')" ], "metadata": { "id": "MV6aH30sw0qi" }, "execution_count": null, "outputs": [] }, { "cell_type": "code", "source": [ "# Miro el primer grafo\n", "cora_data = cora_dataset[0]\n", "\n", "print(cora_data)\n", "print('==============================================================')\n", "\n", "# Estadísticas del grafo.\n", "print(f'Cantidad de nodos: {cora_data.num_nodes}')\n", "print(f'Cantidad de aristas: {cora_data.num_edges}')\n", "print(f'Grado promedio de nodo: {(2*cora_data.num_edges) / cora_data.num_nodes:.2f}')\n", "print(f'Tiene nodos aislados: {cora_data.has_isolated_nodes()}')\n", "print(f'Tiene self-loops: {cora_data.has_self_loops()}')\n", "print(f'Es no dirigido: {cora_data.is_undirected()}')" ], "metadata": { "id": "JCbdXckJ0s74" }, "execution_count": null, "outputs": [] }, { "cell_type": "code", "source": [ "# Dibujo el grafo\n", "from torch_geometric.utils import to_networkx\n", "\n", "G_cora = to_networkx(cora_data)\n", "plt.figure(figsize=(12,12))\n", "cora_pos = nx.spring_layout(G_cora, seed=20)\n", "nx.draw_networkx(G_cora,node_color=cora_data.y,pos=cora_pos,with_labels=False)" ], "metadata": { "id": "2pEmubOQw3Ex" }, "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "source": [ "Los nodos de este grafo están divididos en 7 grupos según el tópico de cada paper. La idea de esta parte es estudiar si la distribución de grados de este grafo obedece una power-law. Para eso, notemos que si tomamos logaritmo en la igualdad $p_k = Ck^{-\\alpha}$ tenemos que $\\log p_k = -\\alpha \\log k + C$, por lo que si la distribución de grados tiene power-law, esperamos que la curva $k$ vs. $p_k$ se asemeje a una recta si la graficamos en escala logarítmica.\n", "\n", "2. Graficar la distribución de grados como función del grado $k$, en escala logarítmica. ¿Cree que esas distribuciones siguen una ley de potencias? ¿Por qué?" ], "metadata": { "id": "9TvS8vKpGi_E" } }, { "cell_type": "code", "source": [ "# Calculo distribución de grados para el grafo Cora\n", "deg_sequence = np.array([deg for (node, deg) in G_cora.degree()])\n", "\n", "deg_distribution = degree_distribution(deg_sequence)\n", "\n", "# TODO: graficar la distribución de grados como función del grado k, en escala\n", "# logarítmica.\n", "\n", "############# Tu código acá #############\n", "\n", "#########################################" ], "metadata": { "id": "cq7YtyOCFFUc" }, "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "source": [ "En redes reales, raramente la distribución de grados sigue una ley de potencias en todo el rango de grados $k$; generalmente se observa una relación de ese tipo para valores grandes de $k$, es decir, en la cola de la distribución. En general, cuando decimos que una red tiene power-law, nos referimos a que la distribución de grados obedece una ley de potencias para valores grandes de $k$. En ese caso, decimos que la red es *scale-free* (o libre de escala).\n", "\n", "En el gráfico de las distribuciones de grados de la red de papers debería ver que la distribución de grados tiene fluctuaciones muy grandes para valores altos de $k$, lo que no permite evaluar claramente la existencia de una ley de potencias. Eso se debe a que, a medida que aumenta el grado $k$, existen menos nodos que tienen ese grado. Por lo tanto, en cada bin del histograma de la secuencia de grados hay pocas muestras, causando el ruido que debería ver en la cola del gráfico anterior. Una posible solución consiste en agrandar los bins en la cola del histograma, para que en cada uno hayan más muestras. Por ejemplo, en lugar de usar bins linealmente equiespaciados, podríamos equiespaciarlos pero en escala logarítmica.\n", "\n", "\n", "3. Hacer un histograma de la distribución de grados usando bins de tamaño $2^n$, con $n=0,1,2, \\dots$ (es decir, equiespaciados en escala logarítmica). ¿Sigue manteniendo la misma respuesta que en la parte 2.? ¿Mejora esto su certeza de que la red es libre de escala?" ], "metadata": { "id": "ZBsx7dxjNP3G" } }, { "cell_type": "code", "source": [ "# TODO: Dibujar histograma de grados, con bins equiespaciados en escala\n", "# logarítmica.\n", "\n", "############# Tu código acá #############\n", "\n", "#########################################" ], "metadata": { "id": "YpfySSfTPqNV" }, "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "source": [ "### Distribución de Pareto\n", "Con esta elección del histograma debería observar una distribución que parece obedecer a una ley de potencias, al menos para valores de $k$ mayores que cierto valor $k_\\text{min}$. Para caracterizar este comportamiento, utilizaremos la distribución de Pareto: una variable aleatoria $X$ se dice que tiene distribución de Pareto si tiene una función de densidad de probabilidad dada por:\n", "\n", "$$p(k) = \\left\\lbrace \\begin{array}{c c} C k^{-\\alpha} & \\text{ si } k\\geq k_\\text{min} \\\\ 0 & \\text{ en otro caso} \\end{array}\\right.$$\n", "\n", "4. ¿Cuánto tiene que valer la constante $C$ para que $p$ sea efectivamente una densidad?\n", "\n", "Si tenemos $n$ observaciones independientes $k_1, \\dots,k_n$ que provienen de una distribución de Pareto, es fácil probar (ver ejercicio opcional al final del laboratorio) que el estimador de máxima verosimilitud para $\\alpha$ es:\n", "$$\\hat{\\alpha} = 1 + n \\left[\\sum_{i=1}^n \\log \\left(\\frac{k_i}{k_\\text{min}}\\right)\\right]^{-1}.$$\n", "\n", "5. Escribir una función que permita estimar $\\alpha$ para un grafo. Estimar ese parámetro para la red de citaciones de papers." ], "metadata": { "id": "nim7AxeAjaK3" } }, { "cell_type": "code", "source": [ "def alpha_maximum_likelihood(degrees_list, k_min):\n", " # TODO: Implementar esta función que acepta como argumento una lista de los\n", " # grados de un grafo y el valor del grado mínimo a partir del cual vale la\n", " # distribución power-law y devuelve la estimación del exponente α\n", "\n", " alpha_hat = 0\n", "\n", " ############# Tu código acá #############\n", "\n", " #########################################\n", "\n", " return alpha_hat" ], "metadata": { "id": "LR9N1eycQmxS" }, "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "source": [ "Calculemos el valor de $\\hat{\\alpha}$ para la red de citaciones de papers. Si la implementación anterior está bien debería ser cercano a $4$." ], "metadata": { "id": "Kugh-rpKSfYk" } }, { "cell_type": "code", "source": [ "k_min = 10\n", "alpha_hat_cora = alpha_maximum_likelihood(deg_sequence, k_min)\n", "\n", "print(f\"El valor de α para la red de papers es {alpha_hat_cora:.3f}\" )" ], "metadata": { "id": "UXtw2txo2eEx" }, "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "source": [ "### Assortative mixing\n", "\n", "En redes sociales, el concepto de *homofilia* ([*homophily*](https://en.wikipedia.org/wiki/Homophily) en inglés) refiere a la tendencia de los nodos a relacionarse con nodos similares. En lenguaje de network science, esta tendencia se denomina *assortative mixing*. Obviamente que esa tendencia depende de qué se entienda por \"similaridad\" entre nodos.\n", "\n", "Una posible medida de similaridad consiste en mirar cuántas conexiones hay entre nodos de la misma clase. Supongamos que tenemos etiquetados a los nodos de una red como pertenecientes a una de $n_c$ clases (es decir, cada nodo $i$ tiene un atributo $c_i\\in \\{1,\\dots,n_c\\}$ que indica a cuál de las $n_c$ clases pertenece). Una medida que permite cuantificar el nivel de homofilia de una red es la llamada *modularidad*, definida como:\n", "$$Q = \\frac{1}{2m} \\sum_{ij} \\left(A_{ij} -\\frac{k_ik_j}{2m} \\right)\\delta(c_i,c_j)$$\n", "donde $m$ es la cantidad total de aristas en la red, $A_{ij}$ son las entradas de la matriz de adyacencia, $k_i$ es el grado del nodo $i$ y $\\delta(r,p)$ es la delta de Kronecker: $\\delta(r,p) = 1$ si $r=p$ y $\\delta(r,p) = 0$ si $r\\neq p$. La modularidad $Q$ mide la proporción entre cuántas aristas existen en la red uniendo nodos del mismo tipo vs. cuántas aristas existirían entre nodos del mismo tipo si la asignación de conexiones fuese hecha al azar. Es estricamente menor a 1, toma valores positivos si hay más aristas entre nodos del mismo tipo que las esperadas, y negativos en caso contrario.\n", "\n", "En esta parte calcularemos el coeficiente de modularidad para el grafo de citaciones y para otro dataset, construido a partir de información de vuelos entre aeropuertos de Estados Unidos." ], "metadata": { "id": "Yxxmr-YoGwXB" } }, { "cell_type": "code", "source": [ "# Lo mismo de siempre, importo el dataset con PyTorch Geometric\n", "from torch_geometric.datasets import Airports\n", "\n", "airports_dataset = Airports(root='/tmp/airports', name='USA')" ], "metadata": { "id": "zpqFxapVFT9o" }, "execution_count": null, "outputs": [] }, { "cell_type": "code", "source": [ "# Algunos datos del grafo\n", "print(f'Dataset: {airports_dataset}:')\n", "print('======================')\n", "print(f'Cantidad de grafos: {len(airports_dataset)}')\n", "print(f'Cantidad de clases: {airports_dataset.num_classes}')" ], "metadata": { "id": "KtyB3KNoFZIG" }, "execution_count": null, "outputs": [] }, { "cell_type": "code", "source": [ "# Miro el primer grafo\n", "airports_data = airports_dataset[0]\n", "\n", "print(airports_data)\n", "print('==============================================================')\n", "\n", "# Estadísticas del grafo.\n", "print(f'Cantidad de nodos: {airports_data.num_nodes}')\n", "print(f'Cantidad de aristas: {airports_data.num_edges}')\n", "print(f'Grado promedio de nodo: {(2*airports_data.num_edges) / airports_data.num_nodes:.2f}')\n", "print(f'Tiene nodos aislados: {airports_data.has_isolated_nodes()}')\n", "print(f'Tiene self-loops: {airports_data.has_self_loops()}')\n", "print(f'Es no dirigido: {airports_data.is_undirected()}')" ], "metadata": { "id": "qRz03nckFoHN" }, "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "source": [ "Los datos para construir el grafo provienen del paper [struc2vec: Learning Node Representations from Structural Identity](https://arxiv.org/pdf/1704.03165.pdf). Los nodos corresponden a aeropuertos, y una arista entre el aeropuerto $i$ y el $j$ indica la existencia de un vuelo comercial de $i$ a $j$ (es un grafo dirigido). Los aeropuertos están etiquetados según su nivel de actividad, medida como la cantidad total de pasajeros que pasaron por ahí en el período de relevamiento de los datos (de enero a octubre de 2016). La asignación está hecha entre 4 clases, calculadas con los cuartiles de la distribución de actividad empírica de los datos. Así, la etiqueta 0 corresponde al 25% de aeropuertos menos activos, y así sucesivamente." ], "metadata": { "id": "-NlyvRN0F8Tr" } }, { "cell_type": "code", "source": [ "# Dibujo el grafo\n", "G_airports = to_networkx(airports_data)\n", "plt.figure(figsize=(12,12))\n", "airports_pos = nx.spring_layout(G_airports, seed=20)\n", "nx.draw_networkx(G_airports,node_color=airports_data.y,pos=airports_pos,with_labels=False)" ], "metadata": { "id": "m11JPyV9IYDy" }, "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "source": [ "6. Calcular la modularidad del grafo de aeropuertos y del grafo de citas entre papers. Para eso puede ser de utilidad la función [`networkx.algorithms.community.modularity`](https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.community.quality.modularity.html) y la función `communities_partition` de abajo.\n", "7. ¿Qué le dicen esos valores sobre la dinámica de las relaciones entre los nodos de cada grafo? ¿Es coherente con el comportamiento que espera de las conexiones entre los nodos de cada red?" ], "metadata": { "id": "_p3cEYwaH_vY" } }, { "cell_type": "code", "source": [ "def communities_partition(labels):\n", " # Función que, dada una lista con la asignación de clases de cada nodo de un\n", " # grafo, devuelve una partición del grafo en esas comunidades\n", "\n", " # Me fijo cuántas comunidades distintas hay\n", " communities_labels = np.unique(labels)\n", "\n", " # Armo partición del grafo. Ver ejemplo en https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.community.quality.modularity.html\n", " # para entender el formato de lo que devuelve esta función\n", "\n", " partition = [set(np.where(labels == community_idx)[0]) for community_idx in communities_labels]\n", "\n", " return partition" ], "metadata": { "id": "Bw2oFh2IbEyE" }, "execution_count": null, "outputs": [] }, { "cell_type": "code", "source": [ "# TODO: calcular la modularidad para el grafo de aeropuertos y el de citas\n", "# entre papers\n", "\n", "############# Tu código acá #############\n", "\n", "#########################################" ], "metadata": { "id": "fta4FRuxLHOQ" }, "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "source": [ "## Detección de (dos) comunidades\n", "En esta parte implementaremos dos algoritmos que vimos en clase para dividir un grafo en dos comunidades: la división espectral (*spectral partitioning*) y la maximización espectral de modularidad (*spectral modularity maximization*). Como su nombre lo indica, son métodos que se basan en la descomposición espectral (i.e. en valores y vectores propios) de alguna matriz. Aplicaremos ambos algoritmos sobre un ejemplo conocido: el Zachary's karate club.\n" ], "metadata": { "id": "y0HbTfctG3ej" } }, { "cell_type": "code", "source": [ "# Levanto la versión del karate club de Networkx, porque tiene la división en\n", "# las dos comunidades originales del paper de Zachary (la versión de PyTorch\n", "# Geometric tiene 4 comunidades)\n", "G_karate = nx.karate_club_graph()\n", "\n", "# Cada nodo tiene un atributo 'club' que dice a qué comunidad pertenece\n", "communities_gt = [G_karate.nodes[node]['club'] for node in G_karate.nodes()]\n", "print(f\"Comunidades en Zachary's karate club: {np.unique(communities_gt)}\")" ], "metadata": { "id": "7AFyjVxHS25B" }, "execution_count": null, "outputs": [] }, { "cell_type": "code", "source": [ "# Networkx define las comunidades con nombre ('Mr. Hi' u 'Officer'). Las\n", "# codifico con dos enteros cualquiera\n", "communities_dict = {'Mr. Hi': -1, 'Officer':1}\n", "communities_gt_int = [communities_dict[gt] for gt in communities_gt]\n", "\n", "# Dibujo el grafo con las comunidades en colores\n", "plt.figure(figsize=(8,8))\n", "karate_pos = nx.spring_layout(G_karate, seed=42)\n", "nx.draw_networkx(G_karate,node_color=communities_gt_int,pos=karate_pos,cmap='coolwarm')" ], "metadata": { "id": "Cteya_-lUhro" }, "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "source": [ "### Spectral partitioning\n", "En este contexto, el problema de *particionar* un grafo consiste en dividir el grafo en dos comunidades cuyo tamaño está fijo de antemano. En caso que querramos dividir al grafo en dos comunidades pero sin pre-especificar su tamaño, diremos que estamos resolviendo el problema de *detección de comunidades*. Como su nombre lo indica, el algoritmo de *spectral partitioning* cae en la primera categoría." ], "metadata": { "id": "tMSGGyBikcnX" } }, { "cell_type": "markdown", "source": [ "8. Implementar el algoritmo de spectral partitioning que vimos en clase, que permita dividir un grafo $G$ en dos comunidades de tamaños $n_1$ y $n_2$ dados." ], "metadata": { "id": "XG7--6WIV3u1" } }, { "cell_type": "code", "source": [ "def spectral_partitioning(G,n_1,n_2):\n", " # TODO: Implementar el algoritmo de spectral partitioning. Esta función acepta\n", " # como argumento un grafo G de Networkx y dos enteros n_1 y n_2 y devuelve\n", " # un vector de numpy con la asignación de clases de cada nodo del grafo,\n", " # codificada con dos enteros distintos. Por ejemplo, a los nodos de la\n", " # comunidad 1 los codifico con un 1 y a los de la comunidad 2 con un 2. Se\n", " # puede usar cualquier par de enteros -siempre que sean distintos-.\n", "\n", " communities_assignments = np.zeros((G.number_of_nodes(),))\n", "\n", " ############# Tu código acá #############\n", "\n", " #########################################\n", "\n", " return communities_assignments" ], "metadata": { "id": "vX7HiLpLG_W2" }, "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "source": [ "Si hizo las cosas bien, el algoritmo debería recuperar perfectamente la asignación de clases cuando la división se hace en dos comunidades de igual tamaño." ], "metadata": { "id": "yPrs5nK1aTK-" } }, { "cell_type": "code", "source": [ "# Divido en comunidades de igual tamaño\n", "n_1 = int(G_karate.number_of_nodes()/2)\n", "n_2 = n_1\n", "karate_partition = spectral_partitioning(G_karate,n_1,n_2)\n", "\n", "# Paso etiquetas de la partición a un orden coherente con el del ground truth\n", "karate_partition = remap_labels(communities_gt_int,karate_partition)\n", "\n", "# Dibujo grafo con asignación de clases dada por la partición espectral\n", "plt.figure(figsize=(16,8))\n", "ax1 = plt.subplot(1,2,1)\n", "_= ax1.set_title('Etiquetas reales',fontsize = 16)\n", "nx.draw_networkx(G_karate,node_color=communities_gt_int,pos=karate_pos,ax=ax1,cmap='coolwarm')\n", "ax2 = plt.subplot(1,2,2)\n", "nx.draw_networkx(G_karate,node_color=karate_partition,pos=karate_pos,ax=ax2,cmap='coolwarm')\n", "_= ax2.set_title('Detección usando spectral partitioning',fontsize = 16)" ], "metadata": { "id": "ltYqRfcFXzEd" }, "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "source": [ "Una forma de medir numéricamente qué tan buena es la asignación de comunidades es mediante el [índice de Rand](https://en.wikipedia.org/wiki/Rand_index). Tiene un máximo de 1, que se da si las asignaciones son iguales." ], "metadata": { "id": "tBRAwghObuJw" } }, { "cell_type": "code", "source": [ "from sklearn.metrics import adjusted_rand_score\n", "# Usamos el adjusted_rand_score, que está definido de manera tal que si la\n", "# asignación es al azar esperamos obtener un valor cercano a 0 (el índice de\n", "# Rand simple no nos asegura esto)\n", "rand_score_spectral = adjusted_rand_score(communities_gt_int,karate_partition)\n", "print(f\"Índice de Rand (ajustado) para el spectral partitioning del karate club: {rand_score_spectral:.3f}\")" ], "metadata": { "id": "v6dx35OXaw7Q" }, "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "source": [ "Otra posible medida de qué tan buena es la asignación de comunidades es el [índice de Fowlkes-Mallows](https://scikit-learn.org/stable/modules/clustering.html#fowlkes-mallows-scores), definido como la media geométrica del [precision y el recall](https://en.wikipedia.org/wiki/Precision_and_recall) de la asignación. Este índice va de 0 a 1, y es 1 si las asignaciones son iguales." ], "metadata": { "id": "3TpvAynUdwLS" } }, { "cell_type": "code", "source": [ "from sklearn.metrics import fowlkes_mallows_score\n", "# Convenientemente, sklearn tiene implementados estos índices (y muchos más)\n", "# Ver https://scikit-learn.org/stable/modules/clustering.html#clustering-performance-evaluation\n", "mallows_score_spectral = fowlkes_mallows_score(communities_gt_int,karate_partition)\n", "print(f\"Índice de Fowlkes-Mallows para el spectral partitioning del karate club: {mallows_score_spectral:.3f}\")" ], "metadata": { "id": "zV56YOwhdSsO" }, "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "source": [ "Miremos qué nos dice cada índice si la asignación es al azar." ], "metadata": { "id": "P-f5RRyhf7QR" } }, { "cell_type": "code", "source": [ "# Asigno etiquetas al azar\n", "random_assignments = np.random.randint(1,size=G_karate.number_of_nodes())\n", "\n", "rand_score_random = adjusted_rand_score(communities_gt_int,random_assignments)\n", "mallows_score_random = fowlkes_mallows_score(communities_gt_int,random_assignments)\n", "print(f\"Índice de Rand (ajustado) para asignación al azar del karate club: {rand_score_random:.3f}\")\n", "print(f\"Índice de Fowlkes-Mallows para asignación al azar del karate club: {mallows_score_random:.3f}\")" ], "metadata": { "id": "8KAveronfGJp" }, "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "source": [ "### Spectral modularity maximization\n", "Una desventaja del método de partición espectral es que necesitamos conocer de antemano la cantidad de nodos en cada comunidad. El método *spectral modularity maximization* permite detectar dos comunidades sin conocer el tamaño de cada una (es, por lo tanto, un algoritmo de *community detection*)." ], "metadata": { "id": "CRkWpXc8kgKJ" } }, { "cell_type": "markdown", "source": [ "9. Implementar el algoritmo de spectral modularity maximization que vimos en clase, que permita dividir un grafo $G$ en dos comunidades. La función [`networkx.modularity_matrix`](https://networkx.org/documentation/stable/reference/generated/networkx.linalg.modularitymatrix.modularity_matrix.html) puede ser de utilidad." ], "metadata": { "id": "ioPfcHB_hjPY" } }, { "cell_type": "code", "source": [ "def spectral_modularity_maximization(G):\n", " # TODO: Implementar el algoritmo de spectral modularity maximization.\n", " # Esta función acepta como argumento un grafo G de Networkx y devuelve\n", " # un vector de numpy con la asignación de clases de cada nodo del grafo,\n", " # codificada con dos enteros distintos. Por ejemplo, a los nodos de la\n", " # comunidad 1 los codifico con un 1 y a los de la comunidad 2 con un 2. Se\n", " # puede usar cualquier par de enteros -siempre que sean distintos-.\n", "\n", " communities_assignments = np.zeros((G.number_of_nodes(),))\n", "\n", " ############# Tu código acá #############\n", "\n", " #########################################\n", "\n", " return communities_assignments" ], "metadata": { "id": "LubOAKo5h99B" }, "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "source": [ "En este caso, el algoritmo debería asignar correctamente a todos los nodos menos a uno (el nodo número 8). Es el precio a pagar por no conocer la cantidad de elementos en cada comunidad de antemano." ], "metadata": { "id": "qgi2MjD6jFnM" } }, { "cell_type": "code", "source": [ "karate_modularity_assingments = spectral_modularity_maximization(G_karate)\n", "\n", "# Paso etiquetas de la partición a un orden coherente con el del ground truth\n", "karate_modularity_assingments = remap_labels(communities_gt_int,karate_modularity_assingments)\n", "\n", "# Dibujo grafo con asignación dada por el spectral modularity maximization\n", "# El nodo 8 pertenece a la comunidad \"de abajo\", pero en esta asignación\n", "# debería aparecer como perteneciente a la comunidad de arriba.\n", "plt.figure(figsize=(16,8))\n", "ax1 = plt.subplot(1,2,1)\n", "_= ax1.set_title('Etiquetas reales',fontsize = 16)\n", "nx.draw_networkx(G_karate,node_color=communities_gt_int,pos=karate_pos,ax=ax1,cmap='coolwarm')\n", "ax2 = plt.subplot(1,2,2)\n", "nx.draw_networkx(G_karate,node_color=karate_modularity_assingments,pos=karate_pos,ax=ax2,cmap='coolwarm')\n", "_= ax2.set_title('Detección usando spectral modularity maximization',fontsize = 16)\n", "\n", "\n", "# Calculo índices para esta asignación\n", "rand_score_modularity = adjusted_rand_score(communities_gt_int,karate_modularity_assingments)\n", "mallows_score_modularity = fowlkes_mallows_score(communities_gt_int,karate_modularity_assingments)\n", "print(f\"Índice de Rand (ajustado) para spectral modularity maximization del karate club: {rand_score_modularity:.3f}\")\n", "print(f\"Índice de Fowlkes-Mallows para spectral modularity maximization del karate club: {mallows_score_modularity:.3f}\")" ], "metadata": { "id": "UsOyY9-Akjnh" }, "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "source": [ "### Detección de orientación política de blogs\n", "Por último, vamos a detectar comunidades en un dataset real. Se trata de datos de blogs sobre política estadounidense, en un momento cercano a la elección del 2004 en ese país. Proviene del paper [The Political Blogosphere and the 2004 US Election: Divided they Blog](https://dl.acm.org/doi/10.1145/1134271.1134277).\n", "\n", "Cada nodo del grafo corresponde a un blog, y hay una arista del nodo $i$ al nodo $j$ si el blog $i$ tiene un link al nodo $j$. Es por lo tanto un grafo dirigido; para esta parte lo convertiremos a no dirigido: simplemente, ponemos una arista entre $i$ y $j$ en el grafo no dirigido si en la versión dirigida existe una arista que une $i$ con $j$ en alguna dirección. Cada blog está etiquetado según su afiliación a uno de los dos grandes partidos de la política estadounidense." ], "metadata": { "id": "FCA64xK7zzml" } }, { "cell_type": "code", "source": [ "# El dataset está disponible en PyTorch Geometric. Lo importamos como siempre\n", "from torch_geometric.datasets import PolBlogs\n", "\n", "blogs_dataset = PolBlogs(root='/tmp/polblogs')" ], "metadata": { "id": "bLKtCj_hw7V3" }, "execution_count": null, "outputs": [] }, { "cell_type": "code", "source": [ "# Características del dataset. Hay un solo grafo y 2 clases de blogs\n", "print(f'Dataset: {blogs_dataset}:')\n", "print('======================')\n", "print(f'Cantidad de grafos: {len(blogs_dataset)}')\n", "print(f'Cantidad de clases: {blogs_dataset.num_classes}')" ], "metadata": { "id": "UmA8O5-S0De6" }, "execution_count": null, "outputs": [] }, { "cell_type": "code", "source": [ "# Miro el único grafo que hay\n", "blogs_data = blogs_dataset[0]\n", "\n", "print(blogs_data)\n", "print('==============================================================')\n", "\n", "# Algunas estadísticas\n", "print(f'Cantidad de nodos: {blogs_data.num_nodes}')\n", "print(f'Cantidad de aristas: {blogs_data.num_edges}')\n", "print(f'Grado promedio de nodo: {(2*blogs_data.num_edges) / blogs_data.num_nodes:.2f}')\n", "print(f'Tiene nodos aislados: {blogs_data.has_isolated_nodes()}')\n", "print(f'Tiene self-loops: {blogs_data.has_self_loops()}')\n", "print(f'Es no dirigido: {blogs_data.is_undirected()}')" ], "metadata": { "id": "nF68e6uk0EHY" }, "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "source": [ "Vemos que el grafo es dirigido y además tiene auto aristas (aristas que van de un nodo a sí mismo). Lo vamos a convertir a no dirigido y vamos a quitar las auto-aristas. Además, no es un grafo conexo; vamos a hacer detección de comunidades en la componente conexa más grande del grafo." ], "metadata": { "id": "zYE4Z11Wmk5h" } }, { "cell_type": "code", "source": [ "# Convierto el grafo a no dirigido usando Networkx porque PyG lo convierte\n", "# usando solo la parte triangular superior o inferior de la adyacencia.\n", "G_blogs = to_networkx(blogs_data, to_undirected=False)\n", "G_blogs = G_blogs.to_undirected()\n", "\n", "# Me quedo solo con la componente conexa más grande\n", "largest_cc_nodes = max(nx.connected_components(G_blogs), key=len)\n", "G_lcc = G_blogs.subgraph(largest_cc_nodes).copy()\n", "\n", "# Le saco los self loops\n", "G_lcc.remove_edges_from(nx.selfloop_edges(G_lcc))\n", "\n", "# Me quedo con las etiquetas de la componente conexa más grande\n", "G_lcc_labels = blogs_data.y[list(largest_cc_nodes)]\n", "\n", "# Dibujo el grafo\n", "G_lcc_pos = nx.spring_layout(G_lcc, seed=20)\n", "plt.figure(figsize=(12,12))\n", "nx.draw_networkx(G_lcc,node_color=G_lcc_labels,pos=G_lcc_pos,with_labels=False)" ], "metadata": { "id": "lRPiXS3R0IkL" }, "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "source": [ "Como en un dataset real en general no conocemos la cantidad de elementos que tiene cada comunidad, vamos a hacer detección de comunidades usando spectral modularity maximization." ], "metadata": { "id": "_83mt1YYoPI-" } }, { "cell_type": "code", "source": [ "# Hago detección de comunidades usando implementación de spectral modularity\n", "# maximization\n", "mod_max_blogs = spectral_modularity_maximization(G_lcc)\n", "# Paso etiquetas de la partición a un orden coherente con el del ground truth\n", "mod_max_blogs = remap_labels(G_lcc_labels,mod_max_blogs)\n", "\n", "# Dibujo comunidades reales y comunidades detectadas\n", "plt.figure(figsize=(20,10))\n", "ax1 = plt.subplot(1,2,1)\n", "_= ax1.set_title('Etiquetas reales',fontsize = 16)\n", "nx.draw_networkx(G_lcc,node_color=G_lcc_labels,pos=G_lcc_pos,with_labels=False,ax=ax1)\n", "ax2 = plt.subplot(1,2,2)\n", "nx.draw_networkx(G_lcc,node_color=mod_max_blogs,pos=G_lcc_pos,with_labels=False,ax=ax2)\n", "_= ax2.set_title('Detección usando spectral modularity maximization',fontsize = 16)" ], "metadata": { "id": "XmRDsLFW0vUH" }, "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "source": [ "Miro qué dicen los indicadores sobre la detección de comunidades. Debería dar algo cercano a 1 en ambos casos." ], "metadata": { "id": "K-hnvk-e3ZeU" } }, { "cell_type": "code", "source": [ "rand_score_blogs = adjusted_rand_score(G_lcc_labels, mod_max_blogs)\n", "mallows_score_blogs = fowlkes_mallows_score(G_lcc_labels,mod_max_blogs)\n", "print(f\"Índice de Rand (ajustado) para spectral modularity maximization de blogs políticos: {rand_score_blogs:.3f}\")\n", "print(f\"Índice de Fowlkes-Mallows para spectral modularity maximization de blogs políticos: {mallows_score_blogs:.3f}\")" ], "metadata": { "id": "6pBt1fdq2keN" }, "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "source": [ "10. ¿Qué diferencias cualitativas ve entre las figuras de arriba? ¿Le dice esto algo sobre las limitaciones del método de spectral modularity maximization?" ], "metadata": { "id": "o15DMdTtp6ST" } }, { "cell_type": "markdown", "source": [ "## (Opcional) Estimador de máxima verosimilitud para el exponente de la distribución de Pareto\n", "\n", "La idea de este ejercicio es demostrar la fórmula del estimador de máxima verosimilitud que usamos antes para el exponente de la distribución de Pareto. Quienes lo entreguen (correctamente resuelto) tendrán puntos extra en el laboratorio.\n", "\n", "1. Supongamos que tenemos $n$ observaciones independientes $k_1, \\dots,k_n$ que provienen de la distribución de Pareto. Demostrar que la función de log-verosimilitud está dada por:\n", "$$\\mathcal{l}_n(\\alpha) = n \\log (\\alpha -1)-n\\log k_\\text{min} - \\alpha \\sum_{i=1}^n \\log \\left(\\frac{k_i}{k_\\text{min}}\\right).$$\n", "\n", "2. Concluir que el estimador de máxima verosimilitud para $\\alpha$ es:\n", "$$\\hat{\\alpha} = 1 + n \\left[\\sum_{i=1}^n \\log \\left(\\frac{k_i}{k_\\text{min}}\\right)\\right]^{-1}.$$" ], "metadata": { "id": "e-3W-qoxVqWI" } }, { "cell_type": "code", "source": [], "metadata": { "id": "UEyFnjuNV6EY" }, "execution_count": null, "outputs": [] } ] }