dwave.graphs.algorithms.social.structural_imbalance#

structural_imbalance(graph: Graph, sampler: Sampler, **sampler_args) → tuple[Mapping[tuple[Hashable, Hashable], Mapping[str, float]], Mapping[tuple[Hashable, Hashable], Literal[0, 1]]][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:

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

  • sampler – A dimod sampler.

  • **sampler_args – Additional keyword parameters passed to the sampler.

Returns:

  • frustrated_edges:

    A dictionary of the edges that violate the edge sign. The imbalance of the network is the length of frustrated_edges.

  • colors:

    A bicoloring of the nodes into two factions.

Return type:

A tuple with two dictionaries

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 = dwave.graphs.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 = dwave.graphs.structural_imbalance(S, sampler)
>>> print(frustrated_edges)
{('Ted', 'Eve'): {'sign': 1}}
>>> print(colors)
{'Bob': 1, 'Ted': 1, 'Alice': 1, 'Eve': 0}

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