Structural Imbalance
This first example is related to structural imbalance and is adapted directly from examples developed by D-Wave Systems. A signed social network is one where the edges are either positive or negative. For instance, a positive edge between two nodes may represent friendly relations between the entities represented by the nodes. Negative edges may represent hostile relations. Structural imbalance measures the degree to which a social network can be divided into two groups with each group containing only positive (friendly) edges, and all negative edges are between groups. Edges that violate this rule (e.g., positive edges across groups, negative edges within groups) are referred to as frustration edges. A larger number of frustration edges means the network is more imbalanced. Nakumura et al. (2011) showed that such structural imbalance is correlated with gang violence. Structural imbalance has also been applied to global terrorism datasets, as well.
In this first example, we will measure structural imbalance of a real-world network of militant organizations. The dataset is from the Stanford Militants Mapping Project. A small subset of the dataset focusing on Syria in 2013 can be downloaded as a CSV file from here.
STEP 1: Load the dataset as a Graph
!wget -O /tmp/network.csv https://raw.githubusercontent.com/amaiya/quixotic/develop/nbs/sample_data/militant_groups_syria_2013.csv
!pip install -q pandas
import pandas as pd
df = pd.read_csv('/tmp/network.csv', index_col=0)
df.head()
Here, we will import the edges in the DataFrame to create a Networkx graph object:
import networkx as nx
G = nx.from_pandas_edgelist(df, edge_attr=True)
positions = nx.spring_layout(G, seed=1967)
nx.draw(G, with_labels=True, pos=positions)
STEP 2: Run QuantumAnnealer
from quixotic.core import QuantumAnnealer
imbalance, bicoloring = QuantumAnnealer(G, task='structural_imbalance').execute().results()
The 'structural_imbalance' task returns two values: imbalance (list of discovered frustration edges) and bicoloring (dictionary showing which of the two groups each node was placed). We find that the network is not completely balanced, as there is one frustration edge between the group 1 and group 533.
list(imbalance.values())
We color the two discovered groups as yellow and magenta. Notice that edges among nodes of the same color are blue (for friendly) and edges among nodes of different colors are red (for hostile). The one exception is the hostile frustration edge between 1 and 533 mentioned above.
node_colors = ['yellow' if bicoloring[node] ==1 else 'magenta' for node in G.nodes]
edge_colors = ['blue' if G.edges[e]['sign'] ==1 else 'red' for e in G.edges]
for i, v in enumerate(G.nodes): G.nodes[v]['color'] = node_colors[i]
#pos = nx.bipartite_layout(G, nodes = [v for i,v in enumerate(G.nodes) if node_colors[i] == 'yellow'])
for u,v in G.edges: G.edges[(u,v)]['weight'] = 1 if G.nodes[u]['color'] == G.nodes[v]['color'] else 2
pos = nx.kamada_kawai_layout(G, weight='weight')
nx.draw(G, with_labels=True, node_color=node_colors, edges=G.edges, edge_color=edge_colors, pos=pos)
import networkx as nx
n_nodes = 6
p = 0.5 # probability of an edge
seed = 1967
g = nx.erdos_renyi_graph(n_nodes, p=p, seed=seed)
positions = nx.spring_layout(g, seed=seed)
nx.draw(g, with_labels=True, pos=positions)
from quixotic.core import QuantumAnnealer
qo = QuantumAnnealer(g, task='maximum_clique')
qo.execute()
nodes = qo.results()
sub = g.subgraph(nodes)
nx.draw(g, pos=positions, with_labels=True)
nx.draw(sub, pos=positions, node_color="r", edge_color="r")
QuantumAnnealer.supported_tasks()
Minimum Vertex Cover
Here, we wil solve a Minimum Vertex Cover problem. The goal is to find the smallest number of nodes that cover every edge in the network.
import networkx as nx
n_nodes = 6
p = 0.5 # probability of an edge
seed = 1967
g = nx.erdos_renyi_graph(n_nodes, p=p, seed=seed)
positions = nx.spring_layout(g, seed=seed)
nx.draw(g, with_labels=True, pos=positions)
from quixotic.core import QuantumAnnealer
qo = QuantumAnnealer(g, task='minimum_vertex_cover')
qo.execute()
nodes = qo.results()
sub = g.subgraph(nodes)
nx.draw(g, pos=positions, with_labels=True)
nx.draw(sub, pos=positions, node_color="r", edge_color="r")
Interestingly, our solution is closer to the ground truth than the Local Ratio algorithm in networkx that simply returns all nodes. The Local Ratio algorithm returns "a set of vertices whose weight sum is no more than 2 * OPT" (see this post for more information).
from networkx.algorithms.approximation.vertex_cover import *
nx_nodes = min_weighted_vertex_cover(g)
# plot nodes comprising the solution
sub = g.subgraph(nx_nodes)
nx.draw(g, pos=positions, with_labels=True)
nx.draw(sub, pos=positions, node_color="r", edge_color="r")
Formulating Your Problem as a QUBO
Finally, for more flexibility, you can formulate your problem directly as a quadratic unconstrained binary optimization problem (QUBO) and supply it directly to QuantumAnnealer. Here, we will solve the same Minimum Vertex Cover problem shown above by supplying QUBO expressed as a Python dictionary instead of a graph and task. The QUBO will represent a Maximum Independent Set problem. The complement of a maximum independent set solution is a solution to the minimum vertex cover problem. We find an equivalent solution to the solution we found above.
cost = dict(g.nodes(data=None, default=1))
scale = max(cost.values())
Q = {(node, node): min(-cost[node] / scale, 0.0) for node in g}
Q.update({edge: 2.0 for edge in g.edges}) # use 2.0 as "tuning" LaGrange value for this problem
# solve QUBO using QuantumAnnealer
independent_set = QuantumAnnealer(qubo=Q).execute().results()
# nodes NOT in the independent set comprise the minimum vertex cover
solution_nodes = [v for v in g if v not in independent_set]
# plot solution as graph
sub = g.subgraph(solution_nodes)
nx.draw(g, pos=positions, with_labels=True)
nx.draw(sub, pos=positions, node_color="r", edge_color="r")
For more information on QUBOs, please see this reference.