TME2-3/diffusion.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# TME 2-3 : Diffusion\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Parsing\n",
    "with open(\"data/cascades_train.txt\") as f:\n",
    "    cascades_train = f.read()\n",
    "\n",
    "diffusions_train = []\n",
    "times_train = []\n",
    "for line in cascades_train.split('\\n'):\n",
    "    diff = line.strip().split(';')\n",
    "    diff = [s.split(':') for s in diff if len(s) > 1]\n",
    "    diff = {int(l[0]):float(l[1]) for l in diff}\n",
    "    times = {}\n",
    "    for elt, t in diff.items():\n",
    "        if t in times:\n",
    "            times[t].append(elt)\n",
    "        else:\n",
    "            times[t] = [elt]\n",
    "    diffusions_train.append(diff)\n",
    "    times_train.append(times)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Diffusion n°0 : {3: 4.0, 4: 10.0, 5: 8.0, 8: 3.0, 73: 4.0, 12: 7.0, 98: 5.0, 82: 11.0, 84: 5.0, 86: 5.0, 89: 3.0, 26: 1.0, 93: 2.0, 96: 7.0, 34: 9.0, 41: 2.0, 42: 2.0, 43: 4.0, 47: 6.0, 48: 6.0, 50: 7.0, 52: 8.0, 54: 9.0, 55: 7.0, 56: 1.0, 20: 7.0, 61: 5.0}\n",
      "Diffusion n°0 : {1.0: [26, 56], 2.0: [93, 41, 42], 3.0: [8, 89], 4.0: [3, 73, 43], 5.0: [98, 84, 86, 61], 6.0: [47, 48], 7.0: [12, 96, 50, 55, 20], 8.0: [5, 52], 9.0: [34, 54], 10.0: [4], 11.0: [82]}\n",
      "Tous les temps : {1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0, 11.0, 12.0, 13.0, 14.0, 15.0, 16.0, 17.0, 18.0, 19.0, 20.0, 21.0, 22.0, 23.0}\n",
      "Tous les noeuds : {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99}\n"
     ]
    }
   ],
   "source": [
    "from functools import reduce\n",
    "# Dans 'diffusions_train' chaque élément est une diffusion,\n",
    "# chaque diffusion est un dictionnaire {élément:temps d'infection}\n",
    "print(\"Diffusion n°0 :\", diffusions_train[0])\n",
    "\n",
    "# Dans 'times_train', chaque élément est une diffusion,\n",
    "# chaque diffusion est un dictionnaire {temps:[éléments infectés]}\n",
    "print(\"Diffusion n°0 :\", times_train[0])\n",
    "\n",
    "all_times = reduce(lambda l,m:set(l)|set(m), [d.keys() for d in times_train])\n",
    "print(\"Tous les temps :\", all_times)\n",
    "all_nodes = reduce(lambda l,m:set(l)|set(m), [d.keys() for d in diffusions_train])\n",
    "print(\"Tous les noeuds :\", all_nodes)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Apprentissage\n",
    "\n",
    "# Calcul de D+ et D-\n",
    "Dplus = []\n",
    "Dminus = []\n",
    "for u in all_nodes:\n",
    "    Dplus.append([])\n",
    "    Dminus.append([])\n",
    "    for v in all_nodes:\n",
    "        Dplus[u].append(set())\n",
    "        Dminus[u].append(0)\n",
    "        for idx, diff in enumerate(diffusions_train):\n",
    "            if v in diff and u in diff and diff[v] > diff[u]:\n",
    "                Dplus[u][v].add(idx)\n",
    "            if v not in diff and u in diff:\n",
    "                Dminus[u][v] += 1\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{2944, 4225, 390, 2438, 3591, 2825, 4746, 4107, 2316, 4495, 3986, 1428, 1301, 151, 2202, 3098, 2076, 3614, 1056, 1825, 546, 675, 2722, 3623, 3496, 1194, 307, 3380, 309, 4915, 2615, 4023, 441, 827, 1341, 1598, 4292, 3653, 4165, 967, 2887, 4937, 2764, 4174, 4688, 1105, 1107, 852, 1621, 2646, 3540, 984, 3033, 2266, 2650, 2140, 3798, 4061, 3557, 4325, 999, 2407, 362, 746, 1130, 1902, 3823, 1904, 2672, 4079, 4220, 1782, 3321, 3963, 124, 1277}\n",
      "531\n"
     ]
    }
   ],
   "source": [
    "print(Dplus[5][6])\n",
    "print(Dminus[5][6])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "==== 0 ====\n"
     ]
    },
    {
     "ename": "ZeroDivisionError",
     "evalue": "division by zero",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mZeroDivisionError\u001b[0m                         Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-34-ca5ad5c1f616>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[1;32m     21\u001b[0m         \u001b[0;32mfor\u001b[0m \u001b[0mv\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mall_nodes\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     22\u001b[0m             theta_star[u,v] = sum([1/compute_P(diff, times, v, new_theta_hat) \n\u001b[0;32m---> 23\u001b[0;31m                                     \u001b[0;32mfor\u001b[0m \u001b[0mdiff\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mtimes\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mzip\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mdiffusions_train\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mtimes_train\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     24\u001b[0m                                      if v in diff])\n\u001b[1;32m     25\u001b[0m             \u001b[0mtheta_star\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mu\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0mv\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m*=\u001b[0m \u001b[0mnew_theta_hat\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mu\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0mv\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m/\u001b[0m \u001b[0;34m(\u001b[0m\u001b[0mlen\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mDplus\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mu\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mv\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m+\u001b[0m \u001b[0mDminus\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mu\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mv\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m<ipython-input-34-ca5ad5c1f616>\u001b[0m in \u001b[0;36m<listcomp>\u001b[0;34m(.0)\u001b[0m\n\u001b[1;32m     22\u001b[0m             theta_star[u,v] = sum([1/compute_P(diff, times, v, new_theta_hat) \n\u001b[1;32m     23\u001b[0m                                     \u001b[0;32mfor\u001b[0m \u001b[0mdiff\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mtimes\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mzip\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mdiffusions_train\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mtimes_train\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 24\u001b[0;31m                                      if v in diff])\n\u001b[0m\u001b[1;32m     25\u001b[0m             \u001b[0mtheta_star\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mu\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0mv\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m*=\u001b[0m \u001b[0mnew_theta_hat\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mu\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0mv\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m/\u001b[0m \u001b[0;34m(\u001b[0m\u001b[0mlen\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mDplus\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mu\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mv\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m+\u001b[0m \u001b[0mDminus\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mu\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mv\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     26\u001b[0m     \u001b[0mold_theta_hat\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mnew_theta_hat\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;31mZeroDivisionError\u001b[0m: division by zero"
     ]
    }
   ],
   "source": [
    "import numpy as np\n",
    "\n",
    "def compute_P(diff, times, v, theta):\n",
    "    \"\"\" Calcule P_{tdv}(v)\n",
    "    :param times: dict {temps:[éléments]}\"\"\"\n",
    "    produit = 1\n",
    "    t_vD = diff[v]\n",
    "    if t_vD - 1 in times:\n",
    "        for w in times[t_vD - 1]:\n",
    "            produit *= (1 - theta[w,v])\n",
    "    return 1 - produit\n",
    "\n",
    "old_theta_hat = np.zeros((len(all_nodes), len(all_nodes)))\n",
    "new_theta_hat = np.random.random((len(all_nodes), len(all_nodes)))\n",
    "\n",
    "it = 0\n",
    "while not np.allclose(old_theta_hat, new_theta_hat) and it < 500:\n",
    "    print(\"==== %d ====\" % it)\n",
    "    theta_star = np.zeros_like(new_theta_hat)\n",
    "    for u in all_nodes:\n",
    "        for v in all_nodes:\n",
    "            theta_star[u,v] = sum([1/compute_P(diff, times, v, new_theta_hat) \n",
    "                                    for diff, times in zip(diffusions_train, times_train)\n",
    "                                     if v in diff and #todo check\n",
    "                                  ])\n",
    "            theta_star[u,v] *= new_theta_hat[u,v] / (len(Dplus[u][v]) + Dminus[u][v])\n",
    "    old_theta_hat = new_theta_hat\n",
    "    new_theta_hat = theta_star\n",
    "    it += 1\n",
    "    \n",
    "print(new_theta_hat)"
   ]
  }
 ],
 "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
}