Signed graph
The name "signed graph" and the notion of balance appeared first in a mathematical paper of Frank Harary in 1953.
[1] Dénes Kőnig had already studied equivalent notions in 1936 under a different terminology but without recognizing the relevance of the sign group.
[2] At the Center for Group Dynamics at the University of Michigan, Dorwin Cartwright and Harary generalized Fritz Heider's psychological theory of balance in triangles of sentiments to a psychological theory of balance in signed graphs.
[3][4] Signed graphs have been rediscovered many times because they come up naturally in many unrelated areas.
[5] For instance, they enable one to describe and analyze the geometry of subsets of the classical root systems.
They appear in computing the ground state energy in the non-ferromagnetic Ising model; for this one needs to find a largest balanced edge set in Σ.
Harary proves that a signed graph is balanced when (1) for every pair of nodes, all paths between them have the same sign, or (2) the vertices partition into a pair of subsets (possibly empty), each containing only positive edges, but connected by negative edges.
[1] It generalizes the theorem that an ordinary (unsigned) graph is bipartite if and only if every cycle has even length.
To prove Harary's theorem, one shows by induction that Σ can be switched to be all positive if and only if it is balanced.
[6] The frustration index (early called the line index of balance[7]) of Σ is the smallest number of edges whose deletion, or equivalently whose sign reversal (a theorem of Harary[7]), makes Σ balanced.
A second way of describing the frustration index is that it is the smallest number of edges that cover all negative cycles.
This definition was first introduced in a different notation by Abelson and Rosenberg under the (obsolete) name complexity.
The second question is called the Frustration Index or Maximum Balanced Subgraph problem.
However, there are two other ways of treating the edge labels that do not fit into signed graph theory.
This is the case in knot theory, where the only significance of the signs is that they can be interchanged by the two-element group, but there is no intrinsic difference between positive and negative.
For instance, there are several definitions of balance, each of which is hard to characterize, in strong contrast with the situation for signed undirected graphs.
This is notably true for the characterization of harmony by Joglekar, Shah, and Diwan (2012).
In social psychology, signed graphs have been used to model social situations, with positive edges representing friendships and negative edges enmities between nodes, which represent people.
[12] The social relations with previous friends of a divorcing couple are used to illustrate the evolution of a signed graph in society.
Another illustration describes the changing international alliances between European powers in the decades before the First World War.
The evolution of the signed graph with N nodes under this process is studied and simulated to describe the stationary density of friendly links.
Balance theory has been severely challenged, especially in its application to large systems, on the theoretical ground that friendly relations tie a society together, while a society divided into two camps of enemies would be highly unstable.
[13] Experimental studies have also provided only weak confirmation of the predictions of structural balance theory.
[14] In physics, signed graphs are a natural context for the nonferromagnetic Ising model, which is applied to the study of spin glasses.
Using an analytic method initially developed in population biology and ecology, but now used in many scientific disciplines, signed digraphs have found application in reasoning about the behavior of complex causal systems.
