GRADED SCHELLING’S CITY SEFREGATION MODEL : DATA STRUCTURES AND IMPLEMENTATION NOTES.

Gérard H.E. Duchamp^{(1)}, Cyrille Bertelle^{(2)}, Rawan Ghnemat^{(2)}

(1)LIPN - University of Paris XIII, 99 avenue Jean-Baptiste Clément, 93430 Villetaneuse, France

                                 email: ghed@lipn.univ-paris13.fr

(2)LITIS - University of Le Havre, 25 rue Philippe Lebon, BP 540, 76058 Le Havre Cedex, France

                   email: rawan.ghnemat@litislab.eu, cyrille.bertelle@litislab.eu

KEYWORDS self-organization, urban modelling, generalized derangement, Schelling’s model, exponential formula

ABSTRACT

INTRODUCTION

ancienne intro :  à reprendre

Urban or territorial systems are nowadays the topics of decentralized simulations which find roots on two majors advances in the development of scientific researches (Pumain 2006). The first one concerns the development of powerful distributed computer networks which allow to simulate in accurate way, detailed phenomena. The second one which finds major support from the first, is the development of decentralized approaches of modelling. This modern vision of modelling has been mainly enlighted by the complex systems theory (LeMoigne 1999) which allows to deal with the dynamic detection of emergent organizations using swarm optimization processes (Ghnemat et al. 2007), for example. Practical applications deal today with the development of Geographical Information Systems (GIS) which give accurate spatial data and allow with specific platforms (Strout 2006) to link these spatial data with agent-based simulation and emergent computing. We can observe that humans are more or less sorted into groups of similar people, according sometimes with racial and ethnic features but also in many others ways according to various characteristics. Thomas Schelling proposed in the 1970’s a very simple rule-based model able to describe segregation phenomena (Schelling 1971). His description concerns two-dimensional lattice support and it generates from random population, a spatial self-organization which is observed as patterns of clusters of similar persons. The cluster formation does not follow linear dependance from any parameter dealing with the evolution of the rule-based systems. More generally, Schelling’s model can be used as generic spatial self-organization concept for various kinds of systems: A. Singh and M. Haahr, for example, use a variant of this model to study the topology adaptation in P2P networks (Singh and Haahr 2006).

GENERAL DESCRIPTION OF SCHELLING’S MODEL USING GENERALIZED DERANGE-MENTS

In a previous contribution, we gave a concurrent version of Schelling’s model in order to obtain an exact definition of the implementation for each time step, not depending of way the grid is scanned. Here we recall this implementation and take avantage of this reminder to give an improved version devised for the study of membranes of clusters.

1) General description of the model

positionnement et notre contribution passe

2) Graded model

le besoin de cellules ”frontalires”

3) Combinatorial study

sries generatrices

4) Conclusion

Even if the qualitative behavior of Schelling’s model is independant of the order of execution od the agents, as long as each agents has the same expected probability to move, the quantitative outcome can be different. Our purpose is to give a non sequential dependant algorithm which mainly allows us to exhibit exact computationn scheme for the whole iterative process.

In the following, we will make use of the (somewhat extended) notion of derangement. For the classical notion see (Stanley 1999):

http://mathworld.wolfram.com/Derangement.html http://en.wikipedia.org/wiki/Derangement

Here it will be called generalized derangement.

Definition 0.1 Let X, Y be two sets X ⊂ Y. A generalized derangement from X to Y is an into (i. e. injective) mapping ^{1} α : X ↦ Y such that

(∀x ∈ X)(α(x) ≠ x)  (1)

To describe Thomas Schelling’s concurrent model, we start with a two-dimensional lattice board which is a rectangle of n×m (n lines and m columns) points (each point will be located by its coordinates (x, y) with 1 ≤ x ≤ m ; 1 ≤ y ≤ n). A state of the board will be simply a mapping s : [1..m] × [1..n] ↦ {0, A, B}^{2} indicating whether a point at (x, y) has a value corresponding to

