There are many different strategies for immunizing populations in order to prevent transmission of a virus or an infectious disease with a minimal number of doses. One such strategy, outlined in [1], is to fragment a population into separate groups via a "separator". This strategy partitions a population into two large groups of similar size and a third group that serves as the separator. The separator is chosen so that all connections between the two larger groups pass through it, and should be kept as small as possible. In this scenario, removing the separator from the population disconnects the two large groups, preventing transmission of the infection between the groups. Immunizing the separator then breaks the transmission cycle, and so selecting a separator that contains as few individuals as possible will minimize the number of immunization doses required. In this example, we show how this optimization problem can be implemented using the Ocean SDK and solved using the hybrid constrained quadratic model solver available in Leap.
To run the demo, type:
python demo.py
Additional options are available to select different graphs to run the problem on. To see the full list of options, type:
python demo.py -h
During a successful run of the program, two images are produced and saved. The
first is the original input graph, saved as input_graph.png.
The second highlights the partition of the population into large groups (left and right) and separator (center).
Several different types of graphs or networks are available for this demo using the options provided. These are all built using NetworkX graph generator functions, and the details of these functions can be found here.
karate: Karate Club graph; a fixed graph on 34 nodes.internet: Internet Autonomous System network; specify number of nodes between 1,000 and 1,666.rand-reg: A random d-regular graph; specify number of nodes and value for d.ER: Erdos-Renyi random graph; specify number of nodes and edge probability.SF: Barabasi-Albert scale-free graph; specify number of nodes and number of edges to add from a new node to any existing nodes.
The default graph is the internet graph on 1,000 nodes. The largest number of nodes allowed for any graph specified can be at most 1,666.
Given a population represented as a graph, the optimization problem can be broken down into the following objective and constraints.
- Objective: Minimize the number of nodes in the separator
- Constraint 1: Large groups have equal size
- Constraint 2: No edges between the large groups
This problem can be modeled as a constrained quadratic model (CQM). For each node in the graph we define three binary variables: one for each large group and one for the separator group. A node can be assigned to exactly one of those three groups.
[1] Chen, Yiping, et al. "Finding a better immunization strategy." Physical review letters 101.5 (2008): 058701.
Released under the Apache License 2.0. See LICENSE file.