hw1.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Part 3 Coding: Shortest Path"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Q8"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import random\n",
    "import matplotlib.pyplot as plt\n",
    "import networkx as nx"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Q8a\n",
    "A procedure that produces a graph (represented by a matrix) of N nodes, each pair connected with probability p <br>\n",
    "input: number of nodes N, probability p <br>\n",
    "output: a graph represented by a matrix, start node, end node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def generate_graph(N, p):\n",
    "    graph = (np.random.rand(N, N) < p).astype(int)\n",
    "    # make the graph undirected/ matrix symmetric\n",
    "    i_lower = np.tril_indices(N, -1)\n",
    "    graph[i_lower] = graph.T[i_lower]\n",
    "    np.fill_diagonal(graph, 0)\n",
    "    return graph"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[0 1 0 1 1 1 0 0 1 1]\n",
      " [1 0 1 1 0 1 1 0 0 1]\n",
      " [0 1 0 1 1 0 0 0 1 0]\n",
      " [1 1 1 0 0 1 0 0 1 0]\n",
      " [1 0 1 0 0 1 1 1 1 0]\n",
      " [1 1 0 1 1 0 0 1 0 1]\n",
      " [0 1 0 0 1 0 0 1 0 1]\n",
      " [0 0 0 0 1 1 1 0 1 1]\n",
      " [1 0 1 1 1 0 0 1 0 1]\n",
      " [1 1 0 0 0 1 1 1 1 0]]\n",
      "[[1, 3, 4, 5, 8, 9], [0, 2, 3, 5, 6, 9], [1, 3, 4, 8], [0, 1, 2, 5, 8], [0, 2, 5, 6, 7, 8], [0, 1, 3, 4, 7, 9], [1, 4, 7, 9], [4, 5, 6, 8, 9], [0, 2, 3, 4, 7, 9], [0, 1, 5, 6, 7, 8]]\n"
     ]
    }
   ],
   "source": [
    "graph = generate_graph(10, 0.5)\n",
    "print (graph)\n",
    "\n",
    "# Print AdjacencyList representation of graph\n",
    "def converGraph(graph, N):\n",
    "    result = [[] for i in range(N)]\n",
    "    for i in range(N):\n",
    "        for j in range(i, N):\n",
    "            if graph[i,j] == 1:\n",
    "                result[i].append(j)\n",
    "                result[j].append(i)\n",
    "    return result\n",
    "\n",
    "print (converGraph(graph, 10))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Q8b\n",
    "Generalized Shortest Path Algorithm: BFS (Breadth First Search) <br>\n",
    "Input: a graph represented by a matrix, start node, end node <br>\n",
    "Output: list of nodes leading from start node to end node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def bfs(graph, start, end):\n",
    "    # maintain a queue of paths\n",
    "    queue = []\n",
    "    explored = []\n",
    "    # push the first path into the queue\n",
    "    queue.append([start])\n",
    "    while queue:\n",
    "        # get the first path from the queue\n",
    "        path = queue.pop(0)\n",
    "        node = path[-1]\n",
    "        if node not in explored:\n",
    "            explored.append(node)\n",
    "            if node == end:\n",
    "                return path\n",
    "            for adjacent in graph[node]:\n",
    "                new_path = list(path)\n",
    "                new_path.append(adjacent)\n",
    "                queue.append(new_path)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Q8c\n",
    "Generate a graph w/ p = 0.1; <br>\n",
    "Pick any two nodes and compute their shortest dist 10000 times;<br> \n",
    "100 sample output is printed;<br> \n",
    "Average distance is 1.9"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 154,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(node A 988, node B 882): path length 2\n",
      "(node A 753, node B 30): path length 2\n",
      "(node A 792, node B 288): path length 2\n",
      "(node A 990, node B 473): path length 2\n",
      "(node A 78, node B 46): path length 2\n",
      "(node A 401, node B 500): path length 1\n",
      "(node A 978, node B 210): path length 2\n",
      "(node A 379, node B 780): path length 2\n",
      "(node A 391, node B 267): path length 2\n",
      "(node A 30, node B 919): path length 2\n",
      "(node A 673, node B 342): path length 2\n",
      "(node A 516, node B 162): path length 2\n",
      "(node A 336, node B 163): path length 2\n",
      "(node A 803, node B 59): path length 2\n",
      "(node A 436, node B 991): path length 2\n",
      "(node A 565, node B 784): path length 2\n",
      "(node A 641, node B 216): path length 2\n",
      "(node A 621, node B 708): path length 2\n",
      "(node A 450, node B 615): path length 2\n",
      "(node A 121, node B 970): path length 2\n",
      "(node A 416, node B 661): path length 2\n",
      "(node A 114, node B 197): path length 2\n",
      "(node A 137, node B 200): path length 2\n",
      "(node A 452, node B 319): path length 2\n",
      "(node A 777, node B 835): path length 2\n",
      "(node A 748, node B 879): path length 2\n",
      "(node A 408, node B 786): path length 2\n",
      "(node A 196, node B 558): path length 1\n",
      "(node A 80, node B 821): path length 2\n",
      "(node A 651, node B 573): path length 1\n",
      "(node A 625, node B 108): path length 2\n",
      "(node A 59, node B 775): path length 2\n",
      "(node A 190, node B 186): path length 2\n",
      "(node A 334, node B 520): path length 1\n",
      "(node A 520, node B 387): path length 1\n",
      "(node A 435, node B 6): path length 2\n",
      "(node A 425, node B 718): path length 2\n",
      "(node A 36, node B 816): path length 2\n",
      "(node A 986, node B 553): path length 2\n",
      "(node A 360, node B 842): path length 2\n",
      "(node A 952, node B 25): path length 2\n",
      "(node A 150, node B 488): path length 2\n",
      "(node A 701, node B 841): path length 2\n",
      "(node A 106, node B 28): path length 2\n",
      "(node A 991, node B 725): path length 2\n",
      "(node A 521, node B 285): path length 2\n",
      "(node A 790, node B 932): path length 2\n",
      "(node A 683, node B 791): path length 2\n",
      "(node A 79, node B 247): path length 2\n",
      "(node A 719, node B 42): path length 2\n",
      "(node A 279, node B 103): path length 1\n",
      "(node A 194, node B 86): path length 1\n",
      "(node A 620, node B 449): path length 2\n",
      "(node A 668, node B 993): path length 2\n",
      "(node A 586, node B 35): path length 2\n",
      "(node A 645, node B 849): path length 2\n",
      "(node A 653, node B 694): path length 2\n",
      "(node A 359, node B 795): path length 2\n",
      "(node A 883, node B 990): path length 2\n",
      "(node A 256, node B 968): path length 2\n",
      "(node A 215, node B 934): path length 2\n",
      "(node A 281, node B 478): path length 2\n",
      "(node A 160, node B 643): path length 2\n",
      "(node A 983, node B 135): path length 2\n",
      "(node A 211, node B 944): path length 2\n",
      "(node A 189, node B 884): path length 2\n",
      "(node A 691, node B 295): path length 2\n",
      "(node A 883, node B 101): path length 2\n",
      "(node A 27, node B 198): path length 2\n",
      "(node A 219, node B 381): path length 1\n",
      "(node A 606, node B 479): path length 2\n",
      "(node A 418, node B 104): path length 2\n",
      "(node A 834, node B 371): path length 2\n",
      "(node A 82, node B 434): path length 2\n",
      "(node A 450, node B 892): path length 2\n",
      "(node A 213, node B 113): path length 2\n",
      "(node A 34, node B 22): path length 2\n",
      "(node A 645, node B 763): path length 2\n",
      "(node A 175, node B 357): path length 2\n",
      "(node A 438, node B 797): path length 2\n",
      "(node A 82, node B 928): path length 2\n",
      "(node A 396, node B 338): path length 2\n",
      "(node A 611, node B 283): path length 2\n",
      "(node A 521, node B 688): path length 2\n",
      "(node A 818, node B 600): path length 2\n",
      "(node A 215, node B 603): path length 2\n",
      "(node A 872, node B 212): path length 2\n",
      "(node A 911, node B 527): path length 2\n",
      "(node A 370, node B 238): path length 2\n",
      "(node A 980, node B 112): path length 2\n",
      "(node A 129, node B 787): path length 2\n",
      "(node A 100, node B 448): path length 2\n",
      "(node A 965, node B 827): path length 2\n",
      "(node A 434, node B 209): path length 2\n",
      "(node A 882, node B 899): path length 2\n",
      "(node A 160, node B 23): path length 2\n",
      "(node A 54, node B 92): path length 2\n",
      "(node A 62, node B 838): path length 1\n",
      "(node A 995, node B 2): path length 2\n",
      "(node A 450, node B 830): path length 2\n",
      "Average distance is 1.9027\n"
     ]
    }
   ],
   "source": [
    "N = 1000\n",
    "p = 0.1\n",
    "maxIter = 10000\n",
    "total = 0;\n",
    "pCount = 100;\n",
    "graph = generate_graph(N, p)\n",
    "myGraph = converGraph(graph, N)\n",
    "numDC = 0;\n",
    "for i in range(maxIter):\n",
    "    start,end = random.sample(range(N), 2)\n",
    "    path = bfs(myGraph, start, end)\n",
    "    if (path == \"infinity\"):\n",
    "        dist = sys.maxint\n",
    "        numDC = numDC + 1\n",
    "    else:\n",
    "        dist = len(path)-1\n",
    "        total = total + dist\n",
    "    if pCount > 0:\n",
    "        print (\"(node A \" + repr(start) + \", node B \"+ repr(end) + \"): path length \" + repr(dist))\n",
    "        pCount = pCount - 1\n",
    "\n",
    "print (\"Average distance is \" + repr(float(total/(maxIter-numDC))))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Q8d\n",
    "Run the shortest-path algorithm on data sets constructed with many values of p<br>\n",
    "Numerical data: [3.244, 2.637, 2.388, 2.14, 2.031, 1.901, 1.852, 1.801, 1.752, 1.689, 1.634, 1.585, 1.544, 1.502] <br>\n",
    "for p values: [0.01, 0.02, 0.03, 0.04, 0.05, 0.1, 0.15000000000000002, 0.2, 0.25, 0.3, 0.35000000000000003, 0.4, 0.45, 0.5] <br>\n",
    "Relation plotted below"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def avgDist(N, p, maxIter):\n",
    "    total = 0;\n",
    "    graph = generate_graph(N, p)\n",
    "    myGraph = converGraph(graph, N)\n",
    "    numDC = 0;\n",
    "    for i in range(maxIter):\n",
    "        start,end = random.sample(range(N), 2)\n",
    "        path = bfs(myGraph, start, end)\n",
    "        if (path == \"infinity\"):\n",
    "            numDC = numDC + 1\n",
    "        else:\n",
    "            dist = len(path) - 1\n",
    "        total = total + dist\n",
    "    return float(total/(maxIter-numDC))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 168,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[3.244, 2.637, 2.388, 2.14, 2.031, 1.901, 1.852, 1.801, 1.752, 1.689, 1.634, 1.585, 1.544, 1.502]\n"
     ]
    }
   ],
   "source": [
    "p = [0.01, 0.02, 0.03, 0.04]\n",
    "for i in range(10):\n",
    "    p.append(0.05+0.05*i)\n",
    "distList = []\n",
    "for pvalue in p:\n",
    "    distList.append(avgDist(1000, pvalue, 1000))\n",
    "print (distList)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 169,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0.01, 0.02, 0.03, 0.04, 0.05, 0.1, 0.15000000000000002, 0.2, 0.25, 0.3, 0.35000000000000003, 0.4, 0.45, 0.5]\n"
     ]
    }
   ],
   "source": [
    "print (p)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 170,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYwAAAEKCAYAAAAB0GKPAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzt3Xt83HWd7/HXJ/fLJE3aTG9J0/QGLZRCS6iKiJQVHxVx\n0RUVRN3do+IFd2Wvcji7HnXPnrNn3bOrrLBYlVW84YWLoCALiiD3pqW09EZL76WlSZs2l7Zpk3zO\nH79fptNhkvwKnUwy834+Hnlk5jvf38znR2g++d7N3RERERlOQbYDEBGRsUEJQ0REIlHCEBGRSJQw\nREQkEiUMERGJRAlDREQiUcIQEZFIlDBERCQSJQwREYmkKNsBnE51dXXe1NSU7TBERMaMFStWtLl7\nPErdnEoYTU1NtLS0ZDsMEZExw8y2R62rLikREYlECUNERCJRwhARkUiUMEREJJKMJQwzKzOz58zs\nBTNba2ZfTlPnWjNbbWZrzOwpMzs36bVtYfkqM9NItohIlmVyllQPcKm7d5lZMfCEmT3o7s8k1dkK\nvN3d283sXcAy4E1Jry9x97YMxigiIhFlLGF4cJRfV/i0OPzylDpPJT19BmjIVDwiIvLGZHQMw8wK\nzWwVsA942N2fHaL6x4EHk5478IiZrTCz6zIVo7vz77/ZxGMvtWbqI0REckJGE4a797n7eQQth8Vm\nNj9dPTNbQpAwvpBUfFF47buA683s4kGuvc7MWsyspbX11H/pmxnLfr+FRzfsO+VrRUTyyYjMknL3\ng8CjwNLU18xsAfBt4Ep33590ze7w+z7gHmDxIO+9zN2b3b05Ho+0uv014rFSWrt6Xte1IiL5IpOz\npOJmVhM+LgcuAzak1GkE7gY+6u4vJZVXmlnVwGPgncCLmYq1LlZKW6cShojIUDI5S2oK8D0zKyRI\nTD9191+a2acB3P024IvABOBWMwPodfdmYBJwT1hWBPzI3X+dqUDrqkrYuLczU28vIpITMjlLajWw\nME35bUmPPwF8Ik2dLcC5qeWZUhcr5cmu/cNXFBHJY1rpTZAwDh05zrHe/myHIiIyailhECQMgP3d\nGscQERmMEgZQFysBoK3zWJYjEREZvZQwgLqqoIXRpqm1IiKDUsIgWIcBaC2GiMgQlDA4MYahFoaI\nyOCUMIDykkJipUW0avGeiMiglDBCdbES2ro06C0iMhgljJC2BxERGZoSRqguVqoxDBGRIShhhOqq\nSpQwRESGoIQRqouV0n74OMf7tD2IiEg6Shihgam1B7o18C0iko4SRmggYWhqrYhIekoYoXhVuJ+U\nxjFERNJSwgidWO2tLikRkXSUMELaHkREZGhKGKHK0iLKiwu1eE9EZBBKGEniVaXasVZEZBAZSxhm\nVmZmz5nZC2a21sy+nKaOmdnNZrbZzFab2aKk15aa2cbwtRszFWeyYD8pJQwRkXQy2cLoAS5193OB\n84ClZvbmlDrvAuaEX9cB/wFgZoXALeHrZwHXmNlZGYwVGNhPSoPeIiLpZCxheKArfFocfnlKtSuB\nO8K6zwA1ZjYFWAxsdvct7n4MuDOsm1F1VdpPSkRkMBkdwzCzQjNbBewDHnb3Z1Oq1AM7k57vCssG\nK8+oulgpBw4fo1fbg4iIvEZGE4a797n7eUADsNjM5p/uzzCz68ysxcxaWltb39B7xWMluMOBw+qW\nEhFJNSKzpNz9IPAosDTlpd3AtKTnDWHZYOXp3nuZuze7e3M8Hn9DcSbWYmgcQ0TkNTI5SypuZjXh\n43LgMmBDSrX7gI+Fs6XeDBxy9z3AcmCOmc0wsxLg6rBuRtVVafGeiMhgijL43lOA74UzngqAn7r7\nL83s0wDufhvwAHA5sBk4DPxp+FqvmX0OeAgoBG5397UZjBXQam8RkaFkLGG4+2pgYZry25IeO3D9\nINc/QJBQRkxdTBsQiogMRiu9k8RKiygtKtAGhCIiaShhJDGzcPGeWhgiIqmUMFLUaT8pEZG0lDBS\nxGOlOnVPRCQNJYwU8aoSjWGIiKShhJGiLlbKge4e+vpTt70SEclvShgp6mKl9Du0a3sQEZGTKGGk\n0OI9EZH0lDBSJBbvaT8pEZGTKGGk0H5SIiLpKWGkUJeUiEh6ShgpqsuKKCks0OI9EZEUShgpgu1B\nSjSGISKSQgkjDZ3tLSLyWkoYadRpexARkddQwkijLlaiFoaISAoljDTiVaXs7z5Gv7YHERFJUMJI\noy5WSl+/c/DI8WyHIiIyaihhpKG1GCIir6WEkUYiYWjgW0QkoShTb2xm04A7gEmAA8vc/espdf4G\nuDYplnlA3N0PmNk2oBPoA3rdvTlTsaaKVwX7SWnxnojICRlLGEAv8FfuvtLMqoAVZvawu68bqODu\nXwW+CmBm7wH+wt0PJL3HEndvy2CMaZ3oktLiPRGRARnrknL3Pe6+MnzcCawH6oe45Brgx5mK51SM\nKy+muNA0hiEikiRSwjCz6Wb2jvBxedhiiMzMmoCFwLODvF4BLAXuSip24BEzW2Fm1w3x3teZWYuZ\ntbS2tp5KWEPFy4TKUo1hiIgkGTZhmNkngZ8D3wyLGoB7o36AmcUIEsEN7t4xSLX3AE+mdEdd5O7n\nAe8Crjezi9Nd6O7L3L3Z3Zvj8XjUsIZVV6XFeyIiyaK0MK4H3gp0ALj7JmBilDc3s2KCZPFDd797\niKpXk9Id5e67w+/7gHuAxVE+83Spi5VqDENEJEmUhNHj7onfnGZWRNBdNCQzM+A7wHp3/9ch6o0D\n3g78IqmscqDby8wqgXcCL0aI9bTRflIiIieLMkvqMTO7CSg3s8uAzwL3R7jurcBHgTVmtiosuwlo\nBHD328Ky9wH/5e7dSddOAu4Jcg5FwI/c/dcRPvO0qYuVsr+7B3cnjENEJK9FSRg3Ah8H1gCfAh4A\nvj3cRe7+BDDsb1p3/y7w3ZSyLcC5EWLLmHhVKcf7nENHjlNTUZLNUERERoUoCaMcuN3dvwVgZoVh\n2eFMBpZtdbEgSbR19ShhiIgQbQzjNwQJYkA58Ehmwhk94uHivVadvCciAkRLGGXu3jXwJHxckbmQ\nRoe6Km1AKCKSLErC6DazRQNPzOx84EjmQhodtGOtiMjJooxh3AD8zMxeIRjEngx8KKNRjQI15cUU\nFmh7EBGRAcMmDHdfbmZzgTPDoo3unvMnCxUUGBMqS2jTGIaICBB9t9oLgKaw/iIzw93vyFhUo0Sw\n2lstDBERiJAwzOz7wCxgFcHZFBCs9M75hDFtfDkb93ZmOwwRkVEhSgujGTjL3YfdDiTXLGys5aG1\nr3Kg+xjjK7UWQ0TyW5RZUi8SDHTnnYXTagBYtbM9y5GIiGRflBZGHbDOzJ4DEh367v6HGYtqlDin\nYRyFBcbzOw5y6dxJ2Q5HRCSroiSML2U6iNGqoqSIeVOqWLlDLQwRkSjTah8biUBGq4XTarnn+d30\n9TuFBdq1VkTyV5QT995sZsvNrMvMjplZn5kNdnJezlnYWENXTy+b93UNX1lEJIdFGfT+BnANsIlg\n48FPALdkMqjRZGFjLQDPq1tKRPJclISBu28GCt29z93/E1ia2bBGj6YJFdRWFGscQ0TyXpRB78Nm\nVgKsMrN/BvYQMdHkAjNjYWMtz+84mO1QRESyKsov/o+G9T4HdAPTgD/KZFCjzcJpNWza18WhIzm/\nhZaIyKCiJIz3uvtRd+9w9y+7+18CV2Q6sNFkYBzjhZ1qZYhI/oqSMP44TdmfDHeRmU0zs0fNbJ2Z\nrTWzz6epc4mZHTKzVeHXF5NeW2pmG81ss5ndGCHOjDl32jjMULeUiOS1QccwzOwa4MPADDO7L+ml\nauBAhPfuBf7K3VeaWRWwwswedvd1KfV+7+4ntVjCc8NvAS4DdgHLzey+NNeOiKqyYs6YWMXz2iJE\nRPLYUIPeTxEMcNcB/y+pvBNYPdwbu/ue8HrcvdPM1gP1QJRf+ouBze6+BcDM7gSujHhtRixsrOHB\nF/fS3+8UaAGfiOShQbuk3H27u/8OeAdBK+AxggTQQHDyXmRm1gQsBJ5N8/KFZrbazB40s7PDsnpg\nZ1KdXWFZ1ixqrOXQkeNs3d+dzTBERLImyhjG40CZmdUD/0Uwa+q7UT/AzGLAXcAN7p66Qnwl0Oju\nC4B/B+6N+r5J73+dmbWYWUtra+upXh7ZwsZg51qNY4hIvoqSMMzdDxNMpb3V3T8AnD3MNcGFZsUE\nyeKH7n536uvhzKuu8PEDQLGZ1QG7CabvDmgIy17D3Ze5e7O7N8fj8ShhvS6z4jGqSou04ltE8lak\nhGFmbwGuBX4VlhVGuQj4DrDe3f91kDqTw3qY2eIwnv3AcmCOmc0IFw1eDdyX7j1GSkGBcV5jDSvV\nwhCRPBVlpfcNwH8H7nH3tWY2E3g0wnVvJei+WmNmq8Kym4BGAHe/DbgK+IyZ9QJHgKvDk/16zexz\nwEMEyel2d197CveVEQsba/nGbzfR3dNLZWnU49BFRHJD1O3NH0t6vgX48wjXPcEwg+Pu/g2CzQ3T\nvfYA8MBwnzOSFjbW0O+wetch3jJrQrbDEREZUUOtw/iau99gZvcDrznPOx9O3Es1cGTryh3tShgi\nkneGamF8P/z+LyMRyFhQU1HCzHilZkqJSF4aNGG4+4rw+2NmFg8fZ27e6hixcFotj720D3cnHK8X\nEckLQ86SMrMvmVkbsBF4ycxak/d7ykcLG2to6zrGzgNHsh2KiMiIGjRhmNlfEsx0usDdx7t7LfAm\n4K1m9hcjFeBok1jAp32lRCTPDNXC+ChwjbtvHSgIZ0h9BPhYpgMbrc6cVEVFSaHGMUQk7wyVMIrd\nvS21MBzHKM5cSKNbUWEBCxrGacW3iOSdoRLGsdf5Ws5b2FjL2lc6OHq8L9uhiIiMmKGm1Z5rZqmb\nBUKwGK8sQ/GMCYsaa+ntd17cfYjmpvHZDkdEZEQMNa122P2i8tXAwPfKHe1KGCKSN6JsPigp6mKl\nNI6v0MC3iOQVJYzXaWFjDSt3tBPslSgikvuUMF6nRY21vNrRw55DR7MdiojIiIiUMMxsupm9I3xc\nbmZVmQ1r9EsexxARyQfDJgwz+yTwc+CbYVEDr+Mo1Vwzb0o1pUUFGscQkbwRpYVxPcEWIR0A7r4J\nmJjJoMaC4nABn1oYIpIvoiSMHndPLNQzsyLSnI+RjxY11rJ2dwc9vVrAJyK5L0rCeMzMbgLKzewy\n4GfA/ZkNa2xY2FjDsb5+1r6Sbn2jiEhuiZIwbgRagTXApwiOTf27TAY1VixsrAXQOIaI5IVhE4a7\n97v7t9z9A+5+Vfh42C4pM5tmZo+a2TozW2tmn09T51ozW21ma8zsKTM7N+m1bWH5KjNrOfVby7xJ\n1WXU15RrHENE8sJQe0kBYGZreO2YxSGgBfhf7r5/kEt7gb9y95XhNNwVZvawu69LqrMVeLu7t5vZ\nu4BlBGduDFiSbsfc0WRhY41aGCKSF6J0ST0I/Aq4Nvy6nyBZ7AW+O9hF7r7H3VeGjzuB9UB9Sp2n\n3H3gz/NnCKbsjikLG2vZffAIr3ZoAZ+I5LZhWxjAO9x9UdLzNWa20t0XmdlHonyImTUBC4Fnh6j2\ncYLkNMCBR8ysD/imuy+L8lkjbdHACXw72lk6f0qWoxERyZwoLYxCM1s88MTMLgAGdrLtHe5iM4sB\ndwE3uHva6URmtoQgYXwhqfgidz8PeBdwvZldPMi115lZi5m1tLa2Rrid0+usqdWUFBawUt1SIpLj\noiSMTwDfMbOtZrYN+A7wSTOrBP7PUBeaWTFBsvihu989SJ0FwLeBK5PHQ9x9d/h9H3APsDjd9e6+\nzN2b3b05Ho9HuJ3Tq7SokPn11TqBT0RyXpRZUsvd/RzgPOBcd1/g7s+5e7e7/3Sw68zMCJLLenf/\n10HqNAJ3Ax9195eSyisH9qsKE9M7gRdP5cZG0sLGWlbvOsSx3v5shyIikjFRxjAws3cDZwNlQR4A\nd//KMJe9FfgowZjHqrDsJqAxvP424IvABODW8H173b0ZmATcE5YVAT9y919Hv62Rtaixlu88sZUN\neztY0FCT7XBERDIiyrTa24AKYAlB19FVwHPDXefuTxAc5zpUnU8QdHmllm8Bzn3tFaNTYufa7e1K\nGCKSs6KMYVzo7h8D2t39y8BbgDMyG9bYMrWmnMnVZTy/UwPfIpK7oiSMgQUGh81sKnAc0PzRFAMn\n8ImI5KooCeN+M6sBvgqsBLYBP8pkUGPRosZadh44QmtnT7ZDERHJiCEThpkVAL9x94PufhcwHZjr\n7l8ckejGkIVJC/hERHLRkAnD3fuBW5Ke97j7oYxHNQbNrx9HcaFpHENEclaULqnfmNn7bWA+raRV\nVlzIWVOqWbldLQwRyU1REsanCA5NOmZmHWbWaWY6MSiNgQV8vX1awCciuSfKSu8qdy9w92J3rw6f\nV49EcGPN+dNrOXK8j6e3DLbju4jI2DVswrDAR8zs78Pn05I3I5QTLjtrEpOry7j5N5uIcMaUiMiY\nEqVL6laCxXofDp93kTQQLieUFRfy2SWzWL6tnadeVitDRHJLlITxJne/nnABX3jgUUlGoxrDPtg8\njcnVZfzbwy+plSEiOSVKwjhuZoWEx7SaWRzQqO4gyooLuX7JLFq2t/PkZrUyRCR3REkYNxOcRzHR\nzP4ReAL43xmNaoz74AXTmDKujH97RK0MEckdUWZJ/RD4W4LDkvYA73X3n2U6sLGstKiQzy6ZzYrt\n7TyxuS3b4YiInBZRZkndDIx391vc/Rvuvn4E4hrzPtjcwNRxGssQkdwRpUtqBfB3Zvaymf2LmTVn\nOqhcMNDKWLnjII9vUitDRMa+KF1S33P3y4ELgI3A/zWzTRmPLAd8IGxlfE1jGSKSA6K0MAbMBuYS\n7Fi7ITPh5JbSokKuv3Q2z+84yGMvtWY7HBGRNyTKGMY/hy2KrwAvAs3u/p6MR5YjPnD+NOpryvna\nI1r9LSJjW5QWxsvAW9x9qbv/p7tr/+5TUFJUwPVLZrNq50G+fP869nUcHf4iEZFRKMoYxjeBPjNb\nbGYXD3wNd12459SjZrbOzNaa2efT1DEzu9nMNpvZajNblPTaUjPbGL524ynf2Shy1fkN/NGieu54\nehsX/fOj/N29a9h54HC2wxIROSU2XDeJmX0C+DzQAKwC3gw87e6XDnPdFGCKu680syqC2Vbvdfd1\nSXUuB/4MuBx4E/B1d39TuLL8JeAyYBewHLgm+dp0mpubvaWlZcj7yaatbd1887GXuWvlLvod/vDc\nqXzmklmcMakq26GJSJ4ysxXuHmn2a5Quqc8TzJDa7u5LgIXAsN1S7r7H3VeGjzuB9UB9SrUrgTs8\n8AxQEyaaxcBmd9/i7seAO8O6Y9qMukr+6f0LePxvl/AnFzbx6xf38s5/e5xP3tGio11FZNSLkjCO\nuvtRADMrdfcNwJmn8iFm1kSQaJ5Neake2Jn0fFdYNlh5uve+zsxazKyltXVszESaMq6cv7/iLJ68\n8VL+/A/m8NzWA7zv1qf48Lee4cnNbRocF5FRKUrC2GVmNcC9wMNm9gtge9QPMLMYcBdwg7uf9pP6\n3H2Zuze7e3M8Hj/db59R4ytL+MvLzuDJGy/lpsvnsmlfF9d++1nee8uTPLR2L/39ShwiMnoUDVfB\n3d8XPvySmT0KjAN+HeXNzayYIFn80N3vTlNlNzAt6XlDWFY8SHlOipUWcd3Fs/jYW5q4a+Uubnvs\nZT71/RXMmRjjM5fM4j3nTqW48FSWzIiInH7DDnq/7jc2M+B7wAF3v2GQOu8GPseJQe+b3X2xmRUR\nDHr/AUGiWA582N3XDvWZo33QO6revn5+tWYPtz76Mhtf7aShtpxPXTyTDzRPo6y4MNvhiUgOOZVB\n70wmjIuA3wNrOHF+xk1AI4C73xYmlW8AS4HDwJ+6e0t4/eXA14BC4HZ3/8fhPjNXEsaA/n7ntxv2\nccvvNvP8joPUxUr5xNtmcO2bGqkqK852eCKSA0ZFwsiGXEsYA9ydZ7Yc4Nbfbeb3m9qoLivijy9s\n4k8ubGJCrDTb4YnIGKaEkcNW7zrIrY++zK/X7qWsuIBrFjfyybfNZGpNebZDE5ExSAkjD2ze18l/\n/G4L967aTYHB+xbW8+m3z2JmPJbt0ERkDFHCyCO72g/zrce3cOfynRzr6+fy+VP4zCWzmF8/Ltuh\nicgYoISRh1o7e7j9ya384OntdPb08vYz4ly/ZDaLZ4zPdmgiMoopYeSxQ0eO84NntnP7E1vZ332M\nC5pq+ewls3nbnDqKtJZDRFIoYQhHjvXxk+U7WPb4Fl45dJSSogLmTIwxd3I186ZUMXdyNXOnVFGn\nWVYieU0JQxKO9fbz8LpXeWHXQdbv6WDD3k5aO3sSr9fFSpk7uSr4mlLN3MlVzJ4Y0wJBkTxxKglj\n2K1BZGwrKSrg3Qum8O4FUxJlbV09bNzbyfo9HWzc28mGvZ18/5nt9PQG6ysLC4yZdZWcObmKeWES\nmTulmqnjygjWWopIPlLCyEN1sVLqZpfy1tl1ibLevn627T/Mhr0dbNgTJJFVOw/yy9V7EnWqyoqY\nN7maMydXMTfs1jpzchWxUv1vJJIP9C9dACgqLGD2xBizJ8a4YsGJ8o6jx3lpbyfr93ayIWyR3PP8\nbrqe6U3UaRxfcVKX1tzJVUyfUElhgVojIrlECUOGVF1WTHPTeJqbTkzPdXd2tR9hQ5hENrwafH9k\n/asM7MheVlzAmZNODK6fNaWaeVOrqdYeWCJjlga95bQ5eryPTa92sX7vwNhIB+v3dHKg+1iizrTx\n5cybXM1ZU6s5a0rwvb6mXGMjIlmiQW/JirLiQs5pGMc5DSdWmbs7+zp7WLeng3WvdLBuTwfrX+ng\n4fWvMvC3SnVZEfOmnEgi86ZUM2dSjNIizdQSGU2UMCSjzIxJ1WVMqi5jyZkTE+WHj/WyYW8n617p\nYP2eIJHc+dxOjhzvA6CowJg9MZZohQwkktrKkmzdikjeU8KQrKgoKWJRYy2LGmsTZX39zrb93UEC\nCVsjT2xu4+7nTxy2OGVcWSKJzJsSJJLG8RUUaIBdJOOUMGTUKCwwZsVjzIrHuGLB1ER5W1dPIokM\ntEZ+91IrfeEIe2VJIfPCFshAa+TMyVVafChymmnQW8ako8f7eOnVzpNaI+v3dNLVE0z3LTCYGY8l\nFh7Om1LFmZO1+FAklQa9JeeVFReyoKGGBQ01ibL+/mC677o9hxJJ5Pkd7dz/wiuJOgOLD+cm7ad1\n5qQqKrX4UGRY+lciOaOgwGicUEHjhAqWzj+xFUrq4sMNezu5e+Vuunq2J+okLz6cF35vHF+hxYci\nSTKWMMzsduAKYJ+7z0/z+t8A1ybFMQ+Iu/sBM9sGdAJ9QG/U5pJIOpEWH4brRoZafDh3ctC9pZla\nkq8yNoZhZhcDXcAd6RJGSt33AH/h7peGz7cBze7ediqfqTEMeaOSFx9u2NPJxldfu/hwUnVpIokM\n7K01Kx6jpEjnjcjYMyrGMNz9cTNrilj9GuDHmYpFJKrBFh+2dvWEmzKGrZE9nTz98n6O9QU7/A6s\nG0neU+uc+nFM0HkjkkOyPoZhZhXAUuBzScUOPGJmfcA33X1ZVoITIVh8OLGqjIlVZVx8RjxRfryv\nn61t3SdtE//c1gPcu+rEIPuMukrOn15L8/RamptqmRWPaZaWjFlZTxjAe4An3f1AUtlF7r7bzCYC\nD5vZBnd/PN3FZnYdcB1AY2Nj5qMVCRUXFnDGpCrOmFR1Uvmhw8dZv7eDVTsP0rKtnd+sf5Wfr9gF\nQE1FMec31nJ+Uy3N08ezoGGc1ovImJHRdRhhl9QvhxrDMLN7gJ+5+48Gef1LQJe7/8twn6cxDBmN\n3J0tbd2s2NZOy/YDtGxvZ0trNwDFhcb8+nE0T6/l/OnjOX96LfEqdWPJyBk1R7QOlzDMbBywFZjm\n7t1hWSVQ4O6d4eOHga+4+6+H+zwlDBkrDnQfY8X29vDrAC/sOsSx8MTDpgkVLJoetECam2qZHY9p\n6xPJmFEx6G1mPwYuAerMbBfwP4FiAHe/Laz2PuC/BpJFaBJwT9jPWwT8KEqyEBlLxleWcNlZk7js\nrEkA9PT28eLuDlZsP0DLtnYe29jK3SuDPbTGlRezqLGG5qagBXJuQw3lJerGkpGnrUFERiF3Z9v+\nw7RsO8CK7e20bG9n874uIJiRdXbYjdU8PRgPmVhVluWIZawaNV1SI00JQ3JZe/cxVu4IkseKbe28\nsOsgPWE3VuP4ikTyaJ4+njkT1Y0l0ShhiOSBY739rH3lUNAC2RYkkrauHgBipUWcNbWac+rHsaBh\nHPPrxzFjQqWSiLyGEoZIHnJ3dhw4TMu2dlbvOsjq3cEmjAOtkFhpEWdPrU4kkHPqx9GkJJL3RsWg\nt4iMLDNj+oRKpk+o5P3nNwDQ29fPpn1drNl9iDW7DrFm9yG+9/T2xIysqtIizq6vZkFDTSKJTNeB\nVDIItTBE8szxvn42vdrFmt0HE4lk/d7OE0mkrIj5U090ZS1oGEfj+AqtUM9RamGIyKCKCwuCkwmn\nVvOhC4Ky4339vPRqZ6IVsmb3If7zyW2JvbKqy4qCFkhD0ApZUF/DtPHlSiJ5RglDRCguLODsqeM4\ne+o4rg7LjvWGSWT3IVbvOsSLuw9x+xNbOd4X9EqMKy9mfn0159TXJAbXG2qVRHKZuqREJLKe3j5e\n2huOiYRdWhv3diaSSE1FMWdPrWZuuO37vMnVzJkU035Zo5i6pEQkI0qLkrd/Dzb77OntY+PezkQr\nZN2eDn7wzPbE7KwCC3btHTjN8MzwICq1RsYeJQwReUNKi157vnpfv7N9f3fiRMP1eztZvesgv1q9\nJ1GnqrSIMydXJU4znDcl2Pm3qqw4G7chEahLSkRGTFdPb3h2SMeJA6n2dNLZ05uo01BbnkggAycb\nNk2o1PnqGaIuKREZlWKlRZw/vZbzp9cmytydVw4dTZytvj78/tsNJ85XLy0Kzh4ZONFwXvh9vM5X\nH1FKGCKSVWZGfU059TXl/MG8SYnyo8f72LyvK9GttWFvJ49u3MfPwsOoACZWlQaD6+GxuGdMqmJG\nXSWVpfq8dPPoAAAJFklEQVTVlgn6ryoio1JZcSHz64PFg8laO3sS3Vrrw26t7z61LbHwEGBSdSkz\n6iqZGY8xs64y8bihtpziwoKRvpWcoYQhImNKvKqUeFUpF82pS5T1huerb97XxZa2bra0drO1rYsH\n1+yh/fDxRL2iAqNxfAUz4yeSyIy6SmbWVRKvKtWsrWEoYYjImFdUWMCcSVXMSTlfHYJt4be0dbO1\nrZstrV1sDR//flNbYuovBOMrMxKtkeD7rHiMprpKYuriApQwRCTH1VaWcH5lyUkD7QD9/c4rh46E\niSRMKG3drNzRzv2rXyF5AunEqtIwiQRdXAMJZdr4irzq4lLCEJG8VFBgNNRW0FBbwdvmxE967ejx\nPnYcOMyW1qCLa2trkEweWruXA93HEvUGurgGWiazJg4klBh1sZKc6+JSwhARSVFWXMgZk4JZV6kO\nHj6WSCJBq6SLLa3dPLH55C6u6rKiYNA9HnRtzYoHiWT6hApKi8bmVikZSxhmdjtwBbDP3eenef0S\n4BfA1rDobnf/SvjaUuDrQCHwbXf/p0zFKSJyKmoqSljUWMKixvRdXC+3BmMlW1qDZPLU5v3cvXJ3\nol6BwbTxFYmWyEBCmRmvJB4b3QPvmWxhfBf4BnDHEHV+7+5XJBeYWSFwC3AZsAtYbmb3ufu6TAUq\nIvJGJXdxvf2Mk7u4unt62drWzcutXScllKe37Ofo8ROtkqrSImZOjDErHCeZGY8xK2yVjIYNHDOW\nMNz9cTNreh2XLgY2u/sWADO7E7gSUMIQkTGpsrQo7ZqS/n5nT8dRtrR28XLSlOBntuzn7udPtErM\ngi1TZtbFEq2RmfFKZsdjIzodONtjGBea2WpgN/DX7r4WqAd2JtXZBbwpG8GJiGRSQcGJVe6pA++H\nj/WG3VpBi2SgZfLc1gMcOd6XqBcrLWLelCp++qm3ZDxxZDNhrAQa3b3LzC4H7gXmnOqbmNl1wHUA\njY2NpzdCEZEsqSgZvFWyt+NoYoxkS2s3R4/3jUgrI2sJw907kh4/YGa3mlkdQWtjWlLVhrBssPdZ\nBiyDYLfaDIUrIjIqFBQYU2vKmVpTftJq9xH57BH9tCRmNtnClGhmi8NY9gPLgTlmNsPMSoCrgfuy\nFaeIiAQyOa32x8AlQJ2Z7QL+J1AM4O63AVcBnzGzXuAIcLUHh3P0mtnngIcIptXeHo5tiIhIFukA\nJRGRPHYqByjlzyYoIiLyhihhiIhIJEoYIiISiRKGiIhEooQhIiKR5NQsKTNrBbYPU60OaBuBcEYb\n3Xd+0X3nlzdy39PdPT58tRxLGFGYWUvUKWS5RPedX3Tf+WWk7ltdUiIiEokShoiIRJKPCWNZtgPI\nEt13ftF955cRue+8G8MQEZHXJx9bGCIi8jrkZMIws6VmttHMNpvZjWleNzO7OXx9tZktykacp1uE\n+55rZk+bWY+Z/XU2YsyECPd9bfhzXmNmT5nZudmIMxMi3PuV4b2vMrMWM7soG3GebsPdd1K9C8ys\n18yuGsn4MiXCz/sSMzsU/rxXmdkXT2sA7p5TXwRbor8MzARKgBeAs1LqXA48CBjwZuDZbMc9Qvc9\nEbgA+EeCI3GzHvcI3feFQG34+F258PM+hXuPcaLreQGwIdtxj8R9J9X7LfAAcFW24x6hn/clwC8z\nFUMutjAWA5vdfYu7HwPuBK5MqXMlcIcHngFqzGzKSAd6mg173+6+z92XA8ezEWCGRLnvp9y9PXz6\nDMEpjrkgyr13efibBKgEcmHQMsq/cYA/A+4C9o1kcBkU9b4zJhcTRj2wM+n5rrDsVOuMNbl4T1Gc\n6n1/nKB1mQsi3buZvc/MNgC/Av7bCMWWScPet5nVA+8D/mME48q0qP+vXxh2Qz5oZmefzgByMWGI\npGVmSwgSxheyHctIcvd73H0u8F7gH7Idzwj5GvAFd+/PdiAjbCXQ6O4LgH8H7j2db56LCWM3MC3p\neUNYdqp1xppcvKcoIt23mS0Avg1c6e77Ryi2TDuln7m7Pw7MNLO6TAeWYVHuuxm408y2ERwHfauZ\nvXdkwsuYYe/b3TvcvSt8/ABQfDp/3rmYMJYDc8xshpmVAFcD96XUuQ/4WDhb6s3AIXffM9KBnmZR\n7jsXDXvfZtYI3A181N1fykKMmRLl3mebmYWPFwGlwFhPmMPet7vPcPcmd28Cfg581t1P61/bWRDl\n5z056ee9mOB3/Gn7eRedrjcaLdy918w+BzxEMKvgdndfa2afDl+/jWDWxOXAZuAw8KfZivd0iXLf\nZjYZaAGqgX4zu4FglkVH1gJ/gyL+vL8ITCD4KxOg13Ngg7qI9/5+gj+OjgNHgA8lDYKPSRHvO+dE\nvO+rgM+YWS/Bz/vq0/nz1kpvERGJJBe7pEREJAOUMEREJBIlDBERiUQJQ0REIlHCEBGRSJQwREaI\nmX03V3ZNlfykhCEiIpEoYYikMLMmM9tgZj80s/Vm9nMzq0ipM9fMnku5Zk34+ItmttzMXjSzZQMr\nb1Ou3zawZYOZNZvZ78LHlWZ2u5k9Z2bPm9mVYfnZYdmqcGO5ORn8TyCSlhKGSHpnAre6+zygA/hs\n8ovuvgEoMbMZYdGHgJ+Ej7/h7he4+3ygHLjiFD73fwC/dffFwBLgq2ZWCXwa+Lq7n0ewT9Ku13lf\nIq+bEoZIejvd/cnw8Q+AdCfV/ZQgUcDJCWOJmT0btjguBU5li+l3Ajea2Srgd0AZ0Ag8DdxkZl8A\nprv7kVO5GZHTIef2khI5TVL3zEm3h85PgJ+Z2d2Au/smMysDbgWa3X2nmX2J4Jd+ql5O/MGW/LoB\n73f3jSn115vZs8C7gQfM7FPu/ttTuyWRN0YtDJH0Gs3sLeHjDwNPpFZw95eBPuDvOdG6GPjl32Zm\nMYLN4NLZBpwfPn5/UvlDwJ8l7Ti6MPw+E9ji7jcDvyA4blVkRClhiKS3EbjezNYDtQx+cttPgI8Q\ndE/h7geBbwEvEvzyXz7IdV8Gvm5mLQRJZ8A/AMXAajNby4kDjz4IvBh2Vc0H7nid9yXyumm3WpEU\nZtYE/DIctBaRkFoYIiISiVoYIiISiVoYIiISiRKGiIhEooQhIiKRKGGIiEgkShgiIhKJEoaIiETy\n/wGP+OUyy2UpmQAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x21994042198>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "plt.plot(p, distList)\n",
    "plt.xlabel(\"p values\")\n",
    "plt.ylabel(\"average Distance\")\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Q8e\n",
    "\n",
    "As p increases, the average distance decreases. Intuitively, the more likely two nodes are connected, the shorter their shortest distance becomes. As p gets closer to 1, the shortest distance should converge to 1 as well because two nodes are highly like to be connected directly. The asymptotic line is \"avg Dist = 1\". "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Q9\n",
    "Load data and convert graph into adjacency list representation "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 136,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Q9\n",
    "# Load fb data\n",
    "fb =  np.loadtxt(fname = 'facebook_combined.txt', delimiter = ' ', dtype = 'int')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 141,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[ 0.  1.  1. ...,  0.  0.  0.]\n",
      " [ 1.  0.  0. ...,  0.  0.  0.]\n",
      " [ 1.  0.  0. ...,  0.  0.  0.]\n",
      " ..., \n",
      " [ 0.  0.  0. ...,  0.  0.  0.]\n",
      " [ 0.  0.  0. ...,  0.  0.  0.]\n",
      " [ 0.  0.  0. ...,  0.  0.  0.]]\n"
     ]
    }
   ],
   "source": [
    "# Convert fb data to graph\n",
    "N = 4039\n",
    "fb_graph = np.zeros((N, N))\n",
    "for i in range(fb.shape[0]):\n",
    "    fb_graph[fb[i,0], fb[i,1]] = 1\n",
    "    fb_graph[fb[i,1], fb[i,0]] = 1\n",
    "print (fb_graph)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 147,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 1]\n"
     ]
    }
   ],
   "source": [
    "myfb = converGraph(fb_graph, N)\n",
    "print (bfs(myfb, 0, 1))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Q9a\n",
    "Below is the code for simulating Q8c on facebook graph; <br>\n",
    "100 sample results are printed; <br>\n",
    "Average distance is 3.64"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 157,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "(node A 517, node B 873): path length 5\n",
      "(node A 2208, node B 940): path length 4\n",
      "(node A 1599, node B 2273): path length 3\n",
      "(node A 701, node B 1048): path length 6\n",
      "(node A 2076, node B 1255): path length 4\n",
      "(node A 697, node B 729): path length 2\n",
      "(node A 261, node B 1536): path length 3\n",
      "(node A 1068, node B 3615): path length 4\n",
      "(node A 3639, node B 3203): path length 5\n",
      "(node A 2172, node B 939): path length 4\n",
      "(node A 1980, node B 1638): path length 4\n",
      "(node A 2767, node B 2782): path length 2\n",
      "(node A 1960, node B 293): path length 4\n",
      "(node A 1557, node B 552): path length 3\n",
      "(node A 3793, node B 3421): path length 5\n",
      "(node A 443, node B 2668): path length 4\n",
      "(node A 1618, node B 1336): path length 2\n",
      "(node A 3465, node B 91): path length 5\n",
      "(node A 2460, node B 3469): path length 5\n",
      "(node A 1024, node B 3600): path length 4\n",
      "(node A 2763, node B 1964): path length 4\n",
      "(node A 2431, node B 544): path length 3\n",
      "(node A 2193, node B 3468): path length 5\n",
      "(node A 3143, node B 2125): path length 4\n",
      "(node A 1514, node B 2877): path length 3\n",
      "(node A 3964, node B 3821): path length 2\n",
      "(node A 1015, node B 1411): path length 2\n",
      "(node A 1950, node B 1231): path length 4\n",
      "(node A 3903, node B 1678): path length 4\n",
      "(node A 1893, node B 2812): path length 3\n",
      "(node A 3727, node B 1139): path length 4\n",
      "(node A 136, node B 1869): path length 3\n",
      "(node A 2333, node B 207): path length 4\n",
      "(node A 4037, node B 2533): path length 5\n",
      "(node A 3251, node B 2236): path length 4\n",
      "(node A 2164, node B 1088): path length 4\n",
      "(node A 4033, node B 234): path length 6\n",
      "(node A 1686, node B 2982): path length 3\n",
      "(node A 3426, node B 1361): path length 3\n",
      "(node A 1290, node B 1467): path length 2\n",
      "(node A 2480, node B 1301): path length 4\n",
      "(node A 1507, node B 816): path length 6\n",
      "(node A 871, node B 134): path length 6\n",
      "(node A 2123, node B 545): path length 3\n",
      "(node A 3135, node B 1046): path length 3\n",
      "(node A 1023, node B 3675): path length 4\n",
      "(node A 2464, node B 284): path length 4\n",
      "(node A 1389, node B 3184): path length 3\n",
      "(node A 3622, node B 3553): path length 2\n",
      "(node A 2249, node B 401): path length 4\n",
      "(node A 2312, node B 2032): path length 2\n",
      "(node A 3636, node B 3398): path length 5\n",
      "(node A 1324, node B 278): path length 3\n",
      "(node A 3501, node B 3250): path length 4\n",
      "(node A 3580, node B 3410): path length 5\n",
      "(node A 245, node B 164): path length 2\n",
      "(node A 1524, node B 113): path length 3\n",
      "(node A 3536, node B 3013): path length 5\n",
      "(node A 3294, node B 3281): path length 2\n",
      "(node A 1702, node B 719): path length 5\n",
      "(node A 3309, node B 1220): path length 3\n",
      "(node A 977, node B 3121): path length 3\n",
      "(node A 2378, node B 3993): path length 5\n",
      "(node A 1450, node B 3797): path length 3\n",
      "(node A 2559, node B 2304): path length 2\n",
      "(node A 4001, node B 1919): path length 5\n",
      "(node A 3937, node B 3565): path length 2\n",
      "(node A 3551, node B 1390): path length 4\n",
      "(node A 3866, node B 2470): path length 5\n",
      "(node A 1271, node B 3012): path length 3\n",
      "(node A 1593, node B 1831): path length 2\n",
      "(node A 3391, node B 2399): path length 4\n",
      "(node A 1960, node B 2322): path length 1\n",
      "(node A 1677, node B 636): path length 3\n",
      "(node A 1858, node B 1753): path length 2\n",
      "(node A 107, node B 2538): path length 3\n",
      "(node A 1070, node B 604): path length 2\n",
      "(node A 2703, node B 520): path length 4\n",
      "(node A 2281, node B 2312): path length 2\n",
      "(node A 3416, node B 3912): path length 5\n",
      "(node A 225, node B 1697): path length 3\n",
      "(node A 3104, node B 3473): path length 5\n",
      "(node A 264, node B 1807): path length 3\n",
      "(node A 196, node B 409): path length 4\n",
      "(node A 792, node B 2036): path length 7\n",
      "(node A 3828, node B 2148): path length 5\n",
      "(node A 426, node B 2277): path length 3\n",
      "(node A 1048, node B 85): path length 3\n",
      "(node A 976, node B 130): path length 3\n",
      "(node A 3699, node B 345): path length 5\n",
      "(node A 3374, node B 2345): path length 4\n",
      "(node A 2987, node B 3213): path length 2\n",
      "(node A 1987, node B 2106): path length 2\n",
      "(node A 2548, node B 3855): path length 5\n",
      "(node A 1405, node B 2584): path length 4\n",
      "(node A 2112, node B 2396): path length 2\n",
      "(node A 204, node B 2779): path length 4\n",
      "(node A 63, node B 3666): path length 5\n",
      "(node A 2813, node B 1362): path length 3\n",
      "(node A 1986, node B 2688): path length 4\n",
      "Average distance is 3.64\n"
     ]
    }
   ],
   "source": [
    "# Q9a\n",
    "N = 4039\n",
    "maxIter = 100\n",
    "total = 0;\n",
    "pCount = 100;\n",
    "numDC = 0;\n",
    "myfb = converGraph(fb_graph, N)\n",
    "for i in range(maxIter):\n",
    "    start,end = random.sample(range(N), 2)\n",
    "    path = bfs(myfb, start, end)\n",
    "    if (path == \"infinity\"):\n",
    "        dist = sys.maxint\n",
    "        numDC = numDC + 1\n",
    "    else:\n",
    "        dist = len(path)-1\n",
    "        total = total + dist\n",
    "    if pCount > 0:\n",
    "        print (\"(node A \" + repr(start) + \", node B \"+ repr(end) + \"): path length \" + repr(dist))\n",
    "        pCount = pCount - 1\n",
    "\n",
    "print (\"Average distance is \" + repr(float(total/(maxIter-numDC))))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Q9b\n",
    "p = number of edges/ total possible edges = 0.0108"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 172,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Facebook data has p value: 0.010819963503439287\n"
     ]
    }
   ],
   "source": [
    "# Q9b\n",
    "p = fb.shape[0]/ ((N*(N-1))/2)\n",
    "print (\"Facebook data has p value: \" + repr(p))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Q9C\n",
    "Average shortest path from Facebook data is about 3.6; <br>\n",
    "Average shortest path from constructed data is about 2.6, which is smaller than the actual data. <br>\n",
    "The reason may be: in the constructed data, the graph is uniformly generated with probability p. Each person has the same expected number of friends. All are equal. However, in the real world, the distribution of number of friends is not uniform. Some people tend to have more friends, some less. The distribution should be more like gaussian. In the graph view, some nodes in the actual Facebook data is more dense than others. That's why the average shortest path is larger in the real data set."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2.58"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Q9c\n",
    "avgDist(4039, 0.01081996, 1000)"
   ]
  }
 ],
 "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.6.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}