Adaptive Automata Community Detection and Clustering - A generic methodology -

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

(1) LITIS - Le Havre University - France (2) LIPN - Paris XIII University - France

ICCIIS’07 - WCE July 2-4, 2007 London, UK

Context  Self-Organization Modeling  Community Detect.  GIS & ABM  Conclusion

Outline

1 Context and Objectives
2 Self-Organization Modeling
3 Spatial and Behavioral Modeling Based on Community Detection
4 Application: Geographical Information Systems and Agent-Based Modeling mixing
5 Conclusion and Perspective

R. Ghnemat, C. Bertelle, G.H.E. Duchamp Community Detection and Clustering 2/29

Context and Objectives

Complexity theory cover wide area of Systems in Science, making relevant links between social, biological and physical systems; In these complex systems, spatial structures emerge from interacting entities crossed by energetic fluxes; These emergent spatial structure are self-organizations, controled by some global objectives; The communities computed in the following respect these characteristics.

R. Ghnemat, C. Bertelle, G.H.E. Duchamp Community Detection and Clustering 3/29

Complexity Concept Approach

Complexity Analysis is based on conceptual functions:

Complexity is based on multi-description

Multi-scale, Multi-actor and Multi-disciplinary Micro/Macro interaction in multi-scale description

Emergent self-organizations and associated morphologies

Dynamic of the organizations: their evolution and their adaptation Hierarchical structure of organization Organization feed-back on the entities (country laws feed-back on the cities management)

R. Ghnemat, C. Bertelle, G.H.E. Duchamp Community Detection and Clustering 4/29

Outline

1 Context and Objectives
2 Self-Organization Modeling
3 Spatial and Behavioral Modeling Based on Community Detection
4 Application: Geographical Information Systems and Agent-Based Modeling mixing
5 Conclusion and Perspective

R. Ghnemat, C. Bertelle, G.H.E. Duchamp Community Detection and Clustering 5/29

Self-Organization Modeling

Emergent Computing Classification Cellular Automata (CA) can model urban land-use or regional dynamics.

From Schelling’s model, we can study by CA simulation, the segregation-like phenomena

Agent-based modelling extends the basic diffusion rules of CA to more sophisticated behavioral processes. We developped in the following our specific agent behavior modeling using automata with multiplicities.

R. Ghnemat, C. Bertelle, G.H.E. Duchamp Community Detection and Clustering 6/29

Context  Self-Organization Modeling  Community Detect.  GIS & ABM  Conclusion

Agent-Based Modeling

Multi-agent for complex systems

R. Ghnemat, C. Bertelle, G.H.E. Duchamp Community Detection and Clustering 7/29

Context  Self-Organization Modeling  Community Detect.  GIS & ABM  Conclusion

Agent-Based Modeling

Interactives Agents System

R. Ghnemat, C. Bertelle, G.H.E. Duchamp Community Detection and Clustering 8/29

Context  Self-Organization Modeling  Community Detect.  GIS & ABM  Conclusion

Agent-Based Modeling

Agents modeling

R. Ghnemat, C. Bertelle, G.H.E. Duchamp Community Detection and Clustering 9/29

Context  Self-Organization Modeling  Community Detect.  GIS & ABM  Conclusion

Agent-Based Modeling

Automata-based Agent Behavior

R. Ghnemat, C. Bertelle, G.H.E. Duchamp Community Detection and Clustering 10/29

Context  Self-Organization Modeling  Community Detect.  GIS & ABM  Conclusion

Automata-based Agent Behavior Modeling

Automata with multiplicities Agent behavior is modelled by automata with multiplicities which is defined by

A set of perception represented by an alphabet A set of actions represented by a semi-ring K A set of states with a subset of initial states and a subset of final states A set of transitions between states which is generate by a perception in input and which generate an action in output

R. Ghnemat, C. Bertelle, G.H.E. Duchamp Community Detection and Clustering 11/29

Automata-based Agent Behavior Modeling

Automata with multiplicities Because the set of actions K is a semi-ring,

we can represented the automata using a linear representation (vectors and matrices), we can defined many kinds of operators on these automata and so improve automatic processes on agent management

R. Ghnemat, C. Bertelle, G.H.E. Duchamp Community Detection and Clustering 12/29

Example

Strategy modeling using probabilistic automata for game theory Automata based model for player behavior with adversory

