2324-L22-Nx.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "### CS4423 - Networks\n",
    "Angela Carnevale  \n",
    "School of Mathematical and Statistical Sciences  \n",
    "University of Galway"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "#### 6. Directed Networks\n",
    "\n",
    "# Week 11, lecture 2:  Hubs and Authorities"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Importance of nodes in directed networks"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Adjacency matrix of a directed network"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Let $M = (m_{ij})$ be the **adjacency matrix** of the directed graph\n",
    "$G = (X, E)$\n",
    "that is \n",
    "\n",
    "$$m_{ij} = \\begin{cases} 1 & \\text{if } x_j \\to x_i,  \\\\\n",
    " 0 & \\text{ otherwise}\\end{cases},$$\n",
    "where $X = \\{x_1, \\dots, x_n\\}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### In-Degree vs. Out-Degree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "In a directed network, one can distinguish between **in-degree centrality** $c_i^{D^{\\text{in}}}$ and **out-degree centrality** $c_i^{D^{\\text{out}}}$\n",
    "based on the number of arrows that point **into** a node, and the number of arrows pointing\n",
    "**out** of a node:\n",
    "$$\n",
    "c_i^{D^{\\text{in}}} = k_i^{\\text{in}} = \\sum_{j=1}^n m_{ij},\n",
    "\\quad\n",
    "c_i^{D^{\\text{out}}} = k_i^{\\text{out}} = \\sum_{j=1}^n m_{ji},\n",
    "$$\n",
    "where $M = (m_{ij})$ is the adjacency matrix of a directed graph\n",
    "$G = (X, E)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Similarly, one can define and study the corresponding **eigenvector centralities** $c^{E^{\\text{in}}}$ and $c^{E^{\\text{out}}}$:\n",
    "$$\n",
    "A c^{E^{\\text{in}}} = \\lambda c^{E^{\\text{in}}},\n",
    "\\quad\n",
    "A^{T} c^{E^{\\text{out}}} = \\lambda c^{E^{\\text{out}}}.\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Especially with a view towards our main example of a directed network (the WWW), we take here a slightly different approach."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "##  Hub Centrality and Authority Centrality"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "In a network of nodes connected by directed edges, each node can\n",
    "play two different roles:\n",
    "\n",
    "* one as a _receiver_ of links, and \n",
    "\n",
    "* one as a _sender_ of links.  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "A first measure of importance, or recognition, of\n",
    "a node in this network might be the number of\n",
    "links it receives, i.e., its **in-degree** in the underlying graph.\n",
    "If in a collection of web pages relating to a search query on the\n",
    "subject of \"networks\", say, a particular page receives a high number\n",
    "of links, this page might count as an **authority** on that subject,\n",
    "with **authority score** measured by its in-degree."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "In turn, the web pages linking to an authority in some sense know\n",
    "where to find valuable information and thus serve as good \"lists\" for\n",
    "the subject.\n",
    "A high-value list is called a **hub** for this query.\n",
    "It makes sense to measure the value of a page as list in\n",
    "terms of the values of the pages it points at, by assigning to its\n",
    "**hub score** the sum of the authority scores of the pages it points\n",
    "at."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "![hubs](images/hubs.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Now\n",
    "the authority score of a page  could take the hub scores\n",
    "of the list pages into account, by using the sum of the hub scores\n",
    "of the pages that point at it as an updated authority score..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Then again, applying the **Principle of Repeated Improvement**,\n",
    "the hub scores can be updated on the basis of the new authority scores,\n",
    "and so on."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "This suggests a ranking procedure that tries to estimate, for each page $p$,\n",
    "its value as an authority and its value as a hub in the form\n",
    "of numerical scores, $a(p)$ and $h(p)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Starting off with values all equal to $1$, the estimates are updated\n",
    "by applying the following two rules in an alternating fashion."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "**Authority Update Rule:**\n",
    "For each page $p$, update $a(p)$\n",
    "to be the sum of the hub scores of all the pages pointing to it."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "    \n",
    "**Hub Update Rule:**\n",
    "For each page $p$,\n",
    "update $h(p)$\n",
    "to be the sum of the authority\n",
    "scores of all the pages\n",
    "that it points to.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "In order to keep the numbers from growing too large,\n",
    "score vectors should be **normalised** after each step,\n",
    "in a way that  replaces $h$ by a scalar multiple $\\hat{h} = sh$\n",
    "so that the entries in $\\hat{h}$ add up to $100$, say,\n",
    "representing relative percentage values,\n",
    "similarly for $a$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "After a number of iterations, the values $a(p)$ and\n",
    "$h(p)$ stabilise, in the sense that further applications of\n",
    "the update rules do not yield essentially better relative estimates."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "**Example.**\n",
    "Continuing the example above ..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "import networkx as nx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "nodes = list(range(1,10)) + [\"A%s\" % (i+1) for i in range(7)]\n",
    "print(nodes)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "edges = [\n",
    "    (1,\"A1\"),(2,\"A1\"),(3,\"A1\"),(3,\"A2\"),(4,\"A2\"),(5,\"A3\"),\n",
    "    (5,\"A5\"),(6,\"A2\"),(6,\"A4\"),(7,\"A4\"),(7,\"A5\"),(8,\"A4\"),\n",
    "    (8,\"A5\"),(8,\"A6\"),(8,\"A7\"),(9,\"A5\"),(9,\"A6\"),(9,\"A7\")\n",
    "]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "G = nx.DiGraph()\n",
    "G.add_nodes_from(nodes)\n",
    "G.add_edges_from(edges)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "pos = nx.circular_layout(G)\n",
    "for i in [1,2,3,4]:\n",
    "    j = 10 - i\n",
    "    pos[i], pos[j] = pos[j], pos[i]\n",
    "colors = 9 * ['y'] + 7 * ['w']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "nx.draw(G, with_labels=True, node_color=colors, pos=pos)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Let's use dictionaries, with nodes as keys and hub or authority scores as values.\n",
    "Here's a way to normalize such a record."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "def normalized(d):\n",
    "    s = sum(d.values())\n",
    "    return { k: 100/s*v for k, v in d.items() }"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Initially, all scores are set to $1$ (and then normalized)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "hubs = normalized({ x : 1 for x in G })\n",
    "auth = normalized({ x : 1 for x in G })\n",
    "hubs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "The update rules can then be implemented as follows."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "def HubsUpdate(G, auth):\n",
    "    h = { x: 0 for x in G }\n",
    "    for x in G:\n",
    "        for y in G.successors(x):\n",
    "            h[x] += auth[y]\n",
    "    return normalized(h)\n",
    "\n",
    "def AuthUpdate(G, hubs):\n",
    "    a = { x: 0 for x in G }\n",
    "    for x in G:\n",
    "        for y in G.successors(x):\n",
    "            a[y] += hubs[x]\n",
    "    return normalized(a)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Now we can apply the rules. alternating between the two, say 10 times, and observe how the scores stabilize."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "for k in range(20):\n",
    "    auth = AuthUpdate(G, hubs)\n",
    "    print(\"auth score A3 = \", auth['A3'])\n",
    "    hubs = HubsUpdate(G, auth)\n",
    "    print(\"hubs score 1 = \", hubs[1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "All in one `python` function:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "def HubsAuth(G, k):\n",
    "    hubs = normalized({ x : 1 for x in G })\n",
    "    auth = normalized({ x : 1 for x in G })\n",
    "    for i in range(k):\n",
    "        auth = AuthUpdate(G, hubs)\n",
    "        hubs = HubsUpdate(G, auth)\n",
    "    \n",
    "    return hubs, auth"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "hubs, auth = HubsAuth(G, 10)\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "hubs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Finally, let's apply this to a random directed graph."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "n, m = 80, 120\n",
    "G = nx.gnm_random_graph(n, m, directed=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "hubs, auth = HubsAuth(G, 50)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Let's inspect the top and the bottom 10 scores."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "[(k,auth[k]) for k in sorted(auth, key=auth.get, reverse=True)][:10]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "[(k,auth[k]) for k in sorted(auth, key=auth.get)][:10]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "[(k, hubs[k]) for k in sorted(hubs, key=hubs.get, reverse=True)][:10]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "[(k, hubs[k]) for k in sorted(hubs, key=hubs.get)][:10]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "In terms of matrix algebra this process can be described as follows."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "###  Spectral Analysis of Hubs and Authorities"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Let $M = (m_{ij})$ be the **adjacency matrix** of the directed graph\n",
    "$G = (X, E)$\n",
    "that is $m_{ij} = 1$ if $x_j \\to x_i$ and $m_{ij} = 0$ otherwise,\n",
    "where $X = \\{x_1, \\dots, x_n\\}$.\n",
    "\n",
    "We write $h = (h_1, \\dots, h_n)$ for a list of hub scores, with $h_i = h(x_i)$,\n",
    "the hub score of node $x_i$.  Similarly, we write $a = (a_1, \\dots, a_n)$ for\n",
    "a list of authority scores."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "The **hub update rule** can now be expressed as\n",
    "a **matrix multiplication**:\n",
    "$$\n",
    "h \\gets M^T a\n",
    "$$\n",
    "and similarly, the **authority update rule**, using the transpose of the matrix $M$:\n",
    "$$\n",
    "a \\gets M h\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Applying two steps of the procedure at once yields update rules\n",
    "$$\n",
    "  h \\gets M^T M h\n",
    "$$\n",
    "and\n",
    "$$\n",
    "  a \\gets M M^T \\, a\n",
    "$$\n",
    "for $h$ and $a$, respectively.  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "**In the limit**, one expects\n",
    "to get vectors $h^{\\ast}$ and $a^{\\ast}$ whose directions do not change\n",
    "under the latter rules, i.e.,\n",
    "$$\n",
    "  (M^T M) h^{\\ast} = c h^{\\ast}\n",
    "$$\n",
    "and\n",
    "$$\n",
    "  (M M^T) a^{\\ast} = d a^{\\ast}\n",
    "$$\n",
    "for certain constants $c$ and $d$, meaning that $h^{\\ast}$ and $a^{\\ast}$\n",
    "are **eigenvectors** for the matrices $M^T M$ and $M M^T$,\n",
    "respectively."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Using the fact that $M^T M$ and $M M^T$ are **symmetric** matrices\n",
    "($(M^T M)^T = M^T (M^T)^T = M^T M$),\n",
    "it can indeed be shown that any sequence of hub score vectors\n",
    "$h$ under repeated application of the above update rule\n",
    "converges to a real-valued eigenvector $h^{\\ast}$ of $M M^T$ for the real eigenvalue $c$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "The argument uses the [Spectral Theorem](https://en.wikipedia.org/wiki/Spectral_theorem)\n",
    "for [real symmetric matrices](https://en.wikipedia.org/wiki/Symmetric_matrix#Real_symmetric_matrices).\n",
    "\n",
    "\n",
    "A similar result exists for any sequence of authority score vectors $a$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "celltoolbar": "Slideshow",
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}