graph_tool_test.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "import networkx as nx\n",
    "import numpy as np\n",
    "import random\n",
    "import math\n",
    "from synthetic_data import add_p_and_delta, load_data_by_gtype\n",
    "from network_stat import get_stat\n",
    "from graph_tool.all import load_graph, GraphView, shortest_distance, pseudo_diameter\n",
    "from tqdm import tqdm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "maxint = np.iinfo(np.int32).max"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "g = load_graph('data/p2p-gnutella08/graph.gt')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "p = 0.7"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "K = 100"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true,
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "def get_gvs(g, p, K):\n",
    "    rands2d = np.random.random((K, g.num_edges()))\n",
    "    edge_masks2d = (rands2d <= p)\n",
    "\n",
    "    gvs = []\n",
    "    for i in range(K):\n",
    "        p = g.new_edge_property('bool')\n",
    "        p.set_2d_array(edge_masks2d[i, :])    \n",
    "        gvs.append(GraphView(g, efilt=p))\n",
    "    return gvs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "gvs = get_gvs(g, 0.7, K)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "def activate_edges_by_p(g, p):\n",
    "    \"\"\"mask the edge according to probability p and return the masked graph\"\"\"\n",
    "    flags = (np.random.random(g.num_edges()) <= p)\n",
    "    p = g.new_edge_property('bool')\n",
    "    p.set_2d_array(flags)\n",
    "    g.set_edge_filter(p)\n",
    "    return g"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "def test_activate_edge_by_p(g):\n",
    "    g.set_edge_filter(None)\n",
    "    num_edges = g.num_edges()\n",
    "    percent = activate_edges_by_p(g, 0.7).num_edges() / num_edges\n",
    "    np.testing.assert_almost_equal(percent, 0.7, decimal=1)\n",
    "    g.set_edge_filter(None)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "def simulate_cascade(g, p, source=None):\n",
    "    \"\"\"return np.ndarray on vertices as the infection time in cascade\n",
    "    uninfected node has dist -1\n",
    "    \"\"\"\n",
    "    if source is None:\n",
    "        source = random.choice(np.arange(g.num_vertices(), dtype=int))\n",
    "    activate_edges_by_p(g, p)\n",
    "    \n",
    "    dist = shortest_distance(g, source=g.vertex(source)).a\n",
    "    dist[dist == maxint] = -1\n",
    "    g.set_edge_filter(None)\n",
    "    return source, dist"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "source, c = simulate_cascade(g, 0.7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "c.min(), c.max()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "c[c != -1].shape[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "def observe_cascade(c, q, method='uniform'):\n",
    "    all_infection = np.nonzero(c != -1)[0]\n",
    "    num_obs = int(math.ceil(all_infection.shape[0] * q))\n",
    "    if method == 'uniform':\n",
    "        return np.random.permutation(all_infection)[:num_obs]\n",
    "    elif method == 'late':\n",
    "        return np.argsort(c)[-num_obs:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true,
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "obs = observe_cascade(c, 0.01)\n",
    "print(c[obs].min(), c[obs].max())\n",
    "obs = observe_cascade(c, 0.01, 'late')\n",
    "print(c[obs].min(), c[obs].max())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def get_o2src_time(obs_nodes, gvs):\n",
    "    o2src_time = {}\n",
    "    for o in obs_nodes:\n",
    "        o2src_time[o] = np.array([shortest_distance(gv, source=o).a for gv in gvs])\n",
    "    return o2src_time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "import itertools\n",
    "def source_likelihood_drs(g, obs_nodes, \n",
    "                          o2src_time,\n",
    "                          infection_times,\n",
    "                          source=None,\n",
    "                          debug=False,\n",
    "                          eps=1e-3,\n",
    "                          nan_proba=1e-3):\n",
    "    num_nodes = g.num_vertices()\n",
    "    N2 = len(sim_flags)\n",
    "    \n",
    "    source_likelihood = np.ones(num_nodes, dtype=np.float64)\n",
    "    obs_nodes = list(obs_nodes)\n",
    "    \n",
    "    for o1, o2 in itertools.combinations(obs_nodes, 2):\n",
    "        t1, t2 = infection_times[o1], infection_times[o2]\n",
    "\n",
    "        dists1, dists2 = o2src_time[o1], o2src_time[o2]\n",
    "        mask = np.logical_and(dists1 != maxint, dists2 != maxint)\n",
    "        counts = mask.sum(axis=0)\n",
    "        probas = (((dists1 - dists2) == (t1 - t2)) * mask).sum(axis=0) / counts\n",
    "        probas[np.isnan(probas)] = nan_proba\n",
    "        \n",
    "        if debug:\n",
    "            print('t1={}, t2={}'.format(t1, t2))\n",
    "            print('source reward: {:.2f}'.format(probas[source]))\n",
    "            print('obs reward: {}'.format([probas[obs] for obs in set(obs_nodes)-{source}]))\n",
    "\n",
    "        source_likelihood *= (probas + eps)\n",
    "        source_likelihood /= source_likelihood.sum()\n",
    "    return source_likelihood"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "source, c = simulate_cascade(g, 0.7)\n",
    "obs_nodes = observe_cascade(c, 0.01, 'uniform')\n",
    "print(source, len(obs_nodes))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "qs = np.linspace(0.001, 0.01, 5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "rows = []\n",
    "for q in tqdm(qs):\n",
    "    row = []\n",
    "    for _ in tqdm(range(50)):\n",
    "        source, c = simulate_cascade(g, 0.7)\n",
    "        obs_nodes = observe_cascade(c, q, 'uniform')\n",
    "        o2src_time = get_o2src_time(obs_nodes, gvs)\n",
    "        sll = source_likelihood_drs(g, obs_nodes,\n",
    "                            o2src_time,\n",
    "                            infection_times=c,\n",
    "                            source=None,\n",
    "                            debug=False,\n",
    "                            eps=1e-3,\n",
    "                            nan_proba=1e-3)\n",
    "        row.append(sll[source])\n",
    "    rows.append(row)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "m = np.array(rows)\n",
    "m.mean(axis=0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "sll = source_likelihood_drs(g, obs_nodes,\n",
    "                            o2src_time,\n",
    "                            infection_times=c,\n",
    "                            source=None,\n",
    "                            debug=False,\n",
    "                            eps=1e-3,\n",
    "                            nan_proba=1e-3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "print(sll.max())\n",
    "print(sll[source])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "pseudo_diameter(g)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "inferred_source = np.argmax(sll)\n",
    "print(shortest_distance(g, source=inferred_source, target=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.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}