02_GraphEmbedding_02_Node2Vec.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 一.Node2Vec原理\n",
    "Node2vec其实是对于DeepWalk中第2)步，随机游走方式的调整，以学习到图结构的同质性和结构性信息。这里：  \n",
    "\n",
    "1）同质性是指相邻两节点之间应该具有较高的相似度；    \n",
    "\n",
    "2）结构性是指邻居结构相似的两节点之间应该具有较高的相似度，即使这两节点之间没有路径连接    \n",
    "\n",
    "如下图，u与s1,s2,s3,s4之间在同质性上应该具有较高的相似度，而u与s6在结构性上应该具有较高相似度\n",
    "![avatar](./pic/node2vec1.jpg)  \n",
    "\n",
    "那如何游走才能提现同质性和结构性呢，这其实可以利用我们常见的图搜索算法，深度优先搜索(DFS)和广度优先搜索(BFS):   \n",
    "\n",
    "1)DFS:深度优先搜索，在相俩节点间游走，倾向于获取同质性信息；   \n",
    "\n",
    "2)BFS:广度优先搜索，优先获取节点周围邻居序列，倾向于获取结构性信息；    \n",
    "\n",
    "具体的游走方式如下 \n",
    "![avatar](./pic/node2vec2.jpg)  \n",
    "\n",
    "已知，当前序列的最后两节点为[t,v]，即最后一步游走为t->v，那么接下的游走方式满足如下公式：   \n",
    "![avatar](./pic/node2vec3.jpg)\n",
    "下面直观解释一下这三种情况：   \n",
    "\n",
    ">(1) $d_{tx}=0$，表示$t$节点与$x$节点距离为0，所以它们是同一节点，言外之意是说从$v$节点又跳回了前节点$t$，它的跳转概率定义为$\\frac{1}{p}$  \n",
    ">(2) $d_{tx}=1$，表示既与$t$相连，又与$v$相连的节点，如图中的$x_1$，它的跳转概率定义为1   \n",
    ">(3) $d_{tx}=2$，即图中的$x_2,x_3$节点，它们的跳转概率被定义为$\\frac{1}{q}$  \n",
    "\n",
    "注意，上面的“概率”都未归一化，最终需要进行归一化操作，另外node2vec还需要考虑边的权重$w_{vx}$，所以它实际是对$\\pi_{vx}=\\alpha_{pq}(t,x)\\cdot w_{vx}$进行归一化，下面对超参数$p,q$进行讨论；   \n",
    "\n",
    "> 对于p：如果$p>max(q,1)$,那么采样倾向于不会往回走，而如何$p<min(q,1)$，采样倾向于返回上一个节点，在初始点周围游走  \n",
    "\n",
    "> 对于q: 如果$q>1$，采样点倾向于在起始点周围游走做BFS采样，而如果$q<1$，倾向于远离起始点，做DFS采样   \n",
    "\n",
    "### 二.实现"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYUAAAD7CAYAAACFfIhNAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi4zLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvIxREBQAAIABJREFUeJzt3Xm8lHXZx/HPxXYARUEFd400RE0RBXNH0UrQxHKpp1yyXHB5Hk3yMZ7KvcittMxIK8HMpZJIE1wTzNwwcEtzy9RcEAXU5HBYzvX8cd0zZ85h5qwzc8+c+b5fL16eM8t9/4aX3Nfcv9/vui5zd0RERAB6pD0AERGpHAoKIiKSpaAgIiJZCgoiIpKloCAiIlkKCiIikqWgICIiWQoKIiKSpaAgIiJZCgoiIpKloCAiIlkKCiIikqWgICIiWQoKIiKSpaAgIiJZCgoiIpKloCAiIlkKCiIikqWgICIiWb3SHoCISEmYDQGOBXYEBgJLgaeAabgvSnNolczcPe0xiIgUj9loYDIwDnCgX86z9YABs4EpuM8r/wArm4KCiHQfZhOBy4G+tD493ggsBybhPrUcQ6sWCgoi0j00BYT+HXjXMhQYmtFCs4hUv5gyyhsQVgAnAZsBOwB/af50f+ByzEaVfIxVQkFBRLqDycSU0RquAT4C/gVcBxwJfNj8JX2T9wsKCiJS7WKX0TgKXM9uAU4mtlqOAjYAnm/+kh7AeMwGl3KY1UJBQUSq3bHELiMAzgU2ATYGrk4eezf574fAq0RgaMGT49Q85SmISLXbkWTb6WJgCrCQ2F50IvAV4DTgH8AfgOHAx9Y8Rr/kODVPQUFEqt3AzA/rAtsA3wAOBKYDawMbAn8F5gM3teM4tUzTRyJS7ZZmfugJzAMOB+YCI4ndR58HxgDbA19ox3FqmYKCiFS7p4hMZV4A9k/+XAy8DbyXvGgK8H0inTmP+uQ4NU9BQUSq3XSSa/0wYG9gaPLzacSC8yygD7FFqQBLjlPzlNEsItXPbAYwgc590W0EZuJ+WHEHVZ10pyAi3cEUopZRh9UDp8ICM9vazGp+842CgohUP/d5T8Elyzr6Nlh2Fqy8Gi4EngHqzewNMzu0BKOsCgoKIlL1zGzCCDj9VriBKHLX2MZbGoFlBpN+CnsAq4A6Ypv++sSadU1SUBCRqmRmvczsSDN7GpgJ9D7a/Whi9+lMYjqpvsXb6pPHZwJjcJ/q7vOBPxGBwYlF583K9DEqjhaaRaTqmNmmwAIiE3nt5OEL3f2cnBcNJn/ntektO6+Z2VDgReAh4E2ibt5NwFFeYxdJBQURqTpm1hu4ETiUmPL5ADjU3e/vwjEPAR5194VmNg74PfAfYKy7/70Iw64Kmj4Skarj7iuBJ4gk5gbijuHRLh7zNndfmPw8GxhM3D08ZWbf69qIq4fuFESk6pjZwcBtwKlE4vJB7n58ic41EfgJ8DIwJhM4uisFBRGpKmb2CeBZ4Dp3P7FM59wUuJ8osHqKu/+iHOdNg4KCiFQNM1sLeAN4zt13T+H8FwPfJLp6jnP3lrubqp6CgohUBTMzoi3COsBm7r46pXHsBNxDrGN8wd3vzhkf1b5bSQvNIlItZgJbADulFRAA3P0JYAhRZ+9OM7shCQh3EJnRVU13CiJS8czsfOA7wJ7u/kja48kws4OA3wEriUKsDmzt7m/mefEQ8udNTGuZN5EmBQURqWhm9nngVuAkd7827fG0ZGYjiKZuPYDVwI3ufkzOC0YDk4nK3U7SOjRRT2RQzwam4D6vTMMuSEFBRCqWmW0HPAlc4+6npj2efMzsPqKNQy+aevjs5e5/JbazXg70pfXp+kai/MYk3KeWcrxtUVAQkYpkZgOInUZPuPs+aY+nEDPbFtgN2A74FLA7sGwuTN0n+vz078DhlpFyYFBQEJGKkyzcvkh8w94yzYXlzjjT7H8vgotbiwYXANckP18IHNf01DKiWN/jJRtgK7T7SEQq0R1EJ82R1RYQAH4Iu/VrpXz3M8Bc4FXgYeBsICdNui+xBpEKBQURqShmNgX4DFFSomJ25bRb7DIaZ61cX58DRhGFmzYHtiRqdSR6AOOTKq9lp6AgIhXDzL5IfHH+uqc0fVIExxK7jLLOBTYhbn2uJhYfbgPeIlKj3wW2bX4MT45TdjXfj1REKoOZ7QD8BrjS3aenPZ4u2JGcbaeLiQbSC4n5pBOBk4k7hIOAD4m6GX2aH6Nfcpyy052CiKTOzAYRDW4ecPdvpD2e9jCzoWZ2pZlNMLN1c54amPu6dYFtgG8QtTGmA9OAoURyw/NEqnaeBIWBaz5UegoKIpKqZKfRAuJL9f4pD6cj1gdOAa4HFpnZIjN79g7YJfdFPYkL/uHE4vJI4AFiCgniIrwTkGeubGmpBt4aBQURKTszG2RmM8xsC+BuYAOiplHF75E3sy3N7Czg+8QU/DpAb+IzDKqDuxojEQ2AF4hItz9wMbGgPAy4hcjKm0P0/fxk89PUEyUwyk5rCiKShjHAwcB44jq0i7svSXdIazKz9Ygv+QcSX/I3JQLA+8BLwBJgEHER/z/gygOiY9uXMscYRqQ7D01+Py35Mx/YJznYyclrck9NzDSVnZLXRKTszOzHxLXRgBXAce5+Y8pj6gccQqz/7krsFO1LJJO9AjwG/Am4w90bkvdcCxwBHOLuD+QcbAYwgc7NxjQCM3E/rNMfpgsUFESk7MzsFaKLGcS37Mfcfd8ynr8ncABx4d4d2AoYQASo14kv8ncCt7r7+60cZz2gh7u/2+KJ0Q5zrXnxu/ZKNaNZ00ciUlxtlIg2sw2JgODEhff7wF9LNxwzYDRwGDFLsw2wHlHR9K1kbNcDv3X3NzpybHdfXOB8g06H+kugd5+OXWcztY9Sy9HQnYKIFEc7SkQ7zB4HA++CjxMZy68Wfxi2NfBFYD9i/XYwMU31LtHbeQ4RAJ4t8nm3AI4CJhJpCB+shrN7qEqqiNScdpaIbgRvAG+E09dyv6rrp7UNiTn9zwAjiMThXsTdyQtEwvAM4OFS7mwys7HAfUADUEcExRPc/ZeYjSKC5XgK91OYRfRTSD2LW0FBRLqmKSAULAq6lJhLmkPcIlCgRLSZHQps5Hm+LZvZWsAXiDuRUURrzjrgI+CfRG2524A7y11Ez8x6E42ADqZp8XyzZrWbopZRvmm16eq8JiLdQ0wZzaGNngGnAWsR+/RzZBdUk4XfS5KXvk0s/I4DPkf0Kvh4cogG4DUiH2wWMNPdPyrWx+ksM6sjAtMg4k7lWXffKd1RdY4WmkWkKyYTU0YFLSDmb/6x5lN9gclmdhJwPzCcuCZtQfQ8XgW8CTwB/Bz4vbsvXPMw6UruEv5BlC/aCDifvFUrqoPuFESkc2KX0avkBIVzgWuJifPvEjUg9gHeIZK4xhGrsJmelSugcTNgUfN1iAYib+GmUn+ErjKzHsTi9RBgq0pMwOso3SmISGc1KxGdrxroTkSVu0uJ7TjfIgLCxOQ9PWDVHPjx9lEO6CBiMXZzUioG1xHJ1tP5xOL2J7pDQAAFBRHpvGYlonOrgR5I1Gi4llgUyJQ9/Qj4LU1BoRf02Q42dPfbgdsBzGxjooxExUoCwkPAJ4BtK3Faq7NUEE9EOqvZt/l81UD7EwsEGX1bvinPcdz9LXdfVtyhFt09xEcc4e6vpT2YYlJQEJHOalbaOV810OFEyvIiYkP+L4hKeK0dp9KZ2W3EUslod38p7fEUm4KCiHTWU8S1HmheDXQYsbd0DPBtYE9gM6LE6NebHyO1EtGdYWY3E+vle7j702mPpxS0+0hEOifP7qOOcmgw2LySkrcKMbNfAF8FxjariNrN6E5BRDrH/R1gNrHZqMMawWdAncEbZvYvM5tvZneZ2S5tv7u8zOwK4Djg4O4cEEBBQUS6ZsrqSDTrsB5Q/4sIKr2J3gUjiXLWK4o4vi4zs4uA/waOcPc70x5PqSkoiEiHWdjZ4JLToPfqnPaT7bQMmHQnHEqUh8ioJ8pZVAQz+z+io9qx7j4j7fGUg4KCiLSbmfU3s8nAv4geCPtOhed6RirCMtqeSmokpxieu68gWlc2AB8QJS0eMrO7zWydUn2O9jCz04GLgInufkOaYyknBQUR6Ygtido+WxALzCuA85Jqp2OAmcRdQ32L99Unj88kiuBlq6C6+zzge8Dx7r5XcpxPAu+a2Xkl/TQ5zKxXkpSGmR0P/Aj4prtfU64xVALtPhKRDjGzU4CfJr+uAAa7+wc5LyhKiWgz+zZRTmkx8F/ufn9RPkDh8/2BCHQ3AdOAc939wlKesxIpKIhIu5nZTkQD+7lEb+On3X33Ep5vAHALUTnjQeDz7v5eCc7TF1hCzJ70AX7o7pOKfZ5qoOkjEWkXMxsGPALc7+6fJnYLnVDKc7r7h+4+HtiVmLpaaGaX5kzz7GZmOxThVPsT6x19iJLde5pZv9bf0j3pTkFE2mRmmxKVLJ509z1SHMcZwA+I2nonAtcQaxVbu3vLdYzMm4aQfzprWmY6y8zuIlp6Znol/xvYz93fLOXnqUQKCiLSKjNbH3gZeB3YsZS9jts5njrgN8BhxEW8AfjZGtM90RVuMlGWolBv5Nmz4BcHwZ+I9ZErgOnu/lypP0elUlAQkYKSOf1/EttFh5W793EhyVTWkzSV2FgF7OruC5IXZPpG96WVaXKHxuVg18DdZ8C4tANeJdCagojklXwjf474Br1dpQSExGeJfjCriTuFXsCjZrZTTkDoT4tr3MVEv8zMnwHQ41Kw02Fvh5PK+QEqle4URGQNZtYTeJ6Ygx/q7h+mPKS8zKw/sB7RDvNLu8HX58A6de1sILYXsbd2RPy6jMiheLwkg60S6rwmIs0kO3sWAIOJvsMVGRAAkmY8y4iF4fn1Ztv2jraebfoz8QFHND3Ul1iDOKzoA60imj4SkZYeBLYCPunu76Y9mHYzG9IPDugRC8hAZL5tAmwMXN3i5VcAZzR/qAcwPkm+q1kKCiKSZWZ3ArsAI9399bTH00HHEruMgEiDngL8HXgGuC/nhf8mVs/zdIHz5Dg1S0FBRAAws1uIJK7d3f2FtMfTCTuSs+10XWAbolLfPcD0nBfeCByZ/xj9kuPULAUFEcHMriHm0sdmt3VWn4G5v/QE5gGHEzU5RtLUqOFWomZ3e45Ta7TQLFLjzOxSonXywe7+l7TH0x5m1icpu53VCEtzv+W+QLRKuxfYh+gP/R5Rx+IVWr0dWFrk4VYV3SmI1LCkEukk4MvuPjvt8bSHmX0aaDCz983sOTN73MxePA8OWp6zpjAM2BsYmvx8GrHg/ABRSKmAeqIERs1SnoJIjTKz04AfE01kqqZngJmtC7xDfOnP+PAImHALzLKmLOfOWA5s0ZES392N7hREapCZHUMEhLOrJSCY2TAzuxF4jaaAsBKYD2z8W/f7LXo+t9X9rZBGYFYtBwRQUBCpOWZ2KHAd8H13vzTt8bTGzAab2VVmtpDIsN4TuBL4MlHi4nlgX3f/KHnLFDreLzpjefL+mqagIFJDzGwssfnmanf/TtrjycfM+pnZeWb2CjFNdCQx5o3dfUt3Pwf4A5GPtnezjOto7TmJyHLuiEzf6JoucQFaUxCpGRalpB8Cbnb3o9MeT66k1tKJwKnAdsB/gFnA+Z0qY93OKqk09U+YlNs3upYpKIjUADPbjqhndKe7T0h7PBlm9gXgLGA0Uf56LnBRUbbGmo0iahmNp3A/hVnAFN0hNFFQEOnmzOxjRAnsR91931QHA5jZXsB3gH2JXKnHgUuBGSXpZxC1jPJ1Xpte64vK+SgoiHRjZrYh8BKRyzUqrSYyZrYNcD7RBW0AEaSuBqZWWJ+GmqegINJNJfv5M4u125Y7ICQB6RzgCKJK9atECaJLcnYLSYVRUBDphsysHxEQGoim9ivLdN61gP8lpmu2BBYBvwMucPeF5RiDdI1qH4l0M2bWm5ieARhe6oCQ7ByaCJwCbAt8SCSRHeju/yjluaX4FBREupGka9pTwDrAx929voTnyewcGkXsHJoDnOTuD5binFIeSl4T6SaSC/U8YDNgO3cverVPM9vLzO4itnTeQmz1PNLd+7r7gQoI1U9BQaT7uA/YHtjR3d8u1kHNbFszu8XMPiCKjG5K9K6pc/fd3X1Gsc4l6VNQEKlSZjbczCZZ+COwF7Ht9JUiHHtjM7vazN4BniWqTf8QGODun3T3n2krafek3UciVcrMrgJOJtoNDwX2dPdHu3C8tYCziZ1DWxBbWX8HXKidQ7VDC80iVShZPzicuNvfmigP8bdOHKcnEVhOAYYTO4fuAD5dpX2apYsUFEQqjdkQ8pdlmJZTlmE4sF7Ou/YhLuw/bvvwZkRC2SRgF6InwRzgBHf/a3E+hFQrTR+JVIqoYjqZKAVRqIDbbGCKRabwwcRW0AeJkhG3u3vBXgJmtg9Rc2gf4gvhY8BlWiiWXAoKIpWgA6WeV8OK/wG7Gm4DTvXk7sHMNgXOI9prrk4e2w44lwg0awN/B34KXKuFYslHQUEkbU0BoX9737IKGnrBGZkeAEmdoXlEb/qvAGOBw4ANgH8RndYuLVUym3QfCgoiaYopozm0EhC2BZYkP/cC/t301DJgjMVFfx6xYyhzl7GQpppDKg8t7aaFZpF0TSamjPJaRiwk5MtEc+j7OvyIyCHok/NUAzBUdwXSGUpeE0lL7DIaRyv/Dp8Edij0duixIey5EbwM3A88AbxLfNnbvsijlRqhoCCSnmOJXUZZ5wKbEAsDVxP9Mx9MHtuKWFnOVQfL34JfuftYdx/p7oOBPq72ktJJCgoi6dmRnG2ni4EpxPagZ4hCRmsDFwNvAr8BTiDmhnL0S46T5e6NpRuydHdaUxBJz8DcX9YFtiEqzR1ItChbO+f53YiuNU8SiwiFjiPSFbpTEElPs9LWPYktRIcTNStGAtcDK3Je8wZ5/9EWvUS21C7dKYiUgZl9KvnxDeBtd1+1EP65HqzsDb0BXgCOA+4lUo43JYLDG8DpRKJBH9ZYeK4nSmCIFIXyFETKwMxeJZrXA9QBNgRWvA69+sRNAgDfAqYlPx9HTCUdAcwHdgauYo2gsBzYAuUiSJEoKIiUWFKA7g/AIUTaAUQ10l081pEn0Lmp3EZgJu6HFWWgImhNQaRkzGwHM7uNmOI5mNh+2kjkom3j7i8SG44KFrFrw/Lk/SJFo6AgUkRmNsDMLjWzt4mNQsOJ5vZ1ye8fEM1w3gLAfR4wafUaO03btAyYhPIRpMgUFES6KGmHeYyZPQW8D3wd+COwsbsPc/efJBVJjyLaZf6z2fthyengSWBoK8egkaaAMLX4n0ZqndYURDrJzEYA3wMOIBaL5wLnufuD7Xz/p4BLgb2BhR5TTJOB8RTupzALmKI7BCkVBQWRDjCzdYlqFEcRZalfJLqdXe3t/MdkZhsAM4lUhEx11LPd/ZLkBYPJ33ltunYZSakpT0GkDcnuoWOBbwLbEZWsbwHO7WRZ6kYioGQqm35Ibn/lOOZlXRiySKdpTUGkADPb2cxmEbt8riFKEO3h7uu7+ymd7VPg7ouJfsq9iITlvsQitEjqFBREcpjZQDO70swWAY8DHycSiuvc/TPu/kgRzrEOcDsxhfQ14EF3f7erxxUpBq0pSM1Lpoe+BpxJNDpbDNxMTA+9V4LzPQ0MAjZv7zqESLloTUFqlpmNAi4C9iN29twPHOfuj5XwnD8hiqFupYAglUjTR1JTzGw9M/uJmb0LPEb0NT6NmB76bIkDwnjgVOBod3+9VOcR6QpNH0m3l0wPnQCcQWQYvwfcREwPLSnTGAYDrwM3u/tXy3FOkc5QUJBuK0kOuxDYl0gG+zPw3XK3qkyC0kvJGD6haSOpZFpTkG7FzNYHLgC+RCzmPgtMBK5L8WJ8HdEeQQvLUvEUFKTqJd/EJxJbR4cR00PXEyUn3k95bF8EjgEO6mxeg0g5KShI1TKz3YnpoX2IqZl7gf9y9wWpDixhZpsDvwaucvfZaY9HpD20piBVJVmwvRA4kqgL9HeiJMT1lTQ1k9y9/BtY7O47tPV6kUqhOwWpeMkF9lTgf4CtgUXEPP0FaU8PtWIGEbSGpz0QkY5QUJCKZWZ7EYvGewOrgXuAI9y9ousEmdkJRIvNMe7+YdrjEekIJa9JRTGzDc3sGjNbAjwArE+UoOjn7p+rgoAwDPgZ8D13/0va4xHpKK0pSOrMrCeRVXwasBXwDrFAe0E1fdNOPsfbwD/d/VNpj0ekMzR9JG0zG0L+pi/TutL0xczGAOcDexLTQ3cBn3f3Z7o85nTcSfRIGJP2QEQ6S3cKUpjZaKI95DgKt4ecTbSHnLfm22174K2kf0DmsY2IInSHA+sQweUS4KZK2j3UUWZ2JtFac7S7z097PCKdpTUFyc9sIjCHWDDtS/OAQPJ73+T5Ocnrc95uo4luYuebWU8zO9PMXgbeAg4CpgID3H0nd7+xygPCSCIgfEsBQaqd7hRkTXGBv5ym/sFZPwCmELcI3wUmNT21DJiE+1Qz2w54mLgTWJ08v5KYXvmOu/+9hKMvKzOrAxYCf3P3/dMej0hXaU1Bmotv+HkDwsNEadEFRH/K3YgMss3j6f7A5ZebLSNaV9Zljghc5u5nl3jkaZkDrAI+k/I4RIpCQUFamkxMC62hP3Aj0Z8S4GNE0+IkKNAI/YbCNCIQrCbuHuqIpjLdjpmdD4wGtnf31W29XqQaaPpImsQuo1dJgsK5wLXECvN3iU7zGW8C2xN1HNbKedyhYRlsvnb8umnyZ1Epm9ekIUmsmwuc7O7XpD0ekWJRUJAmZmcRW0T7LQY2IibLG4ETgVtzXnocsCGxxtBCPXAO7peVeLSpMbMBRD7Cve4+Ie3xiBSTpo8k144ku4zWJeZ8vgEcCEzPedFs4EHgifzH6Jccpzv7K5GrcWjaAxEpNm1JlVwDMz/0BOYRyQRzgZHACqKf5PHAb2g+bVToOBZaeWl1MbMriCJ3e1TzNlqRQhQUJNfSzA8vAPsnfy4m5kreAg4BzgJ2beUgf4ONzOx8M3sAeB94o2QjLgMzG2NmfczsQKJS6zHu/mra4xIpBU0fSa6nHOoN+g0jSpMOTZ44jZgueoIIDpm1hJ8Ch+UcYDk03hQ7ckbnHre0wy6d5C7nfuA5oi7Tb9z95nRHJVI6Cgo1LulV0BvotzM0/BX6Zvaj/oA1F5Lbmi/pCysehJOBnxN1gAB2tMhfeAb4I3BNFbWm3BH4ENg2+f3GFMciUnKaPqpRZvawma0k8gmWA0vnw3cWw1+IDUed0QjMesR9GlEU7n0ik3kv4Ezi4noW8I6ZLTWz+8xsopm1LKFRSXYilk8s+f0OM9skxfGIlJS2pNaoJPHqWzR9m/8PsInHIuoc8mQ0t8MyYAzujyfn2JpIcfhabnJX0lLzRKJu0ieJHUuLiKTpG4AZZUsGa6MCbLIusjfQQOw6+pbnKf4n0l0oKNQgM/sC0QhmSPJQPTDW3R9JXlCw9lErsrWPOjGerYGJRDXWTxDTmv8mNj79wt3ndvSY7ThpmxVgG+CevWH8vFgon+DuBXbhinQfCgo1xMz2BK4nKlTcRqQbXEZ0CftOixdPBC536GutTzM2EtNPnQoIBca5G7HzdSywZXKOl4l2nFO7XFCvKej1pZXP1gi+ElbXwX8X67OJVDoFhRpgZsOJWnYjiDWDL7v7G2bWh9hY9GN3X5XnjaNehqs2g13r4sKfr5/CLKKfwuMlGrsBBwPHEGsTGxIpE88BtwM/d/c3Wrzn08Agd/9tngOW9S5IpNooKHRjZrYhsVtmP+BpIhi0+1u2ma0DLNwQlr4dF9KW8+7Tu9J5rTOSUtVfBr5EbHsdRKyHLABmAL8kkq53I5r5nJ9NMospozm0IyBcR8xdTWt6qNl6iUh3paDQDSV7668jUgheA77a0Xn55OI7h7i4LnT3jYo9zmIws0HA14HPE3dCudnTDcDvic+/CrMZxOJ2q7vuFhH7Tw+mWVBoBGbifljeN4l0EwoK3UjSOP7HxM6epcBp7n5LJ47TA5gJfJqYd18JrO3uK4o43JIws8OIu6M+OQ9/MAK+Nx8u6NHU56Ggo4h9unU0CwoQU2hblPvuSKSclKfQDST1hb5LTKMcA5zl7oM7ExASE4DP0XRhXQFs1/WRlsVQYtwfEjNAU4Fpx8MRDc0DBecCmwAbA1cnj91DbHs6Mf+xndi+KtJtKaO5ypnZ14AfEovAVxD76Lt6+/dH4FPA3cS0yUBgawoWRq0oPwd+B7zW7O/B7NfAqMyvi4m2ormlwY8jMuxmULBYUy1UgJUap6BQpcxsPNEDZ0Pg18BEd28oxrHdvdHMFhA9lncFnicWWiueu39I3CW0NDD3l3ylwc8HjiYSJVqp4Dew8FMi1U9BocpY7KD5NTAMuIOo2LmkBKc6GljhVbbbJgmWXyamjh4F/u7uqz+AhnVyXpcpDX4v8Zf4XeIfw2LitmsFsef2A+LOIcdSRLoxBYUqYWYfB24mpkAeAYaWonxzclHdjJg7f7rYxy+DIcCRxG6kXkBvM2uYDH5uJKL1hCgNfhwRFPYheoa+QKwvQGy7msYaC831VHHFV5H20EJzhTOz9c3sTuAlYG1gF3ffo4T1/CcQFbH3AIaZ2VUVXrAOADPbKFls/wZR9bU/sbDcCEw5GT5eF7uogLjNypQGH0Zk8G28xlHXPA3Nm9CJdDvaklqhkgvxtcB/AW8Cx7v7XWU473HAVcRFtZHYjDPc3etLfe6OMLN1ga8RdwQ7AQOIqZ2/EUltawFLiJpOTydvmtEIh/ZoqnjaEcpTkJqgO4UKY2Y9zOyHRNnpccBx7r55OQJCYj5N04pLgL0rISCYWZ2ZHW9md5vZYiIAXEBMB10IrO/ug9z9AGIZ4J/AiExAMLN1JsDq5Z0fwnJiw5JIt6Y7hQpiZmcB5yW/XuDuF6cwht7EOusqYKS7P1PuMSTj6Em0iP4ykVU9hLgwPwv8iaie+nqB9/YjdmXtRywZ7EcU1luyEC4aEkFEtY9E8tBCcwUws68QmcgDiPn8b5atn8CaVhFz75PKGRCSwnefJRa49ybyylYR6783EN3anm/Psdy93swmE9NLmf9PxJ3wAAAKmUlEQVTHHRg7xP0Jogtcm1VSKUEFWJFKpzuFFJnZAcCviM0vNxPrBuWdqmnRZOYd8Ktgr7Nhm7VKXM7BzPYg6hZlvsk78ApwH3En0OntsMmaw5s03RHMdfd9c14wiuinMJ4C/RQocQVYkUqkoJACMxtB1OfZlqiscFTZexa30mRmBazqE9/SZxMXxaJ0GjOzTxLJw58mMqR7Aq/TVJD0/iJkY2cKAj5KbCzK3HF9xt3/kufFg8nfea3sFWBFKoGCQhmZ2ZZEMNgdeJwoZf1SCgNpV5MZ2pg+SSqprio01ZV83kxHteHEFtGFwEPElNDMYgSBFufM9Iz4iMjGHkXcjXyu2OcS6Y4UFMrAzAYSWcgHEfkGR7v7oykNpihNZpLGPfcDF7v7Fcljmd7LhxC9l/sD7wGPAbcAN5Wy0qqZnUjUtptL3BmktS4jUrUUFAppo6F7/reYETtmZrr7yuSb9M+IyqXvACe5++3lGH5eHWgyk0e2yYyZ7UPsABpAbP18HRhJ1Ep6n9jWeitwfVKLqKSSv/cbiJyOC9z9vFKfU6S7UlBoqR0N3Skw154kfv0KOBXYnCi6WU+Usr629INvQzubzBTQ2Ah/7Bm14k5pcYxHif4Lvyz32kiyoPwYsVB9sLvfW87zi3Q3Cgq5ujDXbmZbAU/S1Pkrk+x0YUXMZcedz6vEZ2tmGk21fgD2JZIl9m3xuugww6pFsUC8ggiQBoxx94eLPuY2mNmuwJ+JJLtR7r6w3GMQ6W6U0ZzRfK69rb+XHsnrLsdsopn1Ii5OmYCwiphrv6DcAcHMhpnZj5KdPrmOJe58Oq0PLH8n7qLWBg4Avk3cNa1s9Y0lYGb/AzwMPABsoYAgUhwKCpCZMmpz8fU3RGXNHP0b4Yd7wovAFsT2x0yewVeLPcx22pqYvnrUzJ4ws6+YWf//xE6cdhW2KxQ5esRdxo7uvszdH3T3y9x9QjnLaydd5m4FfgR8293HV8SdmEg3oYzmMJk80yq5/kRcaQ9t8bhDvyth+ajYZvo20Sy+ARhkZoOK3esgWVTdAtiKKPK5JZH9uxGwAVHssxdRKXQEsQDLX2DFuHaeo5UGM5BikxkzW59og7AxUehublpjEemuFBRirn0cbdw1XUc0YmnZYKAnsAt8zOFl3BcldXfOAc5K/vv9wqc2Iy7kn6DpAr8pcdEbDKxHNAlbmwhavXPGuZIIPsuITmNLgHeJqqaZwLACuB04ZVz0jjkq3zjWIbYPQaTwvtzaX0RKTWbMbC+iPehCYDN3fy+NcYh0dwoKeebazyVqVjsRCE4Bfk+rhfQdONbMXiUaxa9FxIsjzWxH4gK/PvEtewAxjdMneQ3EtNMKmi7wS4n9/U8CbxEX+leJ6/VL7v5RoYGY2QCiYdgzwLHuPj954iliamuNKaQDiYixL5FcsFfhz5lKk5mkUOAPiAD3eU0XiZSOdh9FQ/fsN+jFxDxMbkP3W5PnptF8l06uG2D10U0X+YzlxIX8PWARMb30b+A1Yn//i6X4xmtmI4En3b0x58GCu486IDYglWnbaXIndTtxJ/dNd/9ROc4rUst0p9COhu7tcQTcfXRMF50BfIEIEAvcfY8ijrVd3H1BngffwWw2XchTAGaVMSAMJhrmrA/s6e6PlOO8IrVOu49azJFnGrofTtRKGEnM67SlDt5NduGcQTS9v5eo+FlJphDf9jujbE1mzGwssczRQKwfKCCIlImCQsyRZ8tVvwDsn/y5mJjvaWt+ZxkwGQ43s5XJW64jbjTeL8WAOy0ysCcRQ+6ITO2jkm89Tfos30NkSA8r9u4tEWmdgkLMEGV79namoXs/WH5b07fonsRisgF7WiS3VU7j+8jAzgSGxtZeujr+NFCGJjNm1tPM7iaSqU9z9y9pQVmk/LTQDF2uCUTS0D0pdTGXaB3ZA1gAbE/s+MmUjJ4O3Jb6Ba8dTWZmwcpzYMDfIhHv+lKN2cw2JWbtBgD7uvvfSnEeEWmbggIUrXpoHMo2IDqHrXb3nZPHtiH6ChxIZBz3IHYC/RmYWs6M4DW00mTG4GTgfCIn4iHgW8We3zezA4E/EiXFdytHVVURKUxBIaNIfQbiUNYXWMfd38l/KhtDNH7ZF9iMuOg+D9xBBIlXOzz+EjCzk4ne0bm71NYr1jy/mX2PuFu53t2/WoxjikjXKCjkKlJHso6d0noCRxC5ErsRWzD/AzxBpEj8Mq1vzzlNazL5Fw7UuXuXCuAln/nPwJ7Aie7+qy4NVESKRgvNueICP4bY+bKcnF1Jifrk8ZnElFGXF1/dfbW73+zuB7v7BsQUzjnEQvVFwAdmtsjMbjezLyYX1HLZiOYJeSuIVI4OMbONkjIVmRadbxJ1mUYoIIhUFt0pFFIhDd3N7GPEesRBRF5dL2IP/xzgWnd/sITn7gHsB/ySaBpkxDbRDvWVNrObgcOIelCXAM8Cu7t7y6ArIilTUKgyZrYbcAIwlqiW2kiU7p4N/KyjF+x2nrMOuBI4CTje3X/Z3nalZrZZMr5MeY3r3f3YYo9RRIpDQaGKJbWBDiUuzrsTW2GXEcVcZxB3EkVL/jKzC8bC+HvhNWtnu1Iz+ymxi8mI1IfHgL2a1WUSkYqhoNCNmNlaRIA4EtiZ2Pe/hLgQ3wTc2JVF4hVmp6yGq+qAHjkJf3k0AssXwKU7R9FZiLWY1cAjwOc0dSRSmRQUurEkKexE4BBgW6Jc91tEgt2vgPtyE9LM7FzgeXe/Oc/BOrxldxn4t2HxFVEP6iHgldST9kSkVQoKNcTMdiKCxGeISh5OlPa+G/g50fO4F3AhMCV7AW8juW8esU1qOXH1b9HhrVlyn4hUNgWFGpWsRxxItJ3em9h+mrES+C3RpGd1a2VA3gdGExHFiHmr54FBTS/JlgEpxecQkeJSUBAAzGwycAHNs5eXbAvXPAPf6BFTT2v4B7Hl6Mjk912IJkQ7NH9ZWZvziEjnKXlNMnYi7hAeBy4j7iD++0zYbUX0hgZi1XgTonLs1cBwIiCsJtKvVwLbrXlsJxbARaTCqfOaZHwFaFxjq2gUrDOIVqVTaN6q9JTkZVcC3yaiSZ6U635EPoOIVDjdKQgA7r6qQO5Atl1pbqvSe2jeqvRMIkPt+0S509aOIyKVS0FB2pJtV5qvVekLxJoCRLnX0cRCc2vHEZHKpaAgbcm2K83XqvQt4IvEFf8tImiMXPMY9TTFDhGpYAoK0pZsu9J8rUrHAMcQmXF7A1cQC9EtGM1nm0SkQmlLqrStSO1KizsoESkF3SlIe0whcg06Y3nyfhGpAgoK0jb3ecAkomRFR2TalarEhUiVUJ6CtI/7VMygzO1KRaS8tKYgHWM2CpgMjKdwP4VZRD8F3SGIVBkFBemcCmlXKiLFpaAgIiJZWmgWEZEsBQUREclSUBARkSwFBRERyVJQEBGRLAUFERHJUlAQEZEsBQUREclSUBARkSwFBRERyVJQEBGRLAUFERHJUlAQEZEsBQUREclSUBARkSwFBRERyVJQEBGRLAUFERHJUlAQEZEsBQUREclSUBARkSwFBRERyVJQEBGRLAUFERHJUlAQEZEsBQUREclSUBARkSwFBRERyVJQEBGRLAUFERHJUlAQEZGs/wdlGGaxyua26QAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "#构建图\n",
    "%matplotlib inline\n",
    "from matplotlib import pyplot as plt\n",
    "import networkx as nx\n",
    "plt.axis(\"off\")\n",
    "G=nx.DiGraph()\n",
    "edges=[(\"u\",\"s1\"),(\"u\",\"s2\"),(\"u\",\"s3\"),(\"u\",\"s4\"),(\"s1\",\"s2\"),(\"s1\",\"s3\"),(\"s3\",\"s4\"),\n",
    "                  (\"s2\",\"s4\"),(\"s5\",\"s2\"),(\"s4\",\"s5\"),(\"s6\",\"s5\"),(\"s6\",\"s7\"),(\"s6\",\"s8\"),(\"s6\",\"s9\"),\n",
    "                  (\"s5\",\"s7\"),(\"s7\",\"s8\"),(\"s8\",\"s9\")]\n",
    "G.add_edges_from(edges)\n",
    "G.add_edges_from((edge[1],edge[0]) for edge in edges)\n",
    "nx.draw_networkx(G)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "class Node2Vec(object):\n",
    "    def __init__(self,walk_len=10,num_seqs=10,p=1,q=1):\n",
    "        self.walk_len=walk_len\n",
    "        self.num_seqs=num_seqs\n",
    "        self.p=p\n",
    "        self.q=q\n",
    "    def walk_one_time(self,G,start_node):\n",
    "        #添加第二个点\n",
    "        second_node=np.random.choice(list(G.successors(start_node)))\n",
    "        seq=[start_node,second_node]\n",
    "        for _ in range(self.walk_len-2):\n",
    "            t_node=seq[-2]\n",
    "            v_node=seq[-1]\n",
    "            next_nodes=list(G.successors(v_node))#获取所有邻居节点\n",
    "            proba=[]#记录概率\n",
    "            for next_node in next_nodes:\n",
    "                path_len=nx.shortest_path_length(G,source=t_node,target=next_node)\n",
    "                if path_len==0:\n",
    "                    proba.append(1/self.p)\n",
    "                elif path_len==1:\n",
    "                    proba.append(1)\n",
    "                else:\n",
    "                    proba.append(1/self.q)\n",
    "            proba=np.asarray(proba)\n",
    "            proba=proba/np.sum(proba)#归一化\n",
    "            selected_next_node=np.random.choice(next_nodes,p=proba)#从所有邻居中随机选择一个\n",
    "            seq.append(selected_next_node)\n",
    "        return seq\n",
    "    def deep_walk(self,G):\n",
    "        corpus=[]\n",
    "        for _ in range(self.num_seqs):\n",
    "            start_node=np.random.choice(G.nodes)\n",
    "            corpus.append(self.walk_one_time(G,start_node))\n",
    "        return corpus"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "node2vec=Node2Vec(q=2)\n",
    "corpus=node2vec.deep_walk(G)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[['s1', 'u', 's3', 's4', 's2', 'u', 's1', 's3', 'u', 's1']]"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "corpus[:1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "#训练\n",
    "from gensim.models import word2vec\n",
    "model = word2vec.Word2Vec(corpus,window=2,vector_size=5,min_count=1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([-0.14191031,  0.13018166,  0.1809364 , -0.10049632, -0.07593277],\n",
       "      dtype=float32)"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#查看embedding\n",
    "model.wv['u']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.07862966"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#计算相似度\n",
    "model.wv.similarity(\"u\",\"s5\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.6219288"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "model.wv.similarity(\"u\",\"s6\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}