why-constraint-not-tight.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 154,
   "metadata": {},
   "outputs": [],
   "source": [
    "%matplotlib inline\n",
    "\n",
    "import pandas as pd\n",
    "import numpy as np\n",
    "import networkx as nx\n",
    "import scipy.io as sio\n",
    "import scipy.sparse as sp\n",
    "from tqdm import tqdm\n",
    "\n",
    "from matplotlib import pyplot as plt\n",
    "from helpers import (\n",
    "    draw_edges, get_borderless_fig, pos_spring_layout, signed_layout, get_lcc,\n",
    "    signed_laplacian, signed_normalized_laplacian, flatten, pos_nbrs, neg_nbrs, sbr,\n",
    "    degree_diag, prepare_seed_vector_sparse, eigs\n",
    ")\n",
    "from core import query_graph, sweep_on_x_fast, query_graph_using_sparse_linear_solver, cg, issparse, diags\n",
    "from numpy import linalg as LA\n",
    "from scipy.stats import rankdata"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 91,
   "metadata": {},
   "outputs": [],
   "source": [
    "g = nx.read_gpickle('graphs/slashdot.pkl')\n",
    "A = nx.adj_matrix(g, weight='sign')\n",
    "\n",
    "n = g.number_of_nodes()\n",
    "L = signed_laplacian(g)\n",
    "Ln = signed_normalized_laplacian(A)\n",
    "D = degree_diag(g)\n",
    "\n",
    "l, v = eigs(Ln, k=1, which='SM')  # the smallest eigen value\n",
    "lambda1 = np.real(l[0])\n",
    "v1 = np.real(flatten(v))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 101,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_gap_list(seed, ub=lambda1, kappa=0.9, lb=-0.1, n_steps=100):\n",
    "    seeds = [[seed]]  # 56787\n",
    "\n",
    "    s = prepare_seed_vector_sparse(seeds, D)\n",
    "    b = D @ s\n",
    "    gamma_list = np.linspace(lb, ub, n_steps)[:-1]  # avoid lambda1\n",
    "    gap_list = []\n",
    "    y_list = []\n",
    "    for gamma in tqdm(gamma_list):\n",
    "        A = L - gamma * D\n",
    "        if issparse(b):\n",
    "            b = b.A        \n",
    "        y, info = cg(A, b)\n",
    "        if info != 0:\n",
    "            print('error, info=', info)\n",
    "\n",
    "        y /= LA.norm(y, 2)\n",
    "        y = diags(1 / np.sqrt(D.diagonal())) @ y[:, None]\n",
    "\n",
    "        assert np.isclose((y.T @ D @ y)[0, 0], 1), 'y not normalized w.r.t D'\n",
    "\n",
    "        gap = (np.sqrt(kappa) - y.T @ D @ s)[0, 0]\n",
    "\n",
    "        y_list.append(y)\n",
    "        gap_list.append(gap)\n",
    "    return gamma_list, gap_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 103,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "\n",
      "  0%|          | 0/99 [00:00<?, ?it/s]\u001b[A\n",
      "  1%|          | 1/99 [00:01<02:58,  1.82s/it]\u001b[A\n",
      "Exception in thread Thread-14:\n",
      "Traceback (most recent call last):\n",
      "  File \"/usr/lib/python3.5/threading.py\", line 914, in _bootstrap_inner\n",
      "    self.run()\n",
      "  File \"/usr/local/lib/python3.5/dist-packages/tqdm/_tqdm.py\", line 102, in run\n",
      "    for instance in self.tqdm_cls._instances:\n",
      "  File \"/usr/lib/python3.5/_weakrefset.py\", line 60, in __iter__\n",
      "    for itemref in self.data:\n",
      "RuntimeError: Set changed size during iteration\n",
      "\n",
      "100%|██████████| 99/99 [03:29<00:00,  4.09s/it]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[<matplotlib.lines.Line2D at 0x7f8ca24b7be0>]"
      ]
     },
     "execution_count": 103,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAZoAAAEACAYAAACK+7BGAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzt3XucVXW9//HXe7iVWIgXIFEn9ZRliQXejr/OcVBHSSs7\nhamFMKWCWpMnOyqkMIxminnpWHnUFEHzRpqKmQKiY3m8ADogecEbiowCpoKpdUacz++PtQa20x4Y\n2LNnX+b9fDz2g7W/+7vX+nxnz/CZtdb3+xlFBGZmZvlSUegAzMysvDnRmJlZXjnRmJlZXjnRmJlZ\nXjnRmJlZXjnRmJlZXuWUaCT1lzRb0hJJsyT1a6ffGEnPpv1GZ7TfLalR0mJJl0lS2r6npIfT1+ZJ\n2itt/7akRZIWSnpQ0h65xG9mZvmnXNbRSJoCvBERF0g6A+gfEePb9OkPLACGAgIeA4ZGxBpJW0bE\nO2m/W4AZETFD0izgooiYLenLwOkRMVzSfsDT6XtHAJMjYr/NHoCZmeVdrpfOjgCmp9vTga9n6XMo\nMDsi1kTEamA2MAIgI8n0AnoDrVmvBWg9O9oKaEr7PxIRa9L2R4DBOcZvZmZ51jPH9w+IiJUAEbFC\n0nZZ+gwGXsl43kRGgpB0D7A3cDdwS9r8I2CWpItIzoL2z7Lf49P3mJlZEdtoopE0BxiY2URy5nFW\nB4+hLG3rrtdFxAhJvYHrgQOBucBJwCkRcbukkcBUoDojpuHAd4EvdTAGMzMrkI0mmoiobu81SSsl\nDYyIlZIGAauydFsOVGU83wG4v80xmiXdSXIpbi4wJiJOSV+7RdLVGcccAlwJjIiItzYQm4u4mZlt\nhojIdoKw2XK9RzMTqEm3xwB3ZOkzC6iW1C+dGFBNclmsb5qckNQTOAx4On1Pk6QD0tcOAp5Nt3cC\nbgWOjYgXNhZcRJTto66uruAxeHweX3ccX3tjq6qaRHKx5sOP4cMnFTzmTXnkQ673aKYAMyR9D1gG\nHAkgaRgwLiLGRsRbks4hmXkWQH1ErJY0AJiZXjbrAdwHXJHu9wTgUkk9gH+kzwEmAlsDrVOh34+I\nfXIcg5lZzvr0qQDeBfpmtL7L9tt7uWJOiSYi3gQOztL+GDA24/k0YFqbPquArEkiIh4C9srSfgLr\nk46ZWcFFwC9/CfPm1TBwYB0rV9aTJJt32XXXOs45p7bQIRZcrmc0ViBVVVWFDiGvPL7SVs7jyxzb\nmjVw3HGwdCnMn19JRUUtEydeyKuvtrD99hWcc04tO+9cWbhgi0ROCzaLmaQo17GZWeE1NsKRR8Kh\nh8JFF8FHPlLoiDqHJKLIJgOYmXUrEXD55XDIIXDuufDrX5dPkskXXzozM+ugv/0Nxo2Dv/wF/vd/\n4dOfLnREpcFnNGZmHbB4Mey9N/TtC48+6iSzKZxozMw24ppr4MAD4cwz4Te/gY9+tNARlRZfOjMz\na8e778L3vw/z5sEDD8Duuxc6otLkRGNmllq69GUmTpxGU1MLfftWsGRJDf/6r5XMn59cMrPN4+nN\nZmYkSaa6+pe88ML6BZfbbVfHI4/Usssu3WctjKc3m5nlycSJ0zKSDEBfXn+9nkmTphUwqvLgRGNm\nBjz3XAsfrlMG0JdXX20pRDhlxYnGzLq9a6+FRYtai2JmclHMzuCvoJl1W+++C9/9Lpx3Htx2Ww27\n7lrH+mTTWhSzpnABlglPBjCzbunJJ+Fb34K99krKyGy55fpZZ+uLYtZ0u6KY+ZgM4ERjZt1KBEyd\nCuPHw89/DjU1hY6ouOQj0XgdjZl1G++8AyeeCAsXegFmV/I9GjPrFp54AoYNgz59kpX+TjJdx4nG\nzMpaBFxxBRx0EEycCFdfDVtsUeiouhdfOjOzspFZQmbw4ApOP72Gn/2skqeegj//GT7zmUJH2D15\nMoCZlYVsJWR69qxj5Mhapk6tdMXlDnIJGjOzdmQrIbN2bT09ekxzkikwJxozKwtNTS4hU6ycaMys\nLPTu7RIyxSrnT0BSf0mzJS2RNEtSv3b6jZH0bNpvdEb73ZIaJS2WdJkkpe17Sno4fW2epL3a7G9v\nSWslfSPXMZhZ6WppgQsugPnzaxg40CVkilHOkwEkTQHeiIgLJJ0B9I+I8W369AcWAEMBAY8BQyNi\njaQtI+KdtN8twIyImCFpFnBRRMyW9GXg9IgYnvarAOYAfwemRsTvs8TlyQBmZW7VKhgzBtasgRtv\nhJYWl5DJVbFWBjgCOCDdng40AOPb9DkUmB0RawAkzQZGADdnJJleQG+gNTu0AK1nR1sBTRn7qwVu\nAfbuhPjNrATddx+MHg3HHgtnnw29egFU8tvf1hU6NGujMxLNgIhYCRARKyRtl6XPYOCVjOdNaRsA\nku4hSRp3kyQQgB8BsyRdRHIWtH/adzDwdeBAYJ9OiN/MSsjatUliueoqmDYNDjmk0BHZxnQo0Uia\nAwzMbCI58zirg8fJdhq27rpWRIyQ1Bu4niSBzAVOAk6JiNsljQSmAtXAJcAZERGtt3PaO+jkyZPX\nbVdVVVFVVdXBcM2sGC1fDt/5TnL28vjjMGhQoSMqfQ0NDTQ0NOT1GJ1xj+ZpoCoiVkoaBNwfEZ9t\n0+fotM+J6fPL0343t+k3GtgrIn4oaXVEbJXx2uqI2ErSi61NwLYkd/7GRsTMNvvyPRqzMvKHP8Dx\nx0NtbVJ5uUePQkdUnop1weZMoCbdHgPckaXPLKBaUr90YkA1yWWxvmlyQlJP4DDg6fQ9TZIOSF87\nCHgOICJ2SR87k1xmO7ltkjGz8tHcDD/+MZx8MtxyC5x5ppNMqemMezRTgBmSvgcsA44EkDQMGBcR\nYyPiLUnnkMw8C6A+IlZLGgDMTC+b9QDuA65I93sCcKmkHsA/gLFZju1TFrMy0rZW2Qkn1HDaaZV8\n4hPQ2AjbbFPoCG1zuNaZmRWFbLXKKirq+MlPajn77ErUqRdzrD3FeunMzCxn2WqVtbTUs3TpNCeZ\nEudEY2ZFwbXKypcTjZkVXAS8955rlZUrf4JmVlCrV8NRR8GaNTXsuKNrlZUj/4VNMyuYhx+Gb38b\nvvIVWLiwktdeq2XixAszapXVulZZGfCsMzPrci0tMGUK/OIXcOWVcMQRhY7IWhVrUU0zsw577bWk\nEGZzMyxYADvuWOiILN98j8bMusw998DQofClLyXVl51kugef0ZhZ3jU3w09+AjNmwE03wQEHbPw9\nVj6caMwsr55/Ho45BpeR6cacaMys07StVbbXXjWce24lkybBD36AV/h3U551ZmadIlutsl696rjt\ntloOP9xTlEuFa52ZWdHKVqvs/ffrufHGaQWMyoqBE42ZdQrXKrP2ONGYWc5WrYJnn3WtMsvO3wFm\nlpM5c+CLX4Qjjqhhl11cq8z+mScDmNlmaW6Gs86CG26Aa6+FAw9cP+tsfa2yGtcqKzH5mAzgRGNm\nm6x1bcygQXDNNbDttoWOyDqLZ52ZWcFddx3867/CmDEwc6aTjG2cF2yaWYe8/TacfDI8/jjMnQtD\nhhQ6IisVPqMxs42aNy8phtm3b1Jx2UnGNoXPaMysXS0tcMEFcPHF8D//A9/8ZqEjslLkRGNm62TW\nKuvfv4IVK2ro0aOSBQtgp50KHZ2VqpwSjaT+wM1AJfAS8K2IWJOl3xjgTCCAcyPi2rT9bmBQGsef\nge9HREjaE7gc+AjwPnByRCxI31MFXAL0Al6PiOG5jMHMEtlqlfXvX8ejj9ay006eomybL9d7NOOB\neyNiN+A+YELbDmkymgTsDewL1Enql758ZER8MSL2AAYAR6btFwB1EfFFoA74ebqvfsCvga9ExOcz\n+ptZjrLVKnvrrXrq66cVMCorB7kmmiOA6en2dODrWfocCsyOiDURsRqYDYwAiIh3ACT1AnqTnPEA\ntACtyWgroCnd/jZwa0Q0pe//a47xm1nq2Wddq8zyI9dEMyAiVgJExApguyx9BgOvZDxvStsAkHQP\nsAJ4G7glbf4RcKGkZSRnN61nSp8GtpZ0v6T5ko7NMX6zbi8Cfv1reOIJ1yqz/NjoPRpJc4CBmU0k\nZx5ndfAY2VaYrluyHxEjJPUGrgcOBOYCJwGnRMTtkkYCU4HqNN6hab++wMOSHo6I57MdePLkyeu2\nq6qqqKqq6mDIZt3D66/D974Hr70Gd91Vw7hxdR+6R5PUKqstdJiWRw0NDTQ0NOT1GDmVoJH0NFAV\nESslDQLuj4jPtulzdNrnxPT55Wm/m9v0Gw3sFRE/lLQ6IrbKeG11RGwl6QygT0ScnbZfBdwdEbdm\nic0laMw2YM4cqKmBUaPgnHOgd2/XKrMirHUmaQrwZkRMSZNA/4gY36ZPf2AByZlIRbo9jGQ22cci\nYoWknsBvgQci4n8kPUky0+wBSQcB50fE3pI+A/yS5B5PH+BR4KiIeCpLbE40Zln83//BmWfCTTfB\n9Olw0EGFjsiKST4STa7raKYAMyR9D1hGOgtM0jBgXESMjYi3JJ1DkmACqI+I1ZIGADPTy2Y9SGat\nXZHu9wTgUkk9gH8AYwEi4hlJs4AngA+AK7MlGTPL7pln4NvfTtbELFzoOmXWNVy92awbiICrr4YJ\nE5LLZOPGgTr1d1YrF8V4RmNmRe7NN+GEE+CFF+CBB2D33QsdkXU3TjRmZSSzhMzgwRUcfngNZ5xR\nyciRyR8o69On0BFad+RLZ2ZlIlsJmR496rjqqlpqajxzzDrGf/jMzNqVrYTMBx/Uc++90woYlZkT\njVnZaGpyCRkrTk40ZmXgzTfhxRddQsaKk78DzUrc/ffDF74ABx5Ywy671LE+2bSWkKkpXHBmeDKA\nWclqboZJk+C665I1MiNGuISM5a7oStAUMycaK2dLliQr/AcPTpLMdtnqppttBs86M+vmIuDKK+FL\nX0oWYd5xh5OMFT8v2DQrEX/9Kxx/PLz8MvzpT/DZz278PWbFwGc0ZiVg9mzYc0/49KfhkUecZKy0\n+IzGrIi0LSFz1lk1XHllJb/7HVx7rUv6W2nyZACzIpGthEzv3nUMH17L9ddXss02hY7QugNPBjAr\nY9lKyDQ317PNNtOcZKykOdGYFYn2Ssi89ppLyFhpc6IxKxItLS4hY+XJ38FmBfbuuzB2LLz4Yg2D\nB7uEjJUfzzozK6B582DUKNh/f3jyyUreeKOWiRMvzCghU+sSMlbyPOvMrADWroXzzoNf/Sp5HHlk\noSMyS+Rj1pnPaMy62IsvwrHHwkc/Co89BjvsUOiIzPLL92jMukgETJsG++4LI0cmq/2dZKw78BmN\nWRd44w048UR45hmYOxeGDCl0RGZdJ+czGkn9Jc2WtETSLEn92uk3RtKzab/RGe13S2qUtFjSZZKU\ntu8p6eH0tXmS9krbPy5ppqSF6Xtqch2DWT7NmZPUKdtxR5g/30nGup+cJwNImgK8EREXSDoD6B8R\n49v06Q8sAIYCAh4DhkbEGklbRsQ7ab9bgBkRMUPSLOCiiJgt6cvA6RExXNIE4OMRMUHStsASYGBE\nrG1zTE8GsC6XWats0KAKPvrRGubMqeSaa+DggwsdndnGFetkgCOAA9Lt6UADML5Nn0OB2RGxBkDS\nbGAEcHNGkukF9AZas0ML0Hp2tBXQlG4H8LF0+2MkSe5DScasELLVKuvbt44//amWoUM9Rdm6r86Y\nDDAgIlYCRMQKINufYRoMvJLxvCltA0DSPcAK4G3glrT5R8CFkpYBFwAT0vZfAbtLehVYBJzSCWMw\ny1m2WmXvvlvPxRdPK2BUZoXXoTMaSXOAgZlNJGcWZ3XwONlOw9Zd14qIEZJ6A9cDBwJzgZOAUyLi\ndkkjgalANcmZUGNEHChpV2COpCGtZ0aZJk+evG67qqqKqqqqDoZrtuleeCF7rbJXX3WtMiteDQ0N\nNDQ05PUYHUo0EVHd3muSVkoaGBErJQ0CVmXpthyoyni+A3B/m2M0S7qT5FLcXGBMRJySvnaLpKvS\nrjXAeWn7C5KWAp8huQf0IZmJxixfIuCGG6CxsbVWWWayca0yK25tfwmvr6/v9GN0xk/ATJL//AHG\nAHdk6TMLqJbUL50YUA3MktQ3TU5I6gkcBjydvqdJ0gHpawcBz6Xty4CD0/aBwKeBFzthHGab7M03\n4Zhj4Nxz4Xe/q2HXXV2rzKytzph1tjUwA9iRJAkcGRGrJQ0DxkXE2LRfDXAmySWzn0bEtZIGAH8g\nmQTQA7gP+FFEtEjaH7g0bf8HcHJENEr6BDAN+EQawnkRcWOWuDzrzPLq3nvhu9+Fb3wDzj8/Wenf\nOutsfa2yGtcqs5KSj1lnrnVmton+/neYMAFuvRWmToXqdi8sm5Ue/4VNswJrbIS99oLXXoNFi5xk\nzDrCicasAz74ILk8dsghydnMTTfB1lsXOiqz0uBaZ2YbsXQpjB4NPXsm1ZZ32qnQEZmVFicaswyZ\nJWS2376CPfes4ec/r+SMM+DUU6HC1wDMNpknA5ilspWQ6dWrjttvr+WwwzxzzLoHTwYwy6NsJWTe\nf7+eG26YVsCozEqfE41Zatkyl5AxywcnGjPg4YczS8hkcgkZs1z5J8i6teZmOPNM+I//gAsucAkZ\ns3zwZADrtp58Eo49FgYPht/8BgYNcgkZM5eg2QRONNaelhb4xS/gvPOSx3HHgTr1x8qsdBXrX9g0\nKxkvvww1NfD++/DII7DrroWOyKz8+R6NdQsRMH16UqdsxAh44AEnGbOu4jMaK3uvvw7jxsHzzyel\n/ffcs9ARmXUvTjRWVjJLyAweXEFVVQ2TJlUyahTceCP06VPoCM26H08GsLKRrYRMz551XHddLUcf\n7ZljZh3hEjRmG5CthMzatfX84Q/TChiVmTnRWNl45RWXkDErRk40VhYaG2HRIpeQMStG/gm0krZ2\nLfz0p3DooTBpkkvImBUjTwawkrVkCYwZAx/7GEydCjvu6BIyZrlyCZpN4ERTvlpa4Fe/grPPhvp6\nOOkk/+VLs87iEjTW7S1bBt/9Lrz3XlLa/1OfKnREZrYxOf0eKKm/pNmSlkiaJalfO/3GSHo27Tc6\no/1uSY2SFku6TEpKG0oaIukhSYsk3SFpy4z3TJD0nKSnJR2SS/xWOlpLyAwbBgcfDH/+s5OMWanI\n6dKZpCnAGxFxgaQzgP4RMb5Nn/7AAmAoIOAxYGhErJG0ZUS8k/a7BZgRETMkzQNOjYgHJdUAu0TE\nJEm7A9cDewM7APcCn8p2jcyXzsrHqlUwdiy8+CJcd51LyJjlUzEu2DwCmJ5uTwe+nqXPocDsiFgT\nEauB2cAIgIwk0wvoDbQueNgtIh5Mt+8Fvplufw24KSLWRsRLwHPAPjmOwYrI0qUvM2pUPcOH1zFq\nVD2XX/4yQ4bAZz8L8+c7yZiVolzv0QyIiJUAEbFC0nZZ+gwGXsl43pS2ASDpHpIzlLuBW9PmxZK+\nGhF3At8iOXtp3dfD7e3LSlu2EjI331zHjTfWMnKkZ46ZlaqNJhpJc4CBmU1AAGd18BjZTsHWXdOK\niBGSepNcEjsQmAscB1wqaRIwE2juyL7amjx58rrtqqoqqqqqOhiyFUJ7JWRuv/1CRo6sK2RoZmWr\noaGBhoaGvB5jo4kmIqrbe03SSkkDI2KlpEHAqizdlgNVGc93AO5vc4xmSXeSXIqbGxFLSC65IelT\nwOEZ+9qxzb5ebS++zERjxW/ZMpeQMetqbX8Jr6+v7/Rj5HqPZiZQk26PAe7I0mcWUC2pXzoxoBqY\nJalvmpyQ1BM4DHgmfb5d+m8FyZnT5RnHO1pSb0k7A/8CzMtxDFYE/vxnaGx0CRmzcpTrT/AUkiSy\nBDgYOB9A0jBJVwJExFvAOSQzzx4F6tNJAX2BmZIWAo3AStYnlGPSfT4FNEXEtHRfTwEz0vY/Aid7\nallp+/vf4b/+C446Ci680CVkzMqRKwNYwcyfD6NHwx57wGWXwbbbuoSMWaG5BM0mcKIpXs3NcM45\ncOWVcOmlydmMmRUHl6CxkvfEE8lZzI47wsKF8IlPFDoiM8s332W1LrF2LfzsZ3DQQXDKKTBzppOM\nWXfhMxrLu2eeWV/O/7HHYKedCh2RmXUlJxrrVK0385uakpv5n/xkDVdcUcnZZ8OJJ7qcv1l35ERj\nnSZbCZmPfKSOP/6xluHDPXPMrLvy75fWabKVkPnHP+q5+uppBYzKzArNicY6zQsvuISMmf0zJxrL\nWQRcfbVLyJhZdv4fwHKyfDkcdhj8+tdw220uIWNm/8yVAWyzRMC118Jpp8EPfgATJkCvXi4hY1bq\nXIJmEzjR5M9rr8G4cfDyyzB9OnzhC4WOyMw6SzH+KWfrRiLghhuSxLLnnklRTCcZM9sYr6OxDlm1\nKllwuWQJ3HUX7LVXoSMys1LhMxr7kKVLX2bUqHqGD69j1Kh6li59md/9DoYMgd12S0rIOMmY2abw\nPRpbJ9vK/r596xgwoJYbbqhkv/0KHaGZ5Zvv0VheZVvZ/+679eyzzzQnGTPbbE40tk5TU/aV/atW\neWW/mW0+Jxpbp6XFK/vNrPP5fxDjjTfgO9+Bl16qYfvtvbLfzDqXpzd3c7ffDiefDEcdBU8/XcnK\nlbVMnHhhxsr+Wq/sN7OceNZZN/XGG/DDH8K8eTB1KvzbvxU6IjMrBp51Zp3i9tthjz1gwABYtMhJ\nxszyK6dEI6m/pNmSlkiaJalfO/3GSHo27Tc6o/1uSY2SFku6TJLS9iGSHpK0SNIdkrZM2w+WtCBt\nny9peC7xdzet92JOOw1uvhkuuQS22KLQUZlZucv1jGY8cG9E7AbcB0xo20FSf2ASsDewL1CXkZCO\njIgvRsQewADgyLT9KuD0iNgTuA04PW1/HfhK2l4DXJdj/N2Gz2LMrFBynQxwBHBAuj0daCBJPpkO\nBWZHxBoASbOBEcDNEfFO2tYL6A20LtjYLSIeTLfvBWYBkyJiUetOI+JJSX0k9YqI93McR9loLdPf\n1NTC4MEVnHpqDRddVMm8eclZjBOMmXW1XBPNgIhYCRARKyRtl6XPYOCVjOdNaRsAku4hOdu5G7g1\nbV4s6asRcSfwLWCHtjuVNBJodJJZL1sJmZtuqmP06FoWLar0ZTIzK4iNJhpJc4CBmU1AAGd18BjZ\nZi+smw4WESMk9QauBw4E5gLHAZdKmgTMBJrbxPQ54DygekMHnjx58rrtqqoqqqqqOhhyacpWQuaD\nD+ppbr6QLbaoK2RoZlakGhoaaGhoyOsxNppoIqLd/8wlrZQ0MCJWShoErMrSbTlQlfF8B+D+Nsdo\nlnQnyaW4uRGxhOSSG5I+BRyeccwdgN8Dx0bESxuKPTPRdAftlZB59VWXkDGz7Nr+El5fX9/px8h1\nMsBMkpvyAGOAO7L0mQVUS+qXTgyoBmZJ6psmJyT1BA4Dnkmfb5f+W0Fy5nR5+nwr4A/A+Ih4JMfY\ny8qqVfDiiy4hY2bFJ9f/gaaQJJElwMHA+QCShkm6EiAi3gLOARYAjwL1EbGa5FfvmZIWAo3AStKE\nAhyT7vMpoCkipqXt3wd2BSam06Ifl7RtjmMoaRHJTf4hQ+DQQ2vYeWeXkDGz4uLKACVsxYqkfMyS\nJcnq/n33XT/rbH0JmRqXkDGzDstHZQAnmhIUAddfDz/+MRx/PEyaBH36FDoqMysH+Ug0LqpZYl59\nFcaNg5degj/+EYYNK3REZmYb5rvEJSICrrkGvvAFGDoUHnvMScbMSoPPaErAK6/A2LHJPZnZs5Nk\nY2ZWKpxoikxmCZntt6/gc5+r4ZJLKvnhD2H8eOjVq9ARmpltGieaIpKthEzv3nXcfnstX/6yZ46Z\nWWnyPZoikq2ETHNzPddfP61gMZmZ5cqJpog8/7xLyJhZ+XGiKQIffAAXXQSNjS4hY2blx/+DFdiT\nT8L++8Ndd8GsWTXsuqtLyJhZeXFlgAJ5/32YMgX++7/h3HOTFf4VFS4hY2aF5RI0m6CYE83jj8P3\nvgfbbw9XXAE77ljoiMzMEvlINL501oX+8Q/4yU/gy19O6pTddZeTjJmVP6+j6SIPP5ycxey+Oyxa\nBIMGFToiM7Ou4UTTyTJX9g8eXMGECTVcdVUlN90Ev/wljBxZ6AjNzLqW79F0omwr+3v2rOPww2u5\n+upKttmmS8MxM9tkvkdT5LKt7F+7tp4tt5zmJGNm3ZYTTSdqavLKfjOztpxoOsnrr8PSpV7Zb2bW\nlv8HzFEE3Hgj7LEHVFfXsPPOXtlvZpbJkwFysHw5nHRS8meVr74a9tnHK/vNrLS5MsAmyGeiaWmB\nq66CM8+EH/wAJkyA3r3zcigzsy6Vj0TjdTSb6Pnn4YQT4L334P774fOfL3REZmbFLad7NJL6S5ot\naYmkWZL6tdNvjKRn036jM9rvltQoabGkyyQpbR8i6SFJiyTdIWnLNvvbSdLfJJ2aS/ybYu1auPBC\n2G8/+NrX4KGHnGTMzDoip0tnkqYAb0TEBZLOAPpHxPg2ffoDC4ChgIDHgKERsUbSlhHxTtrvFmBG\nRMyQNA84NSIelFQD7BIRkzL2eQvwAfBoRFzcTmyddunsiSfguOPg4x+H3/wGdtmlU3ZrZlZ0ivHS\n2RHAAen2dKABGN+mz6HA7IhYAyBpNjACuDkjyfQCegOtC052i4gH0+17gVnApLTvEcAL/PM84k6R\nWUJm0KAKtt22hptvruS885JaZerUL7+ZWfnLNdEMiIiVABGxQtJ2WfoMBl7JeN6UtgEg6R5gb+Bu\n4Na0ebGkr0bEncC3gB3Svn2B04Fq4LQcY/8n2UrIbLFFHXPn1rLffp45Zma2OTaaaCTNAQZmNgEB\nnNXBY2Q7B1h3TSsiRkjqDVwPHAjMBY4DLpU0CZgJNKfdJwOXRMR7rbdzNnTgyZMnr9uuqqqiqqpq\ng4FmKyHz3nv1/OpXF7LffnUbfK+ZWSlqaGigoaEhr8fYaKKJiOr2XpO0UtLAiFgpaRCwKku35UBV\nxvMdgPvbHKNZ0p0kl+LmRsQSkktuSPoUcHjadV/gm5IuAPoDH0j6e0Rcli2+zETTEYsXu4SMmXUv\nbX8Jr6+v7/Rj5FoZYCZQk26PAe7I0mcWUC2pXzoxoBqYJalvmpyQ1BM4DHgmfb5d+m8FyZnT5QAR\n8e8RsUttLupNAAAIcklEQVRE7AL8AvhZe0lmU/z1rzB6NLzwgkvImJl1tlz/B51CkkSWAAcD5wNI\nGibpSoCIeAs4h2Tm2aNAfUSsJjl1mClpIdAIrCRNKMAx6T6fApoiYlqOcWaVWT5m223h0Udr2HVX\nl5AxM+tM3bYywLJlSfmYZcvWl48Bl5Axs+7NJWg2QXuJpqUFLrsMJk+G//xPOP10l48xM2tVjOto\nSsrTT8Pxx0NFBTz4IHzmM4WOyMys/HWLu9zNzXD22fDv/w6jRsEDDzjJmJl1lbJONKNG1fP737/M\n0KEwfz48/nhyX6airEdtZlZcyvoeDbxDjx51XHxxLbW1lS4fY2a2Efm4R1Pmv9v35YMP6pk3b5qT\njJlZgZR5ogGv7DczK6xukGi8st/MrJDK/H9gr+w3Myu0sk403/nOhcyZU+uV/WZmBVTWs87KdWxm\nZvniWWdmZlZynGjMzCyvnGjMzCyvnGjMzCyvnGjMzCyvnGjMzCyvnGjMzCyvnGjMzCyvnGjMzCyv\nnGjMzCyvnGjMzCyvcko0kvpLmi1piaRZkvq102+MpGfTfqMz2u+W1ChpsaTLpOTPk0kaIukhSYsk\n3SFpy4z3tL72l/T13rmMwczM8ivXM5rxwL0RsRtwHzChbQdJ/YFJwN7AvkBdRkI6MiK+GBF7AAOA\nI9P2q4DTI2JP4Dbg9HRfPYDrgLER8XmgCng/xzGUpIaGhkKHkFceX2kr5/GV89jyJddEcwQwPd2e\nDnw9S59DgdkRsSYiVgOzgREAEfEOgKReQG+g9U9h7hYRD6bb9wLfTLcPARZFxF/S97/VXUs0l/s3\nu8dX2sp5fOU8tnzJNdEMiIiVABGxAtguS5/BwCsZz5vSNgAk3QOsAN4Gbk2bF0v6arr9LWCHdPvT\nre+RtEDSaTnGb2ZmebbRRCNpjqQnMh6L03+/1sFjZPu7BuvOQiJiBPAJoA9wYNp8HPADSfOBvkBz\n2t4T+H/AMcC/Af8haXgH4zAzs0KIiM1+AE8DA9PtQcDTWfocDVye8fxy4Kgs/UYDl2Zp/xTwSLp9\nFDA147WzgB+3E1v44Ycffvix6Y9c8kK2R09yMxOoAaYAY4A7svSZBZybTgCoAKqB8ZL6Ah+LiBWS\negKHAX8CkLRdRLwuqYIkmVyesa/TJH0EWAscAFycLbDO/gtxZma2eXK9RzMFqJa0BDgYOB9A0jBJ\nVwJExFvAOcAC4FGgPp0U0BeYKWkh0AisZH1COSbd51NAU0RMS/e1miSxLAAeBxZExN05jsHMzPJI\n3XTSlpmZdZGSqwzQCYtEfyppmaS32/TvLekmSc9JeljSTvkeSzadML6h6WSNZyX9IqO9TtJySY+n\njxFdMZ702CMkPZPGdEaW19v92kuakLY/LemQju6zK+VpfC+lC5IbJc3rqrFks7njk7S1pPsk/U3S\npW3ek/X7tBDyNL770302pj9v23bVeNrKYXwHK5ndu0jSfGVMvNrkz6+zb/rk+0Fyue70dPsM4Pws\nffoDLwD9gK1at9PX9gEGAm+3ec9JwGUZkw5uKtHxPQrsk27/ETg03a4DTi3AeCqA54FKoBewEPhM\nR772wO4kl1V7Ap9M96OO7LOUx5e+9iLQvxBj6sTxbQHsD4ylzUSf9r5Py2h89wNfLPHPb09gULr9\nOWD55n5+JXdGQ+6LROdFuvZnA/u9BTioU6PuuM0en6RBJBMsWn8DvrbN+wsxQWIf4LmIeDki3gdu\nIhljprZf+9Zp7l8j+aZfGxEvAc+l++vIPrtKPsYH6xNqoW3O+A4CiIj3IuIh4P8yO3fg+7Qrdfr4\nMpT657cokvWRRMSTQB9JvTbn8yuGL8SmynmRaDvWvSciPgBWS9o693A3WS7jGwwsz2hfzofH/X1J\nCyVd1d4luTxoG2vbmD7UJ/3ar0m/9hsa58b22VXyMT5IppnOSi9ZnJCPwDtoc8a3sZ+djX2fdqV8\njK/V1PSy2VmdEunm6ZTxSRoJNKbJapM/v1ynN+eFpDkkl7fWNZH84HX0A9vgItEOvqf1mJ0uj+Pb\n0LgvA86OiJD0U5LZe8d18Hi56MhnsanjyfYLUqFmteRjfAD7RzL1fztgjqSnY31Zpq60OePb2M/O\n5vx85ks+xgfw7Yh4Tckyjt9LGhURv93cIHOQ8/gkfQ44j2RpSkf3+SFFmWgiorq91yStlDQwIlam\np3CrsnRbTlJws9UOJNdMN+QVYEfgVSXFOz8eydTsTpfH8S0nGUNm+6vpMV/PaP8NcOfmRb/JlgOZ\nEyvWxZSh7de+X0S8Jam98agD++wq+RgfGZcsXpd0G8klkEIkms0Z38Z+dtoddwHkY3xExGvpv+9K\nuoHk8ytEoslpfJJ2AH4PHJte3m3d5yZ9fqV46ax1kShseJFotaR+SqpHV6dtmdpm5TvT/UFSRfq+\nTol20232+NL/nN6WtI8kkVRbuAPWXRdv9Q3gL3mKv635wL9IqlTyJx2OJhljpva+9jOBo9NZMTsD\n/wLM6+A+u0qnj0/SFkr/NEb6G/EhdN3n1VYu48u07udtQ9+nBdDp45PUQ9I26XYv4CuU4OcnaSvg\nD8D4iHiktfNmfX6FnhWxqQ9ga5KKzkuAOcBWafsw4MqMfjUkN1efBUZntE8hyeBrgWXApLS9DzAj\nfc8jwCdLdHzDgMXpa/+d0X4t8ATJrJPbSUsHddGYRqTjeS79pgWoB76ysa89yZ+eeJ6k3NEhG9pn\nAb8nO3V8wM7p59SYfpalPL6lwF9JiuYuI53x1N73aTmMj2Q22oL0M1wMXEI6m7CUxgecCfyNZHF8\nY/rvtpvz+XnBppmZ5VUpXjozM7MS4kRjZmZ55URjZmZ55URjZmZ55URjZmZ55URjZmZ55URjZmZ5\n5URjZmZ59f8Bgdo5NIMs2vUAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x7f8c6b0fa5f8>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "get_gap_list(0)\n",
    "plt.plot(gamma_list, gap_list, 'o-')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 109,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "\n",
      "  0%|          | 0/99 [00:00<?, ?it/s]\u001b[A\n",
      "  1%|          | 1/99 [00:01<02:21,  1.44s/it]\u001b[A\n",
      "  2%|▏         | 2/99 [00:02<02:18,  1.43s/it]\u001b[A\n",
      "  3%|▎         | 3/99 [00:04<02:15,  1.41s/it]\u001b[A\n",
      "Exception in thread Thread-15:\n",
      "Traceback (most recent call last):\n",
      "  File \"/usr/lib/python3.5/threading.py\", line 914, in _bootstrap_inner\n",
      "    self.run()\n",
      "  File \"/usr/local/lib/python3.5/dist-packages/tqdm/_tqdm.py\", line 102, in run\n",
      "    for instance in self.tqdm_cls._instances:\n",
      "  File \"/usr/lib/python3.5/_weakrefset.py\", line 60, in __iter__\n",
      "    for itemref in self.data:\n",
      "RuntimeError: Set changed size during iteration\n",
      "\n",
      "100%|██████████| 99/99 [02:43<00:00,  2.15s/it]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[<matplotlib.lines.Line2D at 0x7f8ca413de80>]"
      ]
     },
     "execution_count": 109,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAZoAAAEACAYAAACK+7BGAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzt3XucVXW9//HXe7iVWIgXIFEn9ZRliQXejr/OcVBHSSs7\nhamFMKWCWpMnOyqkMIxminnpWHnUFEHzRpqKmQKiY3m8ADogecEbiowCpoKpdUacz++PtQa20x4Y\n2LNnX+b9fDz2g7W/+7vX+nxnz/CZtdb3+xlFBGZmZvlSUegAzMysvDnRmJlZXjnRmJlZXjnRmJlZ\nXjnRmJlZXjnRmJlZXuWUaCT1lzRb0hJJsyT1a6ffGEnPpv1GZ7TfLalR0mJJl0lS2r6npIfT1+ZJ\n2itt/7akRZIWSnpQ0h65xG9mZvmnXNbRSJoCvBERF0g6A+gfEePb9OkPLACGAgIeA4ZGxBpJW0bE\nO2m/W4AZETFD0izgooiYLenLwOkRMVzSfsDT6XtHAJMjYr/NHoCZmeVdrpfOjgCmp9vTga9n6XMo\nMDsi1kTEamA2MAIgI8n0AnoDrVmvBWg9O9oKaEr7PxIRa9L2R4DBOcZvZmZ51jPH9w+IiJUAEbFC\n0nZZ+gwGXsl43kRGgpB0D7A3cDdwS9r8I2CWpItIzoL2z7Lf49P3mJlZEdtoopE0BxiY2URy5nFW\nB4+hLG3rrtdFxAhJvYHrgQOBucBJwCkRcbukkcBUoDojpuHAd4EvdTAGMzMrkI0mmoiobu81SSsl\nDYyIlZIGAauydFsOVGU83wG4v80xmiXdSXIpbi4wJiJOSV+7RdLVGcccAlwJjIiItzYQm4u4mZlt\nhojIdoKw2XK9RzMTqEm3xwB3ZOkzC6iW1C+dGFBNclmsb5qckNQTOAx4On1Pk6QD0tcOAp5Nt3cC\nbgWOjYgXNhZcRJTto66uruAxeHweX3ccX3tjq6qaRHKx5sOP4cMnFTzmTXnkQ673aKYAMyR9D1gG\nHAkgaRgwLiLGRsRbks4hmXkWQH1ErJY0AJiZXjbrAdwHXJHu9wTgUkk9gH+kzwEmAlsDrVOh34+I\nfXIcg5lZzvr0qQDeBfpmtL7L9tt7uWJOiSYi3gQOztL+GDA24/k0YFqbPquArEkiIh4C9srSfgLr\nk46ZWcFFwC9/CfPm1TBwYB0rV9aTJJt32XXXOs45p7bQIRZcrmc0ViBVVVWFDiGvPL7SVs7jyxzb\nmjVw3HGwdCnMn19JRUUtEydeyKuvtrD99hWcc04tO+9cWbhgi0ROCzaLmaQo17GZWeE1NsKRR8Kh\nh8JFF8FHPlLoiDqHJKLIJgOYmXUrEXD55XDIIXDuufDrX5dPkskXXzozM+ugv/0Nxo2Dv/wF/vd/\n4dOfLnREpcFnNGZmHbB4Mey9N/TtC48+6iSzKZxozMw24ppr4MAD4cwz4Te/gY9+tNARlRZfOjMz\na8e778L3vw/z5sEDD8Duuxc6otLkRGNmllq69GUmTpxGU1MLfftWsGRJDf/6r5XMn59cMrPN4+nN\nZmYkSaa6+pe88ML6BZfbbVfHI4/Usssu3WctjKc3m5nlycSJ0zKSDEBfXn+9nkmTphUwqvLgRGNm\nBjz3XAsfrlMG0JdXX20pRDhlxYnGzLq9a6+FRYtai2JmclHMzuCvoJl1W+++C9/9Lpx3Htx2Ww27\n7lrH+mTTWhSzpnABlglPBjCzbunJJ+Fb34K99krKyGy55fpZZ+uLYtZ0u6KY+ZgM4ERjZt1KBEyd\nCuPHw89/DjU1hY6ouOQj0XgdjZl1G++8AyeeCAsXegFmV/I9GjPrFp54AoYNgz59kpX+TjJdx4nG\nzMpaBFxxBRx0EEycCFdfDVtsUeiouhdfOjOzspFZQmbw4ApOP72Gn/2skqeegj//GT7zmUJH2D15\nMoCZlYVsJWR69qxj5Mhapk6tdMXlDnIJGjOzdmQrIbN2bT09ekxzkikwJxozKwtNTS4hU6ycaMys\nLPTu7RIyxSrnT0BSf0mzJS2RNEtSv3b6jZH0bNpvdEb73ZIaJS2WdJkkpe17Sno4fW2epL3a7G9v\nSWslfSPXMZhZ6WppgQsugPnzaxg40CVkilHOkwEkTQHeiIgLJJ0B9I+I8W369AcWAEMBAY8BQyNi\njaQtI+KdtN8twIyImCFpFnBRRMyW9GXg9IgYnvarAOYAfwemRsTvs8TlyQBmZW7VKhgzBtasgRtv\nhJYWl5DJVbFWBjgCOCDdng40AOPb9DkUmB0RawAkzQZGADdnJJleQG+gNTu0AK1nR1sBTRn7qwVu\nAfbuhPjNrATddx+MHg3HHgtnnw29egFU8tvf1hU6NGujMxLNgIhYCRARKyRtl6XPYOCVjOdNaRsA\nku4hSRp3kyQQgB8BsyRdRHIWtH/adzDwdeBAYJ9OiN/MSsjatUliueoqmDYNDjmk0BHZxnQo0Uia\nAwzMbCI58zirg8fJdhq27rpWRIyQ1Bu4niSBzAVOAk6JiNsljQSmAtXAJcAZERGtt3PaO+jkyZPX\nbVdVVVFVVdXBcM2sGC1fDt/5TnL28vjjMGhQoSMqfQ0NDTQ0NOT1GJ1xj+ZpoCoiVkoaBNwfEZ9t\n0+fotM+J6fPL0343t+k3GtgrIn4oaXVEbJXx2uqI2ErSi61NwLYkd/7GRsTMNvvyPRqzMvKHP8Dx\nx0NtbVJ5uUePQkdUnop1weZMoCbdHgPckaXPLKBaUr90YkA1yWWxvmlyQlJP4DDg6fQ9TZIOSF87\nCHgOICJ2SR87k1xmO7ltkjGz8tHcDD/+MZx8MtxyC5x5ppNMqemMezRTgBmSvgcsA44EkDQMGBcR\nYyPiLUnnkMw8C6A+IlZLGgDMTC+b9QDuA65I93sCcKmkHsA/gLFZju1TFrMy0rZW2Qkn1HDaaZV8\n4hPQ2AjbbFPoCG1zuNaZmRWFbLXKKirq+MlPajn77ErUqRdzrD3FeunMzCxn2WqVtbTUs3TpNCeZ\nEudEY2ZFwbXKypcTjZkVXAS8955rlZUrf4JmVlCrV8NRR8GaNTXsuKNrlZUj/4VNMyuYhx+Gb38b\nvvIVWLiwktdeq2XixAszapXVulZZGfCsMzPrci0tMGUK/OIXcOWVcMQRhY7IWhVrUU0zsw577bWk\nEGZzMyxYADvuWOiILN98j8bMusw998DQofClLyXVl51kugef0ZhZ3jU3w09+AjNmwE03wQEHbPw9\nVj6caMwsr55/Ho45BpeR6cacaMys07StVbbXXjWce24lkybBD36AV/h3U551ZmadIlutsl696rjt\ntloOP9xTlEuFa52ZWdHKVqvs/ffrufHGaQWMyoqBE42ZdQrXKrP2ONGYWc5WrYJnn3WtMsvO3wFm\nlpM5c+CLX4Qjjqhhl11cq8z+mScDmNlmaW6Gs86CG26Aa6+FAw9cP+tsfa2yGtcqKzH5mAzgRGNm\nm6x1bcygQXDNNbDttoWOyDqLZ52ZWcFddx3867/CmDEwc6aTjG2cF2yaWYe8/TacfDI8/jjMnQtD\nhhQ6IisVPqMxs42aNy8phtm3b1Jx2UnGNoXPaMysXS0tcMEFcPHF8D//A9/8ZqEjslLkRGNm62TW\nKuvfv4IVK2ro0aOSBQtgp50KHZ2VqpwSjaT+wM1AJfAS8K2IWJOl3xjgTCCAcyPi2rT9bmBQGsef\nge9HREjaE7gc+AjwPnByRCxI31MFXAL0Al6PiOG5jMHMEtlqlfXvX8ejj9ay006eomybL9d7NOOB\neyNiN+A+YELbDmkymgTsDewL1Enql758ZER8MSL2AAYAR6btFwB1EfFFoA74ebqvfsCvga9ExOcz\n+ptZjrLVKnvrrXrq66cVMCorB7kmmiOA6en2dODrWfocCsyOiDURsRqYDYwAiIh3ACT1AnqTnPEA\ntACtyWgroCnd/jZwa0Q0pe//a47xm1nq2Wddq8zyI9dEMyAiVgJExApguyx9BgOvZDxvStsAkHQP\nsAJ4G7glbf4RcKGkZSRnN61nSp8GtpZ0v6T5ko7NMX6zbi8Cfv1reOIJ1yqz/NjoPRpJc4CBmU0k\nZx5ndfAY2VaYrluyHxEjJPUGrgcOBOYCJwGnRMTtkkYCU4HqNN6hab++wMOSHo6I57MdePLkyeu2\nq6qqqKqq6mDIZt3D66/D974Hr70Gd91Vw7hxdR+6R5PUKqstdJiWRw0NDTQ0NOT1GDmVoJH0NFAV\nESslDQLuj4jPtulzdNrnxPT55Wm/m9v0Gw3sFRE/lLQ6IrbKeG11RGwl6QygT0ScnbZfBdwdEbdm\nic0laMw2YM4cqKmBUaPgnHOgd2/XKrMirHUmaQrwZkRMSZNA/4gY36ZPf2AByZlIRbo9jGQ22cci\nYoWknsBvgQci4n8kPUky0+wBSQcB50fE3pI+A/yS5B5PH+BR4KiIeCpLbE40Zln83//BmWfCTTfB\n9Olw0EGFjsiKST4STa7raKYAMyR9D1hGOgtM0jBgXESMjYi3JJ1DkmACqI+I1ZIGADPTy2Y9SGat\nXZHu9wTgUkk9gH8AYwEi4hlJs4AngA+AK7MlGTPL7pln4NvfTtbELFzoOmXWNVy92awbiICrr4YJ\nE5LLZOPGgTr1d1YrF8V4RmNmRe7NN+GEE+CFF+CBB2D33QsdkXU3TjRmZSSzhMzgwRUcfngNZ5xR\nyciRyR8o69On0BFad+RLZ2ZlIlsJmR496rjqqlpqajxzzDrGf/jMzNqVrYTMBx/Uc++90woYlZkT\njVnZaGpyCRkrTk40ZmXgzTfhxRddQsaKk78DzUrc/ffDF74ABx5Ywy671LE+2bSWkKkpXHBmeDKA\nWclqboZJk+C665I1MiNGuISM5a7oStAUMycaK2dLliQr/AcPTpLMdtnqppttBs86M+vmIuDKK+FL\nX0oWYd5xh5OMFT8v2DQrEX/9Kxx/PLz8MvzpT/DZz278PWbFwGc0ZiVg9mzYc0/49KfhkUecZKy0\n+IzGrIi0LSFz1lk1XHllJb/7HVx7rUv6W2nyZACzIpGthEzv3nUMH17L9ddXss02hY7QugNPBjAr\nY9lKyDQ317PNNtOcZKykOdGYFYn2Ssi89ppLyFhpc6IxKxItLS4hY+XJ38FmBfbuuzB2LLz4Yg2D\nB7uEjJUfzzozK6B582DUKNh/f3jyyUreeKOWiRMvzCghU+sSMlbyPOvMrADWroXzzoNf/Sp5HHlk\noSMyS+Rj1pnPaMy62IsvwrHHwkc/Co89BjvsUOiIzPLL92jMukgETJsG++4LI0cmq/2dZKw78BmN\nWRd44w048UR45hmYOxeGDCl0RGZdJ+czGkn9Jc2WtETSLEn92uk3RtKzab/RGe13S2qUtFjSZZKU\ntu8p6eH0tXmS9krbPy5ppqSF6Xtqch2DWT7NmZPUKdtxR5g/30nGup+cJwNImgK8EREXSDoD6B8R\n49v06Q8sAIYCAh4DhkbEGklbRsQ7ab9bgBkRMUPSLOCiiJgt6cvA6RExXNIE4OMRMUHStsASYGBE\nrG1zTE8GsC6XWats0KAKPvrRGubMqeSaa+DggwsdndnGFetkgCOAA9Lt6UADML5Nn0OB2RGxBkDS\nbGAEcHNGkukF9AZas0ML0Hp2tBXQlG4H8LF0+2MkSe5DScasELLVKuvbt44//amWoUM9Rdm6r86Y\nDDAgIlYCRMQKINufYRoMvJLxvCltA0DSPcAK4G3glrT5R8CFkpYBFwAT0vZfAbtLehVYBJzSCWMw\ny1m2WmXvvlvPxRdPK2BUZoXXoTMaSXOAgZlNJGcWZ3XwONlOw9Zd14qIEZJ6A9cDBwJzgZOAUyLi\ndkkjgalANcmZUGNEHChpV2COpCGtZ0aZJk+evG67qqqKqqqqDoZrtuleeCF7rbJXX3WtMiteDQ0N\nNDQ05PUYHUo0EVHd3muSVkoaGBErJQ0CVmXpthyoyni+A3B/m2M0S7qT5FLcXGBMRJySvnaLpKvS\nrjXAeWn7C5KWAp8huQf0IZmJxixfIuCGG6CxsbVWWWayca0yK25tfwmvr6/v9GN0xk/ATJL//AHG\nAHdk6TMLqJbUL50YUA3MktQ3TU5I6gkcBjydvqdJ0gHpawcBz6Xty4CD0/aBwKeBFzthHGab7M03\n4Zhj4Nxz4Xe/q2HXXV2rzKytzph1tjUwA9iRJAkcGRGrJQ0DxkXE2LRfDXAmySWzn0bEtZIGAH8g\nmQTQA7gP+FFEtEjaH7g0bf8HcHJENEr6BDAN+EQawnkRcWOWuDzrzPLq3nvhu9+Fb3wDzj8/Wenf\nOutsfa2yGtcqs5KSj1lnrnVmton+/neYMAFuvRWmToXqdi8sm5Ue/4VNswJrbIS99oLXXoNFi5xk\nzDrCicasAz74ILk8dsghydnMTTfB1lsXOiqz0uBaZ2YbsXQpjB4NPXsm1ZZ32qnQEZmVFicaswyZ\nJWS2376CPfes4ec/r+SMM+DUU6HC1wDMNpknA5ilspWQ6dWrjttvr+WwwzxzzLoHTwYwy6NsJWTe\nf7+eG26YVsCozEqfE41Zatkyl5AxywcnGjPg4YczS8hkcgkZs1z5J8i6teZmOPNM+I//gAsucAkZ\ns3zwZADrtp58Eo49FgYPht/8BgYNcgkZM5eg2QRONNaelhb4xS/gvPOSx3HHgTr1x8qsdBXrX9g0\nKxkvvww1NfD++/DII7DrroWOyKz8+R6NdQsRMH16UqdsxAh44AEnGbOu4jMaK3uvvw7jxsHzzyel\n/ffcs9ARmXUvTjRWVjJLyAweXEFVVQ2TJlUyahTceCP06VPoCM26H08GsLKRrYRMz551XHddLUcf\n7ZljZh3hEjRmG5CthMzatfX84Q/TChiVmTnRWNl45RWXkDErRk40VhYaG2HRIpeQMStG/gm0krZ2\nLfz0p3DooTBpkkvImBUjTwawkrVkCYwZAx/7GEydCjvu6BIyZrlyCZpN4ERTvlpa4Fe/grPPhvp6\nOOkk/+VLs87iEjTW7S1bBt/9Lrz3XlLa/1OfKnREZrYxOf0eKKm/pNmSlkiaJalfO/3GSHo27Tc6\no/1uSY2SFku6TEpKG0oaIukhSYsk3SFpy4z3TJD0nKSnJR2SS/xWOlpLyAwbBgcfDH/+s5OMWanI\n6dKZpCnAGxFxgaQzgP4RMb5Nn/7AAmAoIOAxYGhErJG0ZUS8k/a7BZgRETMkzQNOjYgHJdUAu0TE\nJEm7A9cDewM7APcCn8p2jcyXzsrHqlUwdiy8+CJcd51LyJjlUzEu2DwCmJ5uTwe+nqXPocDsiFgT\nEauB2cAIgIwk0wvoDbQueNgtIh5Mt+8Fvplufw24KSLWRsRLwHPAPjmOwYrI0qUvM2pUPcOH1zFq\nVD2XX/4yQ4bAZz8L8+c7yZiVolzv0QyIiJUAEbFC0nZZ+gwGXsl43pS2ASDpHpIzlLuBW9PmxZK+\nGhF3At8iOXtp3dfD7e3LSlu2EjI331zHjTfWMnKkZ46ZlaqNJhpJc4CBmU1AAGd18BjZTsHWXdOK\niBGSepNcEjsQmAscB1wqaRIwE2juyL7amjx58rrtqqoqqqqqOhiyFUJ7JWRuv/1CRo6sK2RoZmWr\noaGBhoaGvB5jo4kmIqrbe03SSkkDI2KlpEHAqizdlgNVGc93AO5vc4xmSXeSXIqbGxFLSC65IelT\nwOEZ+9qxzb5ebS++zERjxW/ZMpeQMetqbX8Jr6+v7/Rj5HqPZiZQk26PAe7I0mcWUC2pXzoxoBqY\nJalvmpyQ1BM4DHgmfb5d+m8FyZnT5RnHO1pSb0k7A/8CzMtxDFYE/vxnaGx0CRmzcpTrT/AUkiSy\nBDgYOB9A0jBJVwJExFvAOSQzzx4F6tNJAX2BmZIWAo3AStYnlGPSfT4FNEXEtHRfTwEz0vY/Aid7\nallp+/vf4b/+C446Ci680CVkzMqRKwNYwcyfD6NHwx57wGWXwbbbuoSMWaG5BM0mcKIpXs3NcM45\ncOWVcOmlydmMmRUHl6CxkvfEE8lZzI47wsKF8IlPFDoiM8s332W1LrF2LfzsZ3DQQXDKKTBzppOM\nWXfhMxrLu2eeWV/O/7HHYKedCh2RmXUlJxrrVK0385uakpv5n/xkDVdcUcnZZ8OJJ7qcv1l35ERj\nnSZbCZmPfKSOP/6xluHDPXPMrLvy75fWabKVkPnHP+q5+uppBYzKzArNicY6zQsvuISMmf0zJxrL\nWQRcfbVLyJhZdv4fwHKyfDkcdhj8+tdw220uIWNm/8yVAWyzRMC118Jpp8EPfgATJkCvXi4hY1bq\nXIJmEzjR5M9rr8G4cfDyyzB9OnzhC4WOyMw6SzH+KWfrRiLghhuSxLLnnklRTCcZM9sYr6OxDlm1\nKllwuWQJ3HUX7LVXoSMys1LhMxr7kKVLX2bUqHqGD69j1Kh6li59md/9DoYMgd12S0rIOMmY2abw\nPRpbJ9vK/r596xgwoJYbbqhkv/0KHaGZ5Zvv0VheZVvZ/+679eyzzzQnGTPbbE40tk5TU/aV/atW\neWW/mW0+Jxpbp6XFK/vNrPP5fxDjjTfgO9+Bl16qYfvtvbLfzDqXpzd3c7ffDiefDEcdBU8/XcnK\nlbVMnHhhxsr+Wq/sN7OceNZZN/XGG/DDH8K8eTB1KvzbvxU6IjMrBp51Zp3i9tthjz1gwABYtMhJ\nxszyK6dEI6m/pNmSlkiaJalfO/3GSHo27Tc6o/1uSY2SFku6TJLS9iGSHpK0SNIdkrZM2w+WtCBt\nny9peC7xdzet92JOOw1uvhkuuQS22KLQUZlZucv1jGY8cG9E7AbcB0xo20FSf2ASsDewL1CXkZCO\njIgvRsQewADgyLT9KuD0iNgTuA04PW1/HfhK2l4DXJdj/N2Gz2LMrFBynQxwBHBAuj0daCBJPpkO\nBWZHxBoASbOBEcDNEfFO2tYL6A20LtjYLSIeTLfvBWYBkyJiUetOI+JJSX0k9YqI93McR9loLdPf\n1NTC4MEVnHpqDRddVMm8eclZjBOMmXW1XBPNgIhYCRARKyRtl6XPYOCVjOdNaRsAku4hOdu5G7g1\nbV4s6asRcSfwLWCHtjuVNBJodJJZL1sJmZtuqmP06FoWLar0ZTIzK4iNJhpJc4CBmU1AAGd18BjZ\nZi+smw4WESMk9QauBw4E5gLHAZdKmgTMBJrbxPQ54DygekMHnjx58rrtqqoqqqqqOhhyacpWQuaD\nD+ppbr6QLbaoK2RoZlakGhoaaGhoyOsxNppoIqLd/8wlrZQ0MCJWShoErMrSbTlQlfF8B+D+Nsdo\nlnQnyaW4uRGxhOSSG5I+BRyeccwdgN8Dx0bESxuKPTPRdAftlZB59VWXkDGz7Nr+El5fX9/px8h1\nMsBMkpvyAGOAO7L0mQVUS+qXTgyoBmZJ6psmJyT1BA4Dnkmfb5f+W0Fy5nR5+nwr4A/A+Ih4JMfY\ny8qqVfDiiy4hY2bFJ9f/gaaQJJElwMHA+QCShkm6EiAi3gLOARYAjwL1EbGa5FfvmZIWAo3AStKE\nAhyT7vMpoCkipqXt3wd2BSam06Ifl7RtjmMoaRHJTf4hQ+DQQ2vYeWeXkDGz4uLKACVsxYqkfMyS\nJcnq/n33XT/rbH0JmRqXkDGzDstHZQAnmhIUAddfDz/+MRx/PEyaBH36FDoqMysH+Ug0LqpZYl59\nFcaNg5degj/+EYYNK3REZmYb5rvEJSICrrkGvvAFGDoUHnvMScbMSoPPaErAK6/A2LHJPZnZs5Nk\nY2ZWKpxoikxmCZntt6/gc5+r4ZJLKvnhD2H8eOjVq9ARmpltGieaIpKthEzv3nXcfnstX/6yZ46Z\nWWnyPZoikq2ETHNzPddfP61gMZmZ5cqJpog8/7xLyJhZ+XGiKQIffAAXXQSNjS4hY2blx/+DFdiT\nT8L++8Ndd8GsWTXsuqtLyJhZeXFlgAJ5/32YMgX++7/h3HOTFf4VFS4hY2aF5RI0m6CYE83jj8P3\nvgfbbw9XXAE77ljoiMzMEvlINL501oX+8Q/4yU/gy19O6pTddZeTjJmVP6+j6SIPP5ycxey+Oyxa\nBIMGFToiM7Ou4UTTyTJX9g8eXMGECTVcdVUlN90Ev/wljBxZ6AjNzLqW79F0omwr+3v2rOPww2u5\n+upKttmmS8MxM9tkvkdT5LKt7F+7tp4tt5zmJGNm3ZYTTSdqavLKfjOztpxoOsnrr8PSpV7Zb2bW\nlv8HzFEE3Hgj7LEHVFfXsPPOXtlvZpbJkwFysHw5nHRS8meVr74a9tnHK/vNrLS5MsAmyGeiaWmB\nq66CM8+EH/wAJkyA3r3zcigzsy6Vj0TjdTSb6Pnn4YQT4L334P774fOfL3REZmbFLad7NJL6S5ot\naYmkWZL6tdNvjKRn036jM9rvltQoabGkyyQpbR8i6SFJiyTdIWnLNvvbSdLfJJ2aS/ybYu1auPBC\n2G8/+NrX4KGHnGTMzDoip0tnkqYAb0TEBZLOAPpHxPg2ffoDC4ChgIDHgKERsUbSlhHxTtrvFmBG\nRMyQNA84NSIelFQD7BIRkzL2eQvwAfBoRFzcTmyddunsiSfguOPg4x+H3/wGdtmlU3ZrZlZ0ivHS\n2RHAAen2dKABGN+mz6HA7IhYAyBpNjACuDkjyfQCegOtC052i4gH0+17gVnApLTvEcAL/PM84k6R\nWUJm0KAKtt22hptvruS885JaZerUL7+ZWfnLNdEMiIiVABGxQtJ2WfoMBl7JeN6UtgEg6R5gb+Bu\n4Na0ebGkr0bEncC3gB3Svn2B04Fq4LQcY/8n2UrIbLFFHXPn1rLffp45Zma2OTaaaCTNAQZmNgEB\nnNXBY2Q7B1h3TSsiRkjqDVwPHAjMBY4DLpU0CZgJNKfdJwOXRMR7rbdzNnTgyZMnr9uuqqqiqqpq\ng4FmKyHz3nv1/OpXF7LffnUbfK+ZWSlqaGigoaEhr8fYaKKJiOr2XpO0UtLAiFgpaRCwKku35UBV\nxvMdgPvbHKNZ0p0kl+LmRsQSkktuSPoUcHjadV/gm5IuAPoDH0j6e0Rcli2+zETTEYsXu4SMmXUv\nbX8Jr6+v7/Rj5FoZYCZQk26PAe7I0mcWUC2pXzoxoBqYJalvmpyQ1BM4DHgmfb5d+m8FyZnT5QAR\n8e8RsUttLupNAAAIcklEQVRE7AL8AvhZe0lmU/z1rzB6NLzwgkvImJl1tlz/B51CkkSWAAcD5wNI\nGibpSoCIeAs4h2Tm2aNAfUSsJjl1mClpIdAIrCRNKMAx6T6fApoiYlqOcWaVWT5m223h0Udr2HVX\nl5AxM+tM3bYywLJlSfmYZcvWl48Bl5Axs+7NJWg2QXuJpqUFLrsMJk+G//xPOP10l48xM2tVjOto\nSsrTT8Pxx0NFBTz4IHzmM4WOyMys/HWLu9zNzXD22fDv/w6jRsEDDzjJmJl1lbJONKNG1fP737/M\n0KEwfz48/nhyX6airEdtZlZcyvoeDbxDjx51XHxxLbW1lS4fY2a2Efm4R1Pmv9v35YMP6pk3b5qT\njJlZgZR5ogGv7DczK6xukGi8st/MrJDK/H9gr+w3Myu0sk403/nOhcyZU+uV/WZmBVTWs87KdWxm\nZvniWWdmZlZynGjMzCyvnGjMzCyvnGjMzCyvnGjMzCyvnGjMzCyvnGjMzCyvnGjMzCyvnGjMzCyv\nnGjMzCyvnGjMzCyvcko0kvpLmi1piaRZkvq102+MpGfTfqMz2u+W1ChpsaTLpOTPk0kaIukhSYsk\n3SFpy4z3tL72l/T13rmMwczM8ivXM5rxwL0RsRtwHzChbQdJ/YFJwN7AvkBdRkI6MiK+GBF7AAOA\nI9P2q4DTI2JP4Dbg9HRfPYDrgLER8XmgCng/xzGUpIaGhkKHkFceX2kr5/GV89jyJddEcwQwPd2e\nDnw9S59DgdkRsSYiVgOzgREAEfEOgKReQG+g9U9h7hYRD6bb9wLfTLcPARZFxF/S97/VXUs0l/s3\nu8dX2sp5fOU8tnzJNdEMiIiVABGxAtguS5/BwCsZz5vSNgAk3QOsAN4Gbk2bF0v6arr9LWCHdPvT\nre+RtEDSaTnGb2ZmebbRRCNpjqQnMh6L03+/1sFjZPu7BuvOQiJiBPAJoA9wYNp8HPADSfOBvkBz\n2t4T+H/AMcC/Af8haXgH4zAzs0KIiM1+AE8DA9PtQcDTWfocDVye8fxy4Kgs/UYDl2Zp/xTwSLp9\nFDA147WzgB+3E1v44Ycffvix6Y9c8kK2R09yMxOoAaYAY4A7svSZBZybTgCoAKqB8ZL6Ah+LiBWS\negKHAX8CkLRdRLwuqYIkmVyesa/TJH0EWAscAFycLbDO/gtxZma2eXK9RzMFqJa0BDgYOB9A0jBJ\nVwJExFvAOcAC4FGgPp0U0BeYKWkh0AisZH1COSbd51NAU0RMS/e1miSxLAAeBxZExN05jsHMzPJI\n3XTSlpmZdZGSqwzQCYtEfyppmaS32/TvLekmSc9JeljSTvkeSzadML6h6WSNZyX9IqO9TtJySY+n\njxFdMZ702CMkPZPGdEaW19v92kuakLY/LemQju6zK+VpfC+lC5IbJc3rqrFks7njk7S1pPsk/U3S\npW3ek/X7tBDyNL770302pj9v23bVeNrKYXwHK5ndu0jSfGVMvNrkz6+zb/rk+0Fyue70dPsM4Pws\nffoDLwD9gK1at9PX9gEGAm+3ec9JwGUZkw5uKtHxPQrsk27/ETg03a4DTi3AeCqA54FKoBewEPhM\nR772wO4kl1V7Ap9M96OO7LOUx5e+9iLQvxBj6sTxbQHsD4ylzUSf9r5Py2h89wNfLPHPb09gULr9\nOWD55n5+JXdGQ+6LROdFuvZnA/u9BTioU6PuuM0en6RBJBMsWn8DvrbN+wsxQWIf4LmIeDki3gdu\nIhljprZf+9Zp7l8j+aZfGxEvAc+l++vIPrtKPsYH6xNqoW3O+A4CiIj3IuIh4P8yO3fg+7Qrdfr4\nMpT657cokvWRRMSTQB9JvTbn8yuGL8SmynmRaDvWvSciPgBWS9o693A3WS7jGwwsz2hfzofH/X1J\nCyVd1d4luTxoG2vbmD7UJ/3ar0m/9hsa58b22VXyMT5IppnOSi9ZnJCPwDtoc8a3sZ+djX2fdqV8\njK/V1PSy2VmdEunm6ZTxSRoJNKbJapM/v1ynN+eFpDkkl7fWNZH84HX0A9vgItEOvqf1mJ0uj+Pb\n0LgvA86OiJD0U5LZe8d18Hi56MhnsanjyfYLUqFmteRjfAD7RzL1fztgjqSnY31Zpq60OePb2M/O\n5vx85ks+xgfw7Yh4Tckyjt9LGhURv93cIHOQ8/gkfQ44j2RpSkf3+SFFmWgiorq91yStlDQwIlam\np3CrsnRbTlJws9UOJNdMN+QVYEfgVSXFOz8eydTsTpfH8S0nGUNm+6vpMV/PaP8NcOfmRb/JlgOZ\nEyvWxZSh7de+X0S8Jam98agD++wq+RgfGZcsXpd0G8klkEIkms0Z38Z+dtoddwHkY3xExGvpv+9K\nuoHk8ytEoslpfJJ2AH4PHJte3m3d5yZ9fqV46ax1kShseJFotaR+SqpHV6dtmdpm5TvT/UFSRfq+\nTol20232+NL/nN6WtI8kkVRbuAPWXRdv9Q3gL3mKv635wL9IqlTyJx2OJhljpva+9jOBo9NZMTsD\n/wLM6+A+u0qnj0/SFkr/NEb6G/EhdN3n1VYu48u07udtQ9+nBdDp45PUQ9I26XYv4CuU4OcnaSvg\nD8D4iHiktfNmfX6FnhWxqQ9ga5KKzkuAOcBWafsw4MqMfjUkN1efBUZntE8hyeBrgWXApLS9DzAj\nfc8jwCdLdHzDgMXpa/+d0X4t8ATJrJPbSUsHddGYRqTjeS79pgWoB76ysa89yZ+eeJ6k3NEhG9pn\nAb8nO3V8wM7p59SYfpalPL6lwF9JiuYuI53x1N73aTmMj2Q22oL0M1wMXEI6m7CUxgecCfyNZHF8\nY/rvtpvz+XnBppmZ5VUpXjozM7MS4kRjZmZ55URjZmZ55URjZmZ55URjZmZ55URjZmZ55URjZmZ5\n5URjZmZ59f8Bgdo5NIMs2vUAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x7f8c6b060d68>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "get_gap_list(49308)\n",
    "plt.plot(gamma_list, gap_list, 'o-')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 127,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "matrices loading done\n",
      "using given ub=0.01722530425428839\n",
      "at iteration 5 (alpha=-31280.04581)\n",
      "residual: sqrt(kappa) - y' D s=-0.05131670194576854\n",
      "at iteration 10 (alpha=-977.48474)\n",
      "residual: sqrt(kappa) - y' D s=-0.05131669815025375\n",
      "at iteration 15 (alpha=-30.52971)\n",
      "residual: sqrt(kappa) - y' D s=-0.051313042486495264\n",
      "at iteration 20 (alpha=-0.93737)\n",
      "residual: sqrt(kappa) - y' D s=-0.050312384312628966\n",
      "at iteration 25 (alpha=-0.01261)\n",
      "residual: sqrt(kappa) - y' D s=-0.04718486363009167\n",
      "at iteration 30 (alpha=0.01629)\n",
      "residual: sqrt(kappa) - y' D s=-0.046884389475305155\n",
      "at iteration 35 (alpha=0.01720)\n",
      "residual: sqrt(kappa) - y' D s=-0.046874396815103525\n",
      "at iteration 40 (alpha=0.01722)\n",
      "residual: sqrt(kappa) - y' D s=-0.04687408385922587\n",
      "at iteration 45 (alpha=0.01723)\n",
      "residual: sqrt(kappa) - y' D s=-0.04687407411474376\n",
      "at iteration 50 (alpha=0.01723)\n",
      "residual: sqrt(kappa) - y' D s=-0.04687407382483533\n"
     ]
    }
   ],
   "source": [
    "x, obj, details = query_graph_using_sparse_linear_solver(\n",
    "    g, [[49308]], kappa=0.9, max_iter=50, verbose=1, return_details=True,\n",
    "    ub=lambda1\n",
    ")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 164,
   "metadata": {},
   "outputs": [],
   "source": [
    "v1_C1, v1_C2, v1_C = sweep_on_x_fast(g, v1, top_k=200)[:3]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 166,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "difference between lambda1 and alpha 4.4451643407827923e-10\n",
      "max|v1-x|= 0.7039649437462611\n",
      "argmax|v1-x|==49308 (query)? True\n",
      "ranks of nodes by v1 by x [28673.  31367.  24626.5 24626.5 22210.5 22210.5 22210.5 22210.5 19251. ]\n",
      "ranks of nodes by v1 by v1 [0.  1.  2.5 2.5 4.  5.5 5.5 7.  8. ]\n"
     ]
    }
   ],
   "source": [
    "vect_diff = np.abs(v1 - x)\n",
    "print('difference between lambda1 and alpha', np.abs(lambda1 - details['alpha']))\n",
    "print('max|v1-x|=', vect_diff.max())\n",
    "print('argmax|v1-x|==49308 (query)?', np.argmax(vect_diff) == 49308)\n",
    "print('ranks of nodes by v1 by x', np.minimum(n-rankdata(x)[v1_C1], rankdata(x)[v1_C1]))\n",
    "print('ranks of nodes by v1 by v1', np.minimum(n-rankdata(v1)[v1_C1], rankdata(v1)[v1_C1]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# What's weird?\n",
    "\n",
    "- running query on 49308 gives $\\alpha \\approx \\lambda_1$. So it should be the case that $x \\approx v_1$\n",
    "- however, we find $v_1$ and $x$ are quite different (the most different entry is the index of the query)\n",
    "\n",
    "what could be the cause?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 165,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(<matplotlib.figure.Figure at 0x7f8ccc9d9be0>,\n",
       " <matplotlib.axes._subplots.AxesSubplot at 0x7f8c6b1943c8>)"
      ]
     },
     "execution_count": 165,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAV0AAADtCAYAAAAcNaZ2AAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzt3Xt8VPWd//FXCDncE3KhiMhFggSYyMVW0CIUK3KrGCoO\n1qrrpa3tY93dXvfxqGn72+22j/y2j+3PX7d9uFvdn7IqlsKhrqhFRYtUijeggHCAIOEmNyFAQu4n\nyczvj68BQu7JzJkzM+/n45GHl0xmTiYz7/mez/l8v9+UcDiMiIh4o1esD0BEJJkodEVEPKTQFRHx\nkEJXRMRDCl0REQ8pdEVEPNS7g++rn0xEpOtS2vqGRroiIh5S6IqIeEihKyLiIYWuiIiHFLoiIh5S\n6IqIeEihKyLiIYWuiIiHFLoiIh5S6IqIeEihKyLiIYWuiIiHFLoiIh5S6IqIeEihKyLiIYWuiIiH\nFLoiIh5S6IqIeEihKyLiIYWuiIiHFLoiIh5S6IqIeEihKyLiIYWuiIiHFLoiIh5S6IqIeEihKyLi\nIYWuiIiHFLoiIh5S6IqIeEihKyLiIYWuiIiHFLoiIh5S6IqIeEihKyLiIYWuiIiHFLoi3eS6bqwP\nQeJQ71gfgEg8sm0bx3EIBAIEg8FYH47EEY10xVfiYfToui6O4wDgOE5cHLP4h0JXfMO2bYqKirBt\nO9aH0i7LsggEAgAEAgEsy4rxEUk8SQmHw+19v91vikSK67oUFRVd+O/CwsKIhZnrulEJxmjdrySE\nlLa+oZqu+ELT6LGpThqpMPvP/7Q5etRhypTI114VuNIdGumKr0Ry9Oi6LkuWFHHNNZCeHtnRs0gH\n2hzpqqYrvhLJULQsi+zsAGlpqr2Kf6i8IAltzJgCvvvdAgYN8m/gqjacXBS6krBWrLB56y2H8eMD\nLF3qz15a9fsmH5UXpFXx3nvqui579zrMmAG7d/uzl1b9vslJoSstxEu/bHssyyI/P0Dv3v6t56rf\nNzmpe0GaiWa/bCzEQ700Ho5RukzdC9I5iTb6iofjj4djlMjRSFdapdGXSI+0OdJV6IqIRJ7KCyIi\nfqDQFRHxkEJXRMRDCt0EEImmejXmxwf9neKfpgHHuUhMI7WXLcN56SUCI0cSnDkT0tLMV2Ym3Hhj\nyx+oq4OjRy/erunLsqBfvx7+RtKWtv7W6jSJLwrdOHb5NNKCgoIuv/lc18UpKYGRI3EaGynIzcUC\nqK+HPn1a/6GqKti0ydzm0q/sbLj//pa3P3UKXnihZUjn5MDs2S1vX10NBw60vH3fvjB4cJd+v0Th\nui6//73D2LEX/9Zg8fTTNidPau2GeKLQjWORWPjbsiwCkydfvI+pUzv+oaws+Ju/6fyDZGZCQUHL\nkG7reGtrYe/e1kO9tWA5fhxWrmwZ0kOHwty5LW9fUQF79rS8/YAB5md8qFcvi7S0AH36OOTlBfjg\nA4uNG1127nQYN677H7riPfXpJoBInF7G9SlqY6MJ0qZwbmgw/+zdG0aNann7c+fgnXdaD/Xbbmt5\n+yNH4LnnWob0VVfBl77U8vZlZbBjR8vbDxoEI0e2vH0oZL5SUyGl9fbOEydgxQqXqVNhyxaLq6+G\nL3wBNmzQKmU+pckRIt0WDrcM6Pp6E5KtjYzLymDbtpa3z8qCW25peftDh0yoh0IXAtpNSaH31bmc\nmfVlju+v5pVvP8xrJ3sz7cvz+OGP72bIkIs/HtcfmIlLoSvie6EQ1Ndjr1rFunW7qK8ax12D+pO/\n5b94/PRHnMyaSJ++vfg/zzyGNSFXQetv2phSxPd69cJNScH56CM+U/sxqXtf4ZbARKzZE/hsfpCd\nJz6BE1n832/+gtph1UxZcjvBe++N9VFLFyl0RXzEsiwCQ4bgvPgigbm3Yg0bBkuWEBw7lgLXJRyG\n7/z9z8ipPoKzZw8FKi3EHZUXfES1OQEgHMY9fhxr5UrTfZGf3+zb2uInLqim63d6IyWhcNj0JA8Y\n0PJ7DQ3mAtvYsa3+qD6gfU+rjPmZ9spKMuGw6RP+2c/gqadav03v3m0GLrSx8Hk4DKtXm4kl4luq\n6fpAJCY5SBwIh+Gjj+Dll03oDh0Kc+ZE7v5TUmDSJHjpJdMPPG9e66NoiSmVF3xEp4wJbtky2LLF\nrE/x5S/D9OlmRBtprgsbNpgJGnPmwJQpbU66kKhRTVck5p591sx6mz27+Qg0FIK//MWEcFvrXXTH\niRPwyiswcyaMHx+5+5XOUOiKxFw43HLEGQ7DH/8IZ87APfdEfuQbCpnH1EjXa7qQJv6UcBcNjx+H\ntWtNmF6uteBbv978zFe+Ep1SQ69eClyf0YU0iZnf/tampMRh2rQEaJM7eRLeegsOHjTrJ1x/Pc0W\nSGjNu++aC2oPPhjZskJnHDxoLuT17+/t44pGuhIbruuyY4fD9u3w8ssOVVUdj3gvHRW39e+eKy0F\n24b//m84e9b8v89+FtLT2/+5Awfgvffgvvti02Fw6BA8/jju5s2tj8olalTT9YC6Elpn2zZ//auD\n6wYYMSLIggWQl9f687VqlZk8kp8fYP9+qKpymDw5ABDbSSUffghbt5qF2q+5xqwilpHR8c+FQlBZ\n2XE4R5H9xBM4L79MYNQogj/9qVlUXiJFF9Ji5Xe/s9mzx2HSpAQ4hY6CpoA9cMBcT9q/38aympcc\nKisr+frXf0l2NmRmNrJpE8yYkUp1dSMnTkBeXiqNjY385Cc/8f7D7fx5ePFFE7bDh3v72D3gui5F\nRUVmlHvsGIVjxmAtXGjayyQSdCEtFlzXZdMmh3ffhdWrHYqL3Qtncgl3AambmkJyzBj42tdcKitN\nyWHVKoeDB11s2+bf/u2X9Ot3noMHYfz4SQwbNolwGMrKJnHddZNwHIe9e/eyZs2a6B1oebmZmnu5\n9HSzi0YcBS5cnJBDSgqBefOwHnnELMouUaeRbpTZts22bQ4DBgTIzg5SUwNlZTZgTpU1+m3Otm0+\n/NChb98AllXAn/9cRGWlmWiVl/cDJk4cyO7dkJHhkplpMXy4S2HhzxgzJpWcHCgsLIzsaLeiwvTQ\nfvghfPWrMGJE5O7bB1T6ihqVF2Lp0hf2kSMuP/95EVdeab4X8ZBIAE3PV2MjPPaYzSuvmLrvnDlB\namuhVy+X/v0tsrLMXpXV1TZnz0b4Q6xp881t28wqX337mh0hlizp+n2Vl8Nrr8Gdd5rdJuJJ07ZH\najvrKoWun2hFsa6pq3P56COLp5+G55+3CYUcbr89wKOPBsnNNXkQ0RFbaalZiCYQMG1V775rLjLd\nemvHbWCXq6qCp582LWQ33BCZ4/PS+vVw9KjZCy47O9ZHE08Uun6j07quc12X++8v4swZuPFG+NGP\nonSWEA7Dvn1m88raWrOmbW5u1++nthaeeQbGjYObb478cXohFIL334eNG82HxowZuI2Neu12TNv1\n+I1etF1nWRa33x7gqaccrrkmiquxpaSYroTJk83V/F7duN5cXw8rVpga8OzZET9Ez/TqZT7hJkyA\ntWuxH34YZ9AgAjNm6CytmzTSlbizYoXL+PEWU6f24E7q62HzZlNjnT49Ysd2wfvvm9PyO+5ImHqo\nW1dH0fe+Z0omo0frekT71DIm8aEzrXTXXmuxZ083H6ChwQTir38NH39s1p2NxoysadNg8eKECVwA\nq08fArNnw+jRWve5BzTSFd9YscJm0yaHL3yh/QuMdXXw2GPwve91YcmCcNjMHNu40Vwcu/lmqKmB\ndevMBbLu1GyTlK5HdIpGuuJvlZWVbNvmUFICf/iDQ2Vl2yPePn1g1CizCUOnpaSYnttg0FwY27DB\n7OAwa5aZmSGd1mrgHjliPtAaG70/oDijkW4P6VO/51assNmyxcF1z5ORkY7rBrjqqiBLlsCQIa0/\nv9u2wf79JkM7zXXhT3+CnTvhpptMCSBSyyk2NsZfD24klZWZedzl5XDbbaZsk9zUvRAN6rftOdd1\n2bbNYe9ecN10brjhBwwfPpDycrj7bpthwxzmzg3wta81f37z8uD11831sLS0S74RDsMnn8AVV7R8\nsNRUM8nhkUciu7LXzp1mxto990TuPuPN4MFmxt7u3WbVtbw8uOUW3NRUDUouo9Dtpst38C0oKNCL\nqxssy+L66wP0728+vBYvHkhFBZSWuhw65FBTAytXOtTUFDBlikV+vnl/9+9vcvXAAfP+vtBb+9Zb\nYFnwwAMtW71SU7vcL9vhmcy+fWa22f33d/l3TzgpKWZCSW4u/OlP2N/+Ns6wYQTy8zUouYTKCz2g\nkW7ktBZuTc/vhAkBpk8PsmuXGUhlZZmZudXVcL48zMK8PVibNpnOhJtvblofskcLg4fDZpH1kyfb\nmV58+DCsXGlGeFosphnXdSn6l3+5UL5JwvYyzUiLFtV0o+vy57ex0Wx6sGsXbN8OH9vfZ+iwPUxd\nOIfgd79rJjWsXw+nT8M3vtGtlq1jx+C111xWry5i6lQzcG4RGidOwPLlpg9XnQ+tSvJBiUJXEk91\ntcvXcudSOv4mrhmXwq/uuAlr+3azzsGMGV0a6bquS0WFxfr15kL87Nlmbd89e9oIjbfeMq1nEydG\n9pdKMEk8KFHodlcSv2jiwv+afC9V+QPI2FfDwlsXM+X7t9A7u/WdG9r6Wz73nM2rrzr06hXgm98M\nMn26Gd229zMiHVD3Qnck+elRXJh51ee44TuzsbKH8NLW4WxdbdrIsrKa3+6ZZ2wOHGhen62pcdm8\nGZ55xmHYMBg50mH69OYXRBW4EmmaHNGGy7sTtNODP4V7p9H7M1fSZ8xw7rwTpk41qzLu3n3xNq7r\nsmKF6YRo+lv+5jc2S5YUYdtruPvuALm5MGVK56a26rUgPaGRbhuatjNpGulqxOMD1dWmDaxv3wv/\nK9w7jbBbD5hrZtOmmUYC2zYb3s6dC+GwRWZmgH79HIYNC1BYCG++6XDTTZCV5XDffYXAxRHu5SWF\nkNtARWkd5xsH8NJLNqdP6+xHuk813Q6opucDDQ3wwQdm25xFi8wyg5964aGXmfej6xmQ23wyRG0t\nrFljJkjdeCOsX+/S2AhvvmkxezYMHWpTUuIwalQeCxbcTVWVWTzr5ZdtiosdhgwJEAgEKT8XYvRm\nGzIyOHXdF9m0qYixY81jJGEblHSearrdpTdVDIXDsGcPvPGG2bHhwQdb7NxwKH8Rja1s5tC3Lyxd\nahYU+4d/MNOMr7wywIIFQaqqYN++ILt3N/Dee8W8/77NrFlBLMuluNihTx+oq3OY/YXbGbbldfp9\nxqXXPXOgd29ycnT2Iz2j0BV/amiA554zQ9ZFi9pclCYlBWprXdLTWwZgSgqMGeMSDjtce60pJeTm\nFgAWtbUuFRXFzJgBKSkOS5ea8kJKysVQHXvobag6ZXb7/bTJPxgMavah9IjKC+JfBw7A6NHt7tzw\nrW/ZpKc7XH99yxprQ4PZnuz0aZv6+pZ12La6U1zXxfrgA7OewoMPQr9+Ef/VJOGpT1cSj+u63Hln\nEbm5kJHRssb6xz9CZaUpM9TXt16bb7Nmv2mT2fd90KBo/goJL4mviWg9XfGpUMhMAesGy7LIzQ1Q\nV0eLGuvOnVBSAgUFpszQ1hu/zUCYMUOB20O2bVNUVIRt27E+FF9R6EpEdKt39cABeOIJs1ZCKNSt\nx1140zzu+dLfNisPnD4Nr75qRriXdJeJhzrqc0/mXmddSJMes22bXbvaWY3rcqWlZpuc06fNVjkT\nJnR7L7ErTu+k7lw1fOlWwCwutnKludvWltQVb7TX557sMz0Vup2UxLWpdjWNaLZuhZ07Ha64ooDx\n4y1yci7maLPnbtcuWLvW7NywdGm3d25ous9+6WmUHzGTI8Jh+MMfXEaM6OJOwadOmcVxMlpfs0G6\np7VOD61DrdDtlGT/ZG5P04imtvZDhg6dRFmZxfPPm86BYcPgo49sKiocJk0KcO+9QVLHjIG/+zuz\nCnkbOvqAW7nSZvduM7KekTGW2vMu4TA8+qgZcd9zTwDo5N/p3DmzROP8+QrdKLj876iZngrdDumT\nuWNlZXD0qAnawYNNefbMGTh82GXHDof0dDMKLikpYMCA/gwYAAMH0uo/N2ywOXzYYcqUAEuXtgxO\n13V5/XWHc+egttZh9oKx1FXW8+qrLi++6LBoERQXO7huAdDB5JbKStMLPHOmlmj0ULL3Oit0O6BP\n5va5rsuePQ69e6dSWenw+c8X8JnPWKRXHCO1T2/sty8+d3feaVFTY7Kuqqr5Pz/+GMrKXF57zaGy\nEt57z+HYsQJyciwyMkyYm39azJwZ4O23HY4dC3D4+ADKS+t5/nG4++4A4bDDxIkBbHsNe/eaEXar\nZye1tSZwp0wx6++Kp5L5faQ+3U5STbdtzcovc+eaHXcPHjQzycaN69Jz13RfeXkB5swJUlZm1k8o\nL+fCv5eWulRUQFWVxdH3j3Fky+McHWLCOD+/gPp62LixiAkTICenlTUSGhvhmWfgyith3rxuX8QT\naYcmR0h0uRUVWJs3w+bN3dq5odl9tRHSoRD89Kc269Y5NDQEyMkJ0r+/y2uvFdG/v1ldbOHCQrKy\nLI4etSkrc7juugAPPRRsvvlvOIy7axdWfr4CV6JFC95IFIXDWM89Z3q0vvWtHl+QsizrQvBWVsL+\n/WaiQ3GxyzvvmAXHr7zS4Re/KODZZy3C4QDZ2Q47dgQYONDijjtcqqqCHD5cQGmpxW9+Y3aCGDbM\nfO3YsZpDhxwmTdrL0qVBLMs0UVyavzqzkWjRSFcio7q63Y6E1tTVuYRCps5bXQ01NeZr9WqbvXsd\nMjIC5OYGGTMGxo41+z+uW3exlLF4cZAHH3R54AGLWbNcysos7r/fpqHBIRgM8PDDppYbDpvSxIkT\ncOSIy29/W8TevWZJhfnzCxkwwKKxEdLSTDh/8onNgAHqVpEe0UhXoqyLgWvbNs8/7zBgQIBp04L0\n72/CsaTEZd06h1GjYOBAh+98p4C+fS+OOC+98v3UUyacDx0y9d/Bg12mTXM4fRps22HChAKmTYM+\nfSwyMyEzEyZOtKioCLBtm0O/fgEGDbIYMAA++1kYN858EPziFx8CqepWkahQ6ErnVVfD1q1mYkMP\naqFNbXiTJ5tlFZcsWcD27QNxHJgzxyI/P0BJiRlpXhq4TZrKD/v2OWRlwccfmxYxyzI/6zhm1bHl\ny9fw6187FEzqx72PfOPCxmmXBncoZMoXW7bAm29CRcUaDh7cC8DSpUsVuBJxCl3p2KU7N+Tnm/9O\nS+v23V3ahldScp4HHvglN94Y4Ic/bLrgFbwQou3dx+DBATIzHfKvGIr16fE0BSrAwYNFhI6f4I3l\nh7h29kNMntn858GsGjlunPn65BOXf/5nE/aNjY0X7kckkrTgTQ8l9MId4bDZ4fHxx82GYw89BAsX\n9ihwmwSDQX7wgx8wYkQ606dDaqpDWtrF57IzI8wxY4L84z8WEjxzxnwQXPKzlmVxbdZghtcd5PPf\nWMrb24ewerWpGbdl6FCLL34xAMCkSZM0ypWo0Ei3BxJ+evDevfDnP7e7c0NPDBw4kKlTuzfxJBQy\nrcALF1rwpzSor2/+YXDwIMH6egqefBJr9Gjq60378H/8h/l1Ro9uvTsh2WdLRZu6QhS6LXT2RZEU\n04Pz8sxXOzs39FR3Q+74cUhP/3TJ27RPQ7dJRQWsXg3BINbo0fDpTebPN7/Or35lM3hw26uiJdzf\n0ScSfpDSSSovXKIriy431SWh5QLaCaNXr6gGbpPuPHcHDpgWsk/voHnoDhoEX/+62ernMsOHu2Rm\nOqSktL7Oq0RHR+vrJhOF7qe686IIBoMUFhbG96d2KAR//Svs2BHrI+mS4mL3YsUjLc0spHupzMxW\nfy4pPix9SM/7RZoccYmkO/05cABef91M150/36xFEAeeeMLm2WcdHnkkwFe/GoRXXjFTj4cO7fR9\nqLYYG0n0vGvthc5KihfF6dPwxhsR2bnBSydOwNtvu/zwh0WUlsKcOfDkk4UMGZLgfy+JR5qR1lkJ\nH7hgAnf06B7t3OCVcBh27XLZutXi7FnIybFITw+QmuowdWqAZ/5fCnekrubqh28lZbAWIRf/00g3\nGYXDcTGyBfjJT2zeesth8eIAd91VwLJlFvv2QWNjJSuW96P8v1bx/jaLUzfdwfwF9eTkJMGHpsQD\nlRck/riuy49/XMTu3XDqlEPfvuPJyprEsWNQU7ODf1pQR3DKFBqDX+Hn//sFDh92WLAgSerx4ndt\nhq66FxLVsWPw/PNmvYQ4ZVkW118fYPLkRgBKSlLZseNDjh37PY2nX2LVhg24ixfTSCPhsMPIkWpH\nEv/zd0FPuq68/OLODTffDH37xvqIeqRp8sRVV61h9WqHXr0mcnD3NjL71cKIsZCWhlVTQ2DUKJzD\nh5O+HUn8T+WFRFFXB5s2RWTnBj+qrIQHHnDJzobx49dwtnQ7k6ZMMaWEjRuhrg531iwFrviFuhcS\n3rlzZqXuCOzc4Ec1NVBcvIbPfc7hqqsCPPLIP10M2LQ0qKxU4HooKVoro0Q13QiJeR3xiivgjjsS\nMnArK+HZZ10yMhyys7kwc/ACy2o5I02ipivT5aUlhW4EeP4ibL8klFDq62HF8yGuu87iuusC1NW1\nMo308gVvJGo6O10+5oMQH1N5oYc8XW2sqsostQhmXdsEFwrBi08c4foPX2bygw9TVRUkK6uAz3/+\nsudXoeuZSxegb+uiZdJNp+8ijXR7yJOFPBoa4J13zGLiALNnR/4xfOhXP3uadb/9OsV5LilWGhkZ\npjmjhUGDIDvb8+NLVu0t9KTVxDqmkW4ERHXh6z17YN06GDLE7NyQkxP5x/Aht7SU8ndWccUNo9lT\nUf7pm3kNu3Y5VFZeNoIaPtx8iWfaeq13ZiSc7NQy1gbfXJ19912zelYUdm7wrepqWLYM++xZnMZG\nAoEABQUFFBUVXbhJYWGhP/4+0irfvH9iRy1jXeGrmtSNN8b28WPh8GHIyyM4Zw4Fl7x5NYKKH/r7\ntE0j3cu4rhubEVVDg+9X/PIDjaAkTmjthc7yfIX7pp0b/v3f4cyZ6D5WAlDgSrzTSLcNnoyomnZu\n6NsX5s2Lm50bfCccNlvEjx4dN0tWSsJTTberohq458+bLWZOn4a5c2H8+OQOi/Pnzda+3ZWSAsuX\nw6OPqkQjvqdXaCz06WO2so2DnRui7i9/geJi0w7Xkw+epgkSyf58iu+ppuuRZk3iffrA9OkKiK1b\nYcsWCAZ7PtLXrDSJE0n+ro+ycBiqq7HXrvVPC5pfOA5s2AAPPNCz0kITha7ECY10o+XYMVi2DPel\nlzQt8nIlJbB2LdxzT+Sm72qlMYkTCt1IKy+HF16A3/8epk7Fuusub1vQ4kFtLdx1l1mOMlJGjIDU\n1Mjdn0iUqGUskt57z6wCNm2a2bnhkoBVU79IUtFuwJ44csQsIp6AC4mLSJcodCNNI1cRvQ/aockR\nkeSrBXH8rrbWTG/W0oue8SoI9T7oHl1I6yIt0twF9fXwu9/B7t2xPpKk4dXWUXofdJ9Ct4s8XxAn\nXjU2wqpVkJkJc+ZE//HOnYOzZ6P/OD7mZRDqfdB9qul2k2pZ7QiHTduc65qpzl60cr39thlZ33JL\n9B/Lx7w+5df7oE26kCYeevVVOHkS7r3XzBTzwnvvQVkZzJ/vzeP5mILQF3QhLZaS7k2Qlwc33+xd\n4IJ5LNUVAa057HcK3ShLyiu8sdjPTWsvSJzQhbQo0hVeDyl0JU4odKNIV3g9lJ6eNNvTS3zThTQP\nJHRN99Ah0x6WmxvrIxHxE21MGUs9DVzfliWOHwfbhl56GcWSb18f0ipdSPM5316IKy01s80WLYKr\nr4710SQt374+pE0aoviYby/ElZfDc8+ZmWbjx8f6aJKWb18f0i6Fro/58kJcKAQrVsANN8CUKbE+\nmqTmy9eHdEgX0uKA7y7EnTtn1lTwk3AYDhxIygt6vnt9COhCmn915pTQd28ovwVuk+XLTSdFkvHd\n60PapQtpMaSLIBGUkmK2R6qvj6u90jRKTT4K3Ri5/CJIQUGB3nw91TQrrW/fWB9Ju6qrXU6etFi+\n3CYU0oduslF5IUbi4iJIOAxvvAEHD8b6SDonLQ23qirWR9Guxx6zWbSoiH/91xUcOOAQDqvzINlo\npBtDwWAw5iPcdk9vN26E/fth5kxvD6qb7F27cD7+mMD06VEZOfa0FOC6LmfOONxwA6SlFZOXl0dx\ncbF/P3QlKhS6MRbLN1u7NeXNm2H7dnjoId+froMJtLVlGaT36ReVck0k6u+WZTFlSqDZ/aimm3xU\nXkhS7TbW79xpRrn33QcDB3bpPmPFsixGTpzOufOpER85RnISQjAYpLCw8EJwK3CTj0LXx2Kyx1Vt\nLaxfb3Z96EJrmFcbIrbnvvuCzJpVSEFBQUTvN9L1dwVtctPkCJ/yqp2s1dPbhgbo3fnKk+u6FBUV\nXfjvwsLCmARLXR18//s22dkO+fmRf95UCpAu0OSIeOL1rq4tdCFwm+7DD50YKSkuOTkOKSnRed5i\n8XupqyHx6EKaDzWFWNNINx5GV37oxIjH5609mjyTmFRe8DFPTmdDoYRbDzcRygB+KdlIt6m8EI+i\n/iarqYEnn4RTp6L7OB5LhHDyS8lGIk8j3WTluvDsszBqlFkXN6XND2bfS4SRbVsS+XdLcG2+oRS6\nyaihwez6MHiw2fkhjgNXdU/xKZUX5FOhEO6qVdCnD9x2W1wHrnZOkHik0E0y9rJlFP3P/2CHw1G/\ngBbtEFTdU+KRygtJxMsr4l6e9sey7qmaq7RB5QXxbmTo9Wl/rELPD1OfJf4odJPM5QuuREMkwt3v\n9VnVk6W7VF6QqOnuqXe8dCTEy3FKTKhlTOJDvM3EUk1X2qCarsSHeOtI8Pvxif9opCu+pBGkxDmV\nF0REPKTygoiIHyh0RUQ8pNAVEfGQQldExEMKXRERDyl0RUQ8pNAVEfGQQldExEMKXRERDyl0RUQ8\npNAVEfGQQldExEMKXRERDyl0RUQ8pNAVEfGQQldExEMKXRERDyl0RUQ8pNAVEfGQQldExEMKXRER\nDyl0RUQM5qDdAAAAcklEQVQ8pNAVEfGQQldExEMKXRERDyl0RUQ8pNAVEfGQQldExEMKXRERDyl0\nRUQ8pNAVEfGQQldExEMKXRERDyl0RUQ81LuD76d4chQiIklCI10REQ8pdEVEPKTQFRHxkEJXRMRD\nCl0REQ8pdEVEPPT/AUAAQrsYE9ncAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x7f8ccc9d9be0>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "C1, C2, C = sweep_on_x_fast(g, x, top_k=200)[:3]\n",
    "draw_graph(C, use_lcc=False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "def draw_graph(C, layout='pos', show_query=False, r=None, use_lcc=True):\n",
    "    assert layout in {'pos', 'spectral'}\n",
    "    subg = g.subgraph(C)\n",
    "    if use_lcc:\n",
    "        print('use largest CC')\n",
    "        subg = get_lcc(subg)\n",
    "    mapping = {n: i for i, n in enumerate(subg.nodes())}\n",
    "    subg = nx.relabel_nodes(subg, mapping=mapping)\n",
    "\n",
    "    if layout == 'pos':\n",
    "        pos = pos_spring_layout(subg)\n",
    "    else:\n",
    "        pos = signed_layout(subg)\n",
    "\n",
    "    fig, ax = get_borderless_fig()\n",
    "    # draw_nodes(subg, pos, ax=ax)\n",
    "    nx.draw_networkx_nodes(subg, pos, node_size=10, linewidths=0, alpha=0.5, node_color='black')        \n",
    "    if show_query:\n",
    "        nx.draw_networkx_nodes(subg, pos, nodelist=[mapping[r['query']]],\n",
    "                               node_size=80, linewidths=0,\n",
    "                               node_color='green',\n",
    "                               node_shape='s')\n",
    "    draw_edges(subg, pos, ax=ax, width=1.0, alpha=0.5)\n",
    "    return fig, ax"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# try some random seeds"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 169,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.01722530425428839"
      ]
     },
     "execution_count": 169,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lambda1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 170,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "seed 63307\n",
      "matrices loading done\n",
      "using given ub=0.01722530425428839\n",
      "at iteration 5 (alpha=-31280.04581)\n",
      "residual: sqrt(kappa) - y' D s=-0.05131670194948623\n",
      "at iteration 10 (alpha=-977.48474)\n",
      "residual: sqrt(kappa) - y' D s=-0.051316701949335575\n",
      "at iteration 15 (alpha=-30.52971)\n",
      "residual: sqrt(kappa) - y' D s=-0.051316701769011264\n",
      "at iteration 20 (alpha=-0.93737)\n",
      "residual: sqrt(kappa) - y' D s=-0.05131342582102838\n",
      "at iteration 25 (alpha=-0.01261)\n",
      "residual: sqrt(kappa) - y' D s=-0.05124341244772168\n",
      "at iteration 30 (alpha=0.01629)\n",
      "residual: sqrt(kappa) - y' D s=-0.05122700450341555\n",
      "at iteration 35 (alpha=0.01720)\n",
      "residual: sqrt(kappa) - y' D s=-0.051193713867859536\n",
      "at iteration 40 (alpha=0.01722)\n",
      "residual: sqrt(kappa) - y' D s=-0.019268292838795054\n",
      "at iteration 45 (alpha=0.01722)\n",
      "residual: sqrt(kappa) - y' D s=-0.0003985334956906339\n",
      "terminates after 45 iterations:\n",
      "  - alpha=0.01722\n",
      "  - residual=-0.00040\n",
      "seed 74692\n",
      "matrices loading done\n",
      "using given ub=0.01722530425428839\n",
      "at iteration 5 (alpha=-31280.04581)\n",
      "residual: sqrt(kappa) - y' D s=-0.051316701943177834\n",
      "at iteration 10 (alpha=-977.48474)\n",
      "residual: sqrt(kappa) - y' D s=-0.05131669550220119\n",
      "at iteration 15 (alpha=-30.52971)\n",
      "residual: sqrt(kappa) - y' D s=-0.05131048976699182\n",
      "at iteration 20 (alpha=-0.93737)\n",
      "residual: sqrt(kappa) - y' D s=-0.04942352870965616\n",
      "at iteration 25 (alpha=-0.01261)\n",
      "residual: sqrt(kappa) - y' D s=-0.04023845727626352\n",
      "at iteration 30 (alpha=0.01629)\n",
      "residual: sqrt(kappa) - y' D s=-0.03904866329916634\n",
      "at iteration 35 (alpha=0.01720)\n",
      "residual: sqrt(kappa) - y' D s=-0.03898451622428745\n",
      "at iteration 40 (alpha=0.01722)\n",
      "residual: sqrt(kappa) - y' D s=-0.015542917033022463\n",
      "at iteration 45 (alpha=0.01722)\n",
      "residual: sqrt(kappa) - y' D s=-0.001408665465962744\n",
      "terminates after 47 iterations:\n",
      "  - alpha=0.01722\n",
      "  - residual=-0.00069\n",
      "seed 30354\n",
      "matrices loading done\n",
      "using given ub=0.01722530425428839\n",
      "at iteration 5 (alpha=-31280.04581)\n",
      "residual: sqrt(kappa) - y' D s=-0.051316701949474575\n",
      "at iteration 10 (alpha=-977.48474)\n",
      "residual: sqrt(kappa) - y' D s=-0.05131670193764437\n",
      "at iteration 15 (alpha=-30.52971)\n",
      "residual: sqrt(kappa) - y' D s=-0.05131669045482423\n",
      "at iteration 20 (alpha=-0.93737)\n",
      "residual: sqrt(kappa) - y' D s=-0.05130632847438754\n",
      "at iteration 25 (alpha=-0.01261)\n",
      "residual: sqrt(kappa) - y' D s=-0.05113961930552702\n",
      "at iteration 30 (alpha=0.01629)\n",
      "residual: sqrt(kappa) - y' D s=-0.05110426455565964\n",
      "at iteration 35 (alpha=0.01720)\n",
      "residual: sqrt(kappa) - y' D s=-0.05110298290789528\n",
      "at iteration 40 (alpha=0.01722)\n",
      "residual: sqrt(kappa) - y' D s=-0.05110294268746518\n",
      "at iteration 45 (alpha=0.01723)\n",
      "residual: sqrt(kappa) - y' D s=-0.05110294141878857\n",
      "at iteration 50 (alpha=0.01723)\n",
      "residual: sqrt(kappa) - y' D s=-0.05110294137641358\n",
      "at iteration 55 (alpha=0.01723)\n",
      "residual: sqrt(kappa) - y' D s=-0.05110294137412774\n",
      "at iteration 60 (alpha=0.01723)\n",
      "residual: sqrt(kappa) - y' D s=-0.0511029413723223\n",
      "at iteration 65 (alpha=0.01723)\n",
      "residual: sqrt(kappa) - y' D s=-0.05110294139033855\n",
      "at iteration 70 (alpha=0.01723)\n",
      "residual: sqrt(kappa) - y' D s=-0.051102941366693244\n",
      "at iteration 75 (alpha=0.01723)\n",
      "residual: sqrt(kappa) - y' D s=-0.05110294137090854\n",
      "at iteration 80 (alpha=0.01723)\n",
      "residual: sqrt(kappa) - y' D s=-0.05110294138931615\n",
      "at iteration 85 (alpha=0.01723)\n",
      "residual: sqrt(kappa) - y' D s=-0.05110294138931615\n",
      "at iteration 90 (alpha=0.01723)\n",
      "residual: sqrt(kappa) - y' D s=-0.05110294138931615\n",
      "at iteration 95 (alpha=0.01723)\n",
      "residual: sqrt(kappa) - y' D s=-0.05110294138931615\n",
      "at iteration 100 (alpha=0.01723)\n",
      "residual: sqrt(kappa) - y' D s=-0.05110294138931615\n",
      "seed 56383\n",
      "matrices loading done\n",
      "using given ub=0.01722530425428839\n",
      "at iteration 5 (alpha=-31280.04581)\n",
      "residual: sqrt(kappa) - y' D s=-0.05131670194948623\n",
      "at iteration 10 (alpha=-977.48474)\n",
      "residual: sqrt(kappa) - y' D s=-0.05131670194939142\n",
      "at iteration 15 (alpha=-30.52971)\n",
      "residual: sqrt(kappa) - y' D s=-0.0513167018440418\n",
      "at iteration 20 (alpha=-0.93737)\n",
      "residual: sqrt(kappa) - y' D s=-0.051315244256951886\n",
      "at iteration 25 (alpha=-0.01261)\n",
      "residual: sqrt(kappa) - y' D s=-0.051283175276482296\n",
      "at iteration 30 (alpha=0.01629)\n",
      "residual: sqrt(kappa) - y' D s=-0.051275209503856334\n",
      "at iteration 35 (alpha=0.01720)\n",
      "residual: sqrt(kappa) - y' D s=-0.051176885274175965\n",
      "at iteration 40 (alpha=0.01722)\n",
      "residual: sqrt(kappa) - y' D s=0.03633623708885292\n",
      "at iteration 45 (alpha=0.01722)\n",
      "residual: sqrt(kappa) - y' D s=0.00019275426214970803\n",
      "terminates after 46 iterations:\n",
      "  - alpha=0.01722\n",
      "  - residual=-0.00090\n",
      "seed 5545\n",
      "matrices loading done\n",
      "using given ub=0.01722530425428839\n",
      "at iteration 5 (alpha=-31280.04581)\n",
      "residual: sqrt(kappa) - y' D s=-0.051316701949486454\n",
      "at iteration 10 (alpha=-977.48474)\n",
      "residual: sqrt(kappa) - y' D s=-0.051316678837242446\n",
      "at iteration 15 (alpha=-30.52971)\n",
      "residual: sqrt(kappa) - y' D s=-0.05129443178678883\n",
      "at iteration 20 (alpha=-0.93737)\n",
      "residual: sqrt(kappa) - y' D s=-0.044761843938082246\n",
      "at iteration 25 (alpha=-0.01261)\n",
      "residual: sqrt(kappa) - y' D s=-0.01798584688218474\n",
      "at iteration 30 (alpha=0.01629)\n",
      "residual: sqrt(kappa) - y' D s=-0.014764407549523462\n",
      "at iteration 35 (alpha=0.01720)\n",
      "residual: sqrt(kappa) - y' D s=-0.008451225291652764\n",
      "at iteration 40 (alpha=0.01721)\n",
      "residual: sqrt(kappa) - y' D s=-0.0004186315333722934\n",
      "terminates after 40 iterations:\n",
      "  - alpha=0.01721\n",
      "  - residual=-0.00042\n"
     ]
    }
   ],
   "source": [
    "np.random.seed(12345)\n",
    "\n",
    "for seed in np.random.permutation(g.number_of_nodes())[:5]:\n",
    "    print('seed', seed)\n",
    "    x, obj, details = query_graph_using_sparse_linear_solver(\n",
    "        g, [[seed]], kappa=0.9, max_iter=100, verbose=1, return_details=True,\n",
    "        ub=lambda1\n",
    "    )"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# how about other graphs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 195,
   "metadata": {},
   "outputs": [],
   "source": [
    "def try_graph(graph_name):\n",
    "    g = nx.read_gpickle('graphs/{}.pkl'.format(graph_name))\n",
    "    A = nx.adj_matrix(g, weight='sign')\n",
    "\n",
    "    n = g.number_of_nodes()\n",
    "    L = signed_laplacian(g)\n",
    "    Ln = signed_normalized_laplacian(A)\n",
    "    D = degree_diag(g)\n",
    "\n",
    "    l, v = eigs(Ln, k=1, which='SM')  # the smallest eigen value\n",
    "    lambda1 = np.real(l[0])\n",
    "    v1 = np.real(flatten(v))\n",
    "    \n",
    "    np.random.seed(12345)\n",
    "    print('lambda1', lambda1)\n",
    "    for seed in np.random.permutation(g.number_of_nodes())[:5]:\n",
    "        print('seed', seed, 'of degree', g.degree(seed))\n",
    "        x, obj, details = query_graph_using_sparse_linear_solver(\n",
    "            g, [[seed]], kappa=0.9, max_iter=50, verbose=1, return_details=True,\n",
    "            ub=lambda1\n",
    "        )\n",
    "        print('alpha - lambda1={}'.format(details['alpha'] - lambda1))\n",
    "        print()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 192,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "lambda1 0.03980619225546313\n",
      "seed 1584 of degree 2\n",
      "matrices loading done\n",
      "using given ub=0.03980619225546313\n",
      "at iteration 5 (alpha=-1343.02394)\n",
      "residual: sqrt(kappa) - y' D s=-0.05131670187145465\n",
      "at iteration 10 (alpha=-41.93094)\n",
      "residual: sqrt(kappa) - y' D s=-0.05131662525597358\n",
      "at iteration 15 (alpha=-1.27178)\n",
      "residual: sqrt(kappa) - y' D s=-0.051255005035898415\n",
      "at iteration 20 (alpha=-0.00118)\n",
      "residual: sqrt(kappa) - y' D s=-0.048912233738692135\n",
      "at iteration 25 (alpha=0.03853)\n",
      "residual: sqrt(kappa) - y' D s=-0.043995277824330103\n",
      "at iteration 30 (alpha=0.03961)\n",
      "residual: sqrt(kappa) - y' D s=0.011728889128212683\n",
      "terminates after 34 iterations:\n",
      "  - alpha=0.03958\n",
      "  - residual=-0.00040\n",
      "alpha - lambda1=-0.00022765025626655944\n",
      "\n",
      "seed 4042 of degree 2\n",
      "matrices loading done\n",
      "using given ub=0.03980619225546313\n",
      "at iteration 5 (alpha=-1343.02394)\n",
      "residual: sqrt(kappa) - y' D s=-0.0513166985290574\n",
      "at iteration 10 (alpha=-41.93094)\n",
      "residual: sqrt(kappa) - y' D s=-0.05131334863998693\n",
      "at iteration 15 (alpha=-1.27178)\n",
      "residual: sqrt(kappa) - y' D s=-0.04999180188416541\n",
      "at iteration 20 (alpha=-0.00118)\n",
      "residual: sqrt(kappa) - y' D s=-0.038470117592597775\n",
      "at iteration 25 (alpha=0.03853)\n",
      "residual: sqrt(kappa) - y' D s=-0.03159775477544102\n",
      "at iteration 30 (alpha=0.03961)\n",
      "residual: sqrt(kappa) - y' D s=-0.007565947890234903\n",
      "terminates after 33 iterations:\n",
      "  - alpha=0.03963\n",
      "  - residual=-0.00045\n",
      "alpha - lambda1=-0.000175115581743511\n",
      "\n",
      "seed 3231 of degree 8\n",
      "matrices loading done\n",
      "using given ub=0.03980619225546313\n",
      "at iteration 5 (alpha=-1343.02394)\n",
      "residual: sqrt(kappa) - y' D s=-0.05131667712531707\n",
      "at iteration 10 (alpha=-41.93094)\n",
      "residual: sqrt(kappa) - y' D s=-0.05129214683631067\n",
      "at iteration 15 (alpha=-1.27178)\n",
      "residual: sqrt(kappa) - y' D s=-0.04136489878973937\n",
      "terminates after 18 iterations:\n",
      "  - alpha=-0.12414\n",
      "  - residual=-0.00025\n",
      "alpha - lambda1=-0.16394821093060402\n",
      "\n",
      "seed 1570 of degree 2\n",
      "matrices loading done\n",
      "using given ub=0.03980619225546313\n",
      "at iteration 5 (alpha=-1343.02394)\n",
      "residual: sqrt(kappa) - y' D s=-0.0513167019229438\n",
      "at iteration 10 (alpha=-41.93094)\n",
      "residual: sqrt(kappa) - y' D s=-0.05131667578569443\n",
      "at iteration 15 (alpha=-1.27178)\n",
      "residual: sqrt(kappa) - y' D s=-0.05128072113624749\n",
      "at iteration 20 (alpha=-0.00118)\n",
      "residual: sqrt(kappa) - y' D s=-0.049232332997965145\n",
      "at iteration 25 (alpha=0.03853)\n",
      "residual: sqrt(kappa) - y' D s=-0.04487287629396597\n",
      "at iteration 30 (alpha=0.03961)\n",
      "residual: sqrt(kappa) - y' D s=-0.0010136169177460408\n",
      "at iteration 35 (alpha=0.03961)\n",
      "residual: sqrt(kappa) - y' D s=-0.0004843222954629134\n",
      "terminates after 35 iterations:\n",
      "  - alpha=0.03961\n",
      "  - residual=-0.00048\n",
      "alpha - lambda1=-0.00019888126783727117\n",
      "\n",
      "seed 3776 of degree 1\n",
      "matrices loading done\n",
      "using given ub=0.03980619225546313\n",
      "at iteration 5 (alpha=-1343.02394)\n",
      "residual: sqrt(kappa) - y' D s=-0.05131670193407112\n",
      "at iteration 10 (alpha=-41.93094)\n",
      "residual: sqrt(kappa) - y' D s=-0.0513166866858743\n",
      "at iteration 15 (alpha=-1.27178)\n",
      "residual: sqrt(kappa) - y' D s=-0.051287701330632984\n",
      "at iteration 20 (alpha=-0.00118)\n",
      "residual: sqrt(kappa) - y' D s=-0.04983741357101401\n",
      "at iteration 25 (alpha=0.03853)\n",
      "residual: sqrt(kappa) - y' D s=-0.04816549683026217\n",
      "at iteration 30 (alpha=0.03969)\n",
      "residual: sqrt(kappa) - y' D s=-0.012453047379041071\n",
      "terminates after 34 iterations:\n",
      "  - alpha=0.03970\n",
      "  - residual=-0.00005\n",
      "alpha - lambda1=-0.0001025676978783363\n",
      "\n"
     ]
    }
   ],
   "source": [
    "try_graph('bitcoin')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 193,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "lambda1 0.029549341418420864\n",
      "seed 727 of degree 9\n",
      "matrices loading done\n",
      "using given ub=0.029549341418420864\n",
      "at iteration 5 (alpha=-2942.97137)\n",
      "residual: sqrt(kappa) - y' D s=-0.05131669930146898\n",
      "at iteration 10 (alpha=-91.93923)\n",
      "residual: sqrt(kappa) - y' D s=-0.051313927809822024\n",
      "at iteration 15 (alpha=-2.84447)\n",
      "residual: sqrt(kappa) - y' D s=-0.04944951499537076\n",
      "at iteration 20 (alpha=-0.59914)\n",
      "residual: sqrt(kappa) - y' D s=0.23081931508867948\n",
      "at iteration 25 (alpha=-0.65808)\n",
      "residual: sqrt(kappa) - y' D s=-0.0011562287376739588\n",
      "terminates after 27 iterations:\n",
      "  - alpha=-0.65738\n",
      "  - residual=-0.00053\n",
      "alpha - lambda1=-0.6869311103880797\n",
      "\n",
      "seed 3173 of degree 14\n",
      "matrices loading done\n",
      "using given ub=0.029549341418420864\n",
      "at iteration 5 (alpha=-2942.97137)\n",
      "residual: sqrt(kappa) - y' D s=-0.05131668583523785\n",
      "at iteration 10 (alpha=-91.93923)\n",
      "residual: sqrt(kappa) - y' D s=-0.05130029450301632\n",
      "at iteration 15 (alpha=-2.84447)\n",
      "residual: sqrt(kappa) - y' D s=-0.035972402002927284\n",
      "at iteration 20 (alpha=-1.49728)\n",
      "residual: sqrt(kappa) - y' D s=0.0049805034608562115\n",
      "terminates after 23 iterations:\n",
      "  - alpha=-1.57586\n",
      "  - residual=-0.00067\n",
      "alpha - lambda1=-1.6054120332665236\n",
      "\n",
      "seed 4756 of degree 2\n",
      "matrices loading done\n",
      "using given ub=0.029549341418420864\n",
      "at iteration 5 (alpha=-2942.97137)\n",
      "residual: sqrt(kappa) - y' D s=-0.05131669908646108\n",
      "at iteration 10 (alpha=-91.93923)\n",
      "residual: sqrt(kappa) - y' D s=-0.05131381980598515\n",
      "at iteration 15 (alpha=-2.84447)\n",
      "residual: sqrt(kappa) - y' D s=-0.0494119123365484\n",
      "at iteration 20 (alpha=-0.23989)\n",
      "residual: sqrt(kappa) - y' D s=-0.013216582588110315\n",
      "at iteration 25 (alpha=-0.20902)\n",
      "residual: sqrt(kappa) - y' D s=-0.0005405124756318047\n",
      "terminates after 25 iterations:\n",
      "  - alpha=-0.20902\n",
      "  - residual=-0.00054\n",
      "alpha - lambda1=-0.23856647347492038\n",
      "\n",
      "seed 1745 of degree 7\n",
      "matrices loading done\n",
      "using given ub=0.029549341418420864\n",
      "at iteration 5 (alpha=-2942.97137)\n",
      "residual: sqrt(kappa) - y' D s=-0.05131669381444459\n",
      "at iteration 10 (alpha=-91.93923)\n",
      "residual: sqrt(kappa) - y' D s=-0.0513084808223333\n",
      "at iteration 15 (alpha=-2.84447)\n",
      "residual: sqrt(kappa) - y' D s=-0.045874525422331836\n",
      "at iteration 20 (alpha=-0.59914)\n",
      "residual: sqrt(kappa) - y' D s=0.025877595831648503\n",
      "terminates after 24 iterations:\n",
      "  - alpha=-0.66089\n",
      "  - residual=-0.00052\n",
      "alpha - lambda1=-0.690439440880358\n",
      "\n",
      "seed 2706 of degree 18\n",
      "matrices loading done\n",
      "using given ub=0.029549341418420864\n",
      "at iteration 5 (alpha=-2942.97137)\n",
      "residual: sqrt(kappa) - y' D s=-0.051316654711694\n",
      "at iteration 10 (alpha=-91.93923)\n",
      "residual: sqrt(kappa) - y' D s=-0.05126892540630623\n",
      "at iteration 15 (alpha=-2.84447)\n",
      "residual: sqrt(kappa) - y' D s=-0.019016651482715252\n",
      "terminates after 17 iterations:\n",
      "  - alpha=-2.12597\n",
      "  - residual=-0.00068\n",
      "alpha - lambda1=-2.155518254455752\n",
      "\n"
     ]
    }
   ],
   "source": [
    "try_graph('word')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 196,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "lambda1 0.0172253042542885\n",
      "seed 63307 of degree 1\n",
      "matrices loading done\n",
      "using given ub=0.0172253042542885\n",
      "at iteration 5 (alpha=-31280.04581)\n",
      "residual: sqrt(kappa) - y' D s=-0.05131670194948623\n",
      "at iteration 10 (alpha=-977.48474)\n",
      "residual: sqrt(kappa) - y' D s=-0.051316701949335575\n",
      "at iteration 15 (alpha=-30.52971)\n",
      "residual: sqrt(kappa) - y' D s=-0.051316701769011264\n",
      "at iteration 20 (alpha=-0.93737)\n",
      "residual: sqrt(kappa) - y' D s=-0.05131342582298282\n",
      "at iteration 25 (alpha=-0.01261)\n",
      "residual: sqrt(kappa) - y' D s=-0.0512434124340434\n",
      "at iteration 30 (alpha=0.01629)\n",
      "residual: sqrt(kappa) - y' D s=-0.051227004212562544\n",
      "at iteration 35 (alpha=0.01720)\n",
      "residual: sqrt(kappa) - y' D s=-0.05119370996868078\n",
      "at iteration 40 (alpha=0.01722)\n",
      "residual: sqrt(kappa) - y' D s=-0.0192685125205313\n",
      "at iteration 45 (alpha=0.01722)\n",
      "residual: sqrt(kappa) - y' D s=-0.0003985621098649972\n",
      "terminates after 45 iterations:\n",
      "  - alpha=0.01722\n",
      "  - residual=-0.00040\n",
      "alpha - lambda1=-7.112262901086408e-07\n",
      "\n",
      "seed 74692 of degree 1\n",
      "matrices loading done\n",
      "using given ub=0.0172253042542885\n",
      "at iteration 5 (alpha=-31280.04581)\n",
      "residual: sqrt(kappa) - y' D s=-0.051316701943177834\n",
      "at iteration 10 (alpha=-977.48474)\n",
      "residual: sqrt(kappa) - y' D s=-0.05131669550220119\n",
      "at iteration 15 (alpha=-30.52971)\n",
      "residual: sqrt(kappa) - y' D s=-0.05131048976699182\n",
      "at iteration 20 (alpha=-0.93737)\n",
      "residual: sqrt(kappa) - y' D s=-0.0494235287096505\n",
      "at iteration 25 (alpha=-0.01261)\n",
      "residual: sqrt(kappa) - y' D s=-0.04023845725888997\n",
      "at iteration 30 (alpha=0.01629)\n",
      "residual: sqrt(kappa) - y' D s=-0.039048663200731526\n",
      "at iteration 35 (alpha=0.01720)\n",
      "residual: sqrt(kappa) - y' D s=-0.03898454899480519\n",
      "at iteration 40 (alpha=0.01722)\n",
      "residual: sqrt(kappa) - y' D s=-0.015542590271727552\n",
      "at iteration 45 (alpha=0.01722)\n",
      "residual: sqrt(kappa) - y' D s=-0.0014088030007605168\n",
      "terminates after 47 iterations:\n",
      "  - alpha=0.01722\n",
      "  - residual=-0.00069\n",
      "alpha - lambda1=-7.041140272084911e-07\n",
      "\n",
      "seed 30354 of degree 1\n",
      "matrices loading done\n",
      "using given ub=0.0172253042542885\n",
      "at iteration 5 (alpha=-31280.04581)\n",
      "residual: sqrt(kappa) - y' D s=-0.051316701949474575\n",
      "at iteration 10 (alpha=-977.48474)\n",
      "residual: sqrt(kappa) - y' D s=-0.05131670193764437\n",
      "at iteration 15 (alpha=-30.52971)\n",
      "residual: sqrt(kappa) - y' D s=-0.05131669045482423\n",
      "at iteration 20 (alpha=-0.93737)\n",
      "residual: sqrt(kappa) - y' D s=-0.051306328474456375\n",
      "at iteration 25 (alpha=-0.01261)\n",
      "residual: sqrt(kappa) - y' D s=-0.051139619314808704\n",
      "at iteration 30 (alpha=0.01629)\n",
      "residual: sqrt(kappa) - y' D s=-0.051104264554568735\n",
      "at iteration 35 (alpha=0.01720)\n",
      "residual: sqrt(kappa) - y' D s=-0.05110298294232685\n",
      "at iteration 40 (alpha=0.01722)\n",
      "residual: sqrt(kappa) - y' D s=-0.0511029426893449\n",
      "at iteration 45 (alpha=0.01723)\n",
      "residual: sqrt(kappa) - y' D s=-0.051102941425076875\n",
      "at iteration 50 (alpha=0.01723)\n",
      "residual: sqrt(kappa) - y' D s=-0.051102941372348054\n",
      "alpha - lambda1=-4.4451643407827923e-10\n",
      "\n",
      "seed 56383 of degree 1\n",
      "matrices loading done\n",
      "using given ub=0.0172253042542885\n",
      "at iteration 5 (alpha=-31280.04581)\n",
      "residual: sqrt(kappa) - y' D s=-0.05131670194948623\n",
      "at iteration 10 (alpha=-977.48474)\n",
      "residual: sqrt(kappa) - y' D s=-0.05131670194939142\n",
      "at iteration 15 (alpha=-30.52971)\n",
      "residual: sqrt(kappa) - y' D s=-0.0513167018440418\n",
      "at iteration 20 (alpha=-0.93737)\n",
      "residual: sqrt(kappa) - y' D s=-0.051315244255725756\n",
      "at iteration 25 (alpha=-0.01261)\n",
      "residual: sqrt(kappa) - y' D s=-0.05128317527493442\n",
      "at iteration 30 (alpha=0.01629)\n",
      "residual: sqrt(kappa) - y' D s=-0.051275209172799374\n",
      "at iteration 35 (alpha=0.01720)\n",
      "residual: sqrt(kappa) - y' D s=-0.051176872842158216\n",
      "at iteration 40 (alpha=0.01722)\n",
      "residual: sqrt(kappa) - y' D s=0.03633672572237667\n",
      "at iteration 45 (alpha=0.01722)\n",
      "residual: sqrt(kappa) - y' D s=0.00019283626557353717\n",
      "terminates after 46 iterations:\n",
      "  - alpha=0.01722\n",
      "  - residual=-0.00090\n",
      "alpha - lambda1=-1.2375337447960433e-06\n",
      "\n",
      "seed 5545 of degree 12\n",
      "matrices loading done\n",
      "using given ub=0.0172253042542885\n",
      "at iteration 5 (alpha=-31280.04581)\n",
      "residual: sqrt(kappa) - y' D s=-0.051316701949486454\n",
      "at iteration 10 (alpha=-977.48474)\n",
      "residual: sqrt(kappa) - y' D s=-0.051316678837242446\n",
      "at iteration 15 (alpha=-30.52971)\n",
      "residual: sqrt(kappa) - y' D s=-0.05129443178678883\n",
      "at iteration 20 (alpha=-0.93737)\n",
      "residual: sqrt(kappa) - y' D s=-0.04476184357510127\n",
      "at iteration 25 (alpha=-0.01261)\n",
      "residual: sqrt(kappa) - y' D s=-0.017985847126307575\n",
      "at iteration 30 (alpha=0.01629)\n",
      "residual: sqrt(kappa) - y' D s=-0.014764456058626974\n",
      "at iteration 35 (alpha=0.01720)\n",
      "residual: sqrt(kappa) - y' D s=-0.008450448769971586\n",
      "at iteration 40 (alpha=0.01721)\n",
      "residual: sqrt(kappa) - y' D s=-0.0004179547208401635\n",
      "terminates after 40 iterations:\n",
      "  - alpha=0.01721\n",
      "  - residual=-0.00042\n",
      "alpha - lambda1=-1.9117762678193956e-05\n",
      "\n"
     ]
    }
   ],
   "source": [
    "try_graph('slashdot')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 198,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "lambda1 0.011227776937344317\n",
      "seed 93647 of degree 1\n",
      "matrices loading done\n",
      "using given ub=0.011227776937344317\n",
      "at iteration 5 (alpha=-44016.67662)\n",
      "residual: sqrt(kappa) - y' D s=-0.05131670194816962\n",
      "at iteration 10 (alpha=-1375.51027)\n",
      "residual: sqrt(kappa) - y' D s=-0.051316700603145304\n",
      "at iteration 15 (alpha=-42.97382)\n",
      "residual: sqrt(kappa) - y' D s=-0.05131537849977341\n",
      "at iteration 20 (alpha=-1.33205)\n",
      "residual: sqrt(kappa) - y' D s=-0.05021506278186849\n",
      "at iteration 25 (alpha=-0.03075)\n",
      "residual: sqrt(kappa) - y' D s=-0.0010748522895934753\n",
      "terminates after 29 iterations:\n",
      "  - alpha=-0.02813\n",
      "  - residual=-0.00010\n",
      "alpha - lambda1=-0.039353985653103614\n",
      "\n",
      "seed 18084 of degree 30\n",
      "matrices loading done\n",
      "using given ub=0.011227776937344317\n",
      "at iteration 5 (alpha=-44016.67662)\n",
      "residual: sqrt(kappa) - y' D s=-0.05131670194948601\n",
      "at iteration 10 (alpha=-1375.51027)\n",
      "residual: sqrt(kappa) - y' D s=-0.051316360829535945\n",
      "at iteration 15 (alpha=-42.97382)\n",
      "residual: sqrt(kappa) - y' D s=-0.050982485699054836\n",
      "at iteration 20 (alpha=-1.33205)\n",
      "residual: sqrt(kappa) - y' D s=0.05047801383369843\n",
      "terminates after 24 iterations:\n",
      "  - alpha=-2.42347\n",
      "  - residual=-0.00018\n",
      "alpha - lambda1=-2.4346999124053434\n",
      "\n",
      "seed 48822 of degree 6\n",
      "matrices loading done\n",
      "using given ub=0.011227776937344317\n",
      "at iteration 5 (alpha=-44016.67662)\n",
      "residual: sqrt(kappa) - y' D s=-0.051316701949486454\n",
      "at iteration 10 (alpha=-1375.51027)\n",
      "residual: sqrt(kappa) - y' D s=-0.051316701882916704\n",
      "at iteration 15 (alpha=-42.97382)\n",
      "residual: sqrt(kappa) - y' D s=-0.05131663661072361\n",
      "at iteration 20 (alpha=-1.33205)\n",
      "residual: sqrt(kappa) - y' D s=-0.05128311240278283\n",
      "at iteration 25 (alpha=-0.03075)\n",
      "residual: sqrt(kappa) - y' D s=-0.05063736873907709\n",
      "at iteration 30 (alpha=0.00992)\n",
      "residual: sqrt(kappa) - y' D s=-0.05026245802485274\n",
      "at iteration 35 (alpha=0.01119)\n",
      "residual: sqrt(kappa) - y' D s=-0.049933898214503225\n",
      "at iteration 40 (alpha=0.01122)\n",
      "residual: sqrt(kappa) - y' D s=-0.016552405246339386\n",
      "terminates after 44 iterations:\n",
      "  - alpha=0.01122\n",
      "  - residual=-0.00047\n",
      "alpha - lambda1=-3.122569662417432e-06\n",
      "\n",
      "seed 61918 of degree 1\n",
      "matrices loading done\n",
      "using given ub=0.011227776937344317\n",
      "at iteration 5 (alpha=-44016.67662)\n",
      "residual: sqrt(kappa) - y' D s=-0.0513167019494537\n",
      "at iteration 10 (alpha=-1375.51027)\n",
      "residual: sqrt(kappa) - y' D s=-0.05131670191617199\n",
      "at iteration 15 (alpha=-42.97382)\n",
      "residual: sqrt(kappa) - y' D s=-0.051316669182831065\n",
      "at iteration 20 (alpha=-1.33205)\n",
      "residual: sqrt(kappa) - y' D s=-0.051287840339353075\n",
      "at iteration 25 (alpha=-0.03075)\n",
      "residual: sqrt(kappa) - y' D s=-0.05057040421442183\n",
      "at iteration 30 (alpha=0.00992)\n",
      "residual: sqrt(kappa) - y' D s=-0.05037816396309325\n",
      "at iteration 35 (alpha=0.01119)\n",
      "residual: sqrt(kappa) - y' D s=-0.05035550451620063\n",
      "at iteration 40 (alpha=0.01123)\n",
      "residual: sqrt(kappa) - y' D s=-0.03483355709183855\n",
      "at iteration 45 (alpha=0.01123)\n",
      "residual: sqrt(kappa) - y' D s=0.0016349624113730643\n",
      "terminates after 48 iterations:\n",
      "  - alpha=0.01123\n",
      "  - residual=-0.00042\n",
      "alpha - lambda1=-6.955724087751025e-07\n",
      "\n",
      "seed 49423 of degree 3\n",
      "matrices loading done\n",
      "using given ub=0.011227776937344317\n",
      "at iteration 5 (alpha=-44016.67662)\n",
      "residual: sqrt(kappa) - y' D s=-0.05131670194948623\n",
      "at iteration 10 (alpha=-1375.51027)\n",
      "residual: sqrt(kappa) - y' D s=-0.05131670194929372\n",
      "at iteration 15 (alpha=-42.97382)\n",
      "residual: sqrt(kappa) - y' D s=-0.05131670175487324\n",
      "at iteration 20 (alpha=-1.33205)\n",
      "residual: sqrt(kappa) - y' D s=-0.05131511355150564\n",
      "at iteration 25 (alpha=-0.03075)\n",
      "residual: sqrt(kappa) - y' D s=-0.05118894266339191\n",
      "at iteration 30 (alpha=0.00992)\n",
      "residual: sqrt(kappa) - y' D s=-0.05110120988545963\n",
      "at iteration 35 (alpha=0.01119)\n",
      "residual: sqrt(kappa) - y' D s=-0.0509942849133318\n",
      "at iteration 40 (alpha=0.01123)\n",
      "residual: sqrt(kappa) - y' D s=0.04067097629386618\n",
      "at iteration 45 (alpha=0.01123)\n",
      "residual: sqrt(kappa) - y' D s=-0.0013950894477837705\n",
      "terminates after 46 iterations:\n",
      "  - alpha=0.01123\n",
      "  - residual=-0.00036\n",
      "alpha - lambda1=-1.7814660253547693e-06\n",
      "\n"
     ]
    }
   ],
   "source": [
    "try_graph('epinions')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# guess: low degree nodes tend to have $\\alpha \\approx \\lambda_1$\n",
    "\n",
    "intuition: \n",
    "\n",
    "- if a node's degree is 1, it's \"similar\" to a singleton node.\n",
    "- for querying on a singleton node $q$, the following solution $x^{'}$ achieves objective close to $\\lambda_1$:\n",
    "  - putting high value to $x^{'}(q)$ (to satisfy the correlation constraint) and this part does not increase the objective because of no incident edges to $q$\n",
    "  - for the values on the rest of $x^{'}$, make it similar to $v_1$\n",
    "- **I assume** the closer $x^{'}$ is to $v_1$, the closer $\\alpha$ is to $\\lambda_1$\n",
    "- if $\\alpha  \\approx \\lambda_1$ (empirically observed), $\\beta$ tends to 0 (due to Case 1 in the proof of Claim 4), therefore the correlation constraint does not need to tight\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 215,
   "metadata": {
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "\n",
    "def degree_experiment_on_graph(graph_name):\n",
    "    g = nx.read_gpickle('graphs/{}.pkl'.format(graph_name))\n",
    "    A = nx.adj_matrix(g, weight='sign')\n",
    "\n",
    "    n = g.number_of_nodes()\n",
    "    L = signed_laplacian(g)\n",
    "    Ln = signed_normalized_laplacian(A)\n",
    "    D = degree_diag(g)\n",
    "\n",
    "    deg = D.diagonal()\n",
    "    low_degree_nodes = list(map(int, np.argsort(deg)[:5]))\n",
    "    high_degree_nodes = list(map(int, np.argsort(deg)[-5:]))\n",
    "\n",
    "    l, v = eigs(Ln, k=1, which='SM')  # the smallest eigen value\n",
    "    lambda1 = np.real(l[0])\n",
    "    v1 = np.real(flatten(v))\n",
    "\n",
    "    print('lambda1', lambda1)\n",
    "\n",
    "    print('-------high degree nodes-------')\n",
    "    for seed in high_degree_nodes:\n",
    "        print('seed', seed, 'of degree', g.degree(seed))\n",
    "        x, obj, details = query_graph_using_sparse_linear_solver(\n",
    "            g, [[seed]], kappa=0.9, max_iter=50, verbose=0, return_details=True,\n",
    "            ub=lambda1\n",
    "        )\n",
    "        print(details)\n",
    "        print('alpha - lambda1={}'.format(details['alpha'] - lambda1))\n",
    "        print()    \n",
    "\n",
    "\n",
    "    print('-------low degree nodes-------')\n",
    "    for seed in low_degree_nodes:\n",
    "        print('seed', seed, 'of degree', g.degree(seed))\n",
    "        x, obj, details = query_graph_using_sparse_linear_solver(\n",
    "            g, [[seed]], kappa=0.9, max_iter=50, verbose=0, return_details=True,\n",
    "            ub=lambda1\n",
    "        )\n",
    "        print(details)\n",
    "        print('alpha - lambda1={}'.format(details['alpha'] - lambda1))\n",
    "        print()\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 216,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "lambda1 0.03980619225546311\n",
      "-------high degree nodes-------\n",
      "seed 1980 of degree 326\n",
      "{'converged': True, 'ub': -18.978186275694604, 'alpha': -19.306082697555812, 'lb': -19.63397911941702, 'gap': -0.0008234565842575314, 'n_iters': 17}\n",
      "alpha - lambda1=-19.345888889811274\n",
      "\n",
      "seed 2071 of degree 436\n",
      "{'converged': True, 'ub': -33.40562883758775, 'alpha': -33.73352525944895, 'lb': -34.061421681310165, 'gap': -0.0005347017948809096, 'n_iters': 17}\n",
      "alpha - lambda1=-33.773331451704415\n",
      "\n",
      "seed 2571 of degree 438\n",
      "{'converged': True, 'ub': -24.880321869196344, 'alpha': -25.208218291057552, 'lb': -25.53611471291876, 'gap': -0.00028132602556962816, 'n_iters': 17}\n",
      "alpha - lambda1=-25.248024483313014\n",
      "\n",
      "seed 1785 of degree 439\n",
      "{'converged': True, 'ub': -20.289771963139437, 'alpha': -20.61766838500064, 'lb': -20.94556480686185, 'gap': -0.00040047829767742016, 'n_iters': 17}\n",
      "alpha - lambda1=-20.657474577256103\n",
      "\n",
      "seed 23 of degree 795\n",
      "{'converged': True, 'ub': -53.735206992982654, 'alpha': -54.39099983670507, 'lb': -55.04679268042749, 'gap': -6.604674395316312e-05, 'n_iters': 16}\n",
      "alpha - lambda1=-54.43080602896053\n",
      "\n",
      "-------low degree nodes-------\n",
      "seed 2937 of degree 1\n",
      "{'converged': True, 'ub': 0.039661096487732785, 'alpha': 0.03965859483656502, 'lb': 0.039656093185397256, 'gap': -0.0006534691023089012, 'n_iters': 34}\n",
      "alpha - lambda1=-0.00014759741889809608\n",
      "\n",
      "seed 3355 of degree 1\n",
      "{'converged': True, 'ub': 0.039716132813423594, 'alpha': 0.03971488198783971, 'lb': 0.03971363116225583, 'gap': -0.0006630682090351669, 'n_iters': 35}\n",
      "alpha - lambda1=-9.131026762339983e-05\n",
      "\n",
      "seed 3359 of degree 1\n",
      "{'converged': True, 'ub': 0.0397086278599203, 'alpha': 0.03970737703433642, 'lb': 0.03970612620875254, 'gap': -0.0003339767106157465, 'n_iters': 35}\n",
      "alpha - lambda1=-9.881522112669544e-05\n",
      "\n",
      "seed 3360 of degree 1\n",
      "{'converged': True, 'ub': 0.0397086278599203, 'alpha': 0.03970737703433642, 'lb': 0.03970612620875254, 'gap': -0.00042275738362684834, 'n_iters': 35}\n",
      "alpha - lambda1=-9.881522112669544e-05\n",
      "\n",
      "seed 3361 of degree 1\n",
      "{'converged': True, 'ub': 0.03972113611575912, 'alpha': 0.039718634464591354, 'lb': 0.039716132813423594, 'gap': -2.7725563649716456e-05, 'n_iters': 34}\n",
      "alpha - lambda1=-8.755779087175897e-05\n",
      "\n"
     ]
    }
   ],
   "source": [
    "degree_experiment_on_graph('bitcoin')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 217,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "lambda1 0.01722530425428827\n",
      "-------high degree nodes-------\n",
      "seed 31 of degree 1727\n",
      "{'converged': True, 'ub': -21.46108946507988, 'alpha': -21.699737406961372, 'lb': -21.938385348842864, 'gap': -0.0004753992612250846, 'n_iters': 22}\n",
      "alpha - lambda1=-21.71696271121566\n",
      "\n",
      "seed 135 of degree 1861\n",
      "{'converged': True, 'ub': -48.66695483956983, 'alpha': -49.14425072333282, 'lb': -49.621546607095794, 'gap': -0.0007908123394283484, 'n_iters': 21}\n",
      "alpha - lambda1=-49.161476027587106\n",
      "\n",
      "seed 60 of degree 2290\n",
      "{'converged': True, 'ub': -13.347059441109195, 'alpha': -13.824355324872176, 'lb': -14.301651208635157, 'gap': -0.0009490402623595351, 'n_iters': 21}\n",
      "alpha - lambda1=-13.841580629126465\n",
      "\n",
      "seed 122 of degree 2347\n",
      "{'converged': True, 'ub': -41.030220699362125, 'alpha': -41.50751658312511, 'lb': -41.98481246688809, 'gap': -0.0007756493546826615, 'n_iters': 21}\n",
      "alpha - lambda1=-41.5247418873794\n",
      "\n",
      "seed 132 of degree 2548\n",
      "{'converged': True, 'ub': -42.93940423441405, 'alpha': -43.41670011817703, 'lb': -43.89399600194001, 'gap': -0.0009914852314505396, 'n_iters': 21}\n",
      "alpha - lambda1=-43.43392542243132\n",
      "\n",
      "-------low degree nodes-------\n",
      "seed 61090 of degree 1\n",
      "{'converged': False, 'ub': 0.01722530425428827, 'alpha': 0.017225303809771837, 'lb': 0.017225303809771837, 'gap': -0.049161848326704005, 'n_iters': 51}\n",
      "alpha - lambda1=-4.4451643407827923e-10\n",
      "\n",
      "seed 58900 of degree 1\n",
      "{'converged': True, 'ub': 0.017224422333688535, 'alpha': 0.01722440810916273, 'lb': 0.01722439388463693, 'gap': -0.00014421286090482432, 'n_iters': 46}\n",
      "alpha - lambda1=-8.961451255402875e-07\n",
      "\n",
      "seed 28625 of degree 1\n",
      "{'converged': False, 'ub': 0.01722530425428827, 'alpha': 0.017225303809771837, 'lb': 0.017225303809771837, 'gap': -0.05103813457530082, 'n_iters': 51}\n",
      "alpha - lambda1=-4.4451643407827923e-10\n",
      "\n",
      "seed 58902 of degree 1\n",
      "{'converged': True, 'ub': 0.017224422333688535, 'alpha': 0.01722440810916273, 'lb': 0.01722439388463693, 'gap': -0.00014420843406626194, 'n_iters': 46}\n",
      "alpha - lambda1=-8.961451255402875e-07\n",
      "\n",
      "seed 58904 of degree 1\n",
      "{'converged': True, 'ub': 0.017224422333688535, 'alpha': 0.01722440810916273, 'lb': 0.01722439388463693, 'gap': -0.00014471723447573304, 'n_iters': 46}\n",
      "alpha - lambda1=-8.961451255402875e-07\n",
      "\n"
     ]
    }
   ],
   "source": [
    "degree_experiment_on_graph('slashdot')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# explaining why $\\alpha \\approx \\lambda_1$ by checking $(Ds)(Ds)^T$\n",
    "\n",
    "we compare two seeds, one with degree 1 and the other with degree max and show their corresponding $(Ds)(Ds)^T$\n",
    "\n",
    "- we found that for large degree nodes, its non-zero entry in $(Ds)(Ds)^T$ is much larger (actually, equal to its degree)\n",
    "\n",
    "\n",
    "Recall that due to complementary slackness and rank-1 result, we need to solve this problem:\n",
    "\n",
    "$x (L_G - \\alpha D - \\beta (Ds)(Ds)^T) = 0$\n",
    "\n",
    "If $(Ds)(Ds)^T$ is insignificant and $\\beta$ is small, the last subtracting term can be ignored. \n",
    "\n",
    "And the problem becomes approximately: \n",
    "\n",
    "$x (L_G - \\alpha D) \\approx 0$ (reminding me of the charactertic polynomial and generalized eigen-problem)\n",
    "\n",
    "which gives $\\alpha \\approx \\lambda_1$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 266,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "seed 1 degree 1\n",
      "seed 2 degree 2548\n"
     ]
    }
   ],
   "source": [
    "seed1 = 49309\n",
    "print('seed 1 degree', g.degree(seed1))\n",
    "seed2 = 132\n",
    "print('seed 2 degree', g.degree(seed2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 269,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "non-zero entry of s1: 1.0\n",
      "non-zero entry of s2: 0.019810721293758184\n"
     ]
    }
   ],
   "source": [
    "s1 = prepare_seed_vector_sparse([[seed1]], D)\n",
    "s2 = prepare_seed_vector_sparse([[seed2]], D)\n",
    "print('non-zero entry of s1:', s1.data[0])\n",
    "print('non-zero entry of s2:', s2.data[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 270,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "nonzero entry of Ds1 (Ds1).T:  1.0\n",
      "nonzero entry of Ds2 (Ds2).T:  2548.0\n"
     ]
    }
   ],
   "source": [
    "Ds1 = (D @ s1)\n",
    "Ds2 = (D @ s2)\n",
    "print('nonzero entry of Ds1 (Ds1).T: ', (Ds1 @ Ds1.T).data[0])\n",
    "print('nonzero entry of Ds2 (Ds2).T: ', (Ds2 @ Ds2.T).data[0])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# what's missing?\n",
    "\n",
    "- low degree nodes have insignificant $(Ds)(Ds)^T$, however, by setting $\\beta$ large, it could still make a big impact. What's the value of $\\beta$ for low degree nodes? \n",
    "  - on one hand, $\\beta$ should be close to zero in order to untighten the correlation constraint. \n",
    "  - on the other hand, $\\beta$ should be large in order to maximize the dual problem objective\n",
    "  - so what's the happening here?"
   ]
  }
 ],
 "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.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}