continous-time-diffusion-model.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "%matplotlib notebook\n",
    "# starter code\n",
    "import random\n",
    "import numpy as np\n",
    "from matplotlib import pyplot as plt\n",
    "from tqdm import tqdm\n",
    "import networkx as nx\n",
    "from graph_tool.all import load_graph, shortest_distance, GraphView\n",
    "from networkx.drawing.nx_agraph import graphviz_layout\n",
    "\n",
    "from cascade import gen_nontrivial_cascade\n",
    "from utils import get_rank_index\n",
    "\n",
    "seed = 123456\n",
    "random.seed(seed)\n",
    "np.random.seed(seed)\n",
    "\n",
    "gtype = 'grid'\n",
    "g = load_graph('data/{}/2-6/graph.gt'.format(gtype))\n",
    "gnx = nx.read_graphml('data/{}/2-6/graph.graphml'.format(gtype))\n",
    "gnx = nx.relabel_nodes(gnx, {i: int(i) for i in gnx.nodes_iter()})\n",
    "N1, N2 = 100, 100\n",
    "p, q = 0.5, 0.2\n",
    "\n",
    "pos = graphviz_layout(gnx, root=0)\n",
    "\n",
    "# infection_times, source, obs_nodes, tree = gen_nontrivial_cascade(g, p, q, model='ic', return_tree=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import random\n",
    "from graph_tool.all import shortest_distance, shortest_path\n",
    "\n",
    "from utils import edges2graph\n",
    "from feasibility import is_arborescence\n",
    "\n",
    "def gen_cascade(g, scale=1.0, source=None, stop_fraction=0.5, return_tree=False):    \n",
    "    rands = np.random.exponential(scale, g.num_edges())\n",
    "    delays = g.new_edge_property('float')\n",
    "    delays.set_2d_array(rands)\n",
    "\n",
    "    if source is None:\n",
    "        source = random.choice(np.arange(g.num_vertices()))\n",
    "\n",
    "    dist, pred = shortest_distance(g, source=source, weights=delays, pred_map=True)\n",
    "\n",
    "    q = stop_fraction * 100\n",
    "    percentile = np.percentile(dist.a, q)\n",
    "    infected_nodes = np.nonzero(dist.a <= percentile)[0]\n",
    "    uninfected_nodes = np.nonzero(dist.a > percentile)[0]\n",
    "\n",
    "    infection_times = np.array(dist.a)\n",
    "    infection_times[uninfected_nodes] = -1\n",
    "    \n",
    "    rets = (source, infection_times)\n",
    "    if return_tree:\n",
    "        tree_edges = set()\n",
    "        for n in infected_nodes:\n",
    "            c = n\n",
    "            while pred[c] != c:\n",
    "                edge = ((pred[c], c))\n",
    "                if edge not in tree_edges:\n",
    "                    tree_edges.add(edge)\n",
    "                else:\n",
    "                    break\n",
    "        tree = edges2graph(g, tree_edges)\n",
    "        rets += (tree, )\n",
    "    return rets\n",
    "\n",
    "for stop_fraction in np.arange(0.1, 1.0, 0.1):\n",
    "    for i in range(10):\n",
    "        source, infection_times, tree = gen_cascade(g, 1.0, source=None,\n",
    "                                                    stop_fraction=stop_fraction, return_tree=True)\n",
    "        assert infection_times[source] == 0\n",
    "        assert is_arborescence(tree)\n",
    "        np.testing.assert_almost_equal(np.count_nonzero(infection_times != -1) / g.num_vertices(),\n",
    "                                       stop_fraction, decimal=1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "np.testing.assert_almost_equal?"
   ]
  }
 ],
 "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
}