In the area of graph theory in mathematics, a signed graph is a graph in which each edge has a positive or negative sign. A signed graph is balanced if the product of edge signs around every cycle is positive. The name "signed graph" and the notion of balance appeared first in a mathematical paper of Frank Harary in 1953. Dénes Kőnig had already studied equivalent notions in 1936 under a different terminology but without recognizing the relevance of the sign group. 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. Signed graphs have been rediscovered many times because they come up naturally in many unrelated areas. For instance, they enable one to describe and analyze the geometry of subsets of the classical root systems. They appear in topological graph theory and group theory. They are a natural context for questions about odd and even cycles in graphs. 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 Σ. They have been applied to data classification in correlation clustering.
Fundamental theorem The sign of a path is the product of the signs of its edges. Thus a path is positive only if there are an even number of negative edges in it (where zero is even). In the mathematical balance theory of Frank Harary, a signed graph is balanced when every cycle is positive. 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. It generalizes the theorem that an ordinary (unsigned) graph is bipartite if and only if every cycle has even length. A simple proof uses the method of switching. Switching a signed graph means reversing the signs of all edges between a vertex subset and its complement. To prove Harary's theorem, one shows by induction that Σ can be switched to be all positive if and only if it is balanced. A weaker theorem, but with a simpler proof, is that if every 3-cycle in a signed complete graph is positive, then the graph is balanced. For the proof, pick an arbitrary node n and place it and all those nodes that are linked to n by a positive edge in one group, called A, and all those linked to n by a negative edge in the other, called B. Since this is a complete graph, every two nodes in A must be friends and every two nodes in B must be friends, otherwise there would be a 3-cycle which was unbalanced. (Since this is a complete graph, any one negative edge would cause an unbalanced 3-cycle.) Likewise, all negative edges must go between the two groups.
Frustration
Frustration index The frustration index (early called the line index of balance) of Σ is the smallest number of edges whose deletion, or equivalently whose sign reversal (a theorem of Harary), makes Σ balanced. The reason for the equivalence is that the frustration index equals the smallest number of edges whose negation (or, equivalently, deletion) 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 quantity has been called the negative cycle cover number. There is another equivalent definition (which can be proved easily by switching). Give each vertex a value of +1 or −1; we call this a state of Σ. An edge is called satisfied if it is positive and both endpoints have the same value, or it is negative and the endpoints have opposite values. An edge that is not satisfied is called frustrated. The smallest number of frustrated edges over all states is the frustration index. This definition was first introduced in a different notation by Abelson and Rosenberg under the (obsolete) name complexity. The complement of such a set is a balanced subgraph of Σ with the most possible edges. Finding the frustration index is an NP-hard problem. One can see the NP-hard complexity by observing that the frustration index of an all-negative signed graph is the same as the maximum cut problem in graph theory, which is NP-hard. The frustration index is important in a model of spin glasses, the mixed Ising model. In this model, the signed graph is fixed. A state consists of giving a "spin", either "up" or "down", to each vertex. We think of spin up as +1 and spin down as −1. Thus, each state has a number of frustrated edges. The energy of a state is larger when it has more frustrated edges, so a ground state is a state with the fewest frustrated energy. Thus, to find the ground state energy of Σ one has to find the frustration index.
Frustration number The analogous vertex number is the frustration number, defined as the smallest number of vertices whose deletion from Σ results in balance. Equivalently, one wants the largest order of a balanced induced subgraph of Σ.
Algorithmic problems Three fundamental questions about a signed graph are: Is it balanced? What is the largest size of a balanced edge set in it? What is the smallest number of vertices that must be deleted to make it balanced? The first question is easy to solve in polynomial time. The second question is called the Frustration Index or Maximum Balanced Subgraph problem. It is NP-hard because its special case (when all edges of the graph are negative) is the NP-hard problem Maximum Cut. The third question is called the Frustration Number or Maximum Balanced Induced Subgraph problem, is also NP-hard; see e.g.
… excerpt ends here. Continue reading the full article.
