08 graphs - 02 computation.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "76bc95e5",
   "metadata": {},
   "source": [
    "[![Binder](https://mybinder.org/badge_logo.svg)](https://notebooks.gesis.org/binder/v2/gh/jolin-io/fall-in-love-with-julia/main?filepath=08%20graphs%20-%2002%20computation.ipynb)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3b62a501",
   "metadata": {},
   "source": [
    "<a href=\"https://www.jolin.io\" target=\"_blank\" rel=\"noreferrer noopener\">\n",
    "<img src=\"https://www.jolin.io/assets/Jolin/Jolin-Banner-Website-v1.1-darkmode.webp\">\n",
    "</a>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b8bc0f13",
   "metadata": {},
   "source": [
    "# Fall-in-love-with-Julia: Graphs in Julia with Graphs.jl\n",
    "\n",
    "a 101 introduction session"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2791e056",
   "metadata": {},
   "outputs": [],
   "source": [
    "using Random; Random.seed!(2022);  # make sure this tutorial is reproducible"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5d0dd598",
   "metadata": {},
   "source": [
    "# Graphs.jl - Computations\n",
    "\n",
    "\"The project goal is to mirror the functionality of robust network and graph analysis libraries such as NetworkX.\" (https://github.com/JuliaGraphs/Graphs.jl)\n",
    "\n",
    "With `Graph` you can do many advanced computations which we are going to look into now "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "14d9d8a9",
   "metadata": {},
   "outputs": [],
   "source": [
    "using Graphs, GraphPlot, Plots"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "18cd507f",
   "metadata": {},
   "source": [
    "# Full example - global cascades on random networks\n",
    "\n",
    "Simple simulation how easy it for a post to go viral in a network. Known as Watts-model.\n",
    "Adapted from here https://nbviewer.org/github/JuliaGraphs/JuliaGraphsTutorials/blob/master/Watts-Model.ipynb"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ab7cb10b",
   "metadata": {},
   "outputs": [],
   "source": [
    "\"\"\"\n",
    "Computes the fraction of neighbors engaged within the neighborhood\n",
    "of a given node.\n",
    "\"\"\"\n",
    "function fraction_engaged(node::Int,\n",
    "                          G::Graph,\n",
    "                          engagement::BitVector)\n",
    "    num_engaged_neighbors = 0\n",
    "    for nbr in neighbors(G, node)\n",
    "        if engagement[nbr] == true\n",
    "            num_engaged_neighbors += 1\n",
    "        end\n",
    "    end\n",
    "    return num_engaged_neighbors / length(neighbors(G, node))\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "348a4796",
   "metadata": {},
   "outputs": [],
   "source": [
    "\"\"\"\n",
    "Updates the engagement of all vertices, one iteration only.\n",
    "\"\"\"\n",
    "function update_engagement!(G::Graph,\n",
    "                            engagement::BitVector,\n",
    "                            threshold::Float64)\n",
    "    for node in Random.shuffle(vertices(G))\n",
    "        if engagement[node] == false\n",
    "            if fraction_engaged(node, G, engagement) > threshold\n",
    "                engagement[node] = true\n",
    "            end\n",
    "        end\n",
    "    end\n",
    "\n",
    "    return nothing\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c3b03c4e",
   "metadata": {},
   "outputs": [],
   "source": [
    "import StatsBase\n",
    "\"\"\"\n",
    "Executes the simulation\n",
    "\n",
    "Output\n",
    "-----------\n",
    "A vector of number of engaged nodes at the end of each realization\n",
    "of the simulation\n",
    "\n",
    "Hyper Parameters of the model\n",
    "----------\n",
    "1. Number of nodes in the Watts-Strogatz graph (n)\n",
    "2. Average degree (z)\n",
    "3. Threshold (a specific value)\n",
    "4. Time steps for simulation to be run (T)\n",
    "5. Number of realizations\n",
    "\"\"\"\n",
    "function simulation(; n::Int, z::Int, threshold::Float64, T::Int, n_realizations::Int)\n",
    "    output = Vector{Int}(undef, n_realizations)\n",
    "    beta = z/n\n",
    "\n",
    "    for r in 1:n_realizations\n",
    "        G = watts_strogatz(n, z, beta)\n",
    "        # Select a single random node from the network and seed it\n",
    "        engagement = falses(nv(G))\n",
    "        engagement[StatsBase.sample(vertices(G))] = true\n",
    "\n",
    "        # Update the network for predefined number of time steps\n",
    "        for _ in 1:T\n",
    "            update_engagement!(G, engagement, threshold)\n",
    "        end\n",
    "        output[r] = sum(engagement)\n",
    "    end\n",
    "\n",
    "    return output\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3eb97b34",
   "metadata": {},
   "outputs": [],
   "source": [
    "n = 10^4\n",
    "z = 5\n",
    "threshold = 0.18\n",
    "T = 50\n",
    "n_realizations = 100"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d29816a2",
   "metadata": {},
   "outputs": [],
   "source": [
    "# !!CAUTION!!, this is a big plot which takes time to compute\n",
    "# and even after slows down your webpage significantly\n",
    "gplot(watts_strogatz(n, z, z/n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "eb52ef82",
   "metadata": {},
   "outputs": [],
   "source": [
    "data1 = simulation(; n, z, threshold, T, n_realizations)\n",
    "histogram(data1, xlab=\"Number of engaged nodes\", ylab=\"Frequency\", legend=false)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7c4d50bf",
   "metadata": {},
   "outputs": [],
   "source": [
    "z2 = 6;  # +1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "39f3f240",
   "metadata": {
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "data2 = simulation(; n, z=z2, threshold, T, n_realizations);\n",
    "histogram(data2, xlab=\"Number of engaged nodes\", ylab=\"Frequency\", legend=false)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1c78dd56",
   "metadata": {},
   "source": [
    "As can be seen from these two graphs, no global cascade occurs in the second case, while there are a few in the first! It is remarkable that just increasing the average degree of the network by 1 changes the entire outcome of the diffusion process.\n",
    "\n",
    "The code presented here can be used to reproduce all the results discussed in Watts (2002)."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0702d9f2",
   "metadata": {},
   "source": [
    "## 💪 it is your turn: Play with the above hyperparameters\n",
    "\n",
    "and see how the results change"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f23c76d3",
   "metadata": {},
   "source": [
    "# Predefined algorithms \n",
    "\n",
    "Provided by Graphs.jl:\n",
    "- [Path traversal](https://docs.juliahub.com/Graphs/VJ6vx/1.4.1/pathing/)\n",
    "- [Coloring](https://docs.juliahub.com/Graphs/VJ6vx/1.4.1/coloring/)\n",
    "- [Distance](https://docs.juliahub.com/Graphs/VJ6vx/1.4.1/distance/)\n",
    "- [Centrality measures](https://docs.juliahub.com/Graphs/VJ6vx/1.4.1/centrality/)\n",
    "- [Community structures](https://docs.juliahub.com/Graphs/VJ6vx/1.4.1/community/)\n",
    "- [Graph decomposition](https://docs.juliahub.com/Graphs/VJ6vx/1.4.1/degeneracy/)\n",
    "\n",
    "Provided by other packages:\n",
    "- [Matching](https://github.com/JuliaGraphs/GraphsMatching.jl)\n",
    "- [Network Interdiction](https://github.com/JuliaGraphs/LightGraphsExtras.jl)\n",
    "- [Partitioning](https://github.com/JuliaSparse/Metis.jl)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "23fa30df",
   "metadata": {},
   "source": [
    "# Parallel algorithms\n",
    "\n",
    "The following is a current list of parallel algorithms.\n",
    "```\n",
    "using Graphs\n",
    "import Graphs.Parallel\n",
    "```\n",
    "\n",
    "Centrality measures:\n",
    "- `Parallel.betweenness_centrality`\n",
    "- `Parallel.closeness_centrality`\n",
    "- `Parallel.pagerank`\n",
    "- `Parallel.radiality_centrality`\n",
    "- `Parallel.stress_centrality`\n",
    "\n",
    "Distance measures:\n",
    "- `Parallel.center`\n",
    "- `Parallel.diameter`\n",
    "- `Parallel.eccentricity`\n",
    "- `Parallel.radius`\n",
    "\n",
    "Shortest paths algorithms:\n",
    "- `Parallel.bellman_ford_shortest_paths`\n",
    "- `Parallel.dijkstra_shortest_paths`\n",
    "- `Parallel.floyd_warshall_shortest_paths`\n",
    "- `Paralell.johnson_shortest_paths`\n",
    "\n",
    "Traversal algorithms:\n",
    "- `Parallel.bfs`\n",
    "- `Parallel.greedy_color`\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8222008f",
   "metadata": {},
   "source": [
    "# Further example notebooks\n",
    "\n",
    "jupyter notebooks with focus on applying Graphs.jl (still referred to as LightGraphs.jl)\n",
    "- [DAG julia pkgs](https://nbviewer.org/github/JuliaGraphs/JuliaGraphsTutorials/blob/master/DAG-Julia-Pkgs.ipynb)\n",
    "- [The tipping point](https://nbviewer.org/github/JuliaGraphs/JuliaGraphsTutorials/blob/master/TheTippingPoint.ipynb)\n",
    "- [Talk of the network](https://nbviewer.org/github/JuliaGraphs/JuliaGraphsTutorials/blob/master/Talk-of-the-network.ipynb)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b6ae4a4c",
   "metadata": {},
   "source": [
    "# Thank you for joining\n",
    "\n",
    "for questions or suggestions please contact me at stephan.sahm@jolin.io"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a38342f7",
   "metadata": {},
   "source": [
    "<a href=\"https://www.jolin.io\" target=\"_blank\" rel=\"noreferrer noopener\">\n",
    "<img src=\"https://www.jolin.io/assets/Jolin/Jolin-Banner-Website-v1.1-darkmode.webp\">\n",
    "</a>"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Julia 1.7.1",
   "language": "julia",
   "name": "julia-1.7"
  },
  "language_info": {
   "file_extension": ".jl",
   "mimetype": "application/julia",
   "name": "julia",
   "version": "1.7.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}