  We propose a simple model of a social network based on so-called
knights-and-knaves puzzles. The model describes the formation of networks
between two classes of agents where links are formed by agents introducing
their neighbours to others of their own class. We show that if the proportion
of knights and knaves is within a certain range, the network self-organizes to
a perfectly bipartite state. However, if the excess of one of the two classes
is greater than a threshold value, bipartiteness is not observed. We offer a
detailed theoretical analysis for the behaviour of the model, investigate its
behaviou r in the thermodynamic limit, and argue that it provides a simple
example of a topology-driven model whose behaviour is strongly reminiscent of a
first-order phase transitions far from equilibrium.
