controversy_score.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The autoreload extension is already loaded. To reload it, use:\n",
      "  %reload_ext autoreload\n"
     ]
    }
   ],
   "source": [
    "%matplotlib inline\n",
    "%load_ext autoreload\n",
    "%autoreload 2\n",
    "\n",
    "import pandas as pd\n",
    "import networkx as nx\n",
    "import ujson as json\n",
    "import metis\n",
    "import numpy as np\n",
    "import random\n",
    "from matplotlib import pyplot as plt\n",
    "from pprint import pprint\n",
    "from collections import Counter"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "dataset=\"circular\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "g = nx.read_gpickle('data/{}.gpkl'.format(dataset))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "50000\n"
     ]
    }
   ],
   "source": [
    "print(g.number_of_nodes())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def populate_r_and_c(g, pr, target_nodes, k):\n",
    "    \"\"\"\n",
    "    g: graph\n",
    "    pr: pagerank scores (dict)\n",
    "    targetr_nodes: list of nodes to consider\n",
    "    k: number of highest degree nodes to take\n",
    "    \n",
    "    return:\n",
    "    r: page rank score\n",
    "    c: node importance on target_nodes in terms of\n",
    "    \"\"\"\n",
    "    r = np.zeros(g.number_of_nodes())    \n",
    "    node2id = {n: i for i, n in enumerate(g.nodes_iter())}\n",
    "    for n in g.nodes_iter():\n",
    "        r[node2id[n]] = pr[n]\n",
    "    \n",
    "    # take highest degree nodes\n",
    "    top_nodes = sorted(target_nodes,\n",
    "                       key=lambda n: g.degree(n),\n",
    "                       reverse=True)[:k]\n",
    "    c = np.zeros(g.number_of_nodes())\n",
    "    for n in top_nodes:\n",
    "        c[node2id[n]] = 1\n",
    "    return r, c\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def controversy_score(g, top_percent=0.001):\n",
    "    \"\"\"consider only two sides only\n",
    "    top_percent: percentage of high degree nodes to consider for the c vector \n",
    "    \"\"\"\n",
    "    k = int(g.number_of_nodes() * top_percent)\n",
    "    assert k > 0\n",
    "    print('k={}'.format(k))\n",
    "    cuts, parts = metis.part_graph(g)\n",
    "    aux = lambda p, target: int(target == p)\n",
    "    \n",
    "    # personalization vector\n",
    "    part_sizes = Counter(parts)\n",
    "    e_0 = {n: aux(p, 0) / part_sizes[0] for n, p in zip(g.nodes(), parts)}\n",
    "    e_1 = {n: aux(p, 1) / part_sizes[1] for n, p in zip(g.nodes(), parts)}\n",
    "\n",
    "    # pagerank scores\n",
    "    pr0 = nx.pagerank(g, alpha=0.85, personalization=e_0, dangling=e_0, max_iter=10000)\n",
    "    pr1 = nx.pagerank(g, alpha=0.85, personalization=e_1, dangling=e_1, max_iter=10000)\n",
    "\n",
    "    # nodes at two sides\n",
    "    nodes0 = [n for n, p in zip(g.nodes(), parts) if p == 0]\n",
    "    nodes1 = [n for n, p in zip(g.nodes(), parts) if p == 1]\n",
    "\n",
    "    r0, c0 = populate_r_and_c(g, pr0, nodes0, k)\n",
    "    r1, c1 = populate_r_and_c(g, pr1, nodes1, k)\n",
    "    \n",
    "    r_list = [r0, r1]\n",
    "    c_list = [c0, c1]\n",
    "    controversy, non_controversy = 0, 0\n",
    "    k = len(r_list)\n",
    "    for i, r in enumerate(r_list):\n",
    "        for j, c in enumerate(c_list):\n",
    "            prod = np.sum(r * c)\n",
    "            # print(prod, prod * part_sizes[i])\n",
    "            if i == j:\n",
    "                controversy += prod\n",
    "            else:\n",
    "                non_controversy += prod\n",
    "    print(controversy, non_controversy)\n",
    "    return controversy / (controversy + non_controversy)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "k=50\n",
      "0.00343846776375 0.000561532236253\n",
      "0.859616940937\n"
     ]
    }
   ],
   "source": [
    "print(controversy_score(g))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "k=28\n",
      "k=56\n",
      "k=93\n",
      "k=50\n",
      "0.00343846776375 0.000561532236253\n",
      "k=2\n",
      "0.387652790091 0.0509276973833\n",
      "k=50\n",
      "0.282845642967 0.0388647300526\n",
      "k=50\n",
      "0.050028412602 0.0393195924934\n",
      "0.471745134496 0.471147206782\n",
      "0.462045118917 0.103348028087\n",
      "0.00397886921661 2.2829080248e-05\n"
     ]
    }
   ],
   "source": [
    "from joblib import Parallel, delayed\n",
    "datasets = ['beefban', 'ukraine', 'baltimore', 'circular', 'barbell_1000_0', 'barabasi', 'star']\n",
    "scores = Parallel(n_jobs=4)(delayed(controversy_score)(nx.read_gpickle('data/{}.gpkl'.format(dataset)))\n",
    "                           for dataset in datasets)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "- barbell_1000_0: 0.9942951520693315\n",
      "- beefban: 0.8838806129369029\n",
      "- ukraine: 0.8791934195724288\n",
      "- circular: 0.8596169409366637\n",
      "- baltimore: 0.8172103276545415\n",
      "- barabasi: 0.5599275837061325\n",
      "- star: 0.5003170710418742\n"
     ]
    }
   ],
   "source": [
    "for d, s in sorted(list(zip(datasets, scores)), key=lambda t: t[1], reverse=True):\n",
    "    print('- {}: {}'.format(d, s))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from rwc import controversy_score as f\n",
    "# print(f(g))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(0.5, {'pr0': None, 'pr1': None})"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "g = nx.star_graphr_graph(1000)\n",
    "\n",
    "node2cluster = {n: 0 for n in g.nodes()}\n",
    "f(g, node2cluster)"
   ]
  }
 ],
 "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": 0
}