
\documentclass[twocolumn]{article} % default is 10 pt
\usepackage{graphicx} % needed for including graphics e.g. EPS, PS

\long\def\comment#1{}

% uncomment if don't want page numbers
 \pagestyle{empty}

%set dimensions of columns, gap between columns, and paragraph indent

\setlength{\textheight}{9.5in} \setlength{\columnsep}{1pc}
\setlength{\textwidth}{7in}

\setlength{\topmargin}{0in}

\setlength{\headheight}{0.0in}
\setlength{\headsep}{0.0in}
\setlength{\oddsidemargin}{-0.35in}
\setlength{\evensidemargin}{-0.35in}
\setlength{\parindent}{0pt}
\setlength{\parskip}{0.12in}
\makeatletter
\def\@normalsize{\@setsize\normalsize{10pt}\xpt\@xpt
\abovedisplayskip 10pt plus2pt minus5pt\belowdisplayskip
\abovedisplayskip \abovedisplayshortskip \z@
plus3pt\belowdisplayshortskip 6pt plus3pt
minus3pt\let\@listi\@listI}

%need an 11 pt font size for subsection and abstract headings
\def\subsize{\@setsize\subsize{12pt}\xipt\@xipt}
%make section titles bold and 12 point, 2 blank lines before, 1 after
\def\section{\@startsection {section}{1}{\z@}{1.0ex plus
1ex minus .2ex}{.2ex plus .2ex}{\large\bf}}
%make subsection titles bold and 11 point, 1 blank line before, 1 after
\def\subsection{\@startsection
   {subsection}{2}{\z@}{.2ex plus 1ex} {.2ex plus .2ex}{\subsize\bf}}
\makeatother


%%%%%%%%%%%%%%%%%%%%%%
% \'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}

% don't want date printed
\date{}

% >>>>>>>>>>>>>>>>>>>>>>>  Put your title here <<<<<<<<<<<<<<<<<<<<<<<<
% make title bold and 14 pt font (Latex default is non-bold, 16pt)
\title{\huge {\bf Adaptive Automata Community \\Detection and Clustering\\-- A generic methodology -- }}

% >>>>>>>>>>>>>>>>>>>>>>> Author's Name, Thanks or Affliation <<<<<<<<
\author{Rawan Ghnemat(1), Cyrille Bertelle(1) and G\'erard H.E. Duchamp (2)
 \thanks{(1) LITIS - Le Havre University, 25 rue Philippe Lebon, 76058 Le Havre Cedex, France,
rawan.ghnemat@gmail.com, cyrille.bertelle@gmail.com;
(2) LIPN - Paris XIII University, 99 avenue Jean-Baptiste Cl\'ement, 93430 Villetaneuse, France,
gheduchamp@gmail.com
 }
}

\maketitle
\thispagestyle{empty}

%\subsection*{}

% >>>>>>>>>>>>>>>>>>>>>>>>> Keywords and Abstract <<<<<<<<<<<<<<<<<<<<<
% Replace with your own keywords and abstract.  Text will be in italics
{\hspace{1pc} {\it{\small Abstract }}{\bf{\small---
% The hardness of social systems modelling comes from the fast evolution of communities, according to their topological properties but also on their shared goals which give meaning to their organization. 
We present in this paper a generic methodology based on genetic automata for modelling community detection.
With Communities, we deal with dynamic organizations which are self-organized from two aspects, the spatial one and the functional one. We propose in this paper a general methodology which extends cellular based modelling - like Schelling models - to more sophisticated approaches based on agent behavior modelling. These agent behaviors are modelled by automata with multiplicities. These automata-based models allow to define powerful operators like genetic operators and behavioral semi-distance. Mixing these operators, we can propose a complex computing, dealing with spatial self-orgnaization coupled with behavioral similarity for adaptive self-organized systems. 

\em Keywords: Agent-based modelling, Community Detection, Genetic Automata, Self-Organization, Segregation models.

Submitted to ICCIIS'07
 }}
 }

% >>>>>>>>>>>>>>>>>>>>>> START OF YOUR PAPER <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
% Typically paper starts of with an Introduction header.  Replace text in
% the french braces if you see fit.  I also typically name the label the
% same as the section