\{ \begin{matrix}• nothing s(x, y) = 0 \\ • an element of type A, s(x, y) = A \\ • an element of type B, s(x, y) = B \end{matrix}  (2)

the dynamics of the system will be described by a sequence of states s_{0}, s_{1}, ⋯, s_{n}, ⋯ generated by the following rules.

1. one fixes a threshold (in percent) 0 ≤ t ≤ 1;

2. the original state is s_{0} (i.e. a distribution of A, B and empty cells along the board);

3. at each step, for each (filled) cell of type X at (x, y), one counts the ratio ρ(x, y) of neighbours of type X over the number of neighbours;

4. if ρ ≥ t the cell is marked r (remain), if not it is marked m (move);

5. let M be the set of cells marked “move” and E the set of empty cells;

6. choose randomly (uniform distribution) α among the generalized derangements M ↦ M ∪ E;

7. then s_{n+1}(x, y) = s_{n}(x, y) if the cell was marked r and s_{n+1}(x, y) = α(s_{n}(x, y)) otherwise.

This algorithm is typically controlled by grid diffusion processus using elementary rule-based systems. The rules leading to each move is based on local computation of neighbourhood, however the moves are global, holistic self-organizational. The following section proposes more sophisticated behavior modelled by agent systems.

RANDOM GENERATION FOR THE STUDY OF THE PROPERTIES OF THE DYNAMIC PROCESS

In order to make experiences for the description of emerging phenomena varying the threshold. We have to be able to draw “at random” a generalized derangement M ↦ M ∪ E (step 6). This can be done very efficiently using a step by step random generation of the images. But one must be aware that, given a fixed element of M, say m_{0} the set of generalized derangements α such that α(m_{0}) ∈ E has not the same cardinality that the set of generalized derangements α such that α(m_{0}) ∈ M. More precisely, if one denotes gd(M, E) the set of generalized derangements M ↦ M ∪ E and gd(m, e) its cardinality (m = |M| and e = |E|), one has

• gd(0, e) = 1

• gd(m, 0) = d_{m}, the number of classical derangements, given by the formula

∑_{n=0}^{∞} d_{n} \frac{z^{n}}{n!} = exp(∑_{n=2}^{∞} \frac{z^{n}}{n!} )  (3)

• gd(m, e + 1) = gd(m, e) + m gd(m − 1, e + 1)

Moreover, the graphs of generalized derangements are of “exponential class” (Duchamp et al. 2003, Stanley 1999, Wilf 1994) and therefore, the multivariate stastistics of them can be treated by the exponential formula (a formula invented by the Physicist G. E. Uhlenbeck, see (Goulden and Jackson 1983)). One can then harness elegantly the random generation by computing explicitely the branching quantities. The combinatorial study of these probabilities does not meet the purpose of this contribution and will be the subject of a forthcoming paper.

CONCLUSION AND PERSPECTIVES

This paper presents a definition of Schelling’s model using generalized derangements. Thanks to the non sequential dependant algorithm formalism proposed here, we gives an efficient tool to study the properties of the system dynamic. Combinatorial studies and implementation of this segregation model description are in progress. Convergence properties could be then studied and are expected to be obtained.

REFERENCES

Benenson I. and Torrens P.M., 2004. Geosimulation. Wiley.

Daudé E. and Langlois P., 2006. Modélisation et simulation multi-agents, Hermès Sciences, Lavoisier, chap. Comparaison de trois implémentations du modèle de Schelling. 411–442.

Duchamp G.; Solomon A.; Penson K.; Horzela A.; and lasiak P.B., 2003. One-parameter groups and combinatorial physics. In M.N.H. J. Govaerts and A.Z.M. (eds.) (Eds.), Proceedings of the Symposium Third International Workshop on Contemporary Problems in Mathematical Physics (COPROMAPH3). World Scientific Publishing 2004, Port-Nove, Benin, 436.

  ArXiv: quant-ph/04011262.

1see http:en.wikipedia.orgwikiInjective function 2We can extend the model using greater alphabet cardinal

Ghnemat R.; Bertelle C.; and Duchamp G.H., 2007. Community Swarm Optimization. In workshop on Emergent Properties for Natural and Artificial Complex Systems, ECCS’07. Dresden, Germany.

Goulden I.P. and Jackson D.M., 1983. Combinatorial Enumeration. John Wiley & Sons Inc.

Laurie A.J. and Jaggi N.K., 2003. Role of ’Vision’ in neighborhood racial segregation: a variant of the Schelling segregation model. Urban Studies, 40(14), 2687–2704.

LeMoigne J.L., 1999. La modélisation des systèmes complexes. Dunod.

Omer I., 2005. How ethnicity influences residential distributions: an agent-based simulation. Environment and Planning B: Planning and Design, 32, 657–672.

Pumain D. (Ed.), 2006. Hierarchy in Natural and Social Sciences. Springer.

Schelling T.C., 1971. Dynamic Models of Segregation. Journal of Mathematical Sociology, 1, 143–186.

Singh A. and Haahr M., 2006. Creating an adaptive network of hubs using Schelling’s model. Communication of the ACM, 49(3), 69–73.

Stanley R., 1999. Enumerative combinatorics. Cambridge University Press.

Strout N., 2006. What is Agent Analyst. In The 2006 ESRI International User Conference. San Diego.

Weiss G. (Ed.), 1999. Multiagent Systems. MIT Press.

Wilf H., 1994. Generating Functionology. Academic Press, New York.