Gradient_computation.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import pandas as pd"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Reading graph from csv file. Storing it as a dictionary, i.e. adjacent list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import sys\n",
    "import csv\n",
    "\n",
    "csv.field_size_limit(sys.maxsize)\n",
    "graph = {}\n",
    "for key, val in csv.reader(open(\"data/graph.csv\")):\n",
    "    if val== \"[]\":\n",
    "        graph[int(key)] = [] \n",
    "    else:\n",
    "        graph[int(key)] = [int(n) for n in val[1:-1].split(',')]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "user_id_1 = []\n",
    "user_id_2 = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "for key in graph:\n",
    "    for i in graph[key]:\n",
    "        user_id_1.append(int(key))\n",
    "        user_id_2.append(int(i))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "graph_frame = pd.DataFrame(\n",
    "    {'user_id_1': user_id_1,\n",
    "     'user_id_2': user_id_2\n",
    "    })"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "users_children = graph_frame.user_id_2.unique()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Making graph inverted to be able to see all the parents of the node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "graph_inverted = {}\n",
    "for i in users_children:\n",
    "    graph_inverted[i] = \\\n",
    "    graph_frame.user_id_1[graph_frame.user_id_2 == i].tolist()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "retwitts = pd.read_csv(\"data/small_retweets.csv\", sep='\\t',  index_col=0)\n",
    "twitts = pd.read_csv(\"data/small_tweets.csv\", sep='\\t',  index_col=0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "retwitts.time = pd.to_datetime(retwitts.time)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "twitts.time = pd.to_datetime(twitts.time)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "56390"
      ]
     },
     "execution_count": 57,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(retwitts.user_id.unique())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Reading the list of frames where each frame is a log for particular twitt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import glob\n",
    "path ='data/twitter_data' # use your path\n",
    "allFiles = glob.glob(path + \"/*.csv\")\n",
    "list_of_frames = {}\n",
    "SHIFT = 1000000000.*60.*60.\n",
    "def time_conv(x):\n",
    "    return x.value/SHIFT\n",
    "for file_ in allFiles:\n",
    "    df = pd.read_csv(file_,index_col=0, sep= '\\t')\n",
    "    df.time = pd.to_datetime(df.time)\n",
    "    df.time = df.time.apply(time_conv)\n",
    "    list_of_frames[int((file_.split('/')[2]).split('.')[0])] = df"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "twitts.time = twitts.time.apply(time_conv)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "retwitts.time = retwitts.time.apply(time_conv)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### For each frame calculating the maximum time "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "max_times = {}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from datetime import timedelta, datetime, date\n",
    "for key in list_of_frames:\n",
    "    max_times[key] = list_of_frames[key].time.max()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "for key in list_of_frames:\n",
    "    list_of_frames[key] = list_of_frames[key].reset_index(drop=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "retwitts = retwitts.reset_index(drop=True)\n",
    "twitts = twitts.reset_index(drop=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>user_id</th>\n",
       "      <th>tweet_id</th>\n",
       "      <th>time</th>\n",
       "      <th>num</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>1257818405</td>\n",
       "      <td>3449713464551829</td>\n",
       "      <td>371663.0</td>\n",
       "      <td>503265</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>1288915263</td>\n",
       "      <td>3470389738808369</td>\n",
       "      <td>373032.0</td>\n",
       "      <td>500152</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>2239954024</td>\n",
       "      <td>3418421884953768</td>\n",
       "      <td>369590.0</td>\n",
       "      <td>499253</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "      user_id          tweet_id      time     num\n",
       "0  1257818405  3449713464551829  371663.0  503265\n",
       "1  1288915263  3470389738808369  373032.0  500152\n",
       "2  2239954024  3418421884953768  369590.0  499253"
      ]
     },
     "execution_count": 65,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "twitts.head()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "del twitts[\"num\"]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>user_id</th>\n",
       "      <th>tweet_id</th>\n",
       "      <th>time</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>1257818405</td>\n",
       "      <td>3449713464551829</td>\n",
       "      <td>371663.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>1288915263</td>\n",
       "      <td>3470389738808369</td>\n",
       "      <td>373032.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>2239954024</td>\n",
       "      <td>3418421884953768</td>\n",
       "      <td>369590.0</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "      user_id          tweet_id      time\n",
       "0  1257818405  3449713464551829  371663.0\n",
       "1  1288915263  3470389738808369  373032.0\n",
       "2  2239954024  3418421884953768  369590.0"
      ]
     },
     "execution_count": 67,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "twitts"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Mearging together the seed set entities and logs. Just because we need to have seed set log in the whole set of logs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 239,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "#for index, row in twitts.iterrows():\n",
    "#   print row\n",
    "#  list_of_frames[row[\"tweet_id\"]].loc[len(list_of_frames[row[\"tweet_id\"]])] = row"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### For each node in each set calculating the time of activation. Making a dictionary"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "activ_times = {}\n",
    "for key in list_of_frames:\n",
    "    activ_times[key] = {}\n",
    "    u_users = list_of_frames[key].user_id.unique() \n",
    "    for u in u_users:\n",
    "        activ_times[key][u] = \\\n",
    "            list_of_frames[key].time[list_of_frames[key].user_id == u].min()\n",
    "    seed_user = \\\n",
    "        twitts.user_id[twitts.tweet_id == key].tolist()[0]\n",
    "    activ_times[key][seed_user] =\\\n",
    "        twitts.time[twitts.tweet_id == key].tolist()[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def activ_time(S, id):\n",
    "    try:\n",
    "        return activ_times[S][id]\n",
    "    except:\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "## constants declaration\n",
    "DELTA = 24\n",
    "ETA = 5"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$ p_{vw} \\textrm{  inistialization} $$\n",
    "$$ \\textrm{Function for  }  P_{w}^{(s)} \\textrm{ computation } $$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "len(graph_frame)\n",
    "import numpy as np\n",
    "probs = np.random.random(len(graph_frame))\n",
    "grad = np.zeros(len(graph_frame))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "edge_index = {}\n",
    "subset = graph_frame[[\"user_id_1\", \"user_id_2\"]]\n",
    "edges = [tuple(x) for x in subset.values]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "j = 0\n",
    "for i in edges:\n",
    "    edge_index[i] = j\n",
    "    j = j + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def P(w, S):\n",
    "    res = 1\n",
    "    w_act = activ_time(S, w)\n",
    "    if w in graph_inverted:\n",
    "        for tau in range(0, DELTA):\n",
    "            for v in graph_inverted[w]:\n",
    "                if (activ_time(S, v) == w_act - 1 - tau):\n",
    "                    res= res * (1 - probs[edge_index[(v,w)]]*np.exp(-tau/ETA))\n",
    "    return 1-res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 75,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 75,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "P( 120671, 5615734448357004557 )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "      user_id          tweet_id      time\n",
      "0  1767454430  3418421884953768  369615.0\n",
      "1  1767467245  3418421884953768  369595.0\n",
      "2  1767468271  3418421884953768  369615.0\n",
      "3  1657168480  3418421884953768  369610.0\n",
      "4  1767471057  3418421884953768  369609.0\n",
      "      user_id          tweet_id      time\n",
      "0       10057  3470389738808369  373040.0\n",
      "1  1837296221  3470389738808369  373035.0\n",
      "2  1767465991  3470389738808369  373046.0\n",
      "3  1767464154  3470389738808369  373032.0\n",
      "4  1767466527  3470389738808369  373051.0\n",
      "      user_id          tweet_id      time\n",
      "0  1767471542  3449713464551829  371665.0\n",
      "1  1837335093  3449713464551829  371677.0\n",
      "2  1767491242  3449713464551829  371674.0\n",
      "3  1767510241  3449713464551829  371663.0\n",
      "4  1678644414  3449713464551829  371694.0\n"
     ]
    }
   ],
   "source": [
    "for key in list_of_frames:\n",
    "    print list_of_frames[key].head()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Computation of"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "\t\\frac{\\partial P_{w}^{(s)}}{\\partial p_{vw}}\n",
    "\t= \n",
    "\t\\left({\\displaystyle \\prod_{\\tau = 0}^{\\Delta-1}\\prod_{\\substack{v' \\in B(w) \\cap D(t_w-\\tau-1)\\\\v' \\neq v}} (1-p_{v'w}e^{-\\tau/\\eta})}\\right) e^{-(t_w-t_v-1)/\\eta}\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def partial(S,v,w):\n",
    "    w_act = activ_time(S, w)\n",
    "    res = 1\n",
    "    if w in graph_inverted:\n",
    "        for tau in range(0,DELTA):\n",
    "            for v_prime in graph_inverted[w]:\n",
    "                if (activ_time(S, v_prime) == w_act - 1 - tau) and (v_prime != v):\n",
    "                    res = res * (1 - probs[edge_index[(v_prime,w)]]*np.exp(-tau/ETA))           \n",
    "    res = res*np.exp(-(w_act - activ_time(S, v) -1)/ETA)\n",
    "    return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 78,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1.0"
      ]
     },
     "execution_count": 78,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "partial(3445888074596137,1616700401,1066926080)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Computation of"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "\tZ_{vw}\n",
    "\t=\n",
    "\t-\\sum_{\\tau = 0}^{t_w-t_v-2}\\frac{1}{1 - p_{vw}e^{-\\tau/\\eta}} e^{-\\tau/\\eta}\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def Z(S, v, w):\n",
    "    res = 0\n",
    "    w_act = activ_time(S, w)\n",
    "    v_act = activ_time(S, v)\n",
    "    for tau in range(0, int(w_act - v_act - 1)):\n",
    "        e = np.exp(-tau/ETA)\n",
    "        res = res + e/(1 -  probs[edge_index[(v,w)]]*e)\n",
    "    return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 80,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 80,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Z(3445888074596137,1616700401,1066926080)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Computation of gradient component"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "\t\\frac{\\partial L}{\\partial p_{vw}} = \\sum_{s=1}^{S}\n",
    "\t\\left\\{\n",
    "\t\\begin{matrix}\n",
    "\t\t{\\displaystyle \\left[\\frac{1}{P_w^{(s)}} \\frac{\\partial P_{w}^{(s)}}{\\partial p_{vw}} + Z_{vw}\\right]}\n",
    "\t\t\t&\n",
    "\t\t\t\\text{if } t_{v}^{(s)} \\in [t_{w}^{(s)}-\\Delta-1, t_{w}^{(s)}-1] \\text{ \\& } v \\in B(w)\n",
    "\t\t\t\\\\[2em]\n",
    "\t\t\t0 & \\text{otherwise}\n",
    "\t\\end{matrix}\n",
    "\t\\right.\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 81,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "S_set = twitts.tweet_id.tolist()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 82,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "users_per_set = {}\n",
    "for key in list_of_frames:\n",
    "    users_per_set[key] = list_of_frames[key].user_id.unique().tolist()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 83,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def grad_comp(v,w):\n",
    "    res = 0\n",
    "    for S in S_set:\n",
    "        w_act = activ_time(S, w)\n",
    "        v_act = activ_time(S, v)\n",
    "        if (w in graph_inverted) and (w in users_per_set[S]):\n",
    "            if (v_act > w_act-DELTA-1) and (v_act < w_act-1):\n",
    "                if v in graph_inverted[w]:\n",
    "                    p = P(w,S)\n",
    "                    ### this to be deleted,but for now we have values of P equals to zero\n",
    "                    if p == 0:\n",
    "                        p = 1\n",
    "                    ###\n",
    "                    res = res + 1/p * partial(S,v,w) + Z(S,v,w)\n",
    "    return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 84,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "grad_comp(1616700401,1066926080)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Gradient Computation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 85,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "alpha = 0.001"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "for i in edge_index:\n",
    "    grad[edge_index[i]] = grad[edge_index[i]] + alpha*grad_comp(i[0], i[1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "for i in grad:\n",
    "    print i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.13"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}