\section{Introduction}
\label{Introduction}

The current effort on Complexity Theory and its formalism, able to cover a wide area in many aspects of Science, allows today to make relevant links between social, biological and physical systems \cite{capra202}. The complicated and reductionnist methodologies avoid since many years to light the natural connections between many aspects of the World representation. For example, ecosystems and urban systems cannot be modelled with disconnected theories. Even if the first ones deals with natural processes and the second with social ones, the both are composed with a wide range of interacting entities crossed by energetic fluxes. These fluxes, whatever they are: light, displacment or simply informational fluxes, act on systems in endless adaptive processes. These fluxes compose, rearrange, destroy and recompose dynamic structures or systems. 
% The life is full of these systems which evolve as dissipative structures far from equilibrium, as defined by I. Prigogyne \cite{xxx}. 
Lighten by social description, we can describe some of these evolutive systems as {\it Communities}. Studying and modelling communities consists in the description of spatial self-organizations, controled by some global objectives. 
% or by cooperative or competitive strategies or also by some global interaction networks. Urban systems deal with such communities; they are the place of complex networks, .... (to complete with purpose of generation 5 paper and MTG-Paper). \\

This paper presents the new way of modelling communities and social systems based on complex systems approach. We will start our study by cellular automata which are widely used in geographical systems modelling. One of the most current studied communities is the result of segregation Schelling model \cite{schelling} is the basis of such simulations. Section~\ref{sso} describes the self-organization concept in social systems which can be considered as the most complex ones. We present computing concepts and tools capable to produce efficient emergent computing to implement such self-organization phenomena.  Section~\ref{ca} describes the segregation-based models as specific spatial self-organization models using cellular automata and grid decomposition where basic elements are fully reactive grid cases controlled by rules-based systems. Our purpose is to deal with more sophisticated behaviors like agent-based ones. So, section~\ref{absm} proposes an algebraic formalism for agent behavior based on automata with multiplicities, characterized by powerful operators like behavior semi-distance and genetic operators. Section~\ref{cd} presents a methodology for Community detection. The general processus proposed here, is based on the following properties which deal with the characteristics of these complex dynamic communities: (i) the process is based on an adaptive computation; (ii) self-organized behavioral systems are automatically computed using algebraic properties of the automata formalism; (iii) a spatial self-organization detection finally results as an emergent property of the overall process. Section~\ref{conclusion} concludes and gives the perspectives of our work.


\section{Modelling Self-Organized Social Systems Using Emergent Computing}
\label{sso}

The complexity modelling for social systems theory focuses nowadays on self-organization processes \cite{fuchs}. The initial self-organization description generally comes from physical or chemical, and it means of self-structuration of mater. The social systems can be considered as the most complex ones because we must be aware of reminding that these systems include human behaviors which are active and self-conscious subjects, and so generate some self-creative consequences. The social systems theory deals with dialectic approaches between systems and individual human behaviors, under the fluxes of economy and politic: systems are the results of human interactions and these systems influence individual thinkings and actions on itself. \\

Today, Computer Sciences both on its conceptual improvment for modelization and on its technological development, allow to give experimental tools for social systems theory \cite{edmonds}. 
The emergent computing gives nowadays relevant simulation tools for complexity study and specifically social systems. It can be mainly classified in two categories:
\begin{itemize}
\item Cellular automata which generally deals with spatial self-organizations; 
Cellular automata \cite{mtg} are tools for study some diffusion models of spatial organizations. They are based on grid case description as rules-based systems.
We present this kind of models in section \ref{ca}.
\item Agent-based modeling which generally deals with adaptive complex behavior. We present this kind of models in section \ref{absm}.  
\end{itemize}

\section{Segregation-Based Models using Cellular Automata}
\label{ca}

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. His description can easily be adapted to cellular automata models 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 model can be used as generic spatial self-organization concept for various kinds of systems: A. Singh and M. Haahr, for example, use a variation of this model to study the topology adaptation in P2P networks \cite{p2pSchelling}.\\


