Talk-of-the-network.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Note: In this workbook, we try to replicate the results from the classic paper \"Talk of the Network: A Complex Systems Look at the Underlying Process of Word-of-Mouth\", Goldenberg, Libai and Muller (2001). This is a self-didactic attempt.*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "using Distributions\n",
    "using MetaGraphs\n",
    "using DataFrames\n",
    "using GLM"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "MersenneTwister(UInt32[0x01332bfa], Base.dSFMT.DSFMT_state(Int32[-1772545288, 1073534108, 1077066014, 1072915095, -2146195133, 1072843413, 301764553, 1073404181, 750472136, 1073628106  …  -1491411563, 1073194977, 716119449, 1072893711, 1632331784, 758890923, 1433693833, -13012230, 382, 0]), [1.69558, 1.71546, 1.04527, 1.31036, 1.89552, 1.02364, 1.02657, 1.08113, 1.40426, 1.11619  …  1.01145, 1.26206, 1.83416, 1.11714, 1.57422, 1.77415, 1.06611, 1.98561, 1.84126, 1.25505], 382)"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "srand(20130810)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 1. Introduction \n",
    "\n",
    "In [Talk of the Network](https://www0.gsb.columbia.edu/mygsb/faculty/research/pubfiles/3391/TalkofNetworks.pdf), the authors  explore the pattern of personal communication betwee an individual's core friends group (strong ties) and a wider set of acquaintances (weak ties). This remarkable study is one of the first ones in marketing that explored the influence of social networks on the diffusion of marketing messages. The key questions investigated in the context of information dissemination are:\n",
    "\n",
    "- What matters more - strong ties or weak ties?\n",
    "- What effect does the size of an average individuals network have?\n",
    "- How does advertising interact with the diffusion through weak ties and that through strong ties\n",
    "\n",
    "In this workbook, we focus on the first question: do strong ties or weak ties influence the speed of information dissemination in a network?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 2. Initializing the network"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Since this study employs a set of synthetic networks, where each of the nodes have a fixed number of strong ties ($s$) and weak ties ($w$), we need to use the `MetaGraph` types to build these networks. We initialize the network as an empty graph and then build the neighborhoods of individual nodes by adhering to the number of strong and weak ties for each node."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "initialize_network (generic function with 1 method)"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "function initialize_network(n_nodes::Int, n_strong_ties::Int, n_weak_ties::Int)\n",
    "    \n",
    "    # Initialize an empty network\n",
    "    \n",
    "    mg = MetaGraph(n_nodes)\n",
    "    nodes = 1:n_nodes\n",
    "    \n",
    "    for node in nodes\n",
    "        set_props!(mg, node, Dict(:weak_ties => Int[],\n",
    "                                  :strong_ties => Int[],\n",
    "                                  :status => false,\n",
    "                                  :activation_prob => 0.0))\n",
    "    end\n",
    "    \n",
    "    # Wire the network according to the number of strong and weak ties\n",
    "    # When wiring with random nodes, take care that the subject node and\n",
    "    # already existing neighbors are not sampled again\n",
    "    \n",
    "    for node in nodes\n",
    "        while length(get_prop(mg, node, :weak_ties)) < n_weak_ties\n",
    "            rand_nbr = sample(nodes[1:end .!= node])\n",
    "            if !(rand_nbr in get_prop(mg, node, :weak_ties) || rand_nbr in get_prop(mg, node, :strong_ties))\n",
    "                append!(get_prop(mg, node, :weak_ties), rand_nbr)\n",
    "            end\n",
    "        end\n",
    "        while length(get_prop(mg, node, :strong_ties)) < n_strong_ties\n",
    "            rand_nbr = sample(nodes[1:end .!= node])\n",
    "            if !(rand_nbr in get_prop(mg, node, :weak_ties) || rand_nbr in get_prop(mg, node, :strong_ties))\n",
    "                append!(get_prop(mg, node, :strong_ties), rand_nbr)\n",
    "            end\n",
    "        end\n",
    "    end\n",
    "    \n",
    "    return mg\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "empty undirected Int64 metagraph with Float64 weights defined by :weight (default weight 1.0)"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "g = initialize_network(3000, 5, 5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 3. Model\n",
    "\n",
    "## 3.1 Assumptions\n",
    "\n",
    "Each individual in the substrate network (referred to as nodes) are connected to the same number of strong ties (varied from 5 - 29) and weak ties (varied from 5 - 29). The probability of activation of a node, i.e., an uninformed individual turning to informed can happen in three ways: through a strong tie with probability $\\beta_s$, through a weak tie with probability $\\beta_w$ or through external marketing efforts with probability $\\alpha$. In line with conventional wisdom, we assume $\\alpha < \\beta_w < \\beta_s$. \n",
    "\n",
    "At timestep $t$, if an individual is connected to $m$ strong ties and $j$ weak ties, the probability of the individual being informed in this time step is:\n",
    "\n",
    "$$\n",
    "p(t) = 1 - (1- \\alpha)(1 - \\beta_w)^j(1 - \\beta_s)^m\n",
    "$$\n",
    "\n",
    "We are interested in two outcome variables:\n",
    "1. The number of time steps elapsed till 15% of the network engages \n",
    "2. The number of time steps elapsed till 95% of the network engages"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3.2 Execution\n",
    "\n",
    "*Step 1:* At $t = 0$, the status of all nodes is set to `false`\n",
    "\n",
    "*Step 2:* For each node, the probability of being informed is calculated as per the above equation. A random draw $U$ is made from a standard uniform distribution and compared with the probability. If $U < p(t)$ the status of the node is changed to `true`\n",
    "\n",
    "*Step 3:* In each successive time step, Step 2 is repeated till 95% of the total network (of size 3000) engages"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We now look at several helper functions that execute the above logic\n",
    "\n",
    "### 3.2.1 Reset node status\n",
    "\n",
    "At the beginning of each simulation, we call the following function to set the status of all the nodes to `false`. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "function reset_node_status!(G::MetaGraphs.MetaGraph, n_nodes::Int)\n",
    "    for node in 1:n_nodes\n",
    "        set_prop!(G, node, :status, false)\n",
    "    end\n",
    "    return nothing\n",
    "end"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.2.2 Activation probability\n",
    "\n",
    "At each time step, the probabilty of activation for each node is calculated using the following function. We count the number of activated strong and weak ties for each node and use the above formula to compute the activation probability."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "function update_activation_prob!(G::MetaGraphs.MetaGraph, node::Int, alpha::Float64, beta_w::Float64, beta_s::Float64)\n",
    "    n_active_weak_ties, n_active_strong_ties = 0, 0\n",
    "\n",
    "    for weak_tie in get_prop(G, node, :weak_ties)\n",
    "        if get_prop(G, weak_tie, :status) == true\n",
    "            n_active_weak_ties += 1\n",
    "        end\n",
    "    end\n",
    "\n",
    "    for strong_tie in get_prop(G, node, :strong_ties)\n",
    "        if get_prop(G, strong_tie, :status) == true\n",
    "            n_active_strong_ties += 1\n",
    "        end\n",
    "    end\n",
    "\n",
    "    set_prop!(G, node, :activation_prob, \n",
    "              1 - (1 - alpha) * (1 - beta_w)^n_active_weak_ties * (1 - beta_s)^n_active_strong_ties)\n",
    "    \n",
    "    return nothing\n",
    "end"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.2.3 Update node status\n",
    "\n",
    "At each time step the status of all the nodes is updated according to the calculated probability of activation. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "function update_status!(G::MetaGraphs.MetaGraph, n_nodes::Int, alpha::Float64, beta_w::Float64, beta_s::Float64)\n",
    "    nodes = 1:n_nodes\n",
    "    \n",
    "    # assuming that the nodes update in random order\n",
    "    \n",
    "    for node in shuffle(nodes)\n",
    "        update_activation_prob!(G, node, alpha, beta_w, beta_s)\n",
    "        \n",
    "        if rand(Uniform()) < get_prop(G, node, :activation_prob)\n",
    "            set_prop!(G, node, :status, true)\n",
    "        end\n",
    "    end\n",
    "    \n",
    "    return nothing\n",
    "end"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.2.4 Simulation on the parameter space\n",
    "\n",
    "The function `execute_simulation` puts together the scaffolding to set up the parameter space $(s, w, \\alpha, \\beta_w, \\beta_s)$ and execute diffusion along the network. From what I can gather from the paper, one simulation was carried out at each point on the parameter space. No further details regarding the execution are mentioned except that since each parameter has 7 levels, a total of $7^5 = 16,808$ simulations were executed in a factorial design. In this workbook, we work on a smaller sized parameter space with 3 levels for illustration.\n",
    "\n",
    "Also, I am assuming that the network is drawn at random for each run of the simulation.\n",
    "\n",
    "One more interesting information: The authors mention that their simulations were written in C, it would be interesting to compare the execution times with Julia. This is a non-standard problem that tests both the robustness of Julia types and its execution speed (maybe this will prompt someone to make a pull request!)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "println(\"Number of strong ties per node (s): \", floor.(Int, linspace(5, 29, 3)))\n",
    "println(\"Number of weak ties per node(w): \", floor.(Int, linspace(5, 29, 3)))\n",
    "println(\"Effect of advertising (α): \", collect(linspace(0.0005, 0.01, 3)))\n",
    "println(\"Effect of weak ties (β_w): \", collect(linspace(0.005, 0.015, 3)))\n",
    "println(\"Effect of strong ties (β_s): \", collect(linspace(0.01, 0.07, 3)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "parameter_space = [(s, w, alpha, beta_w, beta_s) for s in floor.(Int, linspace(5, 29, 3)), \n",
    "                                                     w in floor.(Int, linspace(5, 29, 3)),\n",
    "                                                     alpha in linspace(0.0005, 0.01, 3),\n",
    "                                                     beta_w in linspace(0.005, 0.015, 3),\n",
    "                                                     beta_s in linspace(0.01, 0.07, 3)]\n",
    "\n",
    "size(parameter_space), length(parameter_space)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "function execute_simulation(parameter_space, n_nodes::Int)\n",
    "    \n",
    "    # n_nodes dictates how big the network will be\n",
    "    # We cannot pre-allocate the output since we do not know for how many time steps the simulation will\n",
    "    # run at each setting\n",
    "    \n",
    "    output = DataFrame(s = Int[], w = Int[], alpha = Float64[], \n",
    "                       beta_w = Float64[], beta_s = Float64[], \n",
    "                       t = Int[], num_engaged = Int[])\n",
    "\n",
    "\n",
    "    # Rewiring the network each time is expensive. We can cut down repeats of the same rewiring process\n",
    "    # by building the network only when the parameters used to build the network have changed.\n",
    "    \n",
    "    old_s, old_w = parameter_space[1][1:2]\n",
    "    G = initialize_network(n_nodes, old_s, old_w)\n",
    "    \n",
    "    for (s, w, alpha, beta_w, beta_s) in parameter_space[1:end]\n",
    "        \n",
    "        # Rewire the network only if the network creation parameters have changed\n",
    "  \n",
    "        if !(old_s == s && old_w == w)\n",
    "            G = initialize_network(n_nodes, s, w)\n",
    "        end\n",
    "        reset_node_status!(G, n_nodes)\n",
    "        \n",
    "        println(\"Beginning simulation on setting $((s, w, alpha, beta_w, beta_s)) at : \", Dates.format(now(), \"HH:MM\"))\n",
    "        \n",
    "        num_engaged = sum([get_prop(G, node, :status) for node in 1:n_nodes])\n",
    "        t = 1\n",
    "        \n",
    "        # Continue updates at each setting till 95% of the network engages\n",
    "        \n",
    "        while num_engaged < Int(0.95 * n_nodes)\n",
    "            update_status!(G, n_nodes, alpha, beta_w, beta_s)\n",
    "            num_engaged = sum([get_prop(G, node, :status) for node in 1:n_nodes])\n",
    "            push!(output, [s, w, alpha, beta_w, beta_s, t, num_engaged])\n",
    "            t += 1\n",
    "        end\n",
    "    \n",
    "        old_s, old_w = s, w\n",
    "    end\n",
    "    \n",
    "    return output\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "@time results = execute_simulation(parameter_space, 3000)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 4. Discussion\n",
    "\n",
    "To answer the research questions, the authors resort to simple linear regression. \n",
    "\n",
    "Since our focus in this workbook is on highlighting the strengths of the JuliaGraphs ecosystem, we keep the regression modeling at the most basic level. So, we replicate the linear model in the paper only for for the time till 95% of the network engages.\n",
    "\n",
    "The features used to predict these outcomes are $s$, $w$, $\\alpha$, $\\beta_w$ and $\\beta_S$. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "head(results)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To build the data required for the linear modeling, we group the data by each parameter setting and calculate the time the network takes to reach 95% activation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "all_engaged = by(results, [:s, :w, :alpha, :beta_w, :beta_s], df -> DataFrame(T95 = maximum(df[:t])));\n",
    "head(all_engaged)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We then run a simple linear model on the data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "ols = lm(@formula(T95 ~ s + w + alpha + beta_s + beta_w), all_engaged)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "These results indicate that both strong ties and weak ties have an equally important role in the speedy diffusion of information. As the authors note, this happens despite the inferiority of the weak ties parameter in the model assumptions."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Julia 0.7.0",
   "language": "julia",
   "name": "julia-0.7"
  },
  "language_info": {
   "file_extension": ".jl",
   "mimetype": "application/julia",
   "name": "julia",
   "version": "0.6.2"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}