01-structural-imbalance-overview.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Structural Imbalance with the D-Wave System\n",
    "In the [structural imbalance demo](https://cloud.dwavesys.com/leap/demos/socialnetwork/) you saw how Juliet’s new love of Romeo introduced imbalance into the social network of Verona.   \n",
    "<img src=\"images/Romeo.png\" width=250x/>\n",
    "\n",
    "This notebook examines how you can solve optimization problems on a  D-Wave quantum processing unit (QPU) with the example of a structural imbalance problem.\n",
    "\n",
    "1. [What is Structural Imbalance?](#What-is-Structural-Imbalance?) defines and explains the structural imbalance problem.\n",
    "2. [Formulating the Problem](#Formulating-the-Problem-for-a-D-Wave-System) shows how such optimization problems can be formulated for solution on a quantum computer. \n",
    "3. [A Toy Example](#A-Toy-Example) codes a small structural imbalance problem to demonstrate the solution technique. \n",
    "3. [A Real-World Example](#A-Real-World-Example) applies the solution to the data sets of the Stanford Militants Mapping Project.\n",
    "\n",
    "This notebook should help you understand both the techniques and [Ocean software](https://github.com/dwavesystems) tools used for solving optimization problems on D-Wave quantum computers."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**New to Jupyter Notebooks?** JNs are divided into text or code cells. Pressing the **Run** button in the menu bar moves to the next cell. Code cells are marked by an \"In: \\[\\]\" to the left; when run, an asterisk displays until code completion: \"In: \\[\\*\\]\"."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# What is Structural Imbalance?\n",
    "Let's first define the problem of estimating structural imbalance for real-world social networks.\n",
    "\n",
    "*Social networks* map relationships between people or organizations onto graphs, with\n",
    "the people/organizations as nodes and relationships as edges; for example,\n",
    "Facebook friends form a social network. *Signed social networks* map both friendly and\n",
    "hostile relationships by assigning to edges either positive or negative values. Such networks are said to be *structurally balanced* when they can be cleanly divided into two sets, with each set containing only friends, and all relations between these sets are hostile. The measure of *structural imbalance* or *frustration* for a signed social network, when it cannot be cleanly divided, is the minimum number of edges that violate the social rule, “the enemy of my friend is my enemy.”\n",
    "\n",
    "Finding a division that minimizes frustration is an NP-hard graph problem (it can be viewed as an expansion of the well-known [maximum cut](https://en.wikipedia.org/wiki/Maximum_cut) problem). This is an example of a broad class of optimization problems well-suited to solution on D-Wave systems. Other examples include protein folding, traffic flow optimization, job-shop scheduling, and many more.  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Formulating the Problem for a D-Wave System\n",
    "How can we formulate this problem for a D-Wave quantum computer to solve? \n",
    "\n",
    "D-Wave systems solve Ising problems: given $N$ variables $s_1,...,s_N$, where each variable $s_i$ can have values $-1$ or $+1$, the system finds assignments of values that minimize \n",
    "\n",
    "  $\\sum_{i=1}^N h_i s_i +\n",
    "  \\sum_{i<j}^N J_{i,j} s_i s_j$,\n",
    "\n",
    "where $h_i$ and $J_{i,j}$ are configurable (linear and quadratic) coefficients. To formulate a problem for the D-Wave system is to program $h_i$ and $J_{i,j}$ so that assignments of $s_1, ..., s_N$ that minimize this summation also represent solutions to the problem. \n",
    "\n",
    "In our case, variables $s_i$ can represent people, with values $-1,+1$ denoting a person's assignment to one of the two sets we want to divide the social network into. If we set $J_{i,j}$ to $-1$ for friendly $s_is_j$ pairs and $+1$ for hostile pairs, their multiplication takes values\n",
    "\n",
    "$J_{i,j} s_i s_j=\n",
    "\\begin{cases} \n",
    "      -1 & \\text{friends in same set (} s_i=s_j \\text{) or enemies in different sets ($s_i \\ne s_j$)} \\\\\n",
    "      +1 & \\text{friends in different sets ($s_i \\ne s_j$) or enemies in same set ($s_i=s_j$)} \n",
    "\\end{cases}\n",
    "$\n",
    "\n",
    "The summation $\\sum_{i<j}^N J_{i,j} s_i s_j$ now decrements when an assignment contributes to balance and increments when it contributes to frustration.\n",
    "\n",
    "You can see this in the graphic below, which shows all possible combinations of a two-nodes signed social network. People in the $-1$ set are shown as yellow dots, the $+1$ set as blue dots. Friendly relationships are shown as green edges, hostile as red. \n",
    "\n",
    "<img src=\"images/TwoNodes_AllCombinations.png\" width=450x/>\n",
    "\n",
    "If we set $h_i=0$, the Ising model is just $\\sum_{i<j}^N J_{i,j} s_i s_j$. Programmed with these coefficients for a given signed social network, the quantum computer finds partitions (assignments of $s_i$) that minimize frustration. \n",
    "\n",
    "This is an example of a technique called a *penalty model*, where a problem is formulated so that undesired outcomes are penalized by being assigned higher values in the term being minimized. D-Wave documentation describes this and various other techniques for formulating optimization problems for solution on the quantum computer."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## A Toy Example\n",
    "\n",
    "The code in this section demonstrates the use of Ocean software on a small social network. The next section implements the solution on a real-world problem. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The first code cell creates a K4 complete social graph (each one of four people is connected to the other three). Relationships between the four are set randomly to friend or enemy each time you execute the code (by pressing the **Run** button with your mouse in the cell--try it a few times). "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Use NetworkX graphic package and Python's random library to create a randomly signed network\n",
    "import networkx as nx\n",
    "import random\n",
    "# Create a K4 complete graph (default node labels are indexical from 0)\n",
    "G = nx.complete_graph(4)\n",
    "# Randomly assign +1 or -1 relationship signs to all edges. Rename node 0 to Alice, 1 to Bob, etc\n",
    "G.add_edges_from([(u, v, {'sign': 2*random.randint(0, 1)-1}) for u, v in G.edges])\n",
    "nx.relabel_nodes(G, {0: 'Alice', 1: 'Bob', 2: 'Eve', 3: 'Wally'}, copy=False)\n",
    "\n",
    "# Print the relationships assigned by the current code execution\n",
    "print('Friendly relationships: ', [(x, y) for (x, y, sign) in G.edges(data='sign') if (sign == 1)])\n",
    "print('Hostile relationships: ', [(x, y) for (x, y, sign) in G.edges(data='sign') if (sign == -1)])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Setting Up a Solver\n",
    "Typically when working with a D-Wave system, you configure a default solver and its SAPI URL with your API token and that configuration is used implicitly. Occasionally you may wish to override a default and specify particular solver settings.\n",
    "\n",
    "The cell below displays your default solver configuration. The next cell allows you to explicitly select a solver and API token."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# To see helper functions, select Jupyter File Explorer View from the Online Learning page\n",
    "from helpers.solvers import default_solver\n",
    "my_solver, my_token = default_solver()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Uncomment if you need to paste in a solver and/or token\n",
    "# my_solver = 'paste your solver in here'\n",
    "# my_token = 'paste your token in here'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Your default or manually set solver and token are used in the next cell. The cell sets a *sampler*, the component used to find variable values that minimize the Ising model representing our problem. Here we use a D-Wave system but Ocean tools are designed to swap in and out samplers with ease. For example you might first run a classical sampler on your computer's CPU during testing, and only once your code is ready, submit the problem for solution on the quantum computer.   \n",
    "\n",
    "*DWaveSampler()* from Ocean software's [dwave-system](https://docs.ocean.dwavesys.com/projects/system/en/latest/) tool handles the connection to a D-Wave system. This tool also handles mapping between the graph of our problem, NetworkX's *complete_graph(4)* graph with nodes labeled Alice, Bob etc, to the D-Wave QPU's numerically indexed qubits. This mapping, known as *minor-embedding*, is done by the *EmbeddingComposite()* composite.   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Select a D-Wave system and handle mapping from problem graph to sampler graph\n",
    "from dwave.system.samplers import DWaveSampler\n",
    "from dwave.system.composites import EmbeddingComposite\n",
    "\n",
    "sampler = EmbeddingComposite(DWaveSampler(solver=my_solver, token=my_token))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solving the Problem\n",
    "Next, the *structural_imbalance()* algorithm, from Ocean's [dwave_networkx](https://docs.ocean.dwavesys.com/projects/dwave-networkx/en/latest/) extension of the NetworkX graphic package, submits the Ising model we formulated in the previous section to a D-Wave system. It returns a partition of our social network into two colored sets and the frustrated edges."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Return a good partition (minimal structural imbalance) and its frustrated edges  \n",
    "import dwave_networkx as dnx\n",
    "imbalance, bicoloring = dnx.structural_imbalance(G, sampler)\n",
    "\n",
    "# Mark the returned frustrated edges and node set (color) on the graph \n",
    "for edge in G.edges:\n",
    "    G.edges[edge]['frustrated'] = edge in imbalance\n",
    "for node in G.nodes:\n",
    "    G.nodes[node]['color'] = bicoloring[node]\n",
    "\n",
    "# Print the relationships for the returned partition\n",
    "print('Yellow set: ', [person for (person, color) in bicoloring.items() if (color == 0)])\n",
    "print('Blue set: ', [person for (person, color) in bicoloring.items() if (color == 1)])\n",
    "print('\\nFrustrated relationships: ', list(imbalance.keys()))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Display the solution using a *draw()* function that represents friendly interactions as green lines, hostile interactions as red lines, and frustration as dashed lines."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from helpers.draw import draw\n",
    "draw(G, with_labels=True);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You can rerun the cells of this section to produce different random relationships and display different imbalances.\n",
    "\n",
    "The steps used in this section can solve the structural imbalance problem for other signed social networks. Some coding will be needed to load the social network into a NetworkX graph with signed edges, which is standard software work of converting data between formats. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# A Real-World Example\n",
    "Next we expand to the large data sets of the [Stanford Militants Mapping Project](http://web.stanford.edu/group/mappingmilitants/cgi-bin/)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Load data from the Stanford Militants Mapping Project into NetworkX graph G\n",
    "from helpers.loader import global_signed_social_network\n",
    "G = global_signed_social_network()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's first calculate imbalance on a selected region and time period, Syria 2013, by filtering on these attributes of the data now in graph G."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Select the Syria subregion by creating subgraph S from the full data set G\n",
    "syria_groups = set()\n",
    "for v, data in G.nodes(data=True):\n",
    "    if 'map' not in data:\n",
    "        continue\n",
    "    if data['map'] in {'Syria', 'Aleppo'}:\n",
    "        syria_groups.add(v)\n",
    "S = G.subgraph(syria_groups)\n",
    "\n",
    "# Filter by year\n",
    "year = 2013\n",
    "filtered_edges = ((u, v) for u, v, a in S.edges(data=True) if a['event_year'] <= year)\n",
    "S = S.edge_subgraph(filtered_edges)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The graph we created has nodes representing militant groups, with indexical labels, and edges with a \"sign\" attribute marking friendly or hostile relationships."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# See data associated with nodes (first two nodes only for brevity)\n",
    "list(S.nodes(data=True))[:2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# See data associated with edges (first two)\n",
    "list(S.edges(data=True))[:2]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Display the solution using the *draw()* function that represents friendly interactions as green lines, hostile interactions as red lines. Move your mouse over edges to see attributes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "position = draw(S)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As in the previous section, Ocean suite's *dwave_networkx* calculates the frustration of the network on a D-Wave system. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Return a good partition of the Syrian 2013 network and its frustrated edges \n",
    "imbalance, bicoloring = dnx.structural_imbalance(S, sampler)\n",
    "# Annotate the network with the returned frustrated edges and node sets\n",
    "for edge in S.edges:\n",
    "    S.edges[edge]['frustrated'] = edge in imbalance\n",
    "for node in S.nodes:\n",
    "    S.nodes[node]['color'] = bicoloring[node]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The next two cells let you see the updates made to the graph."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Nodes now have a group bicoloring\n",
    "list(S.nodes(data=True))[:2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Edges now have a marking indicating whether they are frustrated or not\n",
    "list(S.edges(data=True))[:2]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Redraw the network with the previous node positioning: nodes are now bicolored and dashed lines indicate frustrated edges."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "draw(S, position);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Redraw the network with a new positioning that separates the two sets."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Frustrated edges now stand out\n",
    "draw(S);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Summary\n",
    "Structural imbalance for social networks is a problem well suited for solving on the D-Wave system: unlike factoring, where typically large integer variables must be converted to even larger binary variables, this problem's structure of bi-valued variables in a typically sparse graph of quadratic relationships is close to a native Ising problem.\n",
    "\n",
    "We saw how to mathematically formulate an Ising model to represent this problem using the technique of a penalty model, which is used to solve a wide variety of optimization problems on the quantum computer. We then used Ocean tools to formulate the problem and submit it for solution.   "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Finally, the following cell attempts to calculate structural imbalance on the entire data set of the Stanford Militants Mapping Project, which has over 200 variables. Consider the following:\n",
    "\n",
    "* Minor-embedding, performed by the *EmbeddingComposite()* composite, is heuristic and **might fail for a particular run**. If your submission fails, try running the cell again or cut the number of nodes a little closer to 200.\n",
    "* The heuristic minor-embedding used by this code might not reliably represent such a large problem, and consequently solutions might not be optimal. Embedding such problems requires more advanced techniques that are beyond the scope of this demo.  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Try to solve the structural imbalance problem on the entire database\n",
    "imbalance, bicoloring = dnx.structural_imbalance(G, sampler)\n",
    "for edge in G.edges:\n",
    "    G.edges[edge]['frustrated'] = edge in imbalance\n",
    "for node in G.nodes:\n",
    "    G.nodes[node]['color'] = bicoloring[node]\n",
    "draw(G);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For a submission on June 4, 2018 (238 variables in the database), the minor-embedding of the entire database required about half the QPU's qubits:\n",
    "\n",
    "<img src=\"images/EmbeddingFullDB.png\" width=400x/>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ocean software provides tools for formulating many types of problems for solution on a QPU and the D-Wave documentation describes various techniques for formulating problems. Check out D-Wave's Ocean suite of tools on [GitHub](https://github.com/dwavesystems) and  [Read the Docs](https://docs.ocean.dwavesys.com/en/latest/).     "
   ]
  }
 ],
 "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.6.4"
  },
  "latex_envs": {
   "LaTeX_envs_menu_present": true,
   "autoclose": false,
   "autocomplete": true,
   "bibliofile": "biblio.bib",
   "cite_by": "apalike",
   "current_citInitial": 1,
   "eqLabelWithNumbers": true,
   "eqNumInitial": 1,
   "hotkeys": {
    "equation": "Ctrl-E",
    "itemize": "Ctrl-I"
   },
   "labels_anchors": false,
   "latex_user_defs": false,
   "report_style_numbering": false,
   "user_envs_cfg": false
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": false,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {
    "height": "calc(100% - 180px)",
    "left": "10px",
    "top": "150px",
    "width": "202px"
   },
   "toc_section_display": true,
   "toc_window_display": true
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}