% In the next paragraph, we present an original description of the schelling's model implementation using an adapted formalism called {\it Derangement}. 

%\subsection{A correct implementation of Schelling's model}
%\label{schellingFormal}

The original Schelling's model can be extended in concurrent version in order to obtain an exact definition of the implementation for each time step, not depending of the grid way \cite{rawan2007}. 

In the following, we will make use of the (somewhat extended) notion of derangement. For the classical notion see \cite{St}:

\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 mapping $\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 cellular automata 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{itemize}
	\item one fixes a threshold (in percent) $0\leq t\leq 1$
	\item the original state is $s_0$ (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 $r(x,y)$ of neighbours of type $X$ over the number of neighbours
	\item if $r\geq t$ the cell is marked $s$ (stay), 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 $s$ and $s_{n+1}(x,y)=\al(s_n(x,y))$ otherwise.
\end{itemize}

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

\section{Agent-Based System Modelling}
\label{absm}

In this section, we give the basis of the conceptual tools that allow to extend the reactive and diffusive grid cases behavior to more sophisticated entities, using agent-based model. We propose to model the agent behavior with automata with multiplicities which are powerful algebraic stuctures.

\subsection{Basic agent-based concepts and complex systems modelling}
\label{basicABM}

\begin{figure*} [ht]
\begin{center}
\includegraphics[scale=0.85]{sys2beh.eps}
\caption{Multi-scale complex system description: from global to individual 
models}
\label{sys2beh}
\end{center}
\end{figure*}

According to General System Theory \cite{Mo}, a complex system is composed 
of entities in mutual interaction and interacting with the outside environment. A 
system has some characteristic properties which confer its structural aspects, 
as schematically described in part (a) of Figure~\ref{sys2beh}: 
\begin{itemize}
\item The set elements or entities are in interactive dependance. The alteration 
of only one entity or one interaction reverberates on the whole system. 
\item A global organization emerges from interacting constitutive elements. This 
organization can be identified and carries its own autonomous behavior while it 
is in relation and dependance with its environment. The emergent organization 
possesses new properties that its own constitutive entities don't have.
\item The global organization retro-acts over its constitutive components.\\
\end{itemize}

The interacting entities network as described in part (b) of Figure 
\ref{sys2beh} leads each entity to perceive informations or actions from other 
entities or from the whole system and to act itself.\\

A well-adapted modeling consists of using an agent-based representation which is 
composed of the entity called agent as an entity which perceives and acts on an 
environment, using an autonomous behaviour as described in part (c) of 
Figure \ref{sys2beh}.\\

To compute a simulation composed of such entities, we need to describe the 
behaviour of each agent. This one can be schematically described using internal 
states and transition processes between these states, as described in part 
(d) of Figure \ref{sys2beh}. So an automata with multiplicities as described in the following section is well-adapted for the agent behavior modelling.\\  

% There are several definitions of ``agents'' or ``intelligent agents'' according 
% to their behaviour specificities~\cite{Fe, We}.
% Their autonomy  means that the agents try to satisfy a goal
% and execute actions, optimizing a satisfaction function to reach it.\\
% 
% For agents with high level autonomy, specific actions are realized even when no 
% perception are detected from the environment. 
% To represent the process of this deliberation, different formalisms can be 
% used and a behaviour decomposed in internal states is an effective approach.
% Finally, when many agents operate, the social aspects must also be taken into 
% account. 
% These aspects are expressed as communications through agent organisation with 
% message
% passing processes. 
% Sending a message is an agent action and receiving a message is an agent 
% perception. The previous description based on the couple: perception and action, 
% is well adapted to this.


\subsection{Automata-based modelling for agent behavior}
\label{Automata4agent}

An automaton with multiplicities is based on the fact that the output data of 
the automata with output belongs to a specific algebraic structure, a 
semiring, including real, complex, probabilistic, non commutative semantic outputs (transducers) \cite{Go,St}. 
In that way, we will be able to build effective operations on such automata, 
using the power of the algebraic structures of the output data. 
We are also able to describe automaton by means of a matrix 
representation with all the power of the new (i.e. with semirings) linear algebra.\\

\begin{definition}
{\bf (Automaton with multiplicities)}\\
 An automaton with multiplicities over an alphabet  $A$  and a semiring $K$ is 
the 5-uple $(A,Q,I,T,F)$ where
\begin{itemize}
\item  $Q=\{S_1,S_2\cdots S_n\}$ is the finite set of state;
\item   $I: Q\mapsto K$  is a function over the set of states, which 
associates to each initial state a value of K, called entry cost, and to non-
initial state a zero value ;
\item	$F: Q\mapsto K$  is a function over the set states, which 
associates to each final state a value of K, called final cost, and to non-final 
state a zero value;
\item $T$ is the transition function, that is $T: Q\times A\times Q\mapsto K$ 
which to a state $S_i$, a letter $a$ and a state $S_j$ associates a value $z$ of 
$K$ (the cost of the transition) 
if it exist a transition labelled with $a$ from the state $S_i$  to the 
state $S_j$ and and zero otherwise.\\   
\end{itemize}
\end{definition}

% \begin{remark} 
% Automata with multiplicities are a generalisation of finite automata. In fact, 
% finite automata can be considered as automata with multiplicities in the 
% semiring $K$, the boolan set $B=\{0,1\}$ (endowed with the logical ``or/and'').
%  To each transition we affect 1 if it exists and 0 if not.\\
% \end{remark}

\begin{remark}
\label{linearRepresentation}
We have not yet, on purpose, defined what a semiring is. Roughly it is the least 
structure 
 which allows the matrix ``calculus'' with unit (one can think of a ring without the 
"minus" operation).
The previous automata with multiplicities can be, equivalently, expressed by a 
matrix representation which is a triplet 
\begin{itemize}
\item $\lambda\in K^{1\times Q}$ which is a row-vector which coefficients are 
$\lambda_i=I(S_i)$,
\item $\gamma\in K^{Q\times 1}$ is a column-vector which coefficients are 
$\gamma_i=F(S_i)$,
\item $\mu: A^*\mapsto K^{Q\times Q}$ is a morphism of monoids (indeed 
$K^{Q\times Q}$ is endowed with the product of matrices) such that 
the coefficient on the $q_i$th row and $q_j$th column of $\mu(a)$ is 
$T(q_i,a,q_j)$ 
\end{itemize} 

\end{remark}

\begin{definition}
{\bf (Automata-Based Agent Behavior)}\\
We represent the agent behavior by automata with multiplicities $(A,Q,I,T,F)$ over a semiring $K$:
\begin{itemize}
\item The agent behavior is composed of a states set $Q$ and of rule-based transitions between them. These transitions are represented by $T$; $I$ and $F$ represent the initial and final transitions;
\item Alphabet $A$ corresponds to the agent perceptions set;
\item The semiring $K$ is the set of agent actions, eventually associated to a probabilistic value which is the action realization probability (as defined in \cite{ghnemat05}).
\end{itemize}
\end{definition}


\subsection{Agent Behavior Metric Space}
\label{agentMetric}

% If $K$ is a field, one sees that the space $\A_{(n)}$ of automata of dimension 
% $n$ (with multiplicities in $K$) is a $K$-vector space of dimension 
% $k.n^2+2n$ ($k$ is here the number of letters). So, in case the ground field is 
% the field of real or complex numbers \cite{Bo1}, one 
% can take any vector norm (usually one takes one of the H\"older norms 
% $||(x_i)_{i\in I}||_\alpha := \big(\sum_{i\in I} | x_i 
% |^\alpha\big)^{\frac{1}{\alpha}}$ 
% for $\alpha\geq 1$,
%  but any norm will do) and the distance is derived, in the classical way, by 
% \begin{equation}
% d(\A_1,\A_2)=norm(V(\A_1)- V(\A_2))
% \end{equation}
% where $V(\A)$ stands for the vector of all coefficients of $\A=(\lambda,\mu,\gamma)$ 
% arranged in some order one has then the result of Theorem \ref{th1}.
%  Assuming that $K$ is the field of 
% real or complex numbers, we endow the 
% space of series/behaviours with the topology of  pointwise convergence (Topology 
% of F. Treves \cite{Tr}).  
% 
% \begin{theorem}\label{th1}
% Let  $(\A_n)$ be a sequence of automata with limit $\L$ ($\L$ is an automaton), 
% then one has
% \begin{equation}
% Behaviour(\L)=\lim_{n\rightarrow \infty} Behaviour(\A_n)
% \end{equation}
% where the limit is computed in the topology of Treves.
% \end{theorem}

% We describe in this section the bases of the genetic algorithm used on the 
% probabilistic automata allowing to manage emergent self-organizations in the 
% multi-agent simulation.\\


The main advantage of automata-based agent modelling is their efficient operators. We deal is this paragraph on a innovative way to define behavioral semi-distance as the essential key of self-organization processus proposed later.

% {\bf We will give here two evaluation functions for ABAB : Successful-path based one and structural based one ... The last is to define}
% 
% \begin{definition}
% \label{agentEval}
% {\bf (Successful-Path Based Evaluation function for automata-based agent behavior)}\\
% For each automata-based agent, we define $e$ an evaluation function of its own
% behaviour returning the matrix $M$ 
% of evaluations \cite{BR} of subseries of 
% \begin{equation}
% M^*:=\left(\sum_{a\in A} \mu(a)a\right)^*
% \end{equation}
% $M_{i,j}$ is the output series from all possible successive perceptions when
% starting from the initial state $i$ and ending at the final state $j$,
% without cycle
% \end{definition}

\begin{definition}
\label{agentEval}
{\bf (Evaluation function for automata-based behavior)}\\
Let $x$ an agent whom behavior is defined by ${\cal A}$, an automaton with multiplicities over the semiring $K$, we define the evaluation function $e(x)$ by:
$$ e(x)=V({\cal A})$$
where $V({\cal A})$ stands for the vector of all coefficients of $(\lambda, \mu, \gamma) $, the linear representation of ${\cal A}$, defined in remark \ref{linearRepresentation}.
\end{definition}
% \begin{remark}
% $M_{i,j}$ value is $0$ if either $i$ is not an initial
% state or $j$ is not a final one.
% \end{remark}
%equal to the value of the sum of the multipicities of all
%the successful paths between $i$ and $j$, without cycle, if $i$ is an
%initial state and $j$ is a final state, and is equal to $0$ otherwise. 
% \begin{remark}
% The coefficients of this matrix, as defined, are computed whatever the
% value of the perception in the alphabet $A$ on each transition on the successful
% path\footnote{A {\it succesful path} is a path from an initial state to a final 
% state}. 
% \end{remark}

% That means that the contribution of the agent behaviour for
% collective organization formation is only based, here, on
% probabilities to reach a final state from an initial one.     
% This allows to preserve individual characteristics in each agent
% behaviour even if the agent belongs to an organization.\\

\begin{definition}
\label{behavioralDistance}
{\bf (Behavioral semi-distance)}\\
Let $x$ and $y$ two agents and $e(x)$ and $e(y)$ their respective
evaluations as described in the previous definition \ref{agentEval}.
We define $d(x,y)$ a semi-distance or pseudometrics \footnote{see \cite{Bo1} ch IX} 
between the two agents $x$ and $y$ as 
$$d(x,y)=||e(x)-e(y)||$$ a vector norm of the difference of their
evaluations. 
\end{definition}


% \subsection{Cooperative/competitive modelling as an example of an elementary process for decision making}
% \label{dilemma}


\section{Community Detection using Genetic Spatial Automata Population}
\label{cd}

In this section, we give an operational definition of community in terms of functional concept dealing with complex and social modelling. To model such communities, we have to complete the concept of automata behavior with some spatial aspects and with some adaptive capabilities that genetic operators can allow to implement. With these concepts, we can model communities by evolutive population of these genetic spatial automata.

% We have defined in the previous section, the basic and generic tools which allow to implement the communities detection processus. The specific operators needed for this processus are based on genetic computation, leading to adaptive and evolutive systems.

\begin{definition}
{\bf (Community operational definition)}\\
A community is a system or an organization which is characterized by a spatial property, a behavior property and the interaction between the both. 
\end{definition}
% \subsection{Community concept definition}
% \label{communityDef}

\begin{example}
In ecology, a community is a group of plants or animals living in a specific region and interacting with one another.
\end{example}

The spatial patterns generated by Schelling models are some examples of communities and these spatial patterns are linked with the very specific behavioral rules implemented for each grid case. Our purpose here is to give a more generic processus which can be mixed with sophisticated agent behaviors. Using agent communication protocol, we can extend the diffusion process linked with cellular automata to more distant communications and interaction between spatial agents. In the following, we define this notion of spatial automata-based agents and then we develop the genetic operators allowing to transform automata with multiplicities to genetic automata. We will explain how the definition of adapted fitness will generate the detection processus.

\begin{definition}
{\bf (Spatial Automata-Based Agent)}\\
A spatial automata-based agent is defined by its structural representation:
\begin{itemize}
\item An automata with multiplicities corresponding to its behavior as a whole processus managing its perceptions and its actions over its environment. They include its communication capabilities and so its social behavior;
\item A spatial location defined on some specific metric space.
\end{itemize}
\end{definition}

\subsection{Genetic operators on automata population}
\label{geneticAutomata}

We consider in the following, a population of automata with multiplicities which are each represented by a chromosome, following the genetic algorithm principles.
We define the chromosome for each automata with multiplicities as the sequence 
of all the matrices 
 associated to each letter from the (linearly ordered) alphabet. 
The chromosomes are composed with alleles 
which are here the lines of the matrix \cite{BFJOP2}.\\

In the following, genetic algorithms are going to generate new automata 
containing possibly new transitions 
from the ones included in the initial automata.\\

The genetic algorithm over the population of automata with multiplicities 
follows a reproduction iteration 
broken up in three steps \cite{Gol}:
\begin{itemize}
\item 	{\it Duplication}: where each automaton generates a clone of itself; 
\item	{\it Crossing-over}: concerns a couple of automata. Over this couple, we 
consider a sequence of lines of each 
matrix  for all. For each of these matrices, a permutation on the lines of the 
chosen 
sequence is made between the analogue matrices of this couple of automata; 
\item	{\it Mutation}: where a line of each matrix  is randomly chosen and a sequence 
of new values is given for 
this line.
\end{itemize}

Finally the whole genetic algorithm scheduling for a full process of 
reproduction over all the population of 
agents is the evolutionary algorithm:

\begin{enumerate}
\item For all couple of agents, two children are created by duplication, 
crossover and mutation mechanisms over their behavioral automata. The location of the children can be choosen from many ways: on the linear segment defined by the parents location or as the node of a square described by them and their parents (more details are given in \cite{rawan2007b};
\item The fitness for each automaton is computed;
\item For all 4-uple composed of parents and children, the performless agents, 
in term of fitness 
computed in previous step, are suppressed. The two agents, still living, 
result from the evolution of the two initial parents.
\end{enumerate}

\begin{remark}
The fitness is not defined at this level of abstract formulation, but it is 
defined 
corresponding to the context for which the automaton is a model, as we will do in 
the next section.
\end{remark}


\subsection{Adaptive processus to implement community detection}
\label{CDdescription}

% {\bf Two distance ... behavior and spatial. Talk of spatial space and how implement genetic on spatial coordonates for crossing-over} 

The community detection is based on a genetic algorithm over a population of spatial automata-based agents. The formation of the community is the result of the population evolution crossing by a selection process computed with the fitness function defined in the following.\\

For this computation, we deal with two distances defined on agent set. The first is the spatial distance associated to the agent spatial location and the second is the behavioral semi-distance defined in the definition \ref{behavioralDistance}.\\

%%% definition of the fitness %%%%%%
\begin{definition}
{\bf Community clustering and detection fitness}\\
Let ${\cal{V}}_x$ a
neighbourhood of the agent $x$, relatively to its spatial location.  
We define $f(x)$ the agent fitness of the agent $x$ as~:
$$
f(x) = 
\left\lbrace
\begin{array}{ll}
\frac{ {\displaystyle card({\cal{V}}_x) } }
     { {\displaystyle \sum\limits_{y_i \in {\cal{V}}_{x}} d(x, y_i)^2} } 
     \ \ \ \ &\mbox{if} \sum\limits_{y_i \in {\cal{V}}_{x}} d(x,
y_i)^2 \neq 0 \\
\infty &\mbox{otherwise}
\end{array}
\right.
$$
where $d(x,y)$ is the behavioral semi-distance between the two agents $x$ and $y$.\\
\end{definition}

The genetic evolution of the spatial automata-based agents leads to a self-organization which creates a clustering of the agents set in such way that each cluster contains agents of similar behavior. 
During the evaluation process, genetic algorithms can be turned such that individuals {\it outside communities} be attracted to them.
The center of the clusters, the size of the clusters and the behavior of the agents in the center of each cluster are the result of the overall genetic processus which generates self-organization communities. 

\section{Conclusion and Perspectives}
The goal of this paper is to present a methodology for communities detection based on genetic automata population. This methodology is generic and can be adapted to many kinds of applications. We presently, implement this methodology on Geographical Information Systems (GIS) using RePast and Agent Analyst tool \cite{repast}. Spatial automata-based agent model associated to GIS, allows more powerful tools both for spatial and behavior description than cellular automata do and in that way, we can extend the reactive segregation-based modelling to urban area sharing under the influence of both citizen behavior but also under the influence of more elaborated decision making. These applicative experiments are in progress.
\label{conclusion}


\begin{thebibliography}{99}

% >>>>>>>>> Book examples <<<<<<<<<
\bibitem{geosimulation} Benenson, I., Torrens, P.M. (2004) {\it Geosimulation - Automata-based modeling of urban phenomena}, Wiley.

\bibitem{BR} Berstel, J., Reutenauer, G. (1988) {\it Rational series and their 
languages}, EATCS.
%
\bibitem{BFJOP2}Bertelle, C., Flouret, M., Jay, V., Olivier, D., Ponty, J.-L. (2001) 
{\it Genetic algorithms on automata with 
multiplicities for adaptive agent behaviour in emergent organizations} In {\em 
SCI'2001}, Orlando, Florida, USA, 
22-25th July 2001.

\bibitem{Bo1} Bourbaki, N. (1998) {\it Elements of Mathematics: General Topology}, 
Chapters 5-10, Springer-Verlag Telos.
%
\bibitem{capra202} Capra, F. (2002) {\it Hidden Connections. Integrating the biological, cognitive and social dimensions of life into a science of sustainability}, Doubleday ed.  

\bibitem{edmonds}Edmonds, B., Hales, D. (2005) {\it Computational Simulation as Theoretical Experiments}, Journal of Mathematical Sociology, Vol. 29(3):209-232.

\bibitem{fuchs} Fuchs, C. (2003) {\it Concepts of Social Self-Organization}, Research paper INTAS Project "Human Strategies in Complexity".

\bibitem{ghnemat05} Ghnemat, R., Oqeili, S., Bertelle, C., Duchamp, G.H.E. (2006) {\it Automata-Based Adaptive Behavior for Economic Modelling Using Game Theory}, in Aziz-Alaoui, M.A., Bertelle, C., {\it Emergent Properties in Natural and Artificial Dynamical Systems}, Springer.

\bibitem{rawan2007} Ghnemat, R., Duchamp, G.H.E., Bertelle, C. (2007) {\it An exact resolution of Schelling's segregation model using generalized derangements}, (submitted).

\bibitem{rawan2007b} Ghnemat, R., Bertelle, C., Duchamp, G.H.E. (2007) {\it Self-organized communities modelling by genetic spatial automata}, (submitted to the workshop EPNACS'07 within ECCS'2007, Dresden, Germany).

\bibitem{Go} Golan, J.S. (1999) {\em Power algebras over semirings}, Kluwer Academic 
Publishers.
%
\bibitem{Gol} Goldberg, D.E. (1989) {\em Genetic Algorithms}, Addison-Wesley.   
%
\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{Sc} Schutzenberger, M.P. (1961) {\it On the definition of a family of automata}, Information and Control, Vol. 4:245-270.
%
\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}
