PageRank explicado.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# PageRank - Explicado"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Definiciones  \n",
    "\n",
    " - $PR(usuario_i)$: PageRank calculado para la el usuario $i$.\n",
    " - Backlink: Si la el usuario $A$ sigue a $B$, entonces se dice que el usuario $B$ tiene un *backlink* desde $A$.\n",
    " \n",
    "## ¿Qué es PageRank?  \n",
    "\n",
    "En resumen, PageRank es una especie de \"voto\", otorgado por todos los usuarios de twitter qué tan importante un determinado usuario es. Cada follow cuenta como un \"voto\".\n",
    "\n",
    "## ¿Cómo funciona?  \n",
    "\n",
    "Supongamos que tenemos $N$ usuarios en nuestro universo. Y si el usuario $A$ es seguido por $u_1$, $u_2$, $...$, $u_n$, el PageRank del usuario $A$ está determinado por:  \n",
    "\n",
    "$$PR(A) = \\frac{1 - d}{N} + d \\left( \\frac{PR(u_1)}{L(u_1)} +  \\frac{PR(u_2)}{L(u_2)} +\\space...\\space+  \\frac{PR(u_n)}{L(u_n)} \\right)$$\n",
    "\n",
    "Nuevos términos: \n",
    "\n",
    " -  $L(u_n)$ - El término $L(u_n)$ se refiere el número de usuarios que el usuario $u_n$ sigue, su contribución al PageRank de cualquiera de las personas que sigue se ve \"diluido\" entre más usuarios siga.\n",
    " - $d$ - es conocida como factor de moderación. Un valor común es $0.85$.  \n",
    "\n",
    "## ¿Iterativo?  \n",
    "\n",
    "No es suficiente con calcular el PageRank una sola vez, puesto que los valores fluctuan, la importancia de un determinado usuario no puede ser calculado en una sola operación... sin embargo, con el tiempo, los valores de PageRank convergen, es decir, se mantienen estables. La fórmula en realidad se divide en:  \n",
    "\n",
    "Cuando $t = 0$:  \n",
    "\n",
    "$$PR(u_i;0) = \\frac{1}{N}$$\n",
    "\n",
    "Para cualquier otro valor de $t$:  \n",
    "\n",
    "$$PR(u_i;t) = \\frac{1 - d}{N} + d \\sum_{u_j \\in S(u_i) } \\frac{PR(u_j;t-1)}{L(u_j)}$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import json\n",
    "from collections import defaultdict\n",
    "from copy import deepcopy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def invert_graph(graph: dict):\n",
    "\n",
    "    followers_graph = defaultdict(set)\n",
    "\n",
    "    for user, followed_users in graph.items():\n",
    "        for followed_user in followed_users:\n",
    "            followers_graph[followed_user].add(user)\n",
    "    \n",
    "    return dict(followers_graph)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def calculate_pr(graph, d = 0.85, iterations = 100, debug = False):\n",
    "    inverted_graph = invert_graph(graph)\n",
    "    \n",
    "    N = len(graph)\n",
    "    S = lambda u: inverted_graph.get(u, set())\n",
    "    L = lambda u: len(graph[u])\n",
    "\n",
    "    initial_pr = { user: 1 / N for user in graph }\n",
    "    previous_pr = deepcopy(initial_pr)\n",
    "\n",
    "    for it in range(1, iterations + 1):\n",
    "        iteration_pr = {}\n",
    "        for u_i in graph:\n",
    "            simple_page_rank = (1 - d) / N\n",
    "            contributions = 0\n",
    "            for u_j in S(u_i):\n",
    "                contributions += previous_pr[u_j] / L(u_j)\n",
    "            iteration_pr[u_i] = simple_page_rank + d * contributions\n",
    "        previous_pr = deepcopy(iteration_pr)\n",
    "\n",
    "    return previous_pr"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Un micro ejemplo  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "twitter_graph = {}\n",
    "with open(\"twitter_closed.jsonl\") as readable:\n",
    "    for line in readable:\n",
    "        user = json.loads(line)\n",
    "        twitter_graph[user[\"user_id\"]] = user[\"following_id\"]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "results = calculate_pr(twitter_graph, iterations = 10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "results[2582486138]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "results[1306760288243462147]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}