\documentclass[a4paper,twocolumn,10pt]{article}
%\documentclass{llncs}
\usepackage{eurosis}
\usepackage{url}
\usepackage{natbib}

%\bibliographystyle{plainnat}
\bibliographystyle{eurosis}

%\bibliographystyle{abbrvnat}
\bibpunct[; ]{(}{)}{,}{a}{}{;}


%%%%%%%%%%%%%%%%%%%%%%
% \'Enonc\'es
%%%%%%%%%%%%%%%%%%%%%%

\newtheorem{example}{Example}[section]
\newtheorem{exercice}{Exercice}[section]
\newtheorem{note}[example]{Note}
%\newtheorem{mexo}[example]{Exercice Machine}
\newtheorem{theorem}[example]{Theorem}
\newtheorem{corollary}[example]{Corollary}
\newtheorem{definition}[example]{Definition}
\newtheorem{proposition}[example]{Proposition}
\newtheorem{prdef}[example]{Proposition/Definition}
\newtheorem{algorithme}[example]{Algorithm}
\newtheorem{lemma}[example]{Lemme}
\newtheorem{remark}[example]{Remark}
\newtheorem{appli}[example]{Applications}

%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%
% Sauts
%%%%%%%%%%%%%%%%%%%%%%

\def\hs{\hbox to 3mm{}}
\def\hhs{\hbox to 5cm{}}
\def\ss{\smallskip}
\def\ms{\smallskip}
\def\bs{\bigskip}
\def\bbss{\vskip 6mm}

%%%%%%%%%%%%%%%%%%%%%%
% Divers
%%%%%%%%%%%%%%%%%%%%%%

\def\A{{\mathcal A}}
%\def\A{{\sym A}}
\def\B{{\cal B}}
\def\C{{\cal C}}
\def\E{{\sym E}}
\def\F{{\sym F}}
\def\N{{\sym N}}
\def\M{{\cal M}}
\def\al{\alpha}
\def\be{\beta}
\def\ga{\gamma}
\def\ep{\epsilon}
\def\om{\omega}
\def\si{\sigma}
\def\S{{\Sigma}}
\def\ra{\rightarrow}
\def\binomial#1#2{\left(\,\matrix{#1 \cr #2}\,\right)}
\def\pointir{\unskip . --- \ignorespaces}
\def\mref#1{(\ref{#1})}
\def\cqfd{\hfill $\Box$ \bigskip}
\def\Box{\fbox{\hspace{0.5mm}}}
\def\rem{{\bf Remarque}\pointir }
\def\ul#1{\underline{#1}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\begin{document}


\title{GRADED SCHELLING'S CITY SEFREGATION MODEL :\\ 
DATA STRUCTURES AND IMPLEMENTATION NOTES.}

\author{G\'erard H.E. Duchamp$^{(1)}$, Cyrille Bertelle$^{(2)}$, Rawan Ghnemat$^{(2)}$\\~\\
$^{(1)}$LIPN - University of Paris XIII, 99 avenue Jean-Baptiste Cl\'ement, 93430 Villetaneuse, France\\
email: \texttt{ghed@lipn.univ-paris13.fr}\\~\\
$^{(2)}$LITIS - University of Le Havre, 25 rue Philippe Lebon, BP 540, 76058 Le Havre Cedex, France\\
email: \texttt{rawan.ghnemat@litislab.eu},  \texttt{cyrille.bertelle@litislab.eu}
}

\date{}

\maketitle

\thispagestyle{empty}

