Signed graph

A signed graph is a graph in which each edge is labeled with a sign — positive or negative — representing a relationship of alliance or antagonism, trust or distrust, attraction or repulsion. Introduced by Frank Harary in 1953 to model structural balance in social psychology, signed graphs extend ordinary graph theory to capture the qualitative nature of relationships, not merely their existence. A signed graph is \'balanced\' if its vertices can be partitioned into two groups such that all positive edges lie within groups and all negative edges lie between groups.

The theory of signed graphs connects discrete mathematics to social network analysis, where it has been used to model political coalitions, international alliances, and online reputation systems. The spectral properties of signed graphs — involving the signed Laplacian — generalize those of unsigned graphs and reveal how antagonistic relationships alter the flow of information and the stability of collective dynamics.