Bläsius, Thomas ;
Friedrich, Tobias ;
Krejca, Martin S. ;
Molitor, Louise
The Impact of Geometry on Monochrome Regions in the Flip Schelling Process
Abstract
Schelling’s classical segregation model gives a coherent explanation for the widespread phenomenon of residential segregation. We introduce an agentbased saturated opencity variant, the Flip Schelling Process (FSP), in which agents, placed on a graph, have one out of two types and, based on the predominant type in their neighborhood, decide whether to change their types; similar to a new agent arriving as soon as another agent leaves the vertex.
We investigate the probability that an edge {u,v} is monochrome, i.e., that both vertices u and v have the same type in the FSP, and we provide a general framework for analyzing the influence of the underlying graph topology on residential segregation. In particular, for two adjacent vertices, we show that a highly decisive common neighborhood, i.e., a common neighborhood where the absolute value of the difference between the number of vertices with different types is high, supports segregation and, moreover, that large common neighborhoods are more decisive.
As an application, we study the expected behavior of the FSP on two common random graph models with and without geometry: (1) For random geometric graphs, we show that the existence of an edge {u,v} makes a highly decisive common neighborhood for u and v more likely. Based on this, we prove the existence of a constant c > 0 such that the expected fraction of monochrome edges after the FSP is at least 1/2 + c. (2) For ErdősRényi graphs we show that large common neighborhoods are unlikely and that the expected fraction of monochrome edges after the FSP is at most 1/2 + o(1). Our results indicate that the cluster structure of the underlying graph has a significant impact on the obtained segregation strength.
BibTeX  Entry
@InProceedings{blasius_et_al:LIPIcs.ISAAC.2021.29,
author = {Bl\"{a}sius, Thomas and Friedrich, Tobias and Krejca, Martin S. and Molitor, Louise},
title = {{The Impact of Geometry on Monochrome Regions in the Flip Schelling Process}},
booktitle = {32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
pages = {29:129:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772143},
ISSN = {18688969},
year = {2021},
volume = {212},
editor = {Ahn, HeeKap and Sadakane, Kunihiko},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/15462},
URN = {urn:nbn:de:0030drops154623},
doi = {10.4230/LIPIcs.ISAAC.2021.29},
annote = {Keywords: Agentbased Model, Schelling Segregation, Spin System}
}
30.11.2021
Keywords: 

Agentbased Model, Schelling Segregation, Spin System 
Seminar: 

32nd International Symposium on Algorithms and Computation (ISAAC 2021)

Issue date: 

2021 
Date of publication: 

30.11.2021 