dwave_networkx.algorithms.social.structural_imbalance#

structural_imbalance(S, sampler=None, **sampler_args)[source]#

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

Ising model on Wikipedia

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