simplified_partial_crawls.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div style=\"text-align:center;\">\n",
    "<h1>Partial Crawls</h1>\n",
    "<h2>(Simplified -unofficial- version)</h2>\n",
    "</div>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "__author__ = \"Lisette Espin-Noboa\"\n",
    "__reference__ = \"\"\"\n",
    "[1] Inference in OSNs via Lightweight Partial Crawls. Konstantin Avrachenkov, Bruno Ribeiro and Jithin K. Sreedharan\n",
    "    https://github.com/jithin-k-sreedharan/HypRW\n",
    "    https://hal.inria.fr/hal-01403018/document\n",
    "    \n",
    "[2] Stochastic Gradient Descent for Relational Logistic Regression via Partial Network Crawls\n",
    "    https://arxiv.org/pdf/1707.07716.pdf\n",
    "\n",
    "[3] Should We Be Confident in Peer Effects Estimated From Social Network Crawls?    \n",
    "    https://www.aaai.org/ocs/index.php/ICWSM/ICWSM17/paper/viewFile/15696/14882\n",
    "                \"\"\"\n",
    "__license__ = \"GPL\"\n",
    "__version__ = \"1.0.3\"\n",
    "__maintainer__ = \"Lisette Espin-Noboa\"\n",
    "__email__ = \"Lisette.Espin@gesis.org\"\n",
    "__status__ = \"Developing\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "###############################################################################################\n",
    "# Warnings\n",
    "###############################################################################################\n",
    "import warnings\n",
    "warnings.filterwarnings(\"ignore\", message=\"numpy.dtype size changed\")\n",
    "warnings.filterwarnings(\"ignore\", message=\"numpy.ufunc size changed\")\n",
    "\n",
    "###############################################################################################\n",
    "# Dependencies\n",
    "###############################################################################################\n",
    "import numpy as np\n",
    "import pandas as pd\n",
    "import networkx as nx\n",
    "from collections import Counter"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "###############################################################################################\n",
    "# Functions\n",
    "###############################################################################################\n",
    "\n",
    "def random_walk_tour(g, n_tours, sn_size): \n",
    "    '''\n",
    "    Performs a Lightweight partial crawl (see [1] and [3])\n",
    "    Returns the super node, and the created tours.\n",
    "    1.) A super node is created by selecting sn_size random nodes from g\n",
    "    2.) A tour is created:\n",
    "    2.1) A random walker starts from a randomly-selected node (seed) from the super node\n",
    "    2.2) A random neighbor is selected and so-on.\n",
    "    2.3) The random walker stops, if it finds a node from the super node.\n",
    "    2.4) Repeat until gathering n_tours total tours.    \n",
    "    '''\n",
    "    np.random.seed(None)\n",
    "    \n",
    "    super_node = np.random.choice(list(g.nodes()),sn_size)\n",
    "    tours = []\n",
    "    \n",
    "    while len(tours) < n_tours:        \n",
    "        for seed in super_node:        \n",
    "            tour = [seed]\n",
    "            s = np.random.choice(g[seed],1)[0]\n",
    "\n",
    "            while s not in super_node:\n",
    "                tour.append(s)\n",
    "                nbrs = g[s]\n",
    "                if len(nbrs) > 0:\n",
    "                    s = np.random.choice(nbrs,1)[0]\n",
    "                else:\n",
    "                    break\n",
    "\n",
    "            tours.append(tour)\n",
    "        \n",
    "            if len(tours) >= n_tours:\n",
    "                break\n",
    "    \n",
    "    return super_node, tours   \n",
    "\n",
    "def get_priors(G, label, class_values, super_node, tours):\n",
    "    size = len(class_values)\n",
    "    n_tours = len(tours)\n",
    "    prior = pd.Series(np.zeros((size)), index=class_values)\n",
    "\n",
    "    ds = sum([G.degree(s) for s in super_node])\n",
    "    m = n_tours\n",
    "    for c in class_values:\n",
    "        sum_tours = sum([1/G.degree(v) for tour in tours for v in tour[1:] if G.node[v][label] == c])\n",
    "        sum_super_node = sum([1 for v in super_node if G.node[v][label] == c])\n",
    "        prior.loc[c] = ((ds/m) * sum_tours) + sum_super_node\n",
    "        \n",
    "    prior += 1  # smoothing\n",
    "    return prior / prior.sum() # normalizing\n",
    "\n",
    "def get_conditional_probabilities(G, label, class_values, super_node, tours):\n",
    "    columns = ['{}-{}'.format(l, l) for l in class_values]\n",
    "    cpn = {label: pd.DataFrame(np.zeros((len(class_values), len(columns))), index=class_values, columns=columns)}\n",
    "\n",
    "    n_tours = len(tours)\n",
    "    isu = not nx.is_directed(G)\n",
    "    condprobs = np.zeros((len(class_values), len(class_values)))\n",
    "    \n",
    "    ds = sum([G.degree(s) for s in super_node])\n",
    "    m = n_tours\n",
    "    \n",
    "    subgraph = G.subgraph(list(set(super_node) | set([node for tour in tours for node in tour])))\n",
    "        \n",
    "    for row, a in enumerate(class_values):  # ego class (condition)\n",
    "        for col, b in enumerate(class_values):  # neighbor class\n",
    "\n",
    "            sum_tours = sum([1 for tour in tours for t,v in enumerate(tour) if t >= 2 and G.node[tour[t-1]][label]==a and G.node[v][label]==b])\n",
    "            sum_super_node = sum([1 for edge in subgraph.edges() if edge[0] in super_node or edge[1] in super_node])\n",
    "            tmp = ((ds/m)*sum_tours) + sum_super_node\n",
    "            \n",
    "            cpn[label].loc[a, '{}-{}'.format(b, b)] += tmp\n",
    "\n",
    "            if isu and a != b:\n",
    "                # undirected and heterophilic edge then symmetric\n",
    "                cpn[label].loc[b, '{}-{}'.format(a, a)] += tmp\n",
    "\n",
    "    cpn[label] += 1  # smoothing\n",
    "    cpn[label] = cpn[label].div(cpn[label].sum(axis=1), axis=0) # normalizing\n",
    "    return cpn\n",
    "\n",
    "def get_class_priors(G, label, class_values, super_node, tours):    \n",
    "    '''\n",
    "    Returns the class prior estimates.\n",
    "    - P(m) probability of being a minority (class label m)\n",
    "    - P(M) probability of being a majority (class label M)\n",
    "    - P(m) + P(M) = 1    \n",
    "    \n",
    "    See Eq. 2 from [3].\n",
    "    '''\n",
    "    size = len(class_values)\n",
    "    n_tours = len(tours)    \n",
    "    prior = np.zeros(len(class_values))\n",
    "\n",
    "    ds = sum([G.degree(s) for s in super_node])\n",
    "    m = n_tours\n",
    "    for i,c in enumerate(class_values):\n",
    "        sum_tours = sum([1/G.degree(v) for tour in tours for v in tour[1:] if G.node[v][label] == c])\n",
    "        sum_super_node = sum([1 for v in super_node if G.node[v][label] == c])\n",
    "        prior[i] = ((ds/m) * sum_tours) + sum_super_node\n",
    "        \n",
    "    prior += 1  # smoothing\n",
    "    return prior / prior.sum() # normalizing\n",
    "\n",
    "def get_conditional_probabilities(G, label, class_values, super_node, tours):\n",
    "    '''\n",
    "    Returns the conditional probability estimates.\n",
    "    - P(m|m) probability of ego being a minority given that ego is connected to a minorty\n",
    "    - P(m|M) probability of ego being a minority given that ego is connected to a majority\n",
    "    - P(M|m) probability of ego being a majority given that ego is connected to a minorty\n",
    "    - P(M|M) probability of ego being a majority given that ego is connected to a majority    \n",
    "    - P(m|*) = 1\n",
    "    - P(M|*) = 1\n",
    "    \n",
    "    See Eq. 3, 4 from [3].\n",
    "    '''\n",
    "    n_tours = len(tours)\n",
    "    isu = not nx.is_directed(G)\n",
    "    condprobs = np.zeros((len(values),len(values)))    \n",
    "    \n",
    "    ds = sum([G.degree(s) for s in super_node])\n",
    "    m = n_tours\n",
    "    \n",
    "    subgraph = G.subgraph(list(set(super_node) | set([node for tour in tours for node in tour])))\n",
    "        \n",
    "    for i, a in enumerate(class_values):  # ego class (condition)\n",
    "        for j, b in enumerate(class_values):  # neighbor class\n",
    "\n",
    "            sum_tours = sum([1 for tour in tours for t,v in enumerate(tour) if t >= 2 and G.node[tour[t-1]][label]==a and G.node[v][label]==b])\n",
    "            sum_super_node = sum([1 for edge in subgraph.edges() if (edge[0] in super_node or edge[1] in super_node) and (G.node[edge[0]][label]==a and G.node[edge[1]][label]==b) ])\n",
    "            tmp = ((ds/m)*sum_tours) + sum_super_node\n",
    "            \n",
    "            condprobs[i,j] += tmp\n",
    "\n",
    "            if isu and a != b:\n",
    "                # undirected and heterophilic edge then symmetric\n",
    "                condprobs[j,i] += tmp\n",
    "\n",
    "    condprobs += 1  # smoothing    \n",
    "    return condprobs / condprobs.sum(axis=0)[:,None] # normalizing\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h2>Toy-Example</h2>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h3>1. Graph</h3>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Name: \n",
      "Type: Graph\n",
      "Number of nodes: 2000\n",
      "Number of edges: 3996\n",
      "Average degree:   3.9960\n"
     ]
    }
   ],
   "source": [
    "nnodes = 2000\n",
    "minedges = 2\n",
    "G = nx.barabasi_albert_graph(n=nnodes, m=minedges, seed=None)\n",
    "print(nx.info(G))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h3>2. Node attributes</h3>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "minority = int(round(G.number_of_nodes() * 10 / 100))\n",
    "minorities = np.random.choice(G.nodes(),minority)\n",
    "attributes = {n:'m' if n in minorities else 'M' for n in G.nodes()}\n",
    "label = 'group'\n",
    "values = ['M','m']\n",
    "nx.set_node_attributes(G,name=label,values=attributes)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h3>3. Partial Crawls</h3>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "- super_node size: 200\n",
      "- No. tours: 100\n",
      "- No. unique crawled nodes: 543 (27.0%)\n",
      "- Average tour size: 9.51\n",
      "- Min tour size: 1\n",
      "- Max tour size: 62\n"
     ]
    }
   ],
   "source": [
    "sn_size = int(round(G.number_of_nodes() * 10 / 100))\n",
    "n_tours = int(sn_size*0.5)\n",
    "\n",
    "super_node, tours = random_walk_tour(G, n_tours, sn_size)\n",
    "print('- super_node size: {}'.format(len(super_node)))\n",
    "print('- No. tours: {}'.format(len(tours)))\n",
    "n_crawled_nodes = len(set([n for tour in tours for n in tour]))\n",
    "print('- No. unique crawled nodes: {} ({}%)'.format(n_crawled_nodes,round(n_crawled_nodes*100/G.number_of_nodes(),0)))\n",
    "tour_sizes = [len(tour) for tour in tours]\n",
    "print('- Average tour size: {}'.format(np.mean(tour_sizes)))\n",
    "print('- Min tour size: {}'.format(min(tour_sizes)))\n",
    "print('- Max tour size: {}'.format(max(tour_sizes)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h3>4. Estimates</h3>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "M    0.898206\n",
       "m    0.101794\n",
       "dtype: float64"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tmp = get_class_priors(G, label, values, super_node, tours)\n",
    "pd.Series(tmp, index=values)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>M</th>\n",
       "      <th>m</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>M</th>\n",
       "      <td>0.812234</td>\n",
       "      <td>0.187766</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>m</th>\n",
       "      <td>0.959573</td>\n",
       "      <td>0.040427</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "          M         m\n",
       "M  0.812234  0.187766\n",
       "m  0.959573  0.040427"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tmp = get_conditional_probabilities(G, label, values, super_node, tours)\n",
    "pd.DataFrame(tmp, index=values, columns=values)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h3>5. Empirical</h3>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "M    0.906\n",
       "m    0.094\n",
       "dtype: float64"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tmp = Counter([a for n,a in attributes.items()])\n",
    "pd.Series([tmp[a] for a in values], index=values) / G.number_of_nodes()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>M</th>\n",
       "      <th>m</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>M</th>\n",
       "      <td>0.847936</td>\n",
       "      <td>0.152064</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>m</th>\n",
       "      <td>0.961783</td>\n",
       "      <td>0.038217</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "          M         m\n",
       "M  0.847936  0.152064\n",
       "m  0.961783  0.038217"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tmp = np.zeros((len(values),len(values)))\n",
    "counts = Counter(['{}-{}'.format(G.node[e[0]][label],G.node[e[1]][label]) for e in G.edges()])\n",
    "isu = not nx.is_directed(G)\n",
    "\n",
    "for r,v1 in enumerate(values):\n",
    "    for c,v2 in enumerate(values):\n",
    "        ec = counts['{}-{}'.format(v1,v2)]\n",
    "        tmp[r,c] += ec\n",
    "        \n",
    "        if isu and r!=c:\n",
    "            tmp[c,r] += ec\n",
    "    \n",
    "tmp = tmp/tmp.sum(axis=1, keepdims=True)\n",
    "pd.DataFrame(tmp, index=values, columns=values)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "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
}