Signed graph
Encyclopedia
In the area of graph theory
in mathematics
, a signed graph is a graph in which each edge has a positive or negative sign.
Formally, a signed graph Σ is a pair (G, σ) that consists of a graph
G = (V, E) and a sign mapping or signature σ from E to the sign group {+,−}. The graph may have loops and multiple edges as well as half-edges (with only one endpoint) and loose edges (with no endpoints). Half and loose edges do not receive signs. (In the terminology of the article on graphs
, it is a multigraph, but we say graph because in signed graph theory it is usually unnatural to restrict to simple graphs.)
The sign of a circle (this is the edge set of a simple cycle
) is defined to be the product of the signs of its edges; in other words, a circle is positive if it contains an even number of negative edges and negative if it contains an odd number of negative edges. The fundamental fact about a signed graph is the set of positive circles, denoted by B(Σ). A signed graph, or a subgraph or edge set, is called balanced if every circle in it is positive (and it contains no half-edges). Two fundamental questions about a signed graph are: Is it balanced? What is the largest size of a balanced edge set in it? The first question is not difficult; the second is computationally intractable (technically, it is NP-hard
).
Signed graphs were first introduced by Harary
to handle a problem in social psychology
(Cartwright and Harary, 1956). They 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 system
s. 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
.
of a signed graph Σ on n vertices is an n × n matrix
A(Σ). It has a row and column for each vertex. The entry avw in row v and column w is the number of positive vw edges minus the number of negative vw edges. On the diagonal, avv = 0 if there are no loops or half-edges; the correct definition when such edges exist depends on the circumstances.
. (It is very different from a signed digraph.)
. This rule applies to a link, whose column will have two nonzero entries with absolute value 1, a half-edge, whose column has a single nonzero entry +1 or −1, and a loose edge, whose column has only zeroes. The column of a loop, however, is all zero if the loop is positive, and if the loop is negative it has entry ±2 in the row corresponding to its incident vertex.
Any two incidence matrices are related by negating some subset of the columns. Thus, for most purposes it makes no difference which orientation we use to define the incidence matrix, and we may speak of the incidence matrix of Σ without worrying about exactly which one it is.
Negating a row of the incidence matrix corresponds to switching the corresponding vertex.
to that vertex. Switching a set of vertices means negating all the edges that have one end in that set and one end in the complementary set. Switching a series of vertices, once each, is the same as switching the whole set at once.
Switching of signed graphs (signed switching) is generalized from Seidel (1976), where it was applied to graphs (graph switching
), in a way that is equivalent to switching of signed complete graphs.
Switching equivalence means that two graphs are related by switching, and an equivalence class of signed graphs under switching is called a switching class. Sometimes these terms are applied to equivalence of signed graphs under the combination of switching and isomorphism
, especially when the graphs are unlabeled; but to distinguish the two concepts the combined equivalence may be called switching isomorphism and an equivalence class under switching isomorphism may be called a switching isomorphism class.
Switching a set of vertices affects the adjacency matrix by negating the rows and columns of the switched vertices. It affects the incidence matrix by negating the rows of the switched vertices.
if and only if every cycle has even length.
A simple proof uses the method of switching. 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 balanced, then either all nodes are connected by positive edges or the nodes can be divided into two groups A and B such that every pair of nodes in A are connected by a positive edge, every pair of nodes in B are connected by a positive edge, and all edges going between A and B are negative edges. 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 three cycle.) Likewise, all negative edges must go between the two groups.
. One can see this by observing that frustration index of an all-negative signed graph is equivalent to the maximum cut problem in graph theory, which is NP-hard.
The reason is that the frustration index equals the smallest number of edges whose negation (or, equivalently, deletion; a theorem of Harary) makes Σ balanced. (This can be proved easily by switching.)
The frustration index is important in a model of spin glass
es, 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.
s associated with a signed graph, called the signed-graphic matroid (also called the frame matroid or sometimes bias matroid) and the lift matroid, both of which generalize the cycle matroid of a graph. They are special cases of the same matroids of a biased graph
.
The frame matroid (or signed-graphic matroid) M(G) (Zaslavsky, 1982) has for its ground set the edge set E. An edge set is independent if each component contains either no circles or just one circle, which is negative. (In matroid theory a half-edge acts exactly like a negative loop.) A circuit of the matroid is either a positive circle, or a pair of negative circles together with a connecting simple path, such that the two circles are either disjoint (then the connecting path has one end in common with each circle and is otherwise disjoint from both) or share just a single common vertex (in this case the connecting path is that single vertex). The rank of an edge set S is n − b, where n is the number of vertices of G and b is the number of balanced components of S, counting isolated vertices as balanced components.
This matroid is the column matroid of the incidence matrix of the signed graph.
That is why it describes the linear dependencies of the roots of a classical root system.
The extended lift matroid L0(G) has for its ground set the set E0 the union of edge set E with an extra point, which we denote e0. The lift matroid L(G) is the extended lift matroid restricted to E. The extra point acts exactly like a negative loop, so we describe only the lift matroid. An edge set is independent if it contains either no circles or just one circle, which is negative. (This is the same rule that is applied separately to each component in the signed-graphic matroid.) A matroid circuit is either a positive circle or a pair of negative circles that are either disjoint or have just a common vertex. The rank of an edge set S is n − c + ε, where c is the number of components of S, counting isolated vertices, and ε is 0 if S is balanced and 1 if it is not.
The term signed graph is applied occasionally to graphs in which each edge has a weight, w(e) = +1 or −1. These are not the same kind of signed graph; they are weighted graphs
with a restricted weight set. The difference is that weights are added, not multiplied. The problems and methods are completely different.
The name is also applied to graphs in which the signs function as colors on the edges. The significance of the color is that it determines various weights applied to the edge, and not that its sign is intrinsically significant. 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. The matroid of a sign-colored graph is the cycle matroid of the underlying graph; it is not the frame or lift matroid of the signed graph. The sign labels, instead of changing the matroid, become signs on the elements of the matroid.
In this article we discuss only signed graph theory in the strict sense. For sign-colored graphs see colored matroids.
with signed arcs. Signed digraphs are far more complicated than signed graphs, because only the signs of directed cycles are significant. 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.
Signed digraphs should not be confused with oriented signed graphs. The latter are bidirected graphs, not directed graphs (except in the trivial case of all positive signs).
, signed graphs have been used to model social situations, with positive edges representing friendships and negative edges enmities between nodes, which represent people (Cartwright and Harary 1956). Then, for example, a positive 3-cycle is either three mutual friends, or two friends with a common enemy; while a negative 3-cycle is either three mutual enemies, or two enemies who share a mutual friend. Positive cycles are supposed to be stable social situations, whereas negative cycles are supposed to be unstable. According to the theory, in the case of three mutual enemies, this is because sharing a common enemy is likely to cause two of the enemies to become friends. In the case of two enemies sharing a friend, the shared friend is likely to choose one over the other and turn one of his or her friendships into an enmity. This approach to social groups may be called structural balance theory. It has been applied not only in small group psychology but also to large social systems.
Structural balance 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.
Experimental studies have also provided only weak confirmation of the predictions of structural balance theory.
, which is applied to the study of spin glass
es.
looks for natural clustering of data by similarity. The data points are represented as the vertices of a graph, with a positive edge joining similar items and a negative edge joining dissimilar items.
, where the gain group has order 2. The pair (G, B(G)) is a special kind of biased graph
.
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
in mathematics
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, a signed graph is a graph in which each edge has a positive or negative sign.
Formally, a signed graph Σ is a pair (G, σ) that consists of a graph
Graph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
G = (V, E) and a sign mapping or signature σ from E to the sign group {+,−}. The graph may have loops and multiple edges as well as half-edges (with only one endpoint) and loose edges (with no endpoints). Half and loose edges do not receive signs. (In the terminology of the article on graphs
Graph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
, it is a multigraph, but we say graph because in signed graph theory it is usually unnatural to restrict to simple graphs.)
The sign of a circle (this is the edge set of a simple cycle
Cycle (graph theory)
In graph theory, the term cycle may refer to a closed path. If repeated vertices are allowed, it is more often called a closed walk. If the path is a simple path, with no repeated vertices or edges other than the starting and ending vertices, it may also be called a simple cycle, circuit, circle,...
) is defined to be the product of the signs of its edges; in other words, a circle is positive if it contains an even number of negative edges and negative if it contains an odd number of negative edges. The fundamental fact about a signed graph is the set of positive circles, denoted by B(Σ). A signed graph, or a subgraph or edge set, is called balanced if every circle in it is positive (and it contains no half-edges). Two fundamental questions about a signed graph are: Is it balanced? What is the largest size of a balanced edge set in it? The first question is not difficult; the second is computationally intractable (technically, it is NP-hard
NP-hard
NP-hard , in computational complexity theory, is a class of problems that are, informally, "at least as hard as the hardest problems in NP". A problem H is NP-hard if and only if there is an NP-complete problem L that is polynomial time Turing-reducible to H...
).
Signed graphs were first introduced by Harary
Frank Harary
Frank Harary was a prolific American mathematician, who specialized in graph theory. He was widely recognized as one of the "fathers" of modern graph theory....
to handle a problem in social psychology
Social psychology
Social psychology is the scientific study of how people's thoughts, feelings, and behaviors are influenced by the actual, imagined, or implied presence of others. By this definition, scientific refers to the empirical method of investigation. The terms thoughts, feelings, and behaviors include all...
(Cartwright and Harary, 1956). They 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 system
Root system
In mathematics, a root system is a configuration of vectors in a Euclidean space satisfying certain geometrical properties. The concept is fundamental in the theory of Lie groups and Lie algebras...
s. They appear in topological graph theory
Topological graph theory
In mathematics topological graph theory is a branch of graph theory. It studies the embedding of graphs in surfaces, spatial embeddings of graphs, and graphs as topological spaces. It also studies immersions of graphs....
and group theory
Group theory
In mathematics and abstract algebra, group theory studies the algebraic structures known as groups.The concept of a group is central to abstract algebra: other well-known algebraic structures, such as rings, fields, and vector spaces can all be seen as groups endowed with additional operations and...
. They are a natural context for questions about odd and even cycles
Cycle (graph theory)
In graph theory, the term cycle may refer to a closed path. If repeated vertices are allowed, it is more often called a closed walk. If the path is a simple path, with no repeated vertices or edges other than the starting and ending vertices, it may also be called a simple cycle, circuit, circle,...
in graphs. They appear in computing the ground state
Ground state
The ground state of a quantum mechanical system is its lowest-energy state; the energy of the ground state is known as the zero-point energy of the system. An excited state is any state with energy greater than the ground state...
energy in the non-ferromagnetic Ising model
Ising model
The Ising model is a mathematical model of ferromagnetism in statistical mechanics. The model consists of discrete variables called spins that can be in one of two states . The spins are arranged in a graph , and each spin interacts with its nearest neighbors...
; for this one needs to find a largest balanced edge set in Σ. They have been applied to data classification in correlation clustering
Correlation clustering
In machine learning, correlation clustering or cluster editing operates in a scenario where the relationship between the objects are known instead of the actual representation of the objects...
.
Examples
- The complete signed graph on n vertices with loops, denoted by ±Kno, has every possible positive and negative edge including negative loops, but no positive loops. Its edges correspond to the roots of the root systemRoot systemIn mathematics, a root system is a configuration of vectors in a Euclidean space satisfying certain geometrical properties. The concept is fundamental in the theory of Lie groups and Lie algebras...
Cn; the column of an edge in the incidence matrix (see below) is the vector representing the root.
- The complete signed graph with half-edges, ±Kn', is ±Kn with a half-edge at every vertex. Its edges correspond to the roots of the root system Bn, half-edges corresponding to the unit basis vectors.
- The complete signed link graph, ±Kn, is the same but without loops. Its edges correspond to the roots of the root system Dn.
- An all-positive signed graph has only positive edges. If the underlying graph is G, the all-positive signing is written +G.
- An all-negative signed graph has only negative edges. It is balanced if and only if it is bipartiteBipartiteBipartite means having two parts, or an agreement between two parties. More specifically, it may refer to any of the following:-Mathematics:* 2 * bipartite graph* bipartite cubic, a type of cubic function-Medicine:...
because a circle is positive if and only if it has even length. An all-negative graph with underlying graph G is written −G.
- A signed complete graph has as underlying graph G the ordinary complete graph Kn. It may have any signs. Signed complete graphs are equivalent to two-graphTwo-graphIn mathematics, a two-graph is a set of triples chosen from a finite vertex set X, such that every quadruple from X contains an even number of triples of the two-graph. A regular two-graph has the property that every pair of vertices lies in the same number of triples of the two-graph...
s, which are of value in finite groupFinite groupIn mathematics and abstract algebra, a finite group is a group whose underlying set G has finitely many elements. During the twentieth century, mathematicians investigated certain aspects of the theory of finite groups in great depth, especially the local theory of finite groups, and the theory of...
theory. A two-graph can be defined as the class of vertex sets of negative triangles in a signed complete graph.
Adjacency matrix
The adjacency matrixAdjacency matrix
In mathematics and computer science, an adjacency matrix is a means of representing which vertices of a graph are adjacent to which other vertices...
of a signed graph Σ on n vertices is an n × n matrix
Matrix (mathematics)
In mathematics, a matrix is a rectangular array of numbers, symbols, or expressions. The individual items in a matrix are called its elements or entries. An example of a matrix with six elements isMatrices of the same size can be added or subtracted element by element...
A(Σ). It has a row and column for each vertex. The entry avw in row v and column w is the number of positive vw edges minus the number of negative vw edges. On the diagonal, avv = 0 if there are no loops or half-edges; the correct definition when such edges exist depends on the circumstances.
Orientation
A signed graph is oriented when each end of each edge is given a direction, so that in a positive edge the ends are both directed from one endpoint to the other, and in a negative edge either both ends are directed outward, to their own vertices, or both are directed inward, away from their vertices. Thus, an oriented signed graph is the same as a bidirected graphBidirected graph
In the mathematical domain of graph theory, a bidirected graph is a graph in which each edge is given an independent orientation at each end...
. (It is very different from a signed digraph.)
Incidence matrix
The (more correctly, "an") incidence matrix of a signed graph with n vertices and m edges is an n × m matrix, with a row for each vertex and a column for each edge. It is obtained by orienting the signed graph in any way. Then its entry ηij is +1 if edge j is oriented into vertex i, −1 if edge j is oriented out of vertex i, and 0 if vertex i and edge j are not incidentIncident
Incident may refer to:* A property of a graph *Incident , a cultural festival of The National Institute of Technology in Surathkal, Karnataka, India...
. This rule applies to a link, whose column will have two nonzero entries with absolute value 1, a half-edge, whose column has a single nonzero entry +1 or −1, and a loose edge, whose column has only zeroes. The column of a loop, however, is all zero if the loop is positive, and if the loop is negative it has entry ±2 in the row corresponding to its incident vertex.
Any two incidence matrices are related by negating some subset of the columns. Thus, for most purposes it makes no difference which orientation we use to define the incidence matrix, and we may speak of the incidence matrix of Σ without worrying about exactly which one it is.
Negating a row of the incidence matrix corresponds to switching the corresponding vertex.
Switching
Switching a vertex in Σ means negating the signs of all the edges incidentIncident
Incident may refer to:* A property of a graph *Incident , a cultural festival of The National Institute of Technology in Surathkal, Karnataka, India...
to that vertex. Switching a set of vertices means negating all the edges that have one end in that set and one end in the complementary set. Switching a series of vertices, once each, is the same as switching the whole set at once.
Switching of signed graphs (signed switching) is generalized from Seidel (1976), where it was applied to graphs (graph switching
Two-graph
In mathematics, a two-graph is a set of triples chosen from a finite vertex set X, such that every quadruple from X contains an even number of triples of the two-graph. A regular two-graph has the property that every pair of vertices lies in the same number of triples of the two-graph...
), in a way that is equivalent to switching of signed complete graphs.
Switching equivalence means that two graphs are related by switching, and an equivalence class of signed graphs under switching is called a switching class. Sometimes these terms are applied to equivalence of signed graphs under the combination of switching and isomorphism
Isomorphism
In abstract algebra, an isomorphism is a mapping between objects that shows a relationship between two properties or operations. If there exists an isomorphism between two structures, the two structures are said to be isomorphic. In a certain sense, isomorphic structures are...
, especially when the graphs are unlabeled; but to distinguish the two concepts the combined equivalence may be called switching isomorphism and an equivalence class under switching isomorphism may be called a switching isomorphism class.
Switching a set of vertices affects the adjacency matrix by negating the rows and columns of the switched vertices. It affects the incidence matrix by negating the rows of the switched vertices.
Fundamental theorem
A signed graph is balanced if and only if its vertex set can be divided into two sets (either of which may be empty), X and Y, so that each edge between the sets is negative and each edge within a set is positive. This is the first theorem of signed graphs (Harary, 1953). It generalizes the theorem that an ordinary (unsigned) graph is bipartiteBipartite graph
In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V; that is, U and V are independent sets...
if and only if every cycle has even length.
A simple proof uses the method of switching. 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 balanced, then either all nodes are connected by positive edges or the nodes can be divided into two groups A and B such that every pair of nodes in A are connected by a positive edge, every pair of nodes in B are connected by a positive edge, and all edges going between A and B are negative edges. 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 three cycle.) Likewise, all negative edges must go between the two groups.
Frustration
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. The smallest number of frustrated edges in any state is called the frustration index (or line index of balance) of Σ. Finding the frustration index is hard, in fact, it is NP-hardNP-hard
NP-hard , in computational complexity theory, is a class of problems that are, informally, "at least as hard as the hardest problems in NP". A problem H is NP-hard if and only if there is an NP-complete problem L that is polynomial time Turing-reducible to H...
. One can see this by observing that frustration index of an all-negative signed graph is equivalent to the maximum cut problem in graph theory, which is NP-hard.
The reason is that the frustration index equals the smallest number of edges whose negation (or, equivalently, deletion; a theorem of Harary) makes Σ balanced. (This can be proved easily by switching.)
The frustration index is important in a model of spin glass
Spin glass
A spin glass is a magnet with frustrated interactions, augmented by stochastic disorder, where usually ferromagnetic and antiferromagnetic bonds are randomly distributed...
es, 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
Ground state
The ground state of a quantum mechanical system is its lowest-energy state; the energy of the ground state is known as the zero-point energy of the system. An excited state is any state with energy greater than the 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.
Matroid theory
There are two matroidMatroid
In combinatorics, a branch of mathematics, a matroid or independence structure is a structure that captures the essence of a notion of "independence" that generalizes linear independence in vector spaces....
s associated with a signed graph, called the signed-graphic matroid (also called the frame matroid or sometimes bias matroid) and the lift matroid, both of which generalize the cycle matroid of a graph. They are special cases of the same matroids of a biased graph
Biased graph
In mathematics, a biased graph is a graph with a list of distinguished circles , such that if two circles in the list are contained in a theta graph, then so is the third circle of the theta graph...
.
The frame matroid (or signed-graphic matroid) M(G) (Zaslavsky, 1982) has for its ground set the edge set E. An edge set is independent if each component contains either no circles or just one circle, which is negative. (In matroid theory a half-edge acts exactly like a negative loop.) A circuit of the matroid is either a positive circle, or a pair of negative circles together with a connecting simple path, such that the two circles are either disjoint (then the connecting path has one end in common with each circle and is otherwise disjoint from both) or share just a single common vertex (in this case the connecting path is that single vertex). The rank of an edge set S is n − b, where n is the number of vertices of G and b is the number of balanced components of S, counting isolated vertices as balanced components.
This matroid is the column matroid of the incidence matrix of the signed graph.
That is why it describes the linear dependencies of the roots of a classical root system.
The extended lift matroid L0(G) has for its ground set the set E0 the union of edge set E with an extra point, which we denote e0. The lift matroid L(G) is the extended lift matroid restricted to E. The extra point acts exactly like a negative loop, so we describe only the lift matroid. An edge set is independent if it contains either no circles or just one circle, which is negative. (This is the same rule that is applied separately to each component in the signed-graphic matroid.) A matroid circuit is either a positive circle or a pair of negative circles that are either disjoint or have just a common vertex. The rank of an edge set S is n − c + ε, where c is the number of components of S, counting isolated vertices, and ε is 0 if S is balanced and 1 if it is not.
Other kinds of "signed graph"
Sometimes the signs are taken to be +1 and −1. This is only a difference of notation, if the signs are still multiplied around a circle and the sign of the product is the important thing. However, there are two other ways of treating the edge labels that do not fit into signed graph theory.The term signed graph is applied occasionally to graphs in which each edge has a weight, w(e) = +1 or −1. These are not the same kind of signed graph; they are weighted graphs
Graph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
with a restricted weight set. The difference is that weights are added, not multiplied. The problems and methods are completely different.
The name is also applied to graphs in which the signs function as colors on the edges. The significance of the color is that it determines various weights applied to the edge, and not that its sign is intrinsically significant. This is the case in knot theory
Knot theory
In topology, knot theory is the study of mathematical knots. While inspired by knots which appear in daily life in shoelaces and rope, a mathematician's knot differs in that the ends are joined together so that it cannot be undone. In precise mathematical language, a knot is an embedding of a...
, 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. The matroid of a sign-colored graph is the cycle matroid of the underlying graph; it is not the frame or lift matroid of the signed graph. The sign labels, instead of changing the matroid, become signs on the elements of the matroid.
In this article we discuss only signed graph theory in the strict sense. For sign-colored graphs see colored matroids.
Signed digraph
A signed digraph is a directed graphDirected graph
A directed graph or digraph is a pair G= of:* a set V, whose elements are called vertices or nodes,...
with signed arcs. Signed digraphs are far more complicated than signed graphs, because only the signs of directed cycles are significant. 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.
Signed digraphs should not be confused with oriented signed graphs. The latter are bidirected graphs, not directed graphs (except in the trivial case of all positive signs).
Modeling social situations
In social psychologySocial psychology
Social psychology is the scientific study of how people's thoughts, feelings, and behaviors are influenced by the actual, imagined, or implied presence of others. By this definition, scientific refers to the empirical method of investigation. The terms thoughts, feelings, and behaviors include all...
, signed graphs have been used to model social situations, with positive edges representing friendships and negative edges enmities between nodes, which represent people (Cartwright and Harary 1956). Then, for example, a positive 3-cycle is either three mutual friends, or two friends with a common enemy; while a negative 3-cycle is either three mutual enemies, or two enemies who share a mutual friend. Positive cycles are supposed to be stable social situations, whereas negative cycles are supposed to be unstable. According to the theory, in the case of three mutual enemies, this is because sharing a common enemy is likely to cause two of the enemies to become friends. In the case of two enemies sharing a friend, the shared friend is likely to choose one over the other and turn one of his or her friendships into an enmity. This approach to social groups may be called structural balance theory. It has been applied not only in small group psychology but also to large social systems.
Structural balance 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.
Experimental studies have also provided only weak confirmation of the predictions of structural balance theory.
Spin glasses in physics
Signed graphs are a natural context for the general, nonferromagnetic Ising modelIsing model
The Ising model is a mathematical model of ferromagnetism in statistical mechanics. The model consists of discrete variables called spins that can be in one of two states . The spins are arranged in a graph , and each spin interacts with its nearest neighbors...
, which is applied to the study of spin glass
Spin glass
A spin glass is a magnet with frustrated interactions, augmented by stochastic disorder, where usually ferromagnetic and antiferromagnetic bonds are randomly distributed...
es.
Clustering of data
Correlation clusteringCorrelation clustering
In machine learning, correlation clustering or cluster editing operates in a scenario where the relationship between the objects are known instead of the actual representation of the objects...
looks for natural clustering of data by similarity. The data points are represented as the vertices of a graph, with a positive edge joining similar items and a negative edge joining dissimilar items.
Generalizations
A signed graph is a special kind of gain graphGain graph
A gain graph is a graph whose edges are labelled "invertibly", or "orientably", by elements of a group G. This means that, if an edge e in one direction has label g , then in the other direction it has label g −1...
, where the gain group has order 2. The pair (G, B(G)) is a special kind of biased graph
Biased graph
In mathematics, a biased graph is a graph with a list of distinguished circles , such that if two circles in the list are contained in a theta graph, then so is the third circle of the theta graph...
.