\keywords{self-organization, urban modelling, generalized derangement, Schelling's model, exponential formula}

\begin{abstract}

\end{abstract}


\section{INTRODUCTION}
{\tt ancienne intro : \`a 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 \citep{Pumain2006a}. 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 \citep{Moigne1999} which allows to deal with the dynamic detection of emergent organizations using swarm optimization processes \citep{Ghnemat2007}, for example. Practical applications deal today with the development of Geographical Information Systems (GIS) which give accurate spatial data and allow with specific platforms \citep{Strout2006} 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 \citep{schelling1971}. 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 \citep{Singh2006}.\\


\section{GENERAL DESCRIPTION OF SCHELLING'S MODEL USING GENERALIZED DERANGEMENTS}


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 passée\\
2) Graded model\\
le besoin de cellules "frontalières"\\
3) Combinatorial study\\
séries generatrices\\
4) Conclusion
\hrule

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 \citep{Stanley1999}:

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

Here it will be called {\it generalized derangement}.

\begin{definition} Let $X,Y$ be two sets $X\subset Y$. A {\rm generalized derangement} from $X$ to $Y$ is an into (i. e. injective) mapping \footnote{see {\tt http:\/\/en.wikipedia.org\/wiki\/Injective\_function}}
$\al\ :\ X\mapsto Y$ such that 
\begin{equation}
	(\forall x\in X)(\al(x)\not= x)
\end{equation}
\end{definition} 

To describe Thomas Schelling's concurrent model, we start with a two-dimensional lattice board which is a rectangle of $n \times m$ ($n$ lines and $m$ columns) points (each point will be located by its coordinates $(x,y)$ with $1\leq x\leq m\ ;\ 1\leq y\leq n$). A {\it state} of the board will be simply a mapping $s\ :\ [1..m]\times [1..n]\mapsto \{0,A,B\}$\footnote{We can extend the model using greater alphabet cardinal} indicating whether a point at $(x,y)$ has a value corresponding to 

\begin{equation}\label{state}
\left\{
\begin{array}{l}
	\bullet\ \textrm{ nothing } s(x,y)=0\\ 
	\bullet\ \textrm{ an element of type } A,\ s(x,y)=A\\
	\bullet\ \textrm{ an element of type } B,\ s(x,y)=B\\
\end{array}
\right.	
\end{equation}

the dynamics of the system will be described by a sequence of states $s_0,\ s_1,\cdots ,\ s_n,\cdots $ generated by the following rules. 

%\renewcommand{\labelitemi}{$\bullet$}

\begin{enumerate}
	\item one fixes a threshold (in percent) $0\leq t\leq 1$;
	\item the original state is $s_0$ (i.e. a distribution of $A,B$ and empty cells along the board); 
	\item at each step, for each (filled) cell of type $X$ at $(x,y)$, one counts the ratio $\rho(x,y)$ of neighbours of type $X$ over the number of neighbours;
	\item if $\rho\geq t$ the cell is marked $r$ (remain), if not it is marked $m$ (move); 
	\item let $M$ be the set of cells marked ``move'' and $E$ the set of empty cells;
	\item choose randomly (uniform distribution) $\al$ among the generalized derangements $M\mapsto M\cup E$;
	\item then $s_{n+1}(x,y)=s_n(x,y)$ if the cell was marked $r$ and $s_{n+1}(x,y)=\al(s_n(x,y))$ otherwise.
\end{enumerate}

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.


\section{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\mapsto M\cup 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 $\alpha$ such that $\alpha(m_0)\in E$ has not the same cardinality that the set of generalized derangements $\alpha$ such that $\alpha(m_0)\in M$. More precisely, if one denotes $gd(M,E)$ the set of generalized derangements $M\mapsto M\cup E$ and $gd(m,e)$ its cardinality ($m=|M|$ and $e=|E|$), one has 
%
\renewcommand{\labelitemi}{$\bullet$}
%
\begin{itemize}
	\item $gd(0,e)=1$
	\item $gd(m,0)=d_m$, the number of classical derangements, given by the formula 
\begin{equation}
\sum_{n=0}^\infty d_n\frac{z^n}{n!}=exp(\sum_{n=2}^\infty \frac{z^n}{n!})
\end{equation}
  \item $gd(m,e+1)=gd(m,e)+m\ gd(m-1,e+1)$ 
\end{itemize}

Moreover, the graphs of generalized derangements are of ``exponential class'' 
\citep{OPM,Stanley1999,Wi} 
and therefore, the multivariate stastistics of them can be treated by the exponential formula (a formula invented by the Physicist G. E. Uhlenbeck, see \citep{GJ}). 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.  


\section{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.
% The model constructed here takes into account the desynchronization of the process in the real life (say that somebody which has the intention of moving do not often inform other people in the same situation). Implementation of the model can be made rather easy and will lead to new accurate observations. 

\nocite{*}

\begin{thebibliography}{15}
\providecommand{\natexlab}[1]{#1}
\providecommand{\url}[1]{\texttt{#1}}
\providecommand{\urlprefix}{URL }
\expandafter\ifx\csname urlstyle\endcsname\relax
  \providecommand{\doi}[1]{doi:\discretionary{}{}{}#1}\else
  \providecommand{\doi}{doi:\discretionary{}{}{}\begingroup
  \urlstyle{rm}\Url}\fi

\bibitem[{Benenson and Torrens(2004)}]{Benenson2004}
Benenson I. and Torrens P.M., 2004.
\newblock \emph{Geosimulation}.
\newblock Wiley.

\bibitem[{Daud\'e and Langlois(2006)}]{Daude2006}
Daud\'e E. and Langlois P., 2006.
\newblock \emph{Mod\'elisation et simulation multi-agents}, Herm\`es Sciences,
  Lavoisier, chap. Comparaison de trois impl\'ementations du mod\`ele de
  Schelling.
\newblock 411--442.

\bibitem[{Duchamp et~al.(2003)Duchamp, Solomon, Penson, Horzela, and
  lasiak}]{OPM}
Duchamp G.; Solomon A.; Penson K.; Horzela A.; and lasiak P.B., 2003.
\newblock \emph{One-parameter groups and combinatorial physics}.
\newblock In M.N.H. J.~Govaerts and A.Z.M. (eds.) (Eds.), \emph{Proceedings of
  the Symposium Third International Workshop on Contemporary Problems in
  Mathematical Physics (COPROMAPH3)}. World Scientific Publishing 2004,
  Port-Nove, Benin, 436.
\newblock ArXiv: {\tt quant-ph/04011262}.

\bibitem[{Ghnemat et~al.(2007)Ghnemat, Bertelle, and Duchamp}]{Ghnemat2007}
Ghnemat R.; Bertelle C.; and Duchamp G.H., 2007.
\newblock \emph{Community Swarm Optimization}.
\newblock In \emph{workshop on Emergent Properties for Natural and Artificial
  Complex Systems, ECCS'07}. Dresden, Germany.

\bibitem[{Goulden and Jackson(1983)}]{GJ}
Goulden I.P. and Jackson D.M., 1983.
\newblock \emph{Combinatorial Enumeration}.
\newblock John Wiley \& Sons Inc.

\bibitem[{Laurie and Jaggi(2003)}]{Laurie2003}
Laurie A.J. and Jaggi N.K., 2003.
\newblock \emph{Role of 'Vision' in neighborhood racial segregation: a variant
  of the Schelling segregation model}.
\newblock \emph{Urban Studies}, 40(14), 2687--2704.

\bibitem[{LeMoigne(1999)}]{Moigne1999}
LeMoigne J.L., 1999.
\newblock \emph{La mod\'elisation des syst\`emes complexes}.
\newblock Dunod.

\bibitem[{Omer(2005)}]{Omer2005}
Omer I., 2005.
\newblock \emph{How ethnicity influences residential distributions: an
  agent-based simulation}.
\newblock \emph{Environment and Planning B: Planning and Design}, 32, 657--672.

\bibitem[{Pumain(2006)}]{Pumain2006a}
Pumain D. (Ed.), 2006.
\newblock \emph{Hierarchy in Natural and Social Sciences}.
\newblock Springer.

\bibitem[{Schelling(1971)}]{schelling1971}
Schelling T.C., 1971.
\newblock \emph{Dynamic Models of Segregation}.
\newblock \emph{Journal of Mathematical Sociology}, 1, 143--186.

\bibitem[{Singh and Haahr(2006)}]{Singh2006}
Singh A. and Haahr M., 2006.
\newblock \emph{Creating an adaptive network of hubs using Schelling's model}.
\newblock \emph{Communication of the ACM}, 49(3), 69--73.

\bibitem[{Stanley(1999)}]{Stanley1999}
Stanley R., 1999.
\newblock \emph{Enumerative combinatorics}.
\newblock Cambridge University Press.

\bibitem[{Strout(2006)}]{Strout2006}
Strout N., 2006.
\newblock \emph{What is Agent Analyst}.
\newblock In \emph{The 2006 ESRI International User Conference}. San Diego.

\bibitem[{Weiss(1999)}]{Weiss1999}
Weiss G. (Ed.), 1999.
\newblock \emph{Multiagent Systems}.
\newblock MIT Press.

\bibitem[{Wilf(1994)}]{Wi}
Wilf H., 1994.
\newblock \emph{Generating Functionology}.
\newblock Academic Press, New York.

\end{thebibliography}
\end{document}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\bibliography{cossom07ghedBiblio}

% \begin{thebibliography}{apalike}
% 
% \bibitem{geosimulation} Benenson, I., Torrens, P.M. (2004) {\it Geosimulation - Automata-based modeling of urban phenomena}, Wiley.
% 
% \bibitem{rawan2007b} Ghnemat, R., Bertelle, C., Duchamp, G.H.E. (2007) {\it Community Swarm Optimization}, workshop on Emergent Properties for Natural and Artificial Complex Systems, ECCS'2007, Dresden, Germany.
% 
% \bibitem{Mo} Le Moigne, J.-L. (1999) {\it La mod\'elisation des syst\`emes 
% complexes}, Dunod. 
% 
% \bibitem{schelling} Schelling, T.C. (1971) {\it Dynamic Models of Segregation}, Journal of Mathematical Sociology, Vol. 1:143-186.
% 
% \bibitem{p2pSchelling} Singh, A., Haahr, M. (2004) {\it Topology Adaptation in P2P Networks Using Schelling's Model}, workshop on Emergent Behavior and Distributed Computing, PPSN.
% 
% \bibitem{St} Stanley, R.P. (1999) {\it Enumerative combinatorics}, Cambridge University Press.
% %
% \bibitem{repast} Strout, N. (2006) {\it What is Agent Analyst}, The 2006 ESRI International User Conference, San Diego.
% 
% \bibitem{weiss} Weiss, G. (ed.) (1999) {\em Multiagent Systems}, MIT Press.
% 
% \end{thebibliography}

\end{document}

