{ "cells": [ { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "# CS579: Lecture 05 \n", "** Community Detection **\n", "\n", "*[Dr. Aron Culotta](http://cs.iit.edu/~culotta)* \n", "*[Illinois Institute of Technology](http://iit.edu)*\n", "\n", "(Many figures come from [Mining of Massive Datasets](http://www.mmds.org/), Jure Leskovec, Anand Rajaraman, Jeff Ullman)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "![network](network.png)\n", "\n", "- **Why do we want to identify communities?**\n", "- **What are the \"communities\" in this graph?**\n", "- **Why did you choose these communities?**\n", "\n", "




" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**A bad solution: Agglomerative clustering**\n", "\n", "- Let distance function $d(A,B)$ be the shortest path between nodes $A$ and $B$\n", "- Let $C_i$ and $C_j$ be two clusters of nodes. Then, let the distance between two clusters be the minimum distance of any two nodes: $d(C_i, C_j) = \\min_{X \\in C_i, Y \\in C_j} \\hspace{.1cm} d(X, Y)$\n", "- Greedy agglomerative clustering iterative merges the closest two clusters \n", "\n", "" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**What would agglomerative clustering do on this network? **\n", "\n", "![network](network.png)\n", "\n", "$d(A,B) = d(A,C) = d(B, C) = d(B,D) = d(D,E) = d(D,F) = d(D,G) = d(E,F) = d(G,F) = 1$\n", "\n", "$d(A,D) = d(C,D) ... = 2$\n", "\n", "


\n", "First merge: sample randomly from all nodes with distance == 1.\n", "\n", "\n", "


\n", "So, $\\frac{1}{9}$ chance we merge $B$ and $D$ in first merge.\n", "\n", "Not desireable...any other ideas?\n", "\n", "What makes the edge between $B$ and $D$ special?\n", "\n", "



" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "**Betweenness:** The betweenness of an edge $(A, B)$ is the number of shortest paths between any nodes $X$ and $Y$ that include edge $(A, B)$.\n", "\n", "High betweenness $\\rightarrow$ $A$ and $B$ belong in different communities." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "![network](network.png)\n", "\n" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "What is **betweenness** of $(B,D)$?\n", "\n", "


\n", "\n", "> $(B,D)$ is on all shortest paths connecting any of $\\{A,B,C\\}$ to any of $\\{D,E,F,G\\}$.\n", "\n", "> Thus, total number of shortest paths = number passing through $(B,D)$ = $3 * 4 = \\mathbf{12}.$. So, $bt(B,D) = 12$\n", "\n", "\n", "



\n", "What is **betweenness** of $(D,F)$?\n", "\n", "



\n", "\n", "> $(D,F)$ is on shortest paths from $\\{A,B,C,D\\}$ to $\\{F\\}$.\n", "\n", "> Thus, betweenness is $4 * 1 = \\mathbf{4}.$\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "
\n", "Consider this graph:\n", "\n", "![between](between3.png)\n", "\n", "What is **betweenness** of $(D,G)$?\n", "\n", "


\n", "\n", "> $(D,G)$ is on the shortest path from $D$ to $G$. \n", "> $(D,G)$ is also on one of the two shortest paths from $D$ to $F$ and $E$ to $G$. \n", "\n", "> Since there can be several shortest paths between two nodes, an edge (a, b) is credited with the fraction of those shortest paths that include the edge (a, b).\n", "\n", "> Thus, betweenness is $\\frac{1}{2} + \\frac{1}{2} + 1 = \\mathbf{2}.$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Formally:\n", "\n", "$$\n", "bt(e) =\\sum_{s,t \\in V} \\frac{\\sigma(s, t|e)}{\\sigma(s, t)}\n", "$$\n", "where\n", "\n", "- $V$ is the set of nodes\n", "- $\\sigma(s, t)$ is the number of shortest paths between nodes $s$ and $t$\n", "- $\\sigma(s, t|e)$ is the number of those paths passing through some edge $e$ \n", "\n", "If $s = t$, $\\sigma(s, t) = 1$\n", "\n", "So, if there are two shortest paths between $s$ and $t$, but only one goes through $e$, betweenness only increases by 0.5.\n", "\n", "\n" ] }, { "cell_type": "code", "execution_count": 15, "metadata": {}, "outputs": [ { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAb4AAAEuCAYAAADx63eqAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDMuMC4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvOIA7rQAAIABJREFUeJzt3XlYlOXCP/DvMCwDIqKIS6CZoqCmJKaAC+KSJpqmgZrCdFzA8+Kx13ozO0dPb3WOV53j1usvMIdzjjKIivsWuaWYpIjmmmyhopAbosg6AzPz/P4wSQJZdGaeWb6f6+ryYubhma9ZfL2f57nvWyIIggAiIiIrYSN2ACIiImNi8RERkVVh8RERkVVh8RERkVVh8RERkVVh8RERkVVh8RERkVVh8RERkVVh8RERkVVh8RERkVVh8RERkVVh8RERkVVh8RERkVVh8RERkVWxFTsAEZEpulemxrYfC5B1uwQlKg1cZLbw6eCCsP6ecHN2EDsePQcJ9+MjIvrNhfxixKTk4lhOIQBArdHVvCeztYEAINjbHdHDvODbyVWklPQ8WHxERL/akJaHpclZUGm0aOgno0QCyGylWBzig/CALkbLR/rBS51ERHhcepmorNY1eqwgAJXVWixNzgQAlp+Z4cMtRGT1LuQXY2lyVr2ldzvxI+SvmgpBU13nvcpqHZYmZ+FiQbExYpKesPiIyOrFpORCpdHWeV1TfAfqggxAIkFF7ql6v1el0SI2JdfQEUmPWHxEZNXulalxLKew3nt6ZT8dgcML3mjRZyTKL31X7/cLAnA0uxBFZWoDJyV9YfERkVXb9mPBU98r/+kIWvQORovew1F57Sy05Q/qPU4CYNvZp5+HTAuLj4isWtbtklpTFh5T5V+GpuQunHyGwKGDF2xdO6L88rF6z6HS6JB1q9TQUUlPWHxEZNVKVJp6Xy//6Ts4vtQPUqdWAIAWvYah7Kf6L3c+Ok/dh1/INHE6AxFZNRdZ3R+Dumo1yrNSAZ0O+f8v/NGLmmro1OWounMV9u271nMeO0NHJT1h8RGRVfPp4AIH29u1LndW/pwGicQGHed8BYn0t0Ir3PUFyn46gja/Kz47G6BHe2ejZabnw0udRGTVQvt71nmt7NJ3aNFnFGxbtYPUuXXNPy37j0d5RgoEXe2pD9XV1fj7rHFYtGgRLl++bKzo9Iy4ZBkRWb2ohDM4lHmnwWXKnkYiAcb0ao/5/RyhVCqxYcMGdOjQAXK5HG+//TbatWun/8D0XFh8RGT1LuQXY1pcGiqr605ib4yjnRRJUQHo6/lowWqtVosjR45AqVRi7969CAoKglwux/jx4yGTyfQdnZ4Bi4+ICM1bq/MxRzsbLA7p+dS1OktLS7Fjxw4olUqcP38eYWFhkMvlCAwMhEQi0VNyai4WHxHRrzak5eGzvZdRpdEBNk9/BOJZdme4ceMGEhMTER8fD41GA7lcjvDwcHTtWvcJUTIsFh8R0ROGTYqAY/83cU3tBAkeTU5/7PF+fMO93REd7FVzebM5BEHAmTNnoFQqsXnzZvTs2RNyuRxhYWFo1aqV/n4j9FQsPiKiX124cAFjx47FtWvXUFb9aBmyrFulKFFVw0VmB5+OLRHqp78d2KuqqpCcnAylUonvvvsOY8eOhVwux+jRo2Fry9lmhsLiIyL6lVwuR69evfDRRx8Z/bOLioqQlJQEpVKJvLw8TJ8+HXK5HK+88orRs1g6Fh8REYD8/Hz4+vri6tWrcHVt/iVMfcrOzkZCQgISEhLg6uoKuVyO6dOno2PHjqLmshQsPiIiAB988AG0Wi1WrVoldpQaOp0O33//PZRKJXbu3ImAgADI5XJMnDgRTk5OYsczWyw+IrJ6Dx8+RNeuXXH27Fm8+OKLYsepV0VFBXbt2gWlUolTp05h8uTJkMvlGDp0KGwaeAKV6mLxEZHVW7ZsGc6fP4/ExESxozTJzZs3a6ZGlJWVISIiAhEREejRo4fY0cwCi4+IrFpVVRW6du2KvXv3ol+/fmLHaRZBEHD+/HkolUps3LgR3bp1g1wux5QpU9CmTRux45ksFh8RWTWlUgmlUonDhw+LHeW5VFdX4+DBg1Aqldi/fz9ee+01yOVyvP7667C3txc7nklh8RGR1RIEAb6+vvjnP/+J119/Xew4elNcXIytW7dCqVQiOzsb06ZNg1wuR//+/blUGrgtERFZsYMHDwIAxowZI3IS/XJ1dUVkZCSOHz+OkydPws3NDVOnTkXv3r3xxRdfID8/X+yIouKIj4is1qhRoyCXyyGXy8WOYnCCIODEiRNQKpXYunUr/Pz8IJfLMXnyZDg7W9cmuiw+IrJKZ8+exYQJE3D16lWruwemUqmwd+9eKJVKHD9+HBMmTIBcLsfw4cMhlUrFjmdwLD4iskozZszAK6+8goULF4odRVR37tzBpk2boFQqUVhYiPDwcERERKBXr15iRzMYFh8RWZ3r16/Dz88PV69e5Y4IT7h06RISEhKwYcMGeHh4QC6XY9q0aXB3d9fL+e+VqbHtxwJk3S5BiUoDF5ktfDq4IKy//hb+bgoWHxFZnffeew9SqRTLly8XO4pJ0mq1+O6776BUKrFv3z4MGzasZhd5B4fmF9SF/GLEpOTiWE4hAEBdz1ZPwd7uiB7mBd9Ohl8nlcVHRFblwYMH6NatGy5cuIBOnTqJHcfklZaWYvv27VAqlbhw4QKmTJkCuVyOgICAJk2NeLSzfRZUGi0aaptn2dz3WbH4iMiqfPHFF8jIyIBSqRQ7itm5fv06NmzYAKVSCZ1OB7lcjoiICHTp0qXe4x+VXiYqq3X1vl8fRzsbLA7padDyY/ERkdVQq9V46aWX8O2338LX11fsOGZLEASkp6dDqVQiKSkJvXv3hlwuR2hoaM090wv5xZgWl4bKam2t7y2/nIKS07tQXVQAG3tH2LXvilaBUyDr1LvmGEc7KZKiAp5ph/umYPERkdVYt24dNm/ejAMHDogdxWKo1eqaXeSPHDmCcePGQS6XY/tdNxzOulvr8mZJ+k48TNsGtzHzIHvJDxKpLSqv/gh1/mW0HjGr5jiJBBjTqz2+Dn/VIJlZfERkFXQ6Hfr06YMvv/wSr732mthxLNK9e/eQlJSE9Zu24W7gu5DY/jY/UqcqR0HMO3AbtwAtfIY0ei4HWxucWDTCIE97cskyIrIK+/fvh729PUaNGiV2FIvVtm1bzJs3D7OX/qvO05/qm1kQNFVw6hHYpHNJAGw7W2CAlCw+IrISy5YtwwcffMBFmo0g63YJqrS1LyZqK0tg4+QCiU3TVoZRaXTIulVqiHgsPiKyfGfOnMGVK1cwZcoUsaNYhRKVps5rUkcX6CpKIOi09XzH085Trc9YNVh8RGTxli9fjgULFsDOzk7sKFbBRWZb5zWHF3wgsbVDRc7JZpzHMH9eLD4ismjXrl3DoUOHEBkZKXYUq9HWtgpSofbIzkbWAq5DZuD+wa9RkXMSumoVBK0GlVfO4MHR/9Q5h8zWBj4dWxokX91aJiKyIF9++SXmzJmDli0N80OUHlGr1di1axfWrl2Ly1duoMXbq+oc4+I/GTbOrfHwRBLu7V0Oib0jHDp4wSVwap1jBQChfp4GycrpDERkse7fvw8vLy9cunQJHh4eYsexSDk5OYiLi0N8fDx8fX0RFRWFiRMn4k9JF3Eo806Dy5Q9jaHn8fFSJxFZrDVr1mDChAksPT1Tq9XYtGkThg8fjqCgIEilUpw4cQKHDh1CWFgY7O3tMS/YCzLbZ9vbT2YrRXSwl55T/4YjPiKySCqVCi+99BIOHTqEl19+Wew4FiErKwtxcXFQKpXo168foqKiMGHChKdu5Guqa3XyHh8RWaQNGzagX79+LL3npFKpsH37digUCuTk5GDmzJlIS0tDt27dGv3ex+XF3RmIiAxMp9OhV69eiI2NxYgRI8SOY5YyMzMRFxeHhIQE+Pn5Ye7cuXjjjTeeaUrIxYJixKbk4mh2ISR4NDn9scf78Q33dkd0sJfBFqZ+Ekd8RGRxvvnmG7Ro0QLDhw8XO4pZqaysrBnd/fzzz5g1axbS09Px0ksvPdd5+3q64uvwV1FUpsa2swXIulWKElU1XGR28OnYEqF+3IGdiOi5BAUFITo6GtOmTRM7ilnIyMiAQqHAhg0bMGDAAERFRWH8+PEWO+GfIz4isiinTp3CjRs3EBoaKnYUk1ZZWYlt27Zh7dq1uHbtGmbNmoUzZ848dVNZS8LiIyKLsnz5crz33nuwteWPt/r89NNPiIuLQ2JiIgYOHIiFCxdi3LhxVvXvi5c6ichiXLlyBf7+/sjLy4Ozs7PYcUxGRUUFtm7dCoVCgby8PMyePRuzZ8/Giy++KHY0UVhPxRORxVu1ahWioqJYer+6dOkSFAoFNm7ciMDAQCxatAghISFWNbqrj3X/7onIYty7dw+JiYnIyMgQO4qoysvLsWXLFigUCuTn52POnDk4d+4cOnfuLHY0k8HiIyKLEBsbi8mTJ6Njx45iRxHFhQsXEBcXh02bNmHQoEH4y1/+grFjx1r96K4+/DdCRGavsrISMTExSElJETuKUZWXlyMpKQkKhQK//PIL5syZg/Pnz6NTp05iRzNpLD4iMntKpRIDBw5Ez549xY5iFOfPn4dCocDmzZsxdOhQ/PWvf8Xrr78OqfTZFoW2Niw+IjJrOp0OK1asQFxcnNhRDKqsrAxJSUlYu3Ytbt++jTlz5uDixYvw9DTMnnWWjMVHRGZtz549cHV1RVBQkNhRDOLcuXNQKBRISkpCUFAQPvnkE4wZM4aju+fA4iMis7Zs2TIsXLgQEolE7Ch6U1pais2bN0OhUODu3buIjIzkZrp6xOIjIrN14sQJ3Lp1C5MmTRI7il78+OOPUCgU2Lp1K4KDg/G3v/0Nr732Gkd3esbiIyKztXz5crz//vtm/ch+aWkpNm7cCIVCgfv37yMyMhKXL1+22mkZxsAly4jILOXk5GDw4MHIy8tDixYtxI7TLIIg1BrdjRgxAlFRUXjttddgY2MjdjyLZ75/TSIiq7Zq1Sr88Y9/NKvSKykpqRndFRcXIzIyEhkZGRzdGRlHfERkdu7evQtvb29kZWWhffv2YsdpkCAIOH36NBQKBbZv345Ro0YhKioKI0eO5OhOJBzxEZHZiY2NRVhYmEmX3sOHD2tGdyUlJYiMjDSLorYGHPERkVmpqKjASy+9hO+//x7e3t5ix6lFEASkp6dDoVBgx44deO211xAVFYURI0ZwdGdCOOIjIrOyfv16BAYGmlTpFRcXIzExEQqFAuXl5YiKiuLozoRxxEdEZkOr1cLb2xvr16/HkCFDRM0iCALS0tKgUCiwa9cujBkzBlFRUQgODubozsRxxEdEZmPXrl1wd3fH4MGDRcvw4MEDbNiwAQqFAmq1GlFRUfjnP/8Jd3d30TJR87D4iMgsCIKAZcuW4cMPPzT68mSCIODkyZM1o7uxY8di9erVCA4Otqil0qwFi4+IzMIPP/yAoqIiTJw40Wif+eDBAyQkJEChUKC6uhpRUVFYtmwZR3dmjsVHRGZh2bJleP/99w2+bqUgCPjhhx+gUCiwZ88ejBs3DjExMQgKCuLozkLw4RYiMnnZ2dkYOnQo8vLy4OTkZJDPuH//fs3oTqvVIioqCnK5HG3btjXI55F4OOIjIpO3YsUKREdH6730BEFAamoqFAoF9u7di/Hjx2PNmjUYOnQoR3cWjCM+IjJpd+7cgY+PD3JycvR2b62oqAhKpRIKhQISiQRRUVGIiIiAm5ubXs5Ppo0jPiIyaV999RWmTZv23KUnCAK+//57KBQKfPPNN5gwYQLi4uIwePBgju6sDEd8RCS6e2VqbPuxAFm3S1Ci0sBFZgufDi4Y17MN/Hr3wIkTJ9C9e/dnO/e9e4iPj0dcXBykUmnN6K5NmzZ6/l2QuWDxEZFoLuQXIyYlF8dyCgEAao2u5j2ZrQ2qNRq0LL2B+EUz4NvJtcnnFQQBx44dg0KhQHJyMiZOnIioqCgMGjSIozti8RGRODak5WFpchZUGi0a+ikkASCzk2JxiA/CA7o0eM7CwkLEx8dDoVDA3t4ec+fORXh4OFq3bq3X7GTeeI+PiIzuUellorJa1+ixAoDKai2WJmcCQJ3y0+l0SElJgUKhwP79+zFp0iTEx8cjICCAozuqF0d8RGRUF/KLMS0uDZXV2prXCmJnQVdRDEhsILGRwsGzJ9qMmQdbl9oPtDjaSZEUFYC+nq64e/cu1q9fj7i4ODg6OiIqKgrh4eFwdW36JVGyThzxEZFRxaTkQqXR1nndPfRjOHZ5BYKmCkUHYnH/0Fq0e2tJrWNUGi0+2XISdqfW4+DBg5g0aRISEhLg7+/P0R01GYuPiIzmXpkax3IKG76nZ2uPFj6Dcf9wXJ33BAE4e1uNPw0ZDoVCgVatWhkwLVkqbhpFREaz7ceCRo/RVatQnnkcDi/Uv9GszMEBLX1fY+nRM+OIj4iMJut2Sa0pC08q3P53wEYKoVoFqVMrtJvyWb3HqTQ6ZN0qNWRMsnAsPiIymhKV5qnvub+15NE9Pp0WlT+fwp2NH+GFOWsgda47FaFEVW3ImGTheKmTiIzGRdb437UlNlI4eQ8CJDZQFVx+ynns9B2NrAiLj4iMxqeDCxxsG/6xIwgCKnLSoFOVwc6tU533ZbY28OnY0lARyQrwUicRGU1of0+sOpxT73uF2z4DJDaARAJbF3e4jX8P9u4v1jlOABDq52ngpGTJWHxEZDRtnR0wrIc7DmXeqTWlwTP6P036fokEGO7tDjdnBwMlJGvAS51EZFT/NawrbIS6E9ibQmYrRXSwl54TkbVh8RGR0ZSUlOCT+TPR8ueDkDVyr+/3HO1ssDjEB309uSQZPR8WHxEZxc8//4yAgAB06NAB6RtXYsm4nnC0k6KxlcYkkkdrdC4O6dno7gxETcFFqonI4A4cOICIiAh89tln+OMf/1jz+sWCYsSm5OJodiEkeDQ5/TGZrQ0EPLqnFx3sxZEe6Q2Lj4gMRhAErFixAitWrEBSUhKCgoLqPa6oTI1tZwuQdasUJapquMjs4NOxJUL9PPkgC+kdi4+IDKKyshKRkZHIyMjArl270LlzZ7EjEQHgPT4iMoD8/HwMHToUWq0WqampLD0yKSw+ItKr1NRU+Pv7Y8qUKdi4cSOcnJzEjkRUCyewE5HeKBQKLFmyBPHx8Rg7dqzYcYjqxeIjoudWVVWF//7v/0ZKSgpSU1PRo0cPsSMRPRWLj4iey927dxEaGopWrVohLS2NG8SSyeM9PiJ6ZmfPnsWAAQMQFBSE3bt3s/TILHDER0TPZNOmTXj33XcRGxuLsLAwseMQNRmLj4iaRavV4i9/+Qu2bNmCw4cPw9fXV+xIRM3C4iOiJisuLsbbb78NtVqN06dPo23btmJHImo23uMjoibJzMyEv78/unfvjgMHDrD0yGyx+IioUXv37sWwYcPw0UcfYfXq1bCzsxM7EtEz46VOInoqQRDw+eefIyYmBnv27EFAQIDYkYieG4uPiOpVXl6OmTNn4vr160hPT4eHh4fYkYj0gpc6iaiOa9euYdCgQXBycsKxY8dYemRRWHxEVMvRo0cRGBiIWbNmYd26dZDJZGJHItIrXuokIgCP7ud99dVX+Pvf/46NGzdi5MiRYkciMggWHxFBrVYjOjoa6enpOHnyJLp27Sp2JCKD4aVOIit369YtBAcH4+HDhyw9sgosPiIrlp6ejgEDBiAkJARbtmyBs7Oz2JGIDI6XOomsVHx8PD744AP861//wsSJE8WOQ2Q0LD4iK6PRaLBw4ULs27cPKSkp6N27t9iRiIyKxUdkRYqKijB16lRIpVKkp6ejdevWYkciMjre4yOyEpcuXcLAgQPh5+eH5ORklh5ZLY74iKzAjh07MHfuXHz55ZeYMWOG2HGIRMXiI7JgOp0On3zyCdavX4/9+/ejf//+YkciEh2Lj8hClZSUICIiAkVFRTh9+jTat28vdiQik8B7fEQWKDc3F4GBgejQoQOOHDnC0iN6AouPyMIcOHAAgwcPxvz587F27VrY29uLHYnIpPBSJ5GFEAQBK1aswIoVK7B161YEBQWJHYnIJLH4iCxAZWUlIiMjkZGRgVOnTqFz585iRyIyWbzUSWTm8vPzMXToUGi1WqSmprL0iBrB4iMyY6mpqfD398eUKVOwceNGODk5iR2JyOTxUieRmVIoFFiyZAni4+MxduxYseMQmQ0WH5GZqaqqwoIFC3D06FGkpqaiR48eYkciMissPiIzcvfuXYSFhcHFxQVpaWlo1aqV2JGIzA7v8RGZibNnz2LAgAEYOnQodu/ezdIjekYc8RGZgc2bN2P+/PmIjY1FWFiY2HGIzBqLj8iEabVaLF68GElJSTh8+DB8fX3FjkRk9lh8RCaquLgY06dPh0qlwunTp9G2bVuxIxFZBN7jIzJBmZmZ8Pf3h5eXFw4cOMDSI9IjFh+Ridm3bx+CgoKwaNEirF69GnZ2dmJHIrIovNRJZCIEQcDnn3+OmJgY7NmzB4GBgWJHIrJILD4iE1BeXo6ZM2fi+vXrSE9Ph4eHh9iRiCwWL3USiezatWsYNGgQnJyccOzYMZYekYGx+IhEdPToUQQGBmLWrFlYt24dZDKZ2JGILB4vdRKJQBAEfPXVV1i6dCkSExMxcuRIsSMRWQ0WH5GRqdVqREdHIz09HSdOnEDXrl3FjkRkVXipk8iIbt26heDgYDx8+BAnT55k6RGJgMVHZCTp6ekYOHAgQkJCsGXLFjg7O4sdicgq8VInkRHEx8fjgw8+wL/+9S9MnDhR7DhEVo3FR2RAGo0GCxcuxL59+5CSkoLevXuLHYnI6rH4iAykqKgIU6dOhVQqRXp6Olq3bi12JCIC7/ERGcSlS5cwcOBA+Pn5ITk5maVHZEI44iPSsx07dmDu3Ln48ssvMWPGDLHjENHvsPiI9ESn0+HTTz/FunXrsH//fvTv31/sSERUDxYfkR6UlpYiIiIC9+7dw+nTp9G+fXuxIxHRU/AeH9Fzys3NRUBAANq3b48jR46w9IhMHIuP6DkcOHAAgwcPxvz587F27VrY29uLHYmIGsFLnUTPQBAErFy5EsuXL8fWrVsRFBQkdiQiaiIWH1EzVVZWIioqCpcvX8apU6fQuXNnsSMRUTPwUidRM+Tn52Po0KHQaDRITU1l6RGZIRYfUROlpqbC398fU6ZMwcaNG+Hk5CR2JCJ6BrzUSdQEcXFxWLx4MeLj4zF27Fix4xDRc2DxETWgqqoKCxYswNGjR5GamooePXqIHYmInhOLj+gp7t69i7CwMLi4uCAtLQ2tWrUSOxIR6QHv8RHV49y5cxgwYACGDh2K3bt3s/SILAhHfES/s3nzZsyfPx+xsbEICwsTOw4R6RmLj+hXWq0WixcvRlJSEg4fPgxfX1+xIxGRAbD4iAAUFxdj+vTpUKlUOH36NNq2bSt2JCIyEN7jI6uXlZUFf39/eHl54cCBAyw9IgvH4iOrtm/fPgQFBWHRokVYvXo17OzsxI5ERAbGS51klQRBwOeff46YmBjs3r0bgYGBYkciIiNh8ZHVKS8vx8yZM3H9+nWkp6fDw8ND7EhEZES81ElWJS8vD4MHD4aTkxOOHTvG0iOyQhzxkdm6V6bGth8LkHW7BCUqDVxktvDp4IKw/p5wc3aoc3xKSgqmTZuGP//5z3j33XchkUhESE1EYpMIgiCIHYKoOS7kFyMmJRfHcgoBAGqNruY9ma0NBADB3u6IHuYF306uEAQBX331FZYuXYrExESMHDlSpOREZApYfGRWNqTlYWlyFlQaLRr6L1ciAWS2Unw42gup6z5Heno6du/eja5duxovLBGZJBYfmY1HpZeJympd4wc/pq1C53tnkLz6z3B2djZcOCIyG7zHR2bhQn4xliZn1ZReQews6CqKARspILGBfdtOaPHyCDi/8jokkiee2ZLao9BzCK4Wa9CXvUdEYPGRmYhJyYVKo631mnvox3Ds8gp0qnKo8n/C/cMKqG/moO24BbWOU2l0iE3JxdfhrxozMhGZKE5nIJN3r0yNYzmFT72nZyNrAafu/nCf+CHKL32HqsK8Wu8LAnA0uxBFZWrDhyUik8fiI5O37ceCJh3n8II3pC5toc7PqPOeBMC2s007DxFZNhYfmbys2yW1piw0ROrcBjpVaZ3XVRodsm7VfZ2IrA/v8ZHJKi8vR35+Pq7m32ry92hLi2Aja1nveyWqan1FIyIzxuIjUZSXl6OgoAD5+flP/VWtVsPT0xP2wyKBtr0aPaf6Vg60pUVw8Kz/WBcZd14gIhYfGUBFRUWDhVZQUACVSgVPT094enqiU6dO8PT0RL9+/fDGG2/UfN2mTRtIJBJ8fewKVh3OeerlTp26Aqr8n/DgsAItegfDvl2XOsfIbG3g07H+kSARWRdOYKdmqaioaHSkVllZWavUHhfZk78+LrWmuFemxuB/HKlVfLXn8Ulg59YJzr2Hw7nfWEhspHXO4WBrgxOLRtS7hicRWRcWH9WoqKjAL7/8gvz8/KcWW3l5eZ0S+/2vbm5uel8AOirhDA5l3MGz/McqkQBjerXnPD4iAsBLnVajsrISBQUFDY7WysrK6lx+7Nu3L0JCQmq+btu2rdF3NRAEAa6/nIJO0xES2+aP2GS2UkQHexkgGRGZI474LEBlZWXNSO1pxVZWVgYPD48GR2pilFpjKisrERUVhcuXL+MPf/831qTdbtZanY52Nlgc0hPhAV0MF5KIzApHfCZOpVI1OlIrLS2Fh4dHrSLr3bs3xowZU/O1u7u7yZVaYwoKCjBp0iR4eXkhNTUVTk5OaNOmebszLA7xYekRUS2ijPiau4GopVKpVI2O1EpKSpo0UrOxsay1CH744QeEhYVhwYIFWLhwYa3SvlhQjNiUXBzNLoQEjyanPyZoqmBv74CRPdshOtgLfT1dRUhPRKbMqMXX3A1EzZlarW50pPbw4cM6I7Xf/+ru7m5xpdaYuLg4LF68GOvXr0dISMhTjysqU2Pb2QJk3SpFiaoaLjI75P54DN52D7B86SfGC0xEZsVoxdfcDURN+RII+Z4QAAATjklEQVSVWq1udKT28OFDvPDCCw2O1Kyx1BpSXV2NBQsW4MiRI9i9ezd69OjR7HOcPXsWoaGhuHLlitld2iUi4zDKPb7fbyBaMwfriX3TnPuMRJvR/wVBACqrtVianAkARi+/x6XW0EituLgYL7zwQq0i8/b2xsiRI2u+bteuHUutGe7evYuwsDC0bNkSaWlpaNWq1TOdp1+/frC3t8epU6cQEBCg55REZAkMXny/30D0scd7qT1NZbUOS5Oz0NfTVW/3adRqNW7evNngSK24uBgdO3asNTLr0aMHRo4cWfM1S02/zp07h0mTJmHGjBn47LPPIJXWnYDeVBKJBNOnT8fGjRtZfERUL4MXX30biDaVSqNt8gaiVVVVjY7UHjx4gI4dO9YaqXXv3h3Dhw+v+bp9+/YsNSNKSkrCn/70J8TGxiIsLEwv53z77bcxZMgQrFy5Era2fHCZiGoz6E+FxjYQbczjDURvPyiD6uG9Bkdq9+/frzNS8/LywvDhw2uN1J5nNEH6o9VqsWTJEmzevBmHDx+Gr6+v3s7dvXt3vPjiizhy5AhGjx6tt/MSkWUwaPE1tIFo4fa/P1pn8Veth89Ey1der3OcSlWJnuNmwuWX9FojtW7dumHYsGG1RmosNfPw8OFDTJ8+HRUVFUhPT4e7u7veP2PGjBlITExk8RFRHQZ9qnNB0jnsOn+zzusFsbPgFvJug/f4nvTmKy/gy6n99B2PRJCVlYWJEydizJgxWLFiBezsDLNV0K1bt9CrVy/cvHkTjo6OBvkMIjJPBr2ZVaLS6OU8pXo6D4nrm2++QVBQED788EOsXr3aYKUHAB07dsSrr76Kffv2GewziMg8GbT4XGT6uZLKDUTNmyAI+PzzzxEVFYXdu3dj9uzZRvncx093EhE9yaD3+Hw6uMDB9na9G4gWbvus1jw+WZdX0O6tJXWO4wai5q28vByzZ8/G1atXkZ6eDg8PD6N99uTJk7FgwQI8ePAArVu3NtrnEpFpM+g9vvo2EG0ubiBqvvLy8vDmm2/C19cXa9euhUwmM3qG0NBQjB071mijTCIyfQa91NnW2QHDerjjmVeO0unwqocjS88MHTt2DIGBgfjDH/6A9evXi1J6wKPLnYmJiaJ8NhGZJoPP1J4X7AWZ7bNNM7CVAof/byFiYmLAbQPNgyAIiImJwZQpU5CQkIAFCxaIumZmSEgIzp8/j19++UW0DERkWgxefL6dXLE4xAeOds37KEc7G3wyoQ+O705EQkICxowZg4KCp88LJPGp1WpERUVhzZo1OHHiBEaNGiV2JMhkMrz55ptISkoSOwoRmQijrM0VHtAFi0N6wtFO2uhlT4kEcLST1uya3aNHD6SmpmLYsGHw8/PDxo0bOfozQbdv38aIESNQVFSEkydPolu3bmJHqsGnO4noSUbdj6+hDUQf78c33Nv9qRuInj17FhEREejduzfWrFkDNzc3Y0WnBpw+fRqTJ09GZGQklixZYnJrnWq1WnTq1AlHjx6Ft7e32HGISGSi7MBe3waiPh1bItSv8R3YVSoVFi9ejM2bNyMuLq7BjUrJ8BISEvD+++8jLi4Ob775pthxnuq9996Di4sLPv30U7GjEJHIRCk+fUhJScHMmTMxevRorFixAs7OzmJHsioajQaLFi3C7t27sXv3bvTu3VvsSA06ffo0pk+fjpycHG5QS2TlTOuaVDMEBwfjwoUL0Gg08PX1xQ8//CB2JKtx//59hISE4NKlS0hPTzf50gOAV199tLXVmTNnRE5CRGIz2+IDABcXF/z73//GypUrERoaio8++ghqtVrsWBbt8uXLGDhwIPr06YPk5GS0adNG7EhN8uQGtURk3cz2Uufv3b17F3PnzsWVK1eQkJCg1/3d6JFdu3YhMjISK1euREREhNhxmi07OxvBwcEoKCjgFlZEVsysR3xPateuHXbs2IH/+Z//wahRo/DFF19Aq322nd+pNp1Oh08//RTz589HcnKyWZYeAHh7e8PDwwMpKSliRyEiEVnMiO9J169fx8yZM1FVVYX4+HiTmlNmbkpLS/HOO+/gzp072L59Ozp06CB2pOeycuVK/PTTT/jPf/4jdhQiEonFjPie9OKLL+Lw4cMIDQ1FQEAAFAoFJ70/gytXriAwMBBubm44cuSI2ZceAEydOhU7d+6ESqUSOwoRicQiiw8AbGxssGDBAhw7dgwKhQLjxo3DrVu3xI5lNg4fPoxBgwYhOjoaCoUCDg6WsVC4h4cH+vXrh+TkZLGjEJFILLb4HuvVqxdOnjyJgQMH4pVXXsGWLVvEjmTSBEHAqlWrEBERgaSkJERHR1vcvDc+3Ulk3SzyHt/TnD59GhEREfDz80NMTAw3J/0dlUqFuXPn4uLFi9i1axdefPFFsSMZxIMHD9ClSxfcuHEDrVq1EjsOERmZxY/4njRgwACcPXsW7u7u6Nu3Lw4ePCh2JJPxyy+/ICgoCCqVCqmpqRZbegDQunVrjBgxAjt37hQ7ChGJwKqKDwCcnJzwf//3f1i3bh3mzJmDefPmoby8XOxYonp8KXjSpEnYvHkzWrRoIXYkg+MGtUTWy+qK77FRo0bh4sWLKC0tRb9+/ZCWliZ2JFH8+9//xsSJE6FQKPDnP//Z4u7nPc348eNx5swZPvBEZIWkn3zyySdihxCLTCbDpEmT8MILL0Aul6O4uBhDhgyxilU9qqursWDBAiiVShw6dAiBgYFiRzIqOzs7ZGZm4v79+wgICBA7DhEZkdWO+J701ltv4fz587hw4QICAgJw+fJlsSMZVGFhIUaPHo2rV6/i1KlTVrtH3YwZM/h0J5EVYvH9qkOHDtizZw/mzZuH4OBgrFixwiKXPDt//jwGDhyIwMBA7NmzB66udTf8tRYjRozA9evXkZubK3YUIjIiq5rO0FRXr17FH/7wB0gkEsTHx6NLly5iR9KLLVu2YN68efjqq68wdepUseOYhHfffRdt27bFxx9/LHYUIjISjvjq0bVrVxw9ehRvvPEGBgwYgP/85z9mveSZTqfD4sWL8eGHH+LgwYMsvSc8nsxuzn++RNQ8HPE14qeffkJ4eDg6d+6MuLg4tG/fXuxIzfLw4UOEh4ejpKQE27Ztg7u7u9iRTIogCOjWrRu2bdsGPz8/seMQkRFwxNeIl19+Genp6ejTpw98fX3NatJzdnY2/P39axbtZunVxQ1qiawPR3zNcPLkScjlcgwaNAirV6826eWuvv32W7zzzjtYunQpIiMjxY5j0jIzMzFq1CjcuHHDKqayEFk7jviaITAwEOfPn0eLFi3Qt29ffPfdd2JHqkMQBPzjH//AnDlzsHPnTpZeE/Ts2RPt2rXD8ePHxY5CREbAEd8zOnDgAGbPno3Q0FB8/vnncHR0FDsSKioqMHv2bOTm5mLnzp3w9PQUO5LZWLZsGXJychAXFyd2FCIyMI74ntGYMWNw8eJF3LlzB35+fjh9+rSoeW7cuIEhQ4bA1tYW33//PUuvmaZNm4YdO3ZArVaLHYWIDIzF9xzatGmDTZs24X//938xfvx4fPrpp6iurjZ6ju+//x7+/v4IDw+HUqk0idGnuenUqRNefvll7N+/X+woRGRgLD49mDZtGs6dO4e0tDQMGjQIWVlZRvlcQRCwZs0ahIWFQalU4v3337eaRaYNgUuYEVkH3uPTI0EQsHbtWixZsgR//etfMX/+fNjYGObvFlVVVZg/fz5SU1Oxe/dueHl5GeRzrElRURG6du2KgoICtGzZUuw4RGQgLD4DyM3NhVwuh6OjI9atW4fOnTs3ePy9MjW2/ViArNslKFFp4CKzhU8HF4T194Sbs0Od4+/cuYO33noL7u7uUCqV/CGtRxMmTEBYWBgiIiLEjkJEBsLiMxCNRoNly5Zh1apVWLFiBcLDw+tchryQX4yYlFwcyykEAKg1upr3ZLY2EAAEe7sjepgXfDs9Wkz6zJkzmDx5MmbNmoWPP/7YYCNKa7V582asX7+e9/qILBiLz8DOnz+PiIgI9OjRA19//XXN6ikb0vKwNDkLKo0WDf0JSCSAzFaKxSE+QG4q3nvvPaxduxaTJ0820u/AupSXl8PDwwPZ2dlmtzwdETUNi88I1Go1Pv74YyQkJODrr79GSbu+WJqcicpqXePf/CupoIXux23Ys3Ih+vTpY8C0FBERAX9/f/zpT38SOwoRGQCLz4iOHz8O+Xt/hWTUe9BJbGu9VxA7C7qKYkDy26XLF6LWwralW83XMlsbbJkbiL6e1ruHnjF8++23+Nvf/oYTJ06IHYWIDIDFZ2Sz16Xhu+zCWgUHPCo+t5B34djllad+r0QCjOnVHl+Hv2romFaturoaHh4eSEtLQ9euXcWOQ0R6xicjjOhemRqpVx/UKb2mEgTgaHYhisq4uogh2dnZISwsDJs2bRI7ChEZAIvPiLb9WPDc55AA2Hb2+c9DDZs+fToSExO5QS2RBbJt/BDSl6zbJbWmLPxe4fa/AzaPtsWRde6Ddm8tqXOMSqND1q1Sg2WkRwYNGoTKykpcvHgRvr6+YschIj1i8RlRiUrT4Pvuby1p8B7fb+cx/nqg1kYikeDtt9/Gxo0bWXxEFoaXOo3IRaafv2fkZl7C+vXrcerUKZSUlOjlnFTX9OnTsWnTJuh0TZ92QkSmjyM+I/Lp4AIH29sNXu5sjK1EQHt7DQ4f/h6rV69GdnY2WrdujZ49e6JXr161fn08WZ6ezcsvvwxXV1f88MMPGDp0qNhxiEhPWHxGFNrfE6sO5zzXOaRSKdYsfAduzlEAAJ1Ohxs3biAjIwOZmZk4c+YMlEolMjMzIZVKa0rwyUL09PTkLg5N9PghFxYfkeXgPD4ji0o4g0OZdxpcpuxpmjOPTxAE3Llzp6YQH/+amZmJ8vJy+Pj41CrDnj17omvXrpBKpc/wu7Jc169fR//+/XHz5k3Y29uLHYeI9IDFZ2QX8osxLS4NldXaZn+vo50USVEBz71yy4MHD2pK8MlCvH37Nrp3715nlNi9e3c4ONTdJcJaDB06FIsWLcL48ePFjkJEesDiE8GjBaqbt1ano50NFof0RHhAF4PlKi8vR3Z2dq0yzMjIQF5eHjp37lznHqKPjw+cnZ0NlsdUrFmzBsePH+cmtUQWgsUnkmfZncGQpdeQqqoq5Obm1inEnJwcuLu717mH2LNnT7i5uTV+YjNx7949eHl5oaCgwCqKnsjSsfhEdLGgGLEpuTiaXQgJHk1Of+zxfnzDvd0RHexlkgtTa7Va5OXl1XvZVCaT1SnDXr16oWPHjmb5YM24ceMwY8YMTJ8+XewoRPScWHwmoKhMjW1nC5B1qxQlqmq4yOzg07ElQv3q34Hd1AmCgJs3b9YpxIyMDFRVVdUU4ZPF2KVLF5PeVDcxMRHKpJ2Y9D//QNbtEpSoNHCR2cKngwvC+pvnnxORtWLxkVEVFRXVGR1mZGTg3r178Pb2rjNK9PLyEv1pygv5xVj9XRYOX74FBwcHVGl/+1/m8cg82Nsd0cO84NvJ9EbmRFQbi49MQllZGbKysuoUYn5+Prp06VJngr63tzecnJwMnsuc7sUSUdOw+MikqdVq5OTk1Lls+vPPP6NDhw71TtB3ddXPqKu+p2/LM46h5PRuVN+7DomdDLat2sO5z0g49wuBRCIxytO3RPR8WHxkljQaDa5du1bnsmlmZiZatmxZ75Om7du3b/KDNfXNtyw5tQMPT+1Am9F/hONLfpDYO6L6zlU8TN+BtiELILG1A6C/+ZZEZBgsPrIogiCgoKCg3vuIOp2u3kLs3LlznQdrfr/Cjk5VjoIYOdzGvY8WPoMbzNCcFXaIyPi4VidZFIlEgk6dOqFTp04YPXp0rfcKCwtrFeK3336LzMxMFBcXw9vb+7e1TL164mi2Q617euqbWRA01XDqEdBoBkEAjmYXoqhMzac9iUwQi4+shru7O9zd3REUFFTr9YcPHyIrK6tmdLgn+UdUu/cHbH97mlRbUQIbJxdIbH5by/R2wgeoupcPaKvRbspnkHV+ueY9CYBtZwswN6ibwX9fRNQ8LD6yeq1atYK/vz/8/f0BAAuSzmHX+Zu1jpE6toSuogSCTltTfh0ilgMACmLeAYTay8+pNDpk3So1Qnoiai7TnTFMJJISlabOaw4ePpDY2qEiJ60Z56nWZywi0hOO+Ih+x0VW938LG5kzWg1+G/cPrgEg/PpUpwzVd/MgVKmech47AyclomfB4iP6HZ8OLnCwvQ21pvbly1YBoZC2dEPJqe0o2rcKEjsH2Lp2gOvwmXDw7FnrWJmtDXw6tjRmbCJqIk5nIPqde2VqDP7HkTrF1xwOtjY4sWgEn+okMkG8x0f0O22dHTCshzuedRMJieTRrhosPSLTxOIjqse8YC/IbKWNH1gPma0U0cFeek5ERPrC4iOqh28nVywO8YGjXfP+F3m0VqcPlysjMmF8uIXoKR4vNM3dGYgsCx9uIWrExYJixKbk4mh2ISR4NDn9scf78Q33dkd0sBdHekRmgMVH1ERFZWpsO1uArFulKFFVw0VmB5+OLRHqxx3YicwJi4+IiKwKH24hIiKrwuIjIiKrwuIjIiKrwuIjIiKrwuIjIiKrwuIjIiKrwuIjIiKrwuIjIiKrwuIjIiKrwuIjIiKrwuIjIiKrwuIjIiKrwuIjIiKr8v8BzH1QwpZRsoEAAAAASUVORK5CYII=\n", "text/plain": [ "
" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "import networkx as nx\n", "%matplotlib inline\n", "def create_example_graph():\n", " graph = nx.Graph()\n", " graph.add_edges_from([('A', 'B'), ('A', 'C'), ('B', 'C'),\n", " ('B', 'D'), ('D', 'E'), ('D', 'F'),\n", " ('D', 'G'), ('E', 'F'), ('G', 'F')])\n", " return graph\n", "\n", "graph = create_example_graph()\n", "nx.draw(graph, with_labels=True)" ] }, { "cell_type": "code", "execution_count": 16, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "{('A', 'B'): 5.0,\n", " ('A', 'C'): 1.0,\n", " ('B', 'C'): 5.0,\n", " ('B', 'D'): 12.0,\n", " ('D', 'E'): 4.5,\n", " ('D', 'F'): 4.0,\n", " ('D', 'G'): 4.5,\n", " ('E', 'F'): 1.5,\n", " ('F', 'G'): 1.5}" ] }, "execution_count": 16, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# We'll use networkx's built-in betweenness computation in this example.\n", "nx.edge_betweenness_centrality(graph, normalized=False)\n", "# nx.edge_betweenness_centrality(graph, normalized=True)\n", "# normalized between 0-1" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "** How to compute shortest path in undirected graph? **\n", "\n", "


\n", "\n", "\n", "[source](https://en.wikipedia.org/wiki/File:Animated_BFS.gif)\n", "\n", "** Breadth first search: ** Given a sourse node $s$, compute the shortest paths to each of its neighbors. Proceed" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "deque([1])\n", "deque([1, 2])\n", "deque([1, 2, 3])\n", "popleft returns: 1\n", "deque([2, 3])\n", "pop returns: 3\n", "deque([2])\n" ] } ], "source": [ "from collections import deque\n", "# double ended queue\n", "# stored as a doubly linked list\n", "\n", "q = deque()\n", "q.append(1)\n", "print(q)\n", "q.append(2)\n", "print(q)\n", "q.append(3)\n", "print(q)\n", "print('popleft returns: %d' % q.popleft())\n", "print(q)\n", "print('pop returns: %d' % q.pop())\n", "print(q)" ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "1\n" ] }, { "data": { "text/plain": [ "[2, 3]" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# compare with:\n", "a = [1,2,3]\n", "print(a.pop(0))\n", "#print(a.pop())\n", "a" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**What is running time to remove first element of a dynamic array with $n$ elements (a list in Python)?**\n", "\n", "


\n", "\n", "$O(n)$: Need to shift all elements to the left.\n", "\n", "


\n", "\n", "**What is the running time to remove first element of a doubly linked list $n$ elements (a deque in Python)?**\n", "\n", "


\n", "\n", "$O(1)$\n", "\n", "See more:\n", "https://wiki.python.org/moin/TimeComplexity\n" ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[1, 2, 3]\n", "1\n", "2\n" ] } ], "source": [ "# Sample implementation of doubly linked list.\n", "\n", "class Node:\n", " def __init__(self, val):\n", " self.val = val\n", " self.prev = None # previous node\n", " self.next = None # next node\n", " self.head = self\n", " \n", " def display(self):\n", " node = self.head\n", " vals = []\n", " while node:\n", " vals.append(node.val)\n", " node = node.next\n", " print(vals)\n", " \n", " def popleft(self):\n", " \"\"\"\n", " Remove leftmost element of list.\n", " \"\"\"\n", " v = self.head.val\n", " self.next.prev = None\n", " self.head = self.next\n", " return v\n", " \n", "n1 = Node(1)\n", "n2 = Node(2)\n", "n3 = Node(3)\n", "n1.next = n2\n", "n2.prev = n1\n", "n2.next = n3\n", "n3.prev = n2\n", "\n", "mylist = n1\n", "mylist.display() \n", "print(mylist.popleft())\n", "print(mylist.popleft())" ] }, { "cell_type": "code", "execution_count": 17, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "['B', 'C']" ] }, "execution_count": 17, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# to get the neighbors of a node:\n", "list(graph.neighbors('A'))\n", "# vs\n", "#graph.neighbors('A')" ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [ { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAb4AAAEuCAYAAADx63eqAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDMuMC4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvOIA7rQAAIABJREFUeJzt3XtczffjB/DXOZ3qlBRrISqFyP2WRhpiueSemGs42dw2xPbz3fjuyne2ucwtRhcRE7kMqzZEzOXr1hgrFVHNLSlJnXQ65/eHad9WKJ1zPufyej4eHo+vzulzXvnaeXm/z+f9fotUKpUKRERERkIsdAAiIiJtYvEREZFRYfEREZFRYfEREZFRYfEREZFRYfEREZFRYfEREZFRYfEREZFRYfEREZFRYfEREZFRYfEREZFRYfEREZFRYfEREZFRYfEREZFRYfEREZFRYfEREZFRkQgdwNDdLyhG9PksJN/JR75cAWupBG4NrDGyswNsrcyFjkdEZHREPIFdMy5m5mHt0TQkpGQDAIoVyrLHpBIxVAB6tbDDjJ7N0N6xjkApiYiMD4tPAyJP38DimGTIFaV40Z+uSARIJSZY4OuG8V2dtZaPiMiYcapTzZ6WXhKKSpQvfa5KBRSVlGJxTBIAsPyIiLSAIz41upiZh9EbT6OopLTc17OCZVAW5gGiv+8lsmrbB6/1nV72ewtTE0S92xXtHDjtSUSkSRzxqdHao2mQK0orfczO/xNYOHd47vfKFaUIPpqG9ePdNRWPiIjA5Qxqc7+gGAkp2S/8TO9FVCrgyNVs5BQUqzcYERGVw+JTk+jzWTW+hghA9IWaX4eIiJ6PU51qknwnv9yShX/K3rUIEJuU/b6u92TU7tC/3HPkCiWSbz/SWEYiImLxqU2+XPHCx+1GLHzhZ3x/X6dEXZGIiKgSnOpUE2upev4NYS01Vct1iIiociw+NXFrYA1zSc3+OKUSMdzsa6spERERVYZTnWri39kBKw6lPPfx7Ogvyq3jkzp3QL0RC8s9RwXAv5ODpiISERFYfGrzupU5eja3w8GkuxWWNDjMCHvp94tEgHcLO25cTUSkYZzqVKOZvZpBKjF5+RMrIZWYYEavZmpORERE/8TiU6P2jnWwwNcN0mp+1mdhKsYCXzduV0ZEpAUsPjV7u3MjWF6NhQlKIRK9+LkiPN2jc4FvS25QTUSkJSw+Nfvoo49QLz8F0dO90K9VfZhLxBVGgFKJGCZQom5hBqLe7crSIyLSIp7OoEY7d+7E//3f/+HcuXOwtbUFAOQUFCP6QhaSbz9CvrwE1lJTuNnXRl9XG3Ru3Ry//fYbnJycBE5ORGQ8WHxqkpSUhB49euDnn39Gp06dqvQ9c+fOhVgsxtKlSzWcjoiInmHxqUF+fj48PDwwf/58TJ48ucrfd/PmTXTq1AnXr1+HjY2NBhMSEdEz/IyvhlQqFWQyGXr27Fmt0gOAxo0bo2/fvggJCdFQOiIi+ieO+Gpo6dKl2LFjB44fPw5z8+ovPj937hz8/Pxw7do1mJpyn04iIk3jiK8Gjhw5gqVLlyI6OvqVSg8A3N3d4eLigujoaDWnIyKiyrD4XlFWVhbGjh2LyMjIGt+V+cEHH2Dp0qXg4JuISPNYfK+guLgY/v7+mD17Nt56660aX2/gwIF4/PgxEhIS1JCOiIhehJ/xvYKZM2fi1q1b2L17N0Qv256lijZs2IB9+/bhwIEDarkeERFVjsVXTZs3b8aiRYtw9uxZtS5BKCoqgrOzM44ePYqWLVuq7bpERFQei68afvvtN/j4+ODIkSNo06aN2q//2Wef4datW9iwYYPar01ERE+x+KooNzcX7u7uWLRoEcaMGaOR17h37x5atGiB5ORk1K9fXyOvQURk7HhzSxUolUpMmDABgwcP1ljpAUC9evUwatQoBAcHa+w1iIiMHUd8VfDFF1/g4MGDiI+P1/gi8+TkZPTo0QM3btyApaWlRl+LiMgYccT3ErGxsfj++++xY8cOreys4ubmhq5du2Lz5s0afy0iImPEEd8LpKeno2vXrti1axe8vLy09roJCQl45513kJycDLGY/zYhIlInvqs+R1FREUaMGIGPP/5Yq6UHAD169IC1tTX279+v1dclIjIGHPFV4tmJC3K5HNu2bVPbIvXq2L59O4KDg3Hs2DGtvzYRkSHjiK8SGzduxNmzZ7Fx40ZBSg8A/P39cfPmTZw5c0aQ1yciMlQc8f3DmTNnMGjQIPz6669o3ry5oFlWrFiB06dPIyoqStAcRESGhMX3P7Kzs+Hu7o5Vq1Zh6NChQsdBfn4+XFxccP78eTg7Owsdh4jIIHCq8y8KhQJjxozBuHHjdKL0AMDa2hoymQwrV64UOgoRkcHgiO8vH330Ec6dO4e4uDiYmJgIHadMZmYm2rdvj+vXr6NOnTpCxyEi0nsc8QHYs2cPtm3bhm3btulU6QGAo6MjfH19uXE1EZGaGP2ILyUlBV5eXjhw4AA8PDyEjlOpxMREDB48GNevX4eZmZnQcYiI9JpRj/gKCgrg5+eHRYsW6WzpAUDHjh3RokUL3t1JRKQGRjviU6lUGDNmDCwtLREaGirYer2qiomJwccff4zExESdz0pEpMuMdsS3atUqpKamYu3atXpRJP3790dJSQkOHz4sdBQiIr1mlCO+48ePY+TIkTh9+rRerY8LDQ1FdHQ0YmNjhY5CRKS3jK74bt++DXd3d4SGhqJ///5Cx6kWuVwOZ2dnHDp0CG3atBE6DhGRXjKqqc6SkhKMHDkS06ZN07vSAwCpVIr33nsPy5cvFzoKEZHeMqoR35w5c5CWloZ9+/bp7Tl3OTk5aNasGf744w/Y29sLHYeISO/o57v/K/jhhx9w4MABbNmyRW9LDwBsbW0xZswYrFmzRugoRER6yShGfJcvX4a3tzcOHTqE9u3bCx2nxlJTU+Hp6YkbN26gVq1aQschItIr+jv0qaKHDx/Cz88PK1asMIjSAwBXV1d4eXlh06ZNQkchItI7Bj3iUyqV8PPzg4ODg8FNDf7666+YOHEiUlJSdG5/USIiXWbQI76vv/4ad+/eNci7ILt37w47Ozv8+OOPQkchItIrBlt8Bw8exOrVq7Fz506D3NhZJBJh3rx5WLZsmdBRiIj0ikEWX0ZGBiZMmIBt27bBwcFB6DgaM3z4cNy+fRunTp0SOgoRkd4wuOKTy+UYMWIEPvjgA/Tq1UvoOBolkUgwZ84cjvqIiKrB4G5umTp1Kh48eIAdO3boxebTNVVQUABnZ2f897//RdOmTYWOQ0Sk8wxqxBcWFoZjx44hLCzMKEoPAKysrPDOO+/gu+++EzoKEZFeMJgR34ULF9C/f38kJCSgZcuWQsfRqlu3bqF169a4du0aXnvtNaHjEBHpNIMY8eXk5GDEiBEIDg42utIDgIYNG2LIkCFYv3690FGIiHSe3o/4SktLMXDgQLRt2xbffvut0HEEc+nSJfTv3x/p6ekwNzcXOg4Rkc7S+xHf559/juLiYnz11VdCRxFUu3bt0KZNG/zwww9CRyEi0ml6PeI7cOAApk+fjnPnzqF+/fpCxxHcL7/8gnnz5uHSpUtGc3MPEVF16e2ILy0tDTKZDDt27GDp/cXHxwcikQi//PKL0FGIiHSWXhZfYWEhRowYgc8++wzdunUTOo7OEIlEmDt3Lhe0ExG9gN5NdapUKgQEBEAkEiEiIoJTev9QXFwMFxcXxMbGGswxTERE6qR3I75169bh0qVLWL9+PUuvEubm5nj//fcN8kQKIiJ10KsR36lTpzBs2DCcPHmS23O9wIMHD9C0aVNcvnwZjRo1EjoOEZFO0Zniu19QjOjzWUi+k498uQLWUgncGlhjZGcH2FqZ4+7du3B3d8e6deswaNAgoePqvFmzZsHS0hJLliwROgoRkU4RvPguZuZh7dE0JKRkAwCKFcqyx6QSMVQAeri+jstRy9DXvQU+//xzgZLql+vXr8PDwwPp6emoXbu20HGIiHSGoMUXefoGFsckQ64oxQtTqFQQKRX4fFh7BHi6aC2fvvP398ebb76J2bNnCx2FiEhnCFZ8T0svCUUlypc/+S8WpmIs8G2J8V2dNRfMgJw+fRpjxoxBamoqJBKJ0HGIiHSCIMV3MTMPozeeRlFJabmvZwXLoCzMA0R/32za8N3vIaltW/Z7C1MTRL3bFe0c6mgtrz7r3r075syZg5EjRwodhYhIJwgyDFh7NA1yRWmlj9n5fwIL5w7P/V65ohTBR9Owfry7puIZlA8++ABLliyBv78/l38QEUGAdXz3C4qRkJL94s/0XkClAo5czUZOQbF6gxmoIUOGICcnBydOnBA6ChGRTtB68UWfz6rxNUQAoi/U/DrGwMTEBEFBQVi6dKnQUYiIdILWpzqT7+SXW7LwT9m7FgFiEwCA1Kkt6o1YWOE5coUSybcfaSyjoZk0aRI+++wzpKamwtXVVeg4RESC0nrx5csVL3zcbsTCF37G9/d1StQVyeDVqlULU6dOxYoVKxAcHCx0HCIiQWl9qtNaqp6utZaaquU6xuK9997DDz/8gPv37wsdhYhIUFovPrcG1jCX1OxlpRIx3Oy5G0l1NGjQAH5+fli3bp3QUYiIBKX14vPv7FDjaxTJ5fjjp3AkJyerIZHxmDt3LtauXQu5XC50FCIiwWi9+F63MkfP5naobEmZw4ywl36+JxIBXk3qQooSeHt7w9PTEyEhIcjPz9dQYsPRunVrdOrUCZGRkUJHISISjCDn8c3s1QxSickrfa9UYoL5gzvg66+/RmZmJj7++GPExMTAyckJkyZNwrFjx6AjB07opHnz5mH58uVQKqu+VRwRkSERpPjaO9bBAl83WJhW7+Wf7tXpVrZdmUQiwaBBg7B7926kpKSgXbt2mDFjBlxdXbF48WJkZXGt3z/17t0bZmZmiI2NFToKEZEg9OJ0BpHo6Uhvga/bSzeoVqlUOHfuHMLCwhAVFQUPDw/IZDIMHToU5ubm6v0B9FRkZCTCwsIQHx8vdBQiIq0T/Dy+S1l5CD6ahiNXs6FUKvG/hzU8O4/Pu4UdZvRqVu2NqQsLC7Fnzx6Eh4fjt99+w9ixYzF58mR07NhRvT+EnikpKYGLiwv27duHTp06CR2HiEirBC++Z3IKivH5lp9x7OI1dO7mBWupKdzsa8O/09MT2GsqPT0dERERCA8Px2uvvQaZTIaxY8fC1tb25d9sgL755htcvHgRW7duFToKEZFW6UzxAUBERATi4+MRERGhsddQKpU4cuQIwsLC8NNPP6Fv376QyWTw8fGBicmr3XCjj/Ly8tCkSRNcvHgRjo6OQschItIaQW5ueZ68vDzUqaPZc/bEYjH69OmDrVu3Ij09Hd7e3vjkk0/QuHFjLFy4EGlpaRp9fV1Rp04dTJw4EatWrRI6ChGRVulU8eXm5mq8+P5X3bp1MX36dJw5cwaxsbEoLCyEp6cnevbsiYiICDx+/FhrWYQwe/ZshIWFcQ0kERkVnSo+bYz4nqdt27ZYvnw5srKyMGfOHERHR8PBwQFTpkzByZMnDXJtoLOzM3x8fBASEiJ0FCIirdG54qtbt66gGczMzDB8+HDs378fV65cgaurK2QyGVq2bImvv/4at2/fFjSfus2bNw/fffcdSkp42gURGQedKj5tT3W+TMOGDTF//nwkJSUhLCwMqampaNWqFQYPHow9e/bgyZMnQkessS5dusDFxQXR0dFCRyEi0gqdKj4hpzpfRCQSle0JmpmZCX9/f3z33XdwdHTE3LlzcfnyZaEj1si8efOwdOlSg5zOJSL6J50rPqGnOl/GysoKEydOREJCAn799VdYWFigf//+8PDwwLp165CXlyd0xGobNGgQCgoKkJCQIHQUIiKN06ni07Wpzpd5tifozZs38cUXX+DIkSNwdnbGuHHjcPjwYb3ZCFosFmPu3LlYtmyZ0FGIiDROpxawW1tbIzMzEzY2NkJHeWX379/Htm3bEBYWhry8PEyaNAmTJk2Cs7Oz0NFeqKioCM7OzkhISICbm5vQcYiINEZnik+hUEAqleLJkycQi3VqIPrKEhMTERYWhh9++AEdOnTA5MmT4efnBwsLC6GjVerTTz/F7du3sWHDBqGjEBFpjM4UX05ODlxdXfHgwQOho6idXC7Hvn37EBYWhjNnzuDtt9+GTCaDu7s7RJWdyCuQe/fuoUWLFrh69Srq1asndBwiIo3QmaGVrt7RqQ5SqRSjRo1CXFwcLl68CAcHB4wePbps0fy9e/eEjggAqFevHkaOHIm1a9cKHYWISGN0qvh0/Y5OdXB0dMSCBQuQmpqKtWvX4uLFi2jevDn8/Pywf/9+KBQKQfPNnTsX69atQ1FRkaA5iIg0RWeKT9/u6KwpsVhctidoRkYGfH198dVXX8HR0RHz589HcnKyILnc3NzwxhtvYPPmzYK8PhGRpulM8RnyVOfLWFtbl+0JGh8fD5VKBW9v77JF89reRHrevHlYvny53izHICKqDp0qPmOY6nyZli1b4ptvvkFGRgY++ugj/PTTT3BycipbNK+Ne5F69uyJ2rVr48CBAxp/LSIibdOZ4jO2qc6XMTU1LdsTNCUlBe3bt8eMGTPKFs1nZWVp7LVFIhHmzZvHBe1EZJB0pviMearzZerVq1e2J+i2bduQmZmJdu3aoX///tixYweKi4vV/pr+/v5IT0/H2bNn1X5tIiIh6Uzx5ebmcqrzJUQiETw8PLB+/XpkZWVhwoQJ+P7779GoUSO8//77SExMVNtrmZqaYs6cORz1EZHB0Zni44iveiwtLcv2BD179ixsbW0xbNgwdOzYEatXr0ZOTk6NX2PKlCk4ePAgbty4UfPAREQ6Qmd2bvH19cXMmTMxcOBAoaPoLaVSifj4eISFhSEmJgZ9+/aFTCaDj48PTExMXumaH374IRQKBRZ8uQTR57OQfCcf+XIFrKUSuDWwxsjODrC1MlfzT0JEpDk6U3zdunXDsmXL4OnpKXQUg5Cbm4vt27cjLCwMt2/fxsSJEzF58mQ0a9asWtf55dxVTF66HbWadYFIJEKx4u8lDlKJGCoAvVrYYUbPZmjvyBE7Eek+TnUaqLp162L69Ok4e/YsYmNjUVRUBE9Pz7JF848fP37pNSJP38Dsfekwde6EJ6WqcqUHAHKFEsUKJX754y5GbzyNyNM3NPTTEBGpj86M+Ozt7XH+/Hk0bNhQ6CgG68mTJzhw4ADCwsJw4sQJjBgxAjKZDN26dauwWXbk6RtYHJOEopKqL2K3MBVjgW9LjO/qrObkRETqozPFJ5VKkZubq7NH9hiaW7duYcuWLQgLC4NIJMLkyZMREBAAe3t7XMzMw+iNp1FUUgoAyAqWQVmYB4hNAJEYZq87olab3rDq0B8iUflJAwtTE0S92xXtHDh6JyLdpBPFJ5fLYWNjA7lcrlPH9BgDlUqFkydPIjw8HLt27YKXlxdUXu/gykMTPPubkRUsg63vLFg4d4BS/hjyzMt4cGgDpE5t8frAOeWuJxIB/VrVx/rx7gL8NEREL6cTn/E9+3yPpad9IpEI3bt3R0hICDIzM9FvqD8uP1Dhef8cEktrwdL1DdgN/T88/v0wnmTfKPe4SgUcuZqNnAL1L6onIlIHnSg+Ll7XDVZWVpC4esHczOylzzVv2AIm1q+jOPOPCo+JAERf0NyWakRENaETxcc7OnVH8p38CndvPo+J1WtQyh9V+LpcoUTy7YpfJyLSBSw+KidfXvWDcEsf5UAsrf2c65SoKxIRkVrpRPFxqlN3WEslVXpe8e0UlD7KgblDq+dcx1SdsYiI1KZq73IaxhGf7nBrUBumIqDkOTe3KIsLIc+8jNxDG1CrdS+Y1XOu8BwzExHc7CsfCRIRCY3FRwCAoqIiREZGYlXwRpT4fAyYlB+xZUd/8dc6PhFMbR1h3WUYrDoOqPRaxcXFCP9kGkwDxmDUqFGwsrLSxo9ARFQlOlF8ubm5sLOzEzqGUbpz5w7Wrl2LDRs2oEuXLli99CtE3bLBwaS7ZUsaHGaEVfl6IhHQt50DBveYhZCQEMybNw8jRozAlClT8MYbb3DJChEJTic+4+OIT/t+++03TJw4ES1btkROTg6OHTuGAwcOoE+fPpjZqxmkklc7zUEqMcF73q4YPHgwfvzxR/zxxx9wdXVFQEAA2rRpg+XLlyM7O1vNPw0RUdWx+IyIUqnE/v374e3tjUGDBqFly5a4du0agoOD0aJFi7LntXesgwW+brAwrd5fj6d7dbqV267M3t4e8+fPx9WrV7F+/XpcunQJrq6u8Pf3R1xcHEpLS9X28xERVYVObFn21ltvYf78+fDx8RE6ikEqKChAREQEVq5cCRsbGwQFBWHkyJEwNX3xnZdPN6pOhlxR+tydXICn05tSiQkW+LpVaYPqhw8fYvv27QgNDcWdO3cwadIkTJ48GS4uLtX8yYiIqo8jPgOWmZmJ+fPnw9nZueyA2jNnzmDs2LEvLT0AGN/VGVHvdkW/VvVhLhFDKin/10UqEcNcIka/VvUR9W7XKp/KYGNjg6lTp+LMmTM4cOAAHj58CA8PD7z11lvYvn075HL5q/y4RERVohMjvmbNmiE2Nhaurq5CRzEIZ86cwYoVK/Dzzz8jICAAs2bNQpMmTWp0zZyCYkRfyELy7UfIl5fAWmoKN/va8O+knhPY5XI5fvzxR4SGhuLChQsYO3YsAgMD0b59+xpfm4jof+lE8dna2uLq1at4/fXXhY6itxQKBfbu3YsVK1bgzz//xKxZsxAYGAgbGxuho1XbjRs3EB4ejvDwcNSvXx+BgYEYM2aMXv4sRKR7BC8+lUoFU1NTFBUVVWn6jcp7+PAhQkNDsWrVKjRq1AhBQUEYNmwYJBKdWKlSI6WlpTh06BBCQ0Nx8OBBDB48GIGBgejRoweXRRDRKxO8+B49egR7e3sUFBQIGUPvXL9+HatWrcLmzZvRr18/BAUFwcPDQ+hYGpOdnY3IyEiEhobiyZMnkMlkmDhxIuzt7YWORkR6RvCbW7hPZ9WpVCocP34cfn5+8PDwgLm5OS5evIgffvjBoEsPAOzs7BAUFITff/8dW7ZswfXr19GqVSsMGTIE+/btg0JR9c21ici4CT7iu3TpEsaNG4fff/9dyBg6raSkBDt27MB3332HvLw8zJkzBxMnTjT6rcAKCgqwc+dOhIaG4vr16wgICIBMJkPz5s2FjkZEOkzwER+XMjzfgwcPsGTJEri4uCA0NBSffPIJrl69ipkzZxp96QFPD86dPHkyfv31V8THx6O0tBQ9evRAjx49EBERgcePHwsdkYh0kODFx6nOiq5evYoZM2agadOmSEpKwoEDBxAfH4/BgwdDLBb8/zKd5Obmhm+//RaZmZkICgrCzp074ejoiGnTpuHs2bPQgZuXiUhHCP4uyhHfUyqVCocPH8agQYPw5ptvwtbWFn/88QciIiLQoUMHoePpDVNTUwwfPhwHDhzA77//DkdHR4wePRrt27fHypUrkZOTI3REIhIYi09gxcXFCA8PR4cOHTBr1iwMHToUN2/exJdffsk7FmuoUaNGWLBgAVJTU7Fy5UqcPXsWTZs2xejRo3Hw4EEolUqhIxKRAARf7GWsU5337t3DunXrsG7dOnTo0AHffPMN+vbty/VpGiAWi+Ht7Q1vb2/k5uZi27ZtmD9/Ph48eACZTIZJkybByclJ6JhEpCUc8WnZ5cuXERgYiBYtWuDPP/9EfHw84uLi0K9fP5aeFtStWxczZ87EhQsXsGfPHty7dw8dO3ZE//79sXPnThQXFwsdkYg0jMWnBUqlErGxsfDx8UHfvn3h4uKClJQUbNiwAa1atRI6ntHq2LEj1qxZg6ysLEyYMAHr1q2Do6Mj5s6diytXrggdj4g0RPDiM+SpzsLCQnz//fdo3bo1Pv74Y0yYMAHp6elYuHAhT5zXIRYWFhg3bhzi4+Nx6tQpWFhYoG/fvujatSs2btyIR48eCR2RiNRI8OIzxBHfrVu3sGDBAjg7OyMmJgbr1q3DhQsXEBAQAHPzmp9kQJrTtGlTLF68GDdv3sS///1vxMbGwsnJCTKZDCdOnOCyCCIDwOJTowsXLmDChAlo3bo1Hj58iBMnTuDHH39Er169+PmdnpFIJBg4cCB2796N5ORktGzZEoGBgWjVqhW+/fZb3L17V+iIRPSKBC8+fZ/qLC0txd69e9GzZ08MHToUbdu2xfXr17FmzRqeL2gg6tevjw8//BBJSUkICQlBUlIS3Nzc4Ofnh59++on7hBLpGcH36rS2tkZmZqbenbX26NEjhIeHY9WqVbC1tUVQUBBGjBjBo5WMRH5+PqKiohAaGoqsrCxMnDgRMpkMTZs2FToaEb2EoMWnUCgglUrx5MkTvdmK6+bNm1i9ejXCw8PRu3dvBAUFoVu3bpzKNGJXrlxBaGgoIiMj0aZNGwQGBsLPzw8WFhZCRyOiSgjaNg8fPoS1tbVelN6pU6cwatQodOrUCSqVCufPn8fOnTvh6enJ0jNyrVu3xvLly5GZmYnp06djy5YtcHBwwHvvvYfExESh4xHRPwjaOLp+Y4tCocCOHTvQrVs3jBs3Dt27d0d6ejqWLVsGZ2dnoeORjjE3N8fIkSMRFxeHxMRE1KtXD8OHD0enTp2wdu1a5ObmCh2RiCDwVOf58+fxzjvv4MKFC0JFqFReXh5CQkKwevVqNG7cGEFBQRgyZAhMTEyEjkZ6RqlU4vDhwwgNDUVcXBwGDhyIKVOmoGfPnnox00FkiAT9L0/X7ui8du0aZs2ahSZNmiAxMRG7du3CsWPHMHz4cJYevRKxWAwfHx9s374d165dwxtvvIHZs2fD1dUVixcvxp9//il0RCKjY/RTnSqVCgkJCRg2bBi6du2KWrVq4ffff8fWrVvh7u4uaDYyLLa2tpg1axYuXryI7du3IzMzE23btsWgQYOwZ88elJSUCB2RyCgIPuITqviePHmCLVu2oHPnznj33XfRr18/3LhxA1999RUaNWokSCYyDiKRCF26dMH69euRlZWFUaNGYcWKFXB0dMSHH36I5ORkoSMSGTTBR3zanuq8f/8+Fi9eDBcomglAAAAXbklEQVQXF0RERODLL79EUlISpk+fjlq1amk1C5GlpSUCAgJw7NgxHDt2DCYmJvD29oaXlxfCw8NRUFAgdEQigyN48WlrxJeUlISpU6fC1dUV165dQ2xsLA4dOoSBAwfyJgPSCc2bN8eSJUuQkZGBDz/8EHv27IGjoyPeeecdnD59mvuEEqmJQU91qlQqHDx4EL6+vvD29oa9vT2Sk5MRFhaGdu3aaex1iWrC1NQUQ4cOxb59+3DlyhU0bdoUEyZMQNu2bbFixQrcv39f6IhEek3wEZ8mpjrlcjlCQ0PRrl07zJ07F/7+/rhx4wY+++wz1K9fX+2vR6QpDRs2xL/+9S+kpKRg7dq1SExMRLNmzTBy5Ej8/PPPKC0tFToikd4RvPjUOeK7e/cuPv30UzRu3Bi7d+/GihUrcOnSJchkMkilUrW9DpG2iUQi9OzZE5s3b8bNmzfRp08fLFiwAC4uLvj0009x48YNoSMS6Q2tF9/9gmKsT7iGOVGJuNbIB9vSTbE+4RpyCopf+ZqXLl3C5MmT4ebmhrt37yIhIQE//fQT3nrrLW4nRgbHxsYG06ZNw7lz57B//37k5ubC3d0dPj4+iIqKQnHxq/+3RGQMtLZzy8XMPKw9moaElGwAQLFCWfaYVCKGCkCvFnaY0bMZ2ju+fBSoVCoRExODFStWIDk5GTNnzsTUqVNha2urqR+BSGfJ5XLs2bMHoaGhuHjxIsaOHYvAwEB+lk1UCa0UX+TpG1gckwy5ohQvejWRCJBKTLDA1w3juzpX+pzHjx8jIiICK1euhJWVFYKCgjBq1CiYmZlpJjyRnklPT0d4eDjCw8PRoEEDTJkyBaNHj9a7o7+INEXjxfe09JJQVKJ8+ZP/YmEqxgLfluXKLysrC2vWrEFoaCi8vLwQFBSEN998k1OZRM9RWlqKX375BaGhoTh06BCGDh2KwMBA/ndDRk+jxXcxMw+jN55GUUn5O88e/5GA/LM/ouT+TYhMpZDY1IdV2z6w6uhb9h+khakJot7tiuLbqVixYgXi4uIwYcIEzJo1i4d9ElVTdnY2tmzZgpCQEJSWlkImk2HixIlo0KCB0NGItE6jxffulnM4mHS33PRm/n934+F/d+O1vtNg4dIJIjMLlNy9jodnduN13zkQSZ6eYC6CCtL7KSj8ZSVmzZqFwMBAwff1JNJ3KpUKp0+fRmhoKHbt2oUePXogMDAQvr6+kEgkQscj0gqNFd/9gmJ0/zq+3E0sSvljZK0NgO3Auajl1v2l15CIVDgxvzfq21hqIiKRUSsoKMCOHTsQGhqK9PR0TJw4ETKZDK6urkJHI9IojS1niD6fVeFrxbeSoVKUwLJ51ypdQ2Jigr0Xb6s7GhEBsLKygkwmw4kTJ3D48GGUlJTAy8urbL1gYWGh0BGJNEJjxZd8J7/caA8ASgvzIba0hkj899l2d7Z8gIwVbyNjqR/kGZfLPV+uUCL59iNNRSSiv7Rs2RJLly5FZmYmZs+eje3bt8PBwQHTp0/HuXPnuE8oGRSNFV++XFHhayYWtaEszIdK+ffNLg0mLIVTUBTEFrUBVcU7P/PlPKOMSFvMzMzg5+eHmJgYXLp0CY0aNcKoUaPQoUMHrF69Gg8ePBA6IlGNaaz4rKUVPyg3b+QGkcQUhSmnq3EdU3XGIqIqcnBwwMKFC5GWlobly5fj1KlTaNKkCcaMGYNDhw5Bqaz6EiUiXaKx4nNrYA1zSfnLi6VWsOk+Bg9+WYfHyb9CWVwIlUqJJ3evQ/VEXuEaUokYbva1NRWRiKpALBajT58+2LZtG65fv47u3bvjgw8+QNOmTfHll18iMzNT6IhE1aLVuzqfKbhyBI/O7UNJdgZEpuaQ1GkAq/Z9YdW2D0Qmf4/wzCVinJzfG7ZW5pqISESvSKVS4cKFCwgNDUVUVBQ8PDwQGBiIIUOG1HgXpfsFxYg+n4XkO/nIlytgLZXArYE1RnZ24HsBqYXW1/FVlUgE9GtVH+vHu6s/GBGpTWFhIXbv3o3Q0FBcuXIF48ePR2BgIFq3bl2t66h7P1+i5xFk55aqeLZzSzsH/gUn0hdpaWkICwvDpk2b0LhxYwQGBuLtt99G7dov/shCnfv5Er2M3uzVSUT6Q6FQIC4uDiEhIUhISICfnx8CAwPRrVu3CvuE8j3CeOjKNLbenc5ARPrlzp072Lx5M0JDQyEWixEYGIiAgADUq1ev0lmhrGAZlIV5gEgMkdgE5g4t8Vq/mZBY25W7LmeF9IeuTWNr7Ty+S1l5CD6ahiNXsyHC08Xpzzz7wb1b2GFGr2b8i0xkgFQqFU6cOIGQkBDs3bsXffr0gaKbDJceoNw/iLOCZbD1nQUL5w5QKZ4g5+dgKOUFqDdiYbnr8T4A/aCLAx+t7UrbzqEO1o93R05BMaIvZCH59iPky0tgLTWFm31t+HfiHVtEhkwkEsHLywteXl7Iz89H6NYdWJleApg8f62uSGKGWm7d8eDQxgqPqVTAkavZyCko5nuHjqrONLZKBRSVlGJxTBIAaLT8tL4du62VOab24LFCRMbM2toaFq28YX4rpdIlT88oS+R4nHQc5g1bVPq4CED0hSy+p+igi5l5WByTXGnp3dn6L5TcS4fD+5FlJ/I8U1SixOKYZLRzqKOx2T+eQ0JEgqhsP99nsnctAsQmUJXIYWJpg3qjvqj0eXKFEkm38zUZk17R2qNpkCsq3tGvyLuL4qw/IDa3RGHaf1HLzavCc+SKUgQfTdPYNDaLj4gEUdl+vs/YjVj49DM+ZSmKUv+Lu9v+hYZT1sHEqm6F527buQdrxnWBmZlZ2S9zc/Nyv//nrxc9ronHnv365x2thup+QTESUrIr/Uyv4HI8zBu2gFnD5nj8++FKi0/T09gsPiISRGX7+f6TSGwCyxaeyIlbA3nWlUrfJMeNHI5vt3+CJ0+e4MmTJyguLi7735X9etHj//tYYWEh8vLyqvy9VXnc1NRU7YWq7qKWSCQ1LujKjqV75vHleFh7DINZwxa4s3keSh/nwqRWxX/QaHIam8VHRIJ4up/vnRd+xqdSqVCU+l8o5QUwtXWs8PjT/XytIZFIIJFIYGmpu4dWq1QqlJSUqKWU//fXo0eP1FLKzx4vLS196cj1ZYX6h00XFJs5VPgzkGdegSL/HizdvGBiaQNJHXs8vpIAa49hFZ+rwWPpWHxEJAj/zg5YcSil0seyo78ARGJAJILE2g62g4JgZte4wvNUAPw7VXyD1UUikaisHHSZUqmsUNDVLdX0LGug4rkDeHz5MCxcOsLE0gYAUKtVTxRcPlxp8QGaO5aOxUdEgnjdyhw9m9tV2M/XYUZYlb5fJHq69pdLGdRLLBbD3Nwc5uav/uf6e1Qirv12q9zXlCXFeJz8K6BUInP1+KdfVJRAWfwYT+5eh1n9JhWuo6lj6Vh8RCSYmb2a4Xjq/Vfaz9dMLMKMXs00kIpqqrJp7KLU0xCJxLCfsqbcKTzZe5eg4HI8XvtH8WnyWDqNncdHRPQy7R3rYIGvGyxMq/dWZCpSouB4BB7dvKKhZFQT/p0rTj8X/H4Ytdq+BYlNPZhY1S37VbvzIDz+4yhUyvL/+NHkNLbWtiwjInqeV9nWyu7hVUyYMAHr1q3DiBEjtBeWqkSXj6XjVCcRCW58V2e0c6hTzf18nfHzzz9j8ODByMjIQFBQkFDxqRI1mcaWSkw0Oo3NER8R6ZTq7uebkZGBAQMGwMfHB8uWLYOJiYkAqakyunrkFIuPiPRebm4u/Pz88NprryEyMhIWFhZCR6K/lE1jl5TiRWWjzdMZWHxEZBCKi4shk8mQnp6Offv24fXXXxc6Ev3lUlYeZq3/CRmK2jAzNRX8WDoWHxEZDKVSiYULFyI6OhqxsbFo2pSnNugCpVIJV1dXbNj8A9JKbQU/lo43txCRwRCLxfjPf/4DJycneHl5Ye/evXjjjTeEjmX0jh8/DktLS/T27II+OrBRN9fxEZHBmTZtGjZu3IhBgwbhxx9/FDqO0QsLC4NMJtOZ0yk41UlEBuvcuXMYMmQIFixYgJkzZwodxyjl5+fDyckJqampsLOzEzoOAE51EpEBc3d3x4kTJzBgwADcvHkTS5YsgVjMiS5t2rFjB3r37q0zpQdwqpOIDJyLiwtOnDiBU6dOYezYsZDLKzk2gDQmLCwMkydPFjpGOSw+IjJ4tra2OHjwIJRKJfr27YsHDx4IHckoJCcnIz09HQMGDBA6SjksPiIyClKpFNu3b4eHhwe6d++OGzduCB3J4IWHhyMgIAASiW59qsabW4jI6KxevRpLlizBvn370LlzZ6HjGCSFQgEnJyfEx8fDzc1N6DjlcMRHREbn/fffx5o1a9C/f3/ExMQIHccgxcXFwdnZWedKD2DxEZGRGj58OPbv34/AwEBs2LBB6DgGJzw8XOduanmGU51EZNTS0tIwYMAAjBo1CosWLdKZRdb6LDs7G66ursjIyIC1tbXQcSrgiI+IjFqzZs1w8uRJxMfHY8KECXjy5InQkfTe1q1bMWTIEJ0sPYDFR0QEOzs7HD58GI8fP0b//v2Rl5cndCS9pVKpyrYo01UsPiIiAJaWloiOjkabNm3g5eWFzMxMoSPppfPnz6OgoAA9evQQOspzsfiIiP5iYmKClStXQiaTwdPTE7/99pvQkfTOs5tadHlrON7cQkRUiZ07d2LmzJmIjIxE3759hY6jF+RyORo1aoTExEQ4OTkJHee5dLeSiYgENHLkSOzevRsBAQEIDw8XOo5e2Lt3Lzp37qzTpQfwdAYioufy8vJCQkJC2ekOn376KZc7vICu39TyDKc6iYhe4u7duxg0aBDatm2L77//HqampkJH0jkZGRno2LEj/vzzT0ilUqHjvBCnOomIXqJ+/fo4evQosrOzMXDgQOTn5wsdSedERERg9OjROl96AIuPiKhKatWqhT179qBp06bo0aMH/vzzT6Ej6QylUolNmzbp7BZl/8TiIyKqIolEguDgYIwePRqenp64fPmy0JF0wrFjx1CrVi29OemCN7cQEVWDSCTCv/71Lzg5OaF3797Yvn07evfuLXQsQT1bu6cvN/7w5hYiold09OhRvP3221i2bBnGjx8vdBxB5Ofnw8nJCampqbCzsxM6TpVwxEdE9Ip69eqF+Ph4DBw4EBkZGfjoo4/0ZtSjLlFRUejdu7felB7Az/iIiGqkdevWOHnyJHbu3Ilp06ZBoVAIHUmrwsPD9WLt3v/iVCcRkRo8evQII0eOhImJCaKiomBlZSV0JI1LSkpCnz59kJGRAYlEfyYQOeIjIlKD2rVrY//+/bC3t0fPnj1x584doSNp3KZNmzBhwgS9Kj2AIz4iIrVSqVRYtGgRwsLCEBMTg5YtWwodSSMUCgUcHR1x5MgRuLm5CR2nWvSrpomIdJxIJMK///1vODk5oVevXti5c6dOn033quLi4uDi4qJ3pQdwqpOISCMmTpyIyMhI+Pv7IyoqSug4aqcvG1JXhlOdREQadOnSJQwaNAizZs3CvHnzDGK5Q3Z2NlxdXZGRkQFra2uh41QbR3xERBrUrl07nDx5Eps3b8b777+P0tJSoSPVWGRkJIYOHaqXpQew+IiINM7BwQHHjx9HcnIyRowYgcLCQqEjvTKVSoWwsDC92ZC6Miw+IiItsLGxQUxMDGxsbODt7Y179+4JHemVnD9/HoWFhXp9ww6Lj4hIS8zMzLBp0yb069cPnp6eSElJETpStYWFhWHSpEkQi/W3PnhzCxGRAEJCQrBw4ULs3r0bnp6eQsepkqKiIjg4OCAxMRFOTk5Cx3ll+lvZRER6bMqUKQgPD8ewYcOwe/duoeNUyd69e+Hu7q7XpQdwATsRkWAGDBiAuLg4DB48GJmZmZg9e7bQkV5IHzekrgynOomIBHbz5k0MGDAA/fr1w7Jly3Ty87OMjAx06tQJWVlZkEqlQsepEd370yUiMjKNGzfGiRMnkJiYiFGjRqGoqEjoSBVERETg7bff1vvSA1h8REQ6oW7duvj5559hamqKt956C/fv3xc6UhmlUmkw05wAi4+ISGeYm5tj69atePPNN9G9e3dcv35d6EgAgGPHjsHKygqdOnUSOopa8OYWIiIdIhaLsWTJEjRu3BheXl7Yu3cvPDw8BM30bENqQ9hnFODNLUREOmv//v0IDAxESEgIhgwZIkiGhw8fonHjxkhNTYWdnZ0gGdSNU51ERDpq8ODB+OmnnzBt2jQEBwcLkmHHjh3o06ePwZQewOIjItJpXbp0wa+//oqVK1di/vz5UCqVWn19fT5373k41UlEpAdycnIwZMgQODk5YdOmTTA3N9f4ayYlJaFPnz7IyMiARGI4t4RwxEdEpAdsbW1x6NAhKBQK9O3bF7m5uRp/zfDwcAQEBBhU6QEsPiIivWFhYYGoqCh07twZ3bt3x82bNzX2WiUlJdiyZYten7v3PCw+IiI9IhaLsXz5ckydOhWenp64cOGCRl4nLi4OTZo0QYsWLTRyfSGx+IiI9NDs2bOxevVq9OvXD7GxsWq/fnh4uEGO9gDe3EJEpNdOnTqF4cOH48svv8Q777yjlmveu3cPzZs3R0ZGBqytrdVyTV1iWJ9YEhEZmW7duuH48eMYMGAAMjIy8MUXX9R4h5XIyEgMHTrUIEsP4IiPiMgg3Lt3D0OGDEHz5s0REhICMzOzV7qOSqVC27ZtsXbtWvTs2VPNKXUDP+MjIjIA9erVQ3x8PPLz8+Hr64uHDx++0nXOnTsHuVyOHj16qDmh7mDxEREZCEtLS+zatQtubm7w8vJCZmZmta8RHh6OSZMmGcyG1JXhVCcRkYFRqVRYvnw5vvvuOxw4cADt27ev8Jz7BcWIPp+F5Dv5yJcrYC2VoKmtBT6f2B+Jp4/D0dFRgOTaweIjIjJQO3bswHvvvYetW7fCx8cHAHAxMw9rj6YhISUbAFCs+HvvT4lIhdLSUvRt2wgzejZDe8c6guTWNBYfEZEBO378OPz9/fH1119D4tYLi2OSIVeU4kXv/CIRIJWYYIGvG8Z3ddZaVm1h8RERGbikpCQMeP8/MOkyEqUwqfL3WZiKscC3pcGVH9fxEREZuCdW9pB2Gwu5ouKRRo+vHEX+2b0oycmC2MwCpvWbwKbbKEgdW6OoRInFMclo51AH7RwMZ9qTxUdEZODWHk1DcWnF0ss/swcPT0fDtt9MSF06QWQiQdH18yhK/S+kjq0BAHJFKYKPpmH9eHdtx9YYFh8RkQG7X1CMhJTsCp/pKeWPkXd8K2wHzoFlC8+yr1u6vgFL1zfKfq9SAUeuZiOnoBi2Vpo/A1AbuI6PiMiARZ/PqvTrxbeSoVI8gWXzbi+9hghA9IXKr6OPWHxERAYs+U5+uSULz5QW5UNsaQ2R+OU3u8gVSiTffqSJeIJg8RERGbB8uaLSr5tYWENZmA+VsrSK1ylRZyxBsfiIiAyYtbTyWznMG7pBJDFFYcqpKl7HVJ2xBMXiIyIyYG4NrGEuqfhWL5bWQh2vcXjwy3oUppyCskQOVakCRdfOIfdIWLnnSiViuNnX1lZkjeMCdiIiA3a/oBjdv46v9HM+ACi4cgSPzv6IkpxMiMwsYN6gGay7vQ2pQ8uy55hLxDg5v7fB3NXJ5QxERAbsdStz9Gxuh4NJdyvdpsyqtTesWns/9/tFIsC7hZ3BlB7AqU4iIoM3s1czSCVV36rsf0klJpjRq5maEwmLxUdEZODaO9bBAl83WJhW7y3/6V6dbga1XRnAqU4iIqPwbKNpns7Am1uIiIzKpaw8BB9Nw5Gr2RAB5TaulkrEUOHpZ3ozejUzuJHeMyw+IiIjlFNQjOgLWUi+/Qj58hJYS03hZl8b/p0cDOpGlsqw+IiIyKjw5hYiIjIqLD4iIjIqLD4iIjIqLD4iIjIqLD4iIjIqLD4iIjIqLD4iIjIqLD4iIjIqLD4iIjIqLD4iIjIqLD4iIjIqLD4iIjIqLD4iIjIqLD4iIjIqLD4iIjIqLD4iIjIq/w9GAD70G2jX1wAAAABJRU5ErkJggg==\n", "text/plain": [ "
" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "nx.draw(graph, with_labels=True)" ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "['D', 'B', 'E', 'F', 'G', 'A', 'C']" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def bfs(graph, start):\n", " \"\"\"\n", " Return the order in which nodes are visited in a breadth-first \n", " traversal, starting with the given node.\n", " \"\"\"\n", " q = deque()\n", " q.append(start)\n", " seen = set() # nodes we have already visited.\n", " res = []\n", " while len(q) > 0: # while more to visit\n", " n = q.popleft()\n", " if n not in seen:\n", " res.append(n)\n", " seen.add(n)\n", " for nn in graph.neighbors(n):\n", " if nn not in seen:\n", " q.append(nn)\n", " return res\n", "\n", "bfs(graph, 'D')" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "To get all shortest paths from a node, perform BFS, while keeping track of the depth of the search." ] }, { "cell_type": "code", "execution_count": 18, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "\n", "shortest paths for A\n", "{'A': ['A'], 'B': ['A', 'B'], 'C': ['A', 'C'], 'D': ['A', 'B', 'D'], 'E': ['A', 'B', 'D', 'E'], 'F': ['A', 'B', 'D', 'F'], 'G': ['A', 'B', 'D', 'G']}\n", "\n", "shortest paths for B\n", "{'B': ['B'], 'A': ['B', 'A'], 'C': ['B', 'C'], 'D': ['B', 'D'], 'E': ['B', 'D', 'E'], 'F': ['B', 'D', 'F'], 'G': ['B', 'D', 'G']}\n", "\n", "shortest paths for C\n", "{'C': ['C'], 'A': ['C', 'A'], 'B': ['C', 'B'], 'D': ['C', 'B', 'D'], 'E': ['C', 'B', 'D', 'E'], 'F': ['C', 'B', 'D', 'F'], 'G': ['C', 'B', 'D', 'G']}\n", "\n", "shortest paths for D\n", "{'D': ['D'], 'B': ['D', 'B'], 'E': ['D', 'E'], 'F': ['D', 'F'], 'G': ['D', 'G'], 'A': ['D', 'B', 'A'], 'C': ['D', 'B', 'C']}\n", "\n", "shortest paths for E\n", "{'E': ['E'], 'D': ['E', 'D'], 'F': ['E', 'F'], 'B': ['E', 'D', 'B'], 'G': ['E', 'D', 'G'], 'A': ['E', 'D', 'B', 'A'], 'C': ['E', 'D', 'B', 'C']}\n", "\n", "shortest paths for F\n", "{'F': ['F'], 'D': ['F', 'D'], 'E': ['F', 'E'], 'G': ['F', 'G'], 'B': ['F', 'D', 'B'], 'A': ['F', 'D', 'B', 'A'], 'C': ['F', 'D', 'B', 'C']}\n", "\n", "shortest paths for G\n", "{'G': ['G'], 'D': ['G', 'D'], 'F': ['G', 'F'], 'B': ['G', 'D', 'B'], 'E': ['G', 'D', 'E'], 'A': ['G', 'D', 'B', 'A'], 'C': ['G', 'D', 'B', 'C']}\n" ] } ], "source": [ "for s in graph.nodes():\n", " paths = nx.single_source_shortest_path(graph, s)\n", " print('\\nshortest paths for %s' % s)\n", " print(paths)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "# Girvan-Newman Algorithm\n", "\n", "**Input:** Graph $G$; desired number of clusters $k$\n", "\n", "**Output:** A hierarchical clustering of nodes, based on edge betweenness\n", "\n", "- **While** number of clusters $< k$:\n", " - Compute the betweenness of all edges in $G$\n", " - Remove edge with highest betweenness\n" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "![between](between.png)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "![between2](between2.png)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Computing betweenness of all edges\n", "\n", "- All pairs-shortest-paths, but need to store the paths.\n", "- How can we reduce redundant computation?" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Computing betweenness of all edges\n", "\n", "![newman1](newman1.png)\n", "\n", "1.) Do breadth-first search starting at node $E$.\n", " - Each level is length of shortest path from $E$ to that node\n", " - Edges within the same level cannot be part of a shortest path from $E$ to some target.\n", " \n", "2.) Label each node by the number of shortest paths that reach it from the root.\n", " - Start by labeling the root ($E$). Then, each child node is the sum of its parents.\n", " - E.g., $G = D + F$\n" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Computing betweenness of all edges\n", "\n", "![newman1](newman2.png)\n", "\n", "3.) Compute fraction of shortest paths through each edge (bottom up).\n", " - leaf nodes get credit 1\n", " - non-leaf nodes get credit of 1 + credits for edges to nodes at level below\n", " - edges to level above gets credit proportional to fraction of shortest paths that go through it.\n", "\n", "E.g. Level 3:\n", " - $A$ and $C$ are given credit 1 (they are leaf nodes)\n", " \n", "Level 2:\n", " - $B$ gets credit $3$ ($A + C + 1$)\n", " - All shortest paths from $\\{E\\}$ to $\\{A, B, C\\}$ go through B.\n", " - $G$ gets credit 1 (leaf)\n" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Computing betweenness of all edges\n", "\n", "![newman1](newman3.png)\n", "\n", "Level 1 Edges:\n", " - $D,B$ edge gets all credit from node $B$ (3)\n", " - $G$ has two parents, so edges $(D,G)$, $(F,G)$ share the credit from $G$\n", " - From step 1, $D$ and $F$ each have credit 1, so shared equally. $(\\frac{1}{1+1} = .5)$\n", " - What if $D=5$, $F=3$? $\\frac{5}{8}$, $\\frac{3}{8}$\n", " \n", "\n", "Level 1 Nodes:\n", " - $D = 1 + 3 + .5 = 4.5$\n", " - $F = 1 + .5 = 1.5$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Computing betweenness of all edges\n", "\n", "![newman1](newman3.png)\n", "\n", "- What if $D=5$, $F=3$? \n" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Computing betweenness of all edges\n", "\n", "![newman1](newman3.png)\n", "\n", "- What if $D=5$, $F=3$? \n", "$(D,G) = \\frac{5}{8}$, $(F,G) = \\frac{3}{8}$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "Final steps:\n", "\n", "- Repeat for each node as source\n", "- Divide total by 2 (since each shortest path found twice, once in each direction)\n", "\n", "![between](between.png)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**More detailed example for edge (D,E):**\n", "\n", "For each root node, we report the value computed for edge (D,E) for Girvan Newman:\n", "\n", "| root node | value for (D,E)|\n", "|-----------|----------------|\n", "| A | 1 |\n", "| B | 1 |\n", "| C | 1 |\n", "| D | 1 |\n", "| E | 4.5 |\n", "| F | 0 |\n", "| G | .5 |\n", "| **total** | 9 |\n", "\n", "We then divide by 2 to get the final betweenness of (D,E), 4.5.\n", "\n", "\n", "The reason the value is $1$ when the root node is one of ${A,B,C}$ is that $E$ will be a leaf node for each of these. (Shortest paths to $F$ or $G$ from $A,B,C$ will never traverse edge $(D,E)$). The value is 0.5 for $G$ as source, becasue half credit is given as there are two shortest paths of length 2 from $G$ to $E$, but only one traverses $(D,E)$. No other shortest path from root $G$ traverses $(D,E)$. \n" ] }, { "cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "{('A', 'B'): 5.0,\n", " ('A', 'C'): 1.0,\n", " ('B', 'C'): 5.0,\n", " ('B', 'D'): 12.0,\n", " ('D', 'E'): 4.5,\n", " ('D', 'F'): 4.0,\n", " ('D', 'G'): 4.5,\n", " ('E', 'F'): 1.5,\n", " ('F', 'G'): 1.5}" ] }, "execution_count": 11, "metadata": {}, "output_type": "execute_result" } ], "source": [ "nx.edge_betweenness_centrality(graph, normalized=False)" ] }, { "cell_type": "code", "execution_count": 12, "metadata": {}, "outputs": [], "source": [ "def girvan_newman(G, depth=0):\n", " \"\"\" Recursive implementation of the girvan_newman algorithm.\n", " See http://www-rohan.sdsu.edu/~gawron/python_for_ss/course_core/book_draft/Social_Networks/Networkx.html\n", " \n", " Args:\n", " G.....a networkx graph\n", "\n", " Returns:\n", " A list of all discovered communities,\n", " a list of lists of nodes. \"\"\"\n", "\n", " if G.order() == 1:\n", " return [G.nodes()]\n", " \n", " def find_best_edge(G0):\n", " eb = nx.edge_betweenness_centrality(G0)\n", " # eb is dict of (edge, score) pairs, where higher is better\n", " # Return the edge with the highest score.\n", " return sorted(eb.items(), key=lambda x: x[1], reverse=True)[0][0]\n", "\n", " # Each component is a separate community. We cluster each of these.\n", " components = [c for c in nx.connected_component_subgraphs(G)]\n", " indent = ' ' * depth # for printing\n", " while len(components) == 1:\n", " edge_to_remove = find_best_edge(G)\n", " print(indent + 'removing ' + str(edge_to_remove))\n", " G.remove_edge(*edge_to_remove)\n", " components = [c for c in nx.connected_component_subgraphs(G)]\n", "\n", " result = [c.nodes() for c in components]\n", " print(indent + 'components=' + str(result))\n", " for c in components:\n", " result.extend(girvan_newman(c, depth + 1))\n", "\n", " return result" ] }, { "cell_type": "code", "execution_count": 13, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "removing ('B', 'D')\n", "components=[NodeView(('A', 'C', 'B')), NodeView(('D', 'E', 'F', 'G'))]\n", " removing ('A', 'B')\n", " removing ('A', 'C')\n", " components=[NodeView(('A',)), NodeView(('C', 'B'))]\n", " removing ('C', 'B')\n", " components=[NodeView(('C',)), NodeView(('B',))]\n", " removing ('D', 'E')\n", " removing ('E', 'F')\n", " components=[NodeView(('D', 'F', 'G')), NodeView(('E',))]\n", " removing ('D', 'F')\n", " removing ('D', 'G')\n", " components=[NodeView(('D',)), NodeView(('F', 'G'))]\n", " removing ('F', 'G')\n", " components=[NodeView(('F',)), NodeView(('G',))]\n" ] } ], "source": [ "result = girvan_newman(create_example_graph())" ] }, { "cell_type": "code", "execution_count": 14, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[NodeView(('A', 'C', 'B')),\n", " NodeView(('D', 'E', 'F', 'G')),\n", " NodeView(('A',)),\n", " NodeView(('C', 'B')),\n", " NodeView(('A',)),\n", " NodeView(('C',)),\n", " NodeView(('B',)),\n", " NodeView(('C',)),\n", " NodeView(('B',)),\n", " NodeView(('D', 'F', 'G')),\n", " NodeView(('E',)),\n", " NodeView(('D',)),\n", " NodeView(('F', 'G')),\n", " NodeView(('D',)),\n", " NodeView(('F',)),\n", " NodeView(('G',)),\n", " NodeView(('F',)),\n", " NodeView(('G',)),\n", " NodeView(('E',))]" ] }, "execution_count": 14, "metadata": {}, "output_type": "execute_result" } ], "source": [ "result" ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [ { "data": { "text/html": [ "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n" ], "text/plain": [ "" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "from IPython.core.display import HTML\n", "HTML(open('../custom.css').read())" ] } ], "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.7.3" } }, "nbformat": 4, "nbformat_minor": 1 }