dimod.generators.structural_imbalance

structural_imbalance(graph: nx.Graph) → BinaryQuadraticModel

Construct a binary quadratic model (BQM) to calculate the structural imbalance of a signed social network.

A signed social network graph is a graph whose signed edges represent friendly/hostile interactions between nodes. A signed social network is considered balanced if it can be cleanly divided into two factions, where all relations within a faction are friendly, and all relations between factions are hostile. The measure of imbalance or frustration is the minimum number of edges that violate this rule.

Parameters:

graph – A social graph (in a NetworkX graph) on which each edge has a ‘sign’ attribute with a numeric value.

Returns:

A binary quadratic model. Each variable in the model represents a node in the signed social network. The solution that minimized the BQM will assign each variable a value, either -1 or 1. This bi-coloring defines the factions.

Raises:

ValueError – If any edge does not have a ‘sign’ attribute.

Examples

>>> import dimod
>>> import networkx as nx
...
>>> S = nx.Graph()
>>> S.add_edge('Alice', 'Bob', sign=1)  # Alice and Bob are friendly
>>> S.add_edge('Alice', 'Eve', sign=-1)  # Alice and Eve are hostile
>>> S.add_edge('Bob', 'Eve', sign=-1)  # Bob and Eve are hostile
...
>>> bqm = dimod.generators.structural_imbalance(S)
>>> bqm.linear
{'Alice': 0.0, 'Bob': 0.0, 'Eve': 0.0}
>>> bqm.quadratic
{('Alice', 'Bob'): -1.0, ('Alice', 'Eve'): 1.0, ('Bob', 'Eve'): 1.0}