# dwave_networkx.algorithms.social.structural_imbalance¶

Returns an approximate set of frustrated edges and a bicoloring.

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.**sampler**– A binary quadratic model sampler. A sampler is a process that samples from low energy states in models defined by an Ising equation or a Quadratic Unconstrainted Binary Optimization Problem (QUBO). A sampler is expected to have a ‘sample_qubo’ and ‘sample_ising’ method. A sampler is expected to return an iterable of samples, in order of increasing energy. If no sampler is provided, one must be provided using the set_default_sampler function.**sampler_args**– Additional keyword parameters are passed to the sampler.

- Returns
**frustrated_edges**(*dict*) – A dictionary of the edges that violate the edge sign. The imbalance of the network is the length of frustrated_edges.**colors**(*dict*) – A bicoloring of the nodes into two factions.

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

Examples

>>> import dimod >>> sampler = dimod.ExactSolver() >>> 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 >>> frustrated_edges, colors = dnx.structural_imbalance(S, sampler) >>> print(frustrated_edges) {} >>> print(colors) {'Alice': 0, 'Bob': 0, 'Eve': 1} >>> S.add_edge('Ted', 'Bob', sign=1) # Ted is friendly with all >>> S.add_edge('Ted', 'Alice', sign=1) >>> S.add_edge('Ted', 'Eve', sign=1) >>> frustrated_edges, colors = dnx.structural_imbalance(S, sampler) >>> print(frustrated_edges) {('Ted', 'Eve'): {'sign': 1}} >>> print(colors) {'Bob': 1, 'Ted': 1, 'Alice': 1, 'Eve': 0}

Notes

Samplers by their nature may not return the optimal solution. This function does not attempt to confirm the quality of the returned sample.

References

- FIA
Facchetti, G., Iacono G., and Altafini C. (2011). Computing global structural balance in large-scale signed social networks. PNAS, 108, no. 52, 20953-20958