2 behavioral states: Cooperate (s1: C) or Defect (s2:D) Probabilistic transition from one state to another according to what make the adversory at the previous step

R. Ghnemat, C. Bertelle, G.H.E. Duchamp Community Detection and Clustering 13/29

Example

Strategy modeling using probabilistic automata for game theory Automata based model for player behavior with adversory

2 behavioral states: Cooperate (s1: C) or Defect (s2:D) Probabilistic transition from one state to another according to what make the adversory at the previous step

R. Ghnemat, C. Bertelle, G.H.E. Duchamp Community Detection and Clustering 13/29

Example

Strategy modeling using probabilistic automata for game theory Automata based model for player behavior with adversory

2 behavioral states: Cooperate (s1: C) or Defect (s2:D) Probabilistic transition from one state to another according to what make the adversory at the previous step

R. Ghnemat, C. Bertelle, G.H.E. Duchamp Community Detection and Clustering 13/29

Example

Strategy modeling using probabilistic automata for game theory Automata based model for player behavior with adversory

2 behavioral states: Cooperate (s1: C) or Defect (s2:D) Probabilistic transition from one state to another according to what make the adversory at the previous step

R. Ghnemat, C. Bertelle, G.H.E. Duchamp Community Detection and Clustering 13/29

Example

Strategy modeling using probabilistic automata for game theory Automata based model for player behavior with adversory

2 behavioral states: Cooperate (s1: C) or Defect (s2:D) Probabilistic transition from one state to another according to what make the adversory at the previous step

R. Ghnemat, C. Bertelle, G.H.E. Duchamp Community Detection and Clustering 13/29

Example

Strategy modeling using probabilistic automata for game theory Automata based model for player behavior with adversory

2 behavioral states: Cooperate (s1: C) or Defect (s2:D) Probabilistic transition from one state to another according to what make the adversory at the previous step

R. Ghnemat, C. Bertelle, G.H.E. Duchamp Community Detection and Clustering 13/29

Example

Strategy modeling using probabilistic automata for game theory Automata based model for player behavior with adversory

2 behavioral states: Cooperate (s1: C) or Defect (s2:D) Probabilistic transition from one state to another according to what make the adversory at the previous step

R. Ghnemat, C. Bertelle, G.H.E. Duchamp Community Detection and Clustering 13/29

Outline

1 Context and Objectives
2 Self-Organization Modeling
3 Spatial and Behavioral Modeling Based on Community Detection
4 Application: Geographical Information Systems and Agent-Based Modeling mixing
5 Conclusion and Perspective

R. Ghnemat, C. Bertelle, G.H.E. Duchamp Community Detection and Clustering 14/29

Spatial and Behavioral Modeling Based on Community Detection

Spatial agent and associated distances

A spatial agent is defined by

Spatial coordinates

A behavior modeled by an automaton with multiplicities

A spatial distance between 2 agents, can be computed according to their spatial coordinates A behavioral distance between 2 agents can be compute by the distance between the vectors which stores all the coefficients of the linear representation of the agent behavior automata.

R. Ghnemat, C. Bertelle, G.H.E. Duchamp Community Detection and Clustering 15/29

Spatial and Behavioral Modeling Based on Community Detection

Community 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.

R. Ghnemat, C. Bertelle, G.H.E. Duchamp Community Detection and Clustering 16/29

Spatial and Behavioral Modeling Based on Community Detection

Genetic operators on automata Using the matrix representation of the automata with multiplicities, we can defined the classical genetic operators: duplication, crossing-over and mutation, using a chromosome composed of each lines of the matrices of the linear representation.

R. Ghnemat, C. Bertelle, G.H.E. Duchamp Community Detection and Clustering 17/29

Example ... following

Genetic on strategy modeling for player behavior Genetic operators deal with population of individuals (here player behavior modeled by automata). Individual is described by a chromosome which is a sequence of alleles (elementary information). Here, the chromosomes are coding the transition matrices of the automata linear representation. Here, an allele is a matrix line ...

R. Ghnemat, C. Bertelle, G.H.E. Duchamp Community Detection and Clustering 18/29

Example ... following

Genetic on strategy modeling for player behavior Genetic operators deal with population of individuals (here player behavior modeled by automata). Individual is described by a chromosome which is a sequence of alleles (elementary information). Here, the chromosomes are coding the transition matrices of the automata linear representation. Here, an allele is a matrix line ...

R. Ghnemat, C. Bertelle, G.H.E. Duchamp Community Detection and Clustering 18/29

Example ... following

Genetic on strategy modeling for player behavior Genetic operators deal with population of individuals (here player behavior modeled by automata). Individual is described by a chromosome which is a sequence of alleles (elementary information). Here, the chromosomes are coding the transition matrices of the automata linear representation. Here, an allele is a matrix line ...

R. Ghnemat, C. Bertelle, G.H.E. Duchamp Community Detection and Clustering 18/29

Example ... following

Genetic on strategy modeling for player behavior Genetic operators deal with population of individuals (here player behavior modeled by automata). Individual is described by a chromosome which is a sequence of alleles (elementary information). Here, the chromosomes are coding the transition matrices of the automata linear representation. Here, an allele is a matrix line ...

R. Ghnemat, C. Bertelle, G.H.E. Duchamp Community Detection and Clustering 18/29

Context  Self-Organization Modeling  Community Detect.  GIS & ABM  Conclusion

Example ... following

Genetic on strategy modeling for player behavior ... and the chromosome is the set of the matrix lines of all the transition matrices

Context  Self-Organization Modeling  Community Detect.  GIS & ABM  Conclusion

Example ... following

Genetic operators

R. Ghnemat, C. Bertelle, G.H.E. Duchamp Community Detection and Clustering 19/29 R. Ghnemat, C. Bertelle, G.H.E. Duchamp Community Detection and Clustering 20/29 R. Ghnemat, C. Bertelle, G.H.E. Duchamp Community Detection and Clustering 20/29 R. Ghnemat, C. Bertelle, G.H.E. Duchamp Community Detection and Clustering 20/29

Spatial and Behavioral Modeling Based on Community Detection

Community Detection associated to fitness function

We can defined the fitness of each agent as following:

We compute his neighbourhood, using the spatial distance We sum the behavioral distance of the agent itself with all the others agents included in the neighbourhood We define the fitness as the inverse of the average of the previous sum.

Self-organization communities emerge from the use of this fitness inside a genetic algorithm.

R. Ghnemat, C. Bertelle, G.H.E. Duchamp Community Detection and Clustering 21/29

Spatial and Behavioral Modeling Based on Community Detection

Community Detection associated to fitness function Let 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) = \{ \begin{matrix}\frac{card(V_{x})}{∑_{y_{i}∈V_{x}} d(x, y_{i})^{2}} & if ∑_{y_{i}∈V_{x}} d(x, y_{i})^{2} ≠ 0 \\ ∞ & otherwise \end{matrix}

where d(x, y) is the behavioral semi-distance between the two agents x and y.

R. Ghnemat, C. Bertelle, G.H.E. Duchamp Community Detection and Clustering 22/29

Context  Self-Organization Modeling  Community Detect.  GIS & ABM  Conclusion

Example ... following

R. Ghnemat, C. Bertelle, G.H.E. Duchamp Community Detection and Clustering 23/29

Context  Self-Organization Modeling  Community Detect.  GIS & ABM  Conclusion

Example ... following

R. Ghnemat, C. Bertelle, G.H.E. Duchamp Community Detection and Clustering 23/29

Outline

1 Context and Objectives
2 Self-Organization Modeling
3 Spatial and Behavioral Modeling Based on Community Detection
4 Application: Geographical Information Systems and Agent-Based Modeling mixing
5 Conclusion and Perspective

R. Ghnemat, C. Bertelle, G.H.E. Duchamp Community Detection and Clustering 24/29

Application :GIS and Agent-Based Modeling Mixing

Geographical Information Systems - GIS Nowadays, the geographical information is a very wide knowledge database

GIS allow to store, manage and compute all this information Wide-world communication improve the interaction networks dealing with Geo-Politic

R. Ghnemat, C. Bertelle, G.H.E. Duchamp Community Detection and Clustering 25/29

Application :GIS and Agent-Based Modeling Mixing

Geographical Information Systems - GIS → The future improvement of GIS with automatic self-organization processes (like the communities detection proposed) can be one of the major aspect of the increasing of the world complexity to be controled as a whole, with the tools from the complexity concepts

R. Ghnemat, C. Bertelle, G.H.E. Duchamp Community Detection and Clustering 26/29

Context  Self-Organization Modeling  Community Detect.  GIS & ABM  Conclusion

Application :GIS and Agent-Based Modeling Mixing

Agent-based mixing