dwave_networkx.algorithms.social.structural_imbalance_ising

structural_imbalance_ising(S)[source]

Construct the Ising problem 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:S (NetworkX graph) – A social graph on which each edge has a ‘sign’ attribute with a numeric value.
Returns:
  • h (dict) – The linear biases of the Ising problem. Each variable in the Ising problem represent a node in the signed social network. The solution that minimized the Ising problem will assign each variable a value, either -1 or 1. This bi-coloring defines the factions.
  • J (dict) – The quadratic biases of the Ising problem.
Raises:ValueError – If any edge does not have a ‘sign’ attribute.

Examples

>>> import dimod
>>> from dwave_networkx.algorithms.social import structural_imbalance_ising
...
>>> 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
...
>>> h, J = structural_imbalance_ising(S)
>>> h  # doctest: +SKIP
{'Alice': 0.0, 'Bob': 0.0, 'Eve': 0.0}
>>> J  # doctest: +SKIP
{('Alice', 'Bob'): -1.0, ('Alice', 'Eve'): 1.0, ('Bob', 'Eve'): 1.0}