Emergent bipartiteness in a society of knights and knaves

Charo del Genio, Thilo Gross

Research output: Contribution to journalArticle

5 Citations (Scopus)
5 Downloads (Pure)

Abstract

We propose a simple model of a social network based on the 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 neighbors 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 of the behavior of the model, investigate its behavior in the thermodynamic limit and argue that it provides a simple example of a topology-driven model whose behavior is strongly reminiscent of first-order phase transitions far from equilibrium.
Original languageEnglish
Article number103038
JournalNew Journal of Physics
Volume13
DOIs
Publication statusPublished - 31 Oct 2011

Fingerprint

proportion
topology
thermodynamics
thresholds

Bibliographical note

By default, we (IOP) publish all open access articles under a Creative Commons CC BY 3.0 licence, which allows the widest possible sharing of research, while ensuring full attribution for authors.

Cite this

Emergent bipartiteness in a society of knights and knaves. / del Genio, Charo; Gross, Thilo.

In: New Journal of Physics, Vol. 13, 103038, 31.10.2011.

Research output: Contribution to journalArticle

@article{818ac0bd18674f019f2fe0267b209c2c,
title = "Emergent bipartiteness in a society of knights and knaves",
abstract = "We propose a simple model of a social network based on the 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 neighbors 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 of the behavior of the model, investigate its behavior in the thermodynamic limit and argue that it provides a simple example of a topology-driven model whose behavior is strongly reminiscent of first-order phase transitions far from equilibrium.",
author = "{del Genio}, Charo and Thilo Gross",
note = "By default, we (IOP) publish all open access articles under a Creative Commons CC BY 3.0 licence, which allows the widest possible sharing of research, while ensuring full attribution for authors.",
year = "2011",
month = "10",
day = "31",
doi = "10.1088/1367-2630/13/10/103038",
language = "English",
volume = "13",
journal = "New Journal of Physics",

}

TY - JOUR

T1 - Emergent bipartiteness in a society of knights and knaves

AU - del Genio, Charo

AU - Gross, Thilo

N1 - By default, we (IOP) publish all open access articles under a Creative Commons CC BY 3.0 licence, which allows the widest possible sharing of research, while ensuring full attribution for authors.

PY - 2011/10/31

Y1 - 2011/10/31

N2 - We propose a simple model of a social network based on the 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 neighbors 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 of the behavior of the model, investigate its behavior in the thermodynamic limit and argue that it provides a simple example of a topology-driven model whose behavior is strongly reminiscent of first-order phase transitions far from equilibrium.

AB - We propose a simple model of a social network based on the 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 neighbors 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 of the behavior of the model, investigate its behavior in the thermodynamic limit and argue that it provides a simple example of a topology-driven model whose behavior is strongly reminiscent of first-order phase transitions far from equilibrium.

U2 - 10.1088/1367-2630/13/10/103038

DO - 10.1088/1367-2630/13/10/103038

M3 - Article

VL - 13

JO - New Journal of Physics

JF - New Journal of Physics

M1 - 103038

ER -