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 {'Alice': 0.0, 'Bob': 0.0, 'Eve': 0.0} >>> J {('Alice', 'Bob'): -1.0, ('Alice', 'Eve'): 1.0, ('Bob', 'Eve'): 1.0}