Tackling complexity in science : general integration of the application of complexity in science.
Date: 2007-08-02
Institutions: Directorate-General for Research and Innovation
Subjects: biology, information technology, research policy, social sciences

B5_tackling  13/07/07  13:02  Page 3

EUROPEAN COMMISSION

Tackling Complexity in Science
General Integration of the Application of Complexity in Science

edited by
Gérard Weisbuch
and
Sorin Solomon

2007

Directorate-General for Research
Directorate S – Implementation of the 'Ideas' Programme

B5_tackling  13/07/07  13:02  Page 4

EUROPE DIRECT is a service to help you find answers 
to your questions about the European Union

Freephone number:
00 800 6 7 8 9 10 11

(*) Certain mobile telephone operators do not allow access to 00 800 numbers 
or these calls may be billed.

LEGAL NOTICE:

Neither the European Commission nor any person acting on behalf of the Commission is responsible for the use
which might be made of the following information.

The views expressed in this publication are the sole responsibility of the author and do not necessarily reflect
the views of the European Commission.

A great deal of additional information on the European Union is available on the Internet.
It can be accessed through the Europa server (http://europa.eu.int).

Cataloguing data can be found at the end of this publication.

Luxembourg: Office for Official Publications of the European Communities, 2007

ISBN 978-92-79-05504-1

© European Communities, 2007
Reproduction is authorised provided the source is acknowledged.

Printed in Belgium

PRINTED ON WHITE CHLORINE-FREE PAPER

There  is  no  commonly  accepted  definition  of  "complexity".  Nevertheless,  it  is  clear  that 
widely  differing  systems,  composed  of  many  interacting  units,  generate  under  certain 
conditions  a  characteristic  common  phenomenology,  the  most  prominent  signature  of 
which  is  the  "emergence"  of  new  patterns  transcending  the  characteristics  of  the 
individual units.  

The  promise  of  the  science  of  complexity  is  to  provide,  if  not  a  completely  unified 
approach, at least common tools to tackling complex problems arising in a wide range of 
scientific domains.  

NEST,  New  and  Emerging  Science  and  Technology,  is  initiative  under  the  European 
Commission's  Framework  Programme  6  to  promote  highly  interdisciplinary,  high–risk 
research.    NEST  launched  a  number  of  focussed  "PATHFINDER"  initiatives,  including 
"Tackling Complexity in Science".   

The  "Tackling  Complexity"  initiative  aims  at  encouraging  the  development  and  transfer 
from  one  area  of  science  to  another  of  solutions  and  approaches  to  concrete  complex 
real-world problems. Such solutions need, at the same time, to hold the promise of being 
more generalisable.  

The  initiative  undertook  two  calls  for  proposals  (2004  and  2006)  which  resulted  in  the 
funding  of  23  STREP  focussed  research  projects  and  one  Coordination  Action,  GIACS, 
amounting to approximately 35 M Euro worth of new research funding. 

The goal of GIACS (General Integration of the Application of Complexity in Science) is to 
serve  as  a  forum  to  bring  the  research  of  these  research  projects  together  and  help  in 
their relationship with the ongoing research in the field of Complexity in Europe and the 
rest of world. 

The current report is one of the deliverables of GIACS and serves to speculate about the 
future  directions  and  opportunities  of  complexity  research  in  the  long  term.    It  is  the 
result of the interaction of large number of outstanding scientists involved in GIACS and 
other NEST-Complexity projects.  It is intended to be speculative and thought provoking, 
while at the same time serving as an inspiration for future research directions in the field. 

  3

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
TABLE OF CONTENTS 

EXECUTIVE REPORT.............................................................................................. 5 

1 INTRODUCTION ................................................................................................ 7 
1.1 From components to global properties ............................................................ 7 
1.2 A historical perspective................................................................................. 9 
1.3 Concepts and methods ............................................................................... 12 
1.3.1 Concepts ............................................................................................ 12 
1.3.2 Methods ............................................................................................. 13 
1.4 Caveat: to be transversal or not .................................................................. 15 
1.5 Domains of application ............................................................................... 15 

2 SOCIAL SCIENCES ........................................................................................... 18 
2.1 Social systems .......................................................................................... 18 
2.2 Economics ................................................................................................ 21 
2.2.1 Success stories ................................................................................... 22 
2.2.2 Socio-economic networks ..................................................................... 24 

3 BIOLOGY ........................................................................................................ 26 
3.1 Theoretical biology..................................................................................... 26 
3.2 Systems Biology ........................................................................................ 27 
3.3 Cognitive Science ...................................................................................... 31 
3.4 Engineering emergence in self-assembling systems ........................................ 32 
3.4.1 Control and programming of self-assembly.............................................. 32 
3.5 Epidemic modeling and complex realities ...................................................... 34 
3.6 Bio-inspired strategies for new computing architectures and algorithms paradigms
.................................................................................................................... 37 

4 INFORMATION AND COMMUNICATION TECHNOLOGIES......................................... 40 
4.1 Optimization and Complexity....................................................................... 40 
4.2 Networks, especially computer .................................................................... 41 

5 COMPLEX SYSTEMS, BUSINESS AND SOCIETY ..................................................... 44 
5.1 Econophysics and Finance as a success story................................................. 44 
5.2 Present challenges ..................................................................................... 44 
5.3 Supply Networks Management..................................................................... 45 
5.4 Credit networks and Systemic Risk............................................................... 46 
5.5 Collective Evaluation and Trust-based Networks............................................. 47 
5.5.1 Overview of emerging technologies ........................................................ 47 
5.5.2 Potential Impact .................................................................................. 47 
5.5.3 Trust-based Networks .......................................................................... 48 
5.6 Penetration of CS science in the business world ............................................. 49 

6 LIST OF CONTRIBUTORS AND EXPERTS .............................................................. 50 
6.1 Editor ...................................................................................................... 50 
6.2 Contributors to specific parts of the document ............................................... 50 
6.3 Participants to think tank meetings .............................................................. 50 
6.3.1 Jerusalem. 26 May 2006....................................................................... 50 
6.3.2 Paris, 6 and 8 June 2006 ...................................................................... 50 
6.3.3 Torino, Villa Gualino, 25-26 July 2006 .................................................... 51 
6.4 Acknowledgment ....................................................................................... 51 

7 REFERENCES .................................................................................................. 52 

  4

 
 
 
 
 
 
 
 
 
 
 
 
EXECUTIVE REPORT 

A  theory  of  complex  systems  has  been  developed  from  the  forties,  relating  simple 
elementary processes to collective functional properties in physics, biology and the social 
sciences. 

More recently, applications to design and business have been developed. 
A  major  turning  point  around  the  year  2000  is  the  availability  of  huge  sets  of  data 

which complex systems methodology allows to transform into useful knowledge. 

A list of promising research avenues would include: 

•  From model systems to real world systems. 

• 

Inverse  dynamics  especially  in  biological  networks,  but  also  in  many  other  fields 
such as markets or crowds when data become available. 

•  Distributed  processing  in  the  industry  and  services,  starting  with  the  Internet, 
data processing, etc. find solution which are distributed, scalable and adaptive. 

•  A  nearly  unchecked  field  is  policy  design:  defining  a  policy  and  checking  its 
consequences  by  what/if  simulations;  policy  implementation  taking  into  account 
the adaptivity of both measures and constituency. 

Among the general issues are: 

•  Since  complex  systems  is  such  an  invasive  methodology  applicable  to  so  many 
fundamental  and  applied  fields  of  research,  a  preliminary  question  is:  does  it 
make  sense  to  have  specific  calls  about  complex  systems  research  or  should  we 
rather  keep  the  standard  calls  specific  of  the  domain  of  application?  In  the  long 
run  one  can  hope  for  a  better  integration of  field  research  and  complex  systems 
specialists which would allow mixed collaborations to answer domain specific calls. 
Presently,  this  integration  is  far  from  achieved;  it  would  thus  be  appropriate  to 
maintain  some  calls  inside  a  STREP  Pathfinder  complexity  initiative  as  was 
previously  done  with  such  programs  as  what  it  means  to  be  human,  tackling 
complexity in science, synthetic biology, etc. 

•  Education.  Promote  education  in  complex  systems  methods  and  results  both  at 
intermediate  (master  and  doctorate)  and  elementary  level.  Most  of  this  effort 
(writing  books,  manuals,  paper  series,  or  equivalent  web  sites,  syllabus  design, 
summer  schools,  libraries,  etc.)  has  to  be  done  by  the  scientific  community.  But 
the  European  Commission  (EC)  could  consider  supporting  coordination  actions 
built  to  promote  education.  At  the  master  or  even  undergraduate  level,  it  is 
important  to  ensure  that  specialists  in  biology  or  social  science  understand  the 
reach  of  complex  systems  methods.  The  EC  might  also  support  some  effort  to 
translate documents. Such an effort could help for instance students from Eastern 
countries to readily access this literature, but could also help the diffusion of good 
material produced in Eastern Europe. 

•  Databases. Sustain efforts to maintain large and easily accessible data bases. The 
situation is very contrasted between different fields. Public databases are available 
in genomics. The same is true for many financial time series. This is not the case 
for social sciences. In economics, many valuable data about individual firms such 
as production, trading links, employment patterns are confidential in Europe. Even 
data  collected  thanks  to  the  European  Commission  financial  support  are  not 
generally  available.  Making  such  data  generally  available  would  have  a  strong 
positive  impact  on  sound-based  research  and  would  of  course  finally  benefit  the 
industry and government. Unfortunately, solutions are not obvious. 

  5

 
 
 
 
 
 
 
 
 
 
 
 
 
  
 
1 INTRODUCTION 

1.1 From components to global properties  

The challenge 

Let  us  exemplify  the  challenge  of  complex  system  research  with  the  mind/brain  issue. 

11

interacting  neurons  which  can  be  considered  as  electric 
The  brain  is  composed  of  10
cables  (axons)  with  chemical  connexions  (synapses).  How  can  we  deduce  the  mind 
properties (cognition) from the brain structure? More generally, how can we explain the 
functional organization of biological systems at the level of organs for instance, from the 
properties  of  their  components  (from  neurons  to  mind  or  from  lymphocytes  to  the 
immune response)? 

Similar questions arise in the social sciences; can we understand social organizations 
(institutions)  and  collective  behaviour  from  the  properties  of  the  human  agents  which 
compose  them?  Such  a  research  program  is  called  methodological  individualism  in  the 
social sciences. 

Can we define complex systems? 

The  answer  is  yes,  but  some  caution  should  be  used  in  keeping  in  mind  the  difference 
between real world complex systems and their models. 

Let us start with models: complex systems are composed of a very large number of 
different  elements  with  non-linear  interactions;  furthermore  the  interaction  structure,  a 
network, comprises many entangled loops. 

The purpose of complex system research is to propose and solve models such that we 
can  deduce  the  functional  organization  from  the  interaction  of  the  components.  But  to 
handle  such  large  systems,  the  description  of  their  elementary  components  is  generally 
oversimplified with respect to real systems: hence the issue of the comparison between 
the  predictions  of  the  model  with  the  real  system.  We  will  see  that  complex  system 
theory  often  addressed  the  issue  by  restricting  predictions  to  generic  properties.  (A 
recent  shift  in  interests  occurred  with  the  availability  of  large  data  sets  in  biology  or 
social sciences). 

Before  addressing  the  issue  of  generic  properties,  which  can  be  rather  technical,  let  us 
discuss  one  of  the  caricatures  of  complex  systems:  complex  systems  is  a  theory  of  the 
whole, in other words it is so general that it has no practical use. Let us use at this stage 
some comparisons. 

Thermodynamics  is  not  only  a  theory  about  work  and  heat  but  it  applies  to  all 
physical  systems:  gases,  liquids,  solids  with  electric,  magnetic  or  elastic  properties.  In 
fact  statistical  mechanics,  the  microscopic  theory  behind  thermodynamics,  is  probably 
the closest theoretical analogue to complex systems theory: its purpose is to deduce the 
macroscopic  properties  of  matter  from  those  of  its  individual  components,  atoms, 
molecules,  polymers.  But  not  all  properties  of  matter  rest  on  thermodynamics:  optical 
properties  can  often  be  deduced  by  adding  up  properties  of  individual  atoms.  The  fact 
that  some  answers  can  be  obtained  from  complex  systems  theory,  does  not  mean  that 
complex  systems  theory  exhausts  all  fields  of  research.  There  are  many  other 
approaches  of  real  systems  with  little  direct  connection  with  complex  systems 
methodology:  experiments,  empirical  data  collection,  monographs,  etc.  Even  if  we 
consider  complex  systems  theory  as  particularly  well  adapted  to  the  formalization  of 
problems  in  biological  and  social  sciences,  it  does  not  imply  that  it  should  be  the  only 
approach to logical or mathematical formulations. 

The projection perspective is probably an appropriate metaphor (see figure 1). 

  7

 
 
 
 
 
 
 
 
Figure 1: The projection metaphor. Different fields of research, say biology, sociology,  
physical-chemistry,  optimization,  share  many  common  traits  when  checked  from  a 
complex  system  perspective;  this  is  illustrated  by  the  large  overlap  of  the  two-
dimensional  projections  on  the  x,y  plane  of  the  four  spheres  in  the  3d  space.  A 
projection along another axis, say x, would strongly reduce the overlap.   

  8

 
 
 
 
1.2 A historical perspective 

Complex  systems  perspective  and  methods  are roughly  half  a  century  old.  The  purpose 
of these reminders is important in the present context: we have now acquired technical 
tools to deal with real world complex systems. "Complex systems" is not a buzzword, and 
the interest in complex systems does not boil down to a bandwagon effect. This implies 
that practitioners in the different fields of application could avoid re-inventing the wheel 
by  either  learning  the  theory,  concepts  or  methods,  or  collaborating  with  complex 
systems specialists. 

One could argue that the first computation in the spirit of complex systems approach 
is  Clausius’  virial  theorem  (1857)  relating  pressure  to  individual  molecules  velocity.  Of 
course the names of Gibbs and Boltzmann who later set the basis of statistical mechanics 
in  the  1860’s  are  more  familiar.  Let  us  rather  start  with  the  first  challenges  in  the 
applications to biological problems, in the 1940’s. 

The  two  seminal  papers  in  complex  systems  are  sixty  years  old.  They  address  such 

issues as: 

•  What are the logical units necessary to build a self reproducing automation? (Von 

Neumann) 

•  What can you do with an assembly of formal neurons? (McCulloch and Pitts) 

In  other  words,  rather  than  discussing  "wet  biology"  they  approach  the  issue  from  an 
abstract perspective. Both results are expressed in terms of universality, independent of 
any physical implementation. Assemblies of formal neurons can achieve the computation 
of  any  recursive  function  (i.e.  they  are  equivalent  to  Universal  Turing  Machines).  Von 
Neumann  proposed  a  cellular  automaton  capable  of  self-reproduction,  and  of  universal 
computation. Both papers where based on the concept of networks of automata and their 
dynamical properties (threshold automata for McCulloch and Pitts, Boolean automata for 
Von Neumann). 

The  perceptron  is  a  simple  architecture  and  algorithm  allowing  a  machine  (a  simple 
threshold automaton) to learn from examples and classify patterns. It is the first example 
of a device based on complex systems ideas. One of its variant, the adaline, is still in use 
to automatically trim modems. 

Close  to  the  year  1970,  three  independent  contributions  stressed  the  importance  of 
genericity  and  universality  classes.  Thom  catastrophe  theory,  and  its  variant  bifurcation 
theory,  is  applicable  to  macroscopic  systems,  while  Wilson  and  Kauffmann  ideas  are 
applicable to microscopic systems. The three contributions established the importance of 
generic  properties  and  classes  of  universality,  a  very  new  concept  at  that  time.  Some 
properties are common to classes of systems independently of the details of the model. 
Thom and Wilson concepts apply in the vicinity of transitions (singularities for Thom). In 
a  few  words,  Kauffman  model  (dynamics  of  random  Boolean  nets)  suggests  that 
organization phenomena observed in biology (in his case cell differentiation) are common 
to  large  majority  of  random  systems  built  on  some  simple  prescription.  In  other  words, 
biological  organization  might  not  be  the  result  of  a  strong  selection  principle,  a  radical 
departure from conventional biological wisdom in the 60’s. 

During the early eighties, physicists started invading biology, cognitive sciences, etc. 
(Before  that  time,  their  efforts  mostly  concerned  the  discovery  and  application  of 
complex systems to phase transitions and to the physics of disordered systems). Hopfield 
model of associative memories was influential in bringing physicists to cognitive sciences. 
Kirkpatrick approach to optimization problems through the simulated annealing algorithm 
inspired from statistical mechanics concerned applied sciences (e.g. chip placement and 
wiring in computer design). Parisi replica solution to the spin glass problem is an example 
of the bold simplification of the original problem associated with sophisticated formalism 
to  get  formal  solutions  of  very  difficult  problems.  The  early  eighties  are  also  the  time 
when  computers  became  inexpensive  and  widely  available  for  simulations.  Easier 

  9

 
 
 
 
 
 
numerical  simulations  helped  to  bridge  the  gap  between  observations  and  experiments 
on the one hand and simplified theoretical models on the other hand. 

The  development  of  cognitive  sciences  since  the  mid  80’s  is  probably  a  general 
scheme followed by several other disciplines. Two major factors were critical in the shift 
from  psychology  to  cognitive  sciences:  a  fast  development  of  experimental  techniques 
(intra-cellular  recordings,  psycho-physics,  and  later,  imagery)  and  the  development  of 
theory (neural nets). 

An  analogue  development,  also  based  on  the  availability  of  empirical  and 
experimental data, is the case for the study of financial markets (in the 90’s) and of the 
internet studies (2000’s), system biology (biochips in the 2000’s), etc. 

Applied science domains also flourished since the 80’s, implying large communities of 
scientists:  signal  processing  (artificial  vision,  speech  recognition)  and  combinatorial 
optimization.  

  10

 
 
Figure 2: A short historical perspective in complex systems 

  11

 
 
 
 
 
 
 
 
 
1.3 Concepts and methods 

Is  there  a  complexity  science?  The  question  is  often  asked,  but  the  answer  depends 
largely of what is meant by complexity. If we restrict the answer to complex systems, the 
answer is definitely yes, we have built a theory of complex systems. We will review very 
briefly in this section a set of concepts and methods which give us a better insight of real 
complex systems. 

1.3.1 Concepts 

Among the most important concepts are the notions of 

•  Scaling:  Scaling  laws  can  be  considered  as  a  first  level  in  modeling; 

they relate two quantities by rules such as: 

QαL α  

(1) 

where L is a parameter (e.g. a length or a number of agents, Q a dynamic quantity 
(e.g. a period, some degree of complexity) and α some real number. The concept is 
pervasive in all sciences but its importance in complex systems is due to two reasons: 

-  since  understanding  complex  systems  is  so  difficult,  knowing  how  things 

depend on each other is already an important result; 

-  scaling laws are often generic; genericity is itself an important concept which 

states that some results are robust and do not depend upon details. 

•  Universality,  genericity.  Because  the  full  description  of  real  complex  systems  is 
very complicated (in other words of large algorithmic complexity, necessitating a 
long  description),  a  modeler  cannot  a  priori  be  assured  that  the  necessary 
simplification  of  his  model  would  not  change  the  behaviour  predicted  by  the 
model. Rather than trying to reproduce all the details of a real system one looks 
for  classes  (of  universality)  of  systems  which  share  the  same  set  of  properties: 
the generic properties. 

•  Attractors:  complex  systems  evolve  in  time  towards  a  restricted  set  of 
configurations,  called  attractors  of  the  dynamics.  The  nature  of  the  attractors 
(fixed points, limit cycles or chaos), their number, etc. characterise the dynamics. 
The  notion  of  attractors  is  the  answer  to  the  "Emergence  paradox":  the  system 
displays  some  form  of  organization  apparently  unpredictable  from  the  rules  that 
specify it. 

•  Robustness:  the  attractors  remain  qualitatively  unchanged  over  a  finite  range  of 
parameters,  defining  a  dynamical  regime.  But  sharp  transitions  in  the  space  of 
parameters  separate  dynamical  regimes.  These  properties,  dynamical  regimes 
and sharp phase transitions, are the generic properties of the dynamics. Because 
the  conclusions  of  complex  systems  studies  are  about  the  attractors,  they  are 
generic:  they  are  common  to  large  classes  of  equivalent  systems,  which  may 
differ in their details. 

•  Networks:  The  concept  of  an  interaction  network  is  central  to  complex  systems. 
The study of the static structure of the interaction network was recently renewed 
by  the  ideas  of  "small  world"  (Watts  and  Strogatz)  and  of  scale  free  networks 
(Barabasi  and  Albert,  see  further  section  4.2).  Many  empirical  studies  on  real 
world nets, whether biological (from food webs to gene regulatory networks) and 

  12

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
social  (from  small  communities  to  WWW)  were  done  in  recent  years;  new 
characterizations of networks have been proposed and in some cases a bridge was 
re-established  between  network  sociologists  and  complex  system  scientists,  e.g. 
in  the  search  for  small  motifs  in  relation  with  functional  properties  for  instance. 
Dynamics  and  functional  organization  studies  are  far  more  difficult  to  achieve; 
they  also  require  larger  data  sets.  The  predictions  of  Vespignani  et  al.  on  virus 
infection and immunization strategies  in scale-free networks are a good example 
of the importance of dynamical studies (see further section 3.5). 

•  Many  other  general  concepts  were  introduced  such  as  percolation,  fractals,  self 

organised criticality, order parameters and functions, etc. 

These general concepts guide research on any particular complex system: they are part 
of  a  theory  of  complex  systems  as  the  concepts  of  energy,  temperature,  entropy,  state 
functions,  shape  thermodynamics…  The  analogy  was  first  stated  by  Stuart  Kauffman 
("Waiting for Carnot").  

1.3.2 Methods 

In quantum mechanics e.g. computations are based on a series of techniques (e.g. group 
theory,  eigenvalues  and  eigen  functions,  perturbation  methods).  The  same  is  true  for 
complex systems. Let’s enumerate some formal techniques: 

•  Discretization, of time and/or space, e.g. cellular automata. 

•  Computation of the Z function via the replica ansatz. 

•  Renormalization group. 

•  Transfer matrix. 

•  Random matrices. 

•  Damage spreading methods. 

•  Langevin equations. 

When  formal  methods  are  not  applicable,  numerical  simulations  can  be  used.  But 
complex  system  methods  are  not  restricted  to  computer  simulations  as  sometimes 
stated. The idea is rather to couple formal methods on the simplest models and computer 
simulations to check the genericity of their conclusions on more elaborate versions. 

Computer  simulations  are  often  based  on  methods  inspired  by  the  complex  system 

approach to physical and biological phenomena: 

•  Probabilistic  methods  such  as  simulated  annealing  rather  than  exhaustive 

searches in NP complete optimization problems. 

•  Learning  methods  such  as  the  perceptron  algorithm  and  its  generalizations 

inspired from neural nets. 

•  Genetic algorithms and their variants. 

•  Ants algorithms ... 

  13

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Figure 3: Perspectives in complex systems

  14

 
 
 
 
 
 
1.4 Caveat: to be transversal or not 
By François Képès 

It  is  a  common  view  among  complex  systems  researchers  that  their  science  addresses 
issues that are fundamental to complex systems in general, starting from important open 
questions  relevant  to  many  domains,  and  searching  for  methods  to  deal  with  them.  In 
the  following,  this  will  be  called  the  transversal  approach,  as  it  transversally  crosses 
many disciplines. 

The  transversal  approach  has  proven  its  value  at  the  methodological  level,  and 
various  fields  of  application  have  benefited  from  it.  However,  its  indiscriminate 
application could potentially lead to failure to recognize the diversity and richness of the 
applications  (’all  networks  were  born  equal’),  instead  of  using  this  richness  to  improve 
the transversal approach. 

Here  we  suggest  that  there  are  other  possible  paths  to  the  science  of  complex 
systems.  In  particular,  we  propose  an  alternative  path  that  starts  from  a  field  of 
application,  and  subsequently  raises  increasingly  theoretical  and  wide-ranging  issues. 
The  starting  point  would  be  a  case  study  that  exemplifies  many  challenges  in  complex 
systems  research,  for  example  elemental  heterogeneity,  interconnected  scales  in  time 
and space, emergence of higher level behaviour. In a second stage, the analysis of this 
case study would inspire multidisciplinary research. In a third stage, the challenge of the 
complex  problem  offered  by  this  case  study  and  surrounding  multidisciplinary 
approaches,  and  of  large  data  sets,  would  attract  excellent  theoreticians.  These 
theoreticians,  in  trying  to  build  novel  theoretical  frameworks  and  novel  concepts  from 
this  rich  substrate,  would  uncover  specific  complex  system  research  tracks,  therefore 
valuably contributing to this science. 

1.5 Domains of application 

We  will  develop  in  the  following  sections,  examples  of  applications  of  complex  systems 
methods  to  several  fields  of  research  and  development.  This  set  of  examples  is  not 
meant  to  be  exhaustive:  it  reflects  the  availability  of  experts  in  these  different  fields  of 
research, and the timeliness of these topics. The convergence of issues is reflected in the 
plan of these contributions: 

•  The  different  domains  have  a  long  history  of  research  previous  to  the  complex 
system approach; we briefly recall the more standard approaches and their limits. 

• 

"Gaps". Quite often the research communities are partitioned between specialists 
of  the  microstructure  (or  the  individual  components)  and  specialists  of  the 
collective aspects. 

•  The  success  stories  of  the  application  of  complex  systems  methods  to  the 

particular field of research. 

•  The future challenges for complex systems methods. 

Because  complex  systems  studies  are  based  on  the  same  set  of  methodologies,  the 
general perspective reflects many commonalities across domains. For instance: 

• 

It  is  often  the  case  that  the  success  stories  relate  to  theoretical  results  obtained 
on  non-structured  systems,  thanks  to  mean  field  or  related  structure  methods. 
While  the  future  challenges  concern  the  application  of  reverse  dynamics  to  large 
data  sets  in  biology  (e.g.  gene  regulatory  networks),  economics  (financial 
markets), etc. 

  15

 
 
 
 
 
 
 
 
 
 
 
 
•  The  importance  of  networks  is  pervasive  in  all  domains.  One  contribution,  by 
Guido Caldarelli (see further section 4.2), summarizes the most recent progress in 
networks characterization and dynamics. 

• 

In several domains the individual moves are recorded for large ensembles (in the 
thousands) in order to track the elementary processes responsible for interaction: 

– in ethology of animals groups such as schools of fish, swarms of insects or 
   birds, 

– walkers in crowds, 

– in economics, traders on financial markets, 

– email exchange inside a given community, 

– even in embryology, individual cells of the zebra fish are recorded during 
   ontogenetic development. 

These  huge  recordings  have  necessitated  new  progress  in  tracking  algorithms,  not  to 
mention the hardware needs. 

  16

 
 
 
 
 
 
 
 
 
 
Figure 4: A plan of this brochure 

  17

 
 
 
 
 
 
2 SOCIAL SCIENCES 

2.1 Social systems 

Social  systems  are  recognised  as  complex  by  most  modern  researchers  in  the  social 
sciences,  but  sociology  and  political  sciences  are  for  historical  reasons  among  the  less 
penetrable  fields  of  application  for  complex  system  scientists  (economics  will  be  later 
described). 

What  can  a  complex  system  perspective  bring  to  social  sciences?  Since  Max  Weber 
(1864 - 1920), a dominant paradigm in the research program of social sciences has been 
methodological  individualism:  how  to  explain  social  phenomena  from  individual 
rationality. This view is commonly shared in sociology or economics, but its connection to 
complex  system  research  is  accepted,  and  used,  by  a  minority  of  social  scientists,  e.g. 
Kirman  in  economics,  Axelrod  in  political  sciences  (and  the  BACH  group  in  Ann  Harbor, 
Michigan), Epstein, Axtell and P. Young (the Brookings Institution) in political philosophy 
and economics. In Europe, Gilbert and Conte e.g. are active in "simulating societies". 

The  equivalent  problem  to  functional  organization  in  biology  is  the  problem  of 
institutions  in  social  sciences.  In  a  bounded  rationality  perspective,  institutions  allow 
societies  to  meet  the  challenges  that  they  face.  Social  scientists,  and  not  only 
structuralists, recognize that some social organization allows individuals to act in society. 
There  are  many  kinds  of  institutions,  from  what  we  obviously  recognise  as  institutions 
such  as  schools,  hospital,  state,  law,  religions  ...  to  less  obvious  instances  such  as 
cultural traits, routines, etiquette. Even language can be considered as an institution. 

Many questions have been asked about institutions but a central issue is the origin of 
institutions:  how  do  individuals  in  a  society  "choose",  adopt  and  maintain  institutions? 
How do institutions evolve? What makes people abide or not by social norms? 

The  complex  system  approach  as  developed  by  Axelrod,  Epstein,  Axtell,  etc. 
interprets institutions as the attractors of the dynamics of interacting individuals. Axelrod 
for  instance  has  launched  the  research  program  on  the  emergence  of  cooperation  in  a 
prisoner dilemma framework. Along this line of research, Epstein and Axtell discussed the 
emergence of a class system among social agents with a priori neutral labels. Luc Steels 
demonstrated  the  emergence  of  a  common  vocabulary  among  a  set  of  communicating 
robots ("talking heads"). 

Interpreting  institutions  as  attractors  of  the  social  dynamics  among  agents  explain 
their  emergence,  their  stability  and  robustness,  and  the  fact  that  the  history  of 
institutions  follows  punctuated  equilibria.  If  we  think  of  social  regimes  in  societies,  one 
gets  an  explanation  of  long  stasis  of  organizations  such  as  tribes,  chiefdoms  or  modern 
states;  transitions  among  such  metastable  regimes  occur  fast  and  bring  very  different 
organizational forms ("revolutions"). 

Another  line  of  research,  also  following  complex  system  methodology,  is  the  search 
for scaling laws in social systems. Quantitative approaches to social systems started with 
scaling laws (Pareto, Levy, Zipf) reflecting the abundance of structures according to their 
size. Zipf’s law for instance established that the distribution of the size of cities  roughly 
follows an 1/size law (1920’s). The same kind of scaling was observed in the distribution 
of individual wealth, income, frequency of words in large corpuses, as in natural systems 
such as earthquakes or climatic events. They imply that there does not exist e.g. a city of 
"characteristic size" as would imply a normal distribution. The same scale free behaviour 
is observed in financial time series of returns or in firm size distributions. 

Since the pioneering works of Simon and Mandelbrot we have a simple explanation of 
the  origin  of  these  scaling  laws:  a  simple  random  multiplicative  mechanism  such  as 
"riches get richer" suffices to yield power law distributions. 

A  complex  system  perspective  offers  many  opportunities  in  the  most  fundamental 

aspects of most social sciences. A few examples: 

  18

 
 
 
 
 
-  Language.  One  is  looking  for  threads  to  answer  questions  about  the  origin  and 
diversity of human language. Not only in terms of vocabulary, but also grammar. Why do 
we have a limited number of grammatical markers systems among the variety of human 
languages and why those? The challenges of linguistics and its applications to translation, 
information  retrieving,  human/computer  communication  and  communication  protocols 
are of tremendous interest to the European Communities. 

- Economic geography. Differences in economic activity, and especially in Europe, are 
striking; it is a major challenge to European construction (of course the same can be said 
about cultures). In what respect is economic differentiation due to physical geography or 
to  history?  How  much  differentiation  is  "natural"  or  inevitable,  because  driven  by 
economic  growth  itself  and  its  aleas  (see  further  section  2.2.2).  Understanding  cities, 
growth,  shape,  interactions,  evolution,  etc.  in  connection  with  their  inhabitants' 
challenges, abilities and individual choices is a typical challenge of economic geography. 
Many problems call for a complex system approach such as modeling land use, for which 
cellular automata approaches have been developed. 

-  Economics  (see  further  section  2.2.2).  More  generally  economics  calls  for  complex 
systems methods and ideas as proposed by Nobel laureates in economy (K. Arrow) and 
physics  (P.W.  Anderson)  and  D.  Pines  ("The  Economy  as  an  Evolving  complex  system" 
1987-8).  With  such  "founding  fathers"  and  followers  this  research  program  soon 
developed  in  the  US  (B.  Arthur,  SFI)  and  in  Europe  (the  WEHIA  conferences  involving 
e.g. M. Gallegati and A. Kirman). Another factor which has facilitated these developments 
is  the  prevalence  of  mathematical  culture  among  a  large  fraction  of  economists.  But 
some  tensions  and  competition  with  physicists  (the  econophysicists)  and  their 
contribution remain. 

- A second area which has been very successful is cognitive science, where complex 
systems  methods  helped  to  establish  bridges  between  the  (wet,  biological)  brain  and 
cognition (see further section 3.3). The fast development of cognitive sciences in Europe 
since the mid 80’s is due to the conjunction of two factors: the use of complex systems 
methods  (especially  neural  nets)  and  new  recording  and  imagery  techniques  (multi-
recording, MRI, etc.) 

Because of barriers to inter-discipline communication the progress has been much slower 
in areas such as sociology, political sciences, political philosophy and even management. 
There exists some interest for complex systems among some scientists in this disciplines, 
but most often for some "softer" versions.  

- In the case of social sciences in a wide sense (including e.g. political philosophy and 
political  science),  the  chosen  methodology  is  most  often  numerical  simulation  with  little 
interest  for  complex  systems  concepts.  This  often  translates  into  bringing  all  possible 
knowledge  as  input  to  the  model,  running  the  simulations  (often  under  multi-agents 
ideology and platforms), and observing temporal or spatio-temporal patterns. This line of 
research has been active for more than ten years in Europe ("Simulating societies" with 
leaders such as Nigel Gilbert, Rosaria Conte, and Andrzej Nowak). Applications to present 
social  challenges  such  as  environment  have  been  a  strong  incentive  for  these 
simulations.  They  are  often  developed  in  institutions  closer  to  applications  such  as 
agriculture  or  halieutics  rather  than  in  inner  academic  circles.  By  contrast,  some 
physicists  (Dietrich  Stauffer,  Serge  Galam,  Sorin  Solomon,  Gérard  Weisbuch...)  applied 
complex systems methodology. 

-  In  the  case  of  history,  political  philosophy  and  even  in  management,  the  softer 
(rather  verbal  than  modeling)  version  of  complexity  is  most  often  used:  Edgar  Morin  in 
France is an example. These communities often relate to cybernetics. 

Normative approaches and design 

Many  applications  of  CSR  concern  priority  areas  of  European  research  defined  by  the 
Commission  such  as  health,  governance,  environment,  etc.  In  all  these  concrete 
challenges  the  picture  involves  on  the  one  hand  hard  scientific  knowledge  either  in 
medicine,  climate,  economy,  and  on  the  other  hand  choices  by  many  inhomogeneous 

  19

 
 
 
 
 
agents  with  incomplete  information.  The  agency,  EC  or  national  government,  has  to 
extract information from a huge set of data, define a policy acceptable for its constituents 
and implement it. Any help in the different steps of the political action is awfully needed: 
from  data  to  knowledge,  defining  a  policy  taking  into  account  the  conflicting 
requirements of production, environment and social needs, and imagine those measures 
acceptable  by  the  constituency  and  helpful  in  bringing  the  state  of  the  world  chosen  by 
the political level. 

All tools and methods of complex  systems research are needed to get an integrated 
assessment  of  the  issues  and  possibilities.  A  major  challenge  for  complex  system 
research  is  to  be  associated  to  search  for  solutions  to  these  societal  issues.  If  we  for 
instance  take  the  case  of  global  warming,  the  communities  of  climatologists  and 
economics developed sophisticated models of climate on the one hand and of economics 
on  the  other  hand.  But  the  integration  of  these  models  to  achieve  some  useful 
assessment has been terribly hard and unsuccessful. 

A  challenge  that  is  faced  both  by  the  scientific  community  and  by  funding  agencies 
such as the EC is how to have projects in the priority areas of European research which 
bring  together  complex  system  scientists  and  specialists  of  the  fields  of  application, 
whether agriculture, economics, medicine, etc. 

Design 

The scientists’ vision of design starts taking into account the fact that designed objects are to 
be  used  by  humans  (of  course  sellers  already  understood  that,  but  for  them  users  are  only 
possible customers). The idea of human usage of technical products makes even more sense in 
our  present  well  connected  societies.  In  the  connected  society,  the  success  of  any 
communication  device  largely  relies  on  human  factors  which  might  overcome  technical 
strengths  or  weaknesses.  More  than  ever,  innovation  means  finding  new  use  for  sets  of 
technical  components  that  can  be  either  already  available  or  which  development  can  be 
programmed.  Research  programs  of  the  IST  division  are  well  aware  of  the  importance  of 
these  human  factors  and  of  the  fact  that  a  large  part  of  innovation  is  driven  by 
communication or based upon the development of ICT. The parallel assessment document 
for the IST division should be more explicit than ours about challenges and opportunities in 
IST. 

Resource  allocation  problems  are  a  set  of  familiar  problems  in  Operational  Research  (see 
further section 4.1). But new challenges in our present society such as local decision and the 
necessity of fast adaptation call for new algorithms. Supply chains methods for instance have 
to  be  re-adapted  because  of  the  large  variability  of  consumers  demand:  supplying  local 
dealers  with  black  Ford  T  in  the  20’s  is  a  different  challenge  than  supplying  the  specific 
model  (in  terms  of  colour,  motorization  and  other  options)  requested  by  a  21st  century 
customer. Scheduling  cannot  be completely  made  in  advance and has to be adaptive (see 
further  section  5.3).  The  "Federal  Express"  problem  is  a  paradigm  of  many  scheduling 
problems encountered today, from routing messages along the Internet to handling natural 
catastrophes: what are the best algorithms to allocate vehicles collecting letters or parcels 
according to received calls? Simple local optimization algorithms have been invented which 
parameters  are  adjusted  according  to  past  history  of  calls.  The  research  community,  and 
especially computer scientists, is more aware of applications in distributed computer science, 
but many other sectors in business administration call for local and adaptive approaches to 
resource allocation and scheduling. 

In a society where services represent the largest part of the economic activity,  a better 
adaptive  allocation  is  a  real  challenge  which  is  seldom  met  (think  for  instance  of  the 
medical services crisis in Europe). One gets the impression that the new developments in the 
field do not percolate to business through consulting firms or business schools which should 
be the normal channels (with fortunately some exceptions, see further section 5.6). 

  20

 
 
 
 
 
2.2 Economics  
By Mauro Gallegati, Peter Richmond and Massimo Salzano 

Everyone  would  agree  that  the  economy  is  a  complex  system.  Traditional  economics  is 
already a very formalised approach to economy. 

Adam  Smith,  in  1776,  proposed  that  the  economy  is  a  complex  self-organizing 
system governed by an ’invisible hand’. This idea of self-regulating order emerging from 
interactions  between  elemental  components  without  it  "being  part  of  their  intentions" 
became a guiding principle of human behaviour. The approach was transformed in 1870 
into a ’theory of General Equilibrium’ (GE) by Léon Walras. He proposed a system with a 
configuration  of  prices  and  action  plans  such  that  all  agents  can  carry  out  their  chosen 
plans  and  markets  clear.  As  this  theory  was  generalized  modern,  neo-classical, 
economists seeking to build micro-foundations for macroeconomics soon reverted to the 
refinement  proposed  in  the  1950s  by  Arrow  and  Debreu.  They  showed  that  individual 
agent  inter-temporal  (on  an  infinite  horizon)  optimization  also  yields  a  GE,  as  soon  as 
each  representative  agent  (RA)  that  makes  up  this  economy  is  equipped  with  perfect 
price  foresights  for  each  future  state  of  nature  and  a  complete  set  of  Arrow-securities 
markets,  all  open  at  time  zero  and  closed  simultaneously.  Whenever  these  conditions 
hold  true,  GE  is  an  allocation  that  maximizes  a  properly  defined  social  welfare  function 
or, in other terms, the equilibrium is Pareto-efficient (First Welfare Theorem). 

The  "gaps":  the  failure  of  the  micro-foundation  program  based  on  representative 
agents  is  one.  The  flaws  in  solutions  to  this  problem  adopted  by  mainstream  macro-
economists are pervasive and well known: 

•  GE is neither unique nor locally stable. 

•  The GE solution is not computable. Indeed it is not even possible to approximate 
the system state without going through a full simulation of the actual exchanges 
occurring  in  the  system.  The  same  problem  applies  to  the  class  of  so-called 
Computable GE models. 

•  The GE model is one in which price formation precedes the process of exchange, 
instead  of  being  the  result  of  it.  Real  markets  work  the  other  way  round  and 
operate in real time. Thus the GE model cannot be considered to offer a realistic 
explanation of economic phenomena. 

• 

It  is  widely  recognized  that  integrating  money  into  the  theory  of  value 
represented by the GE model is at best problematic. No individual economic agent 
can  decide  to  monetize  alone;  monetary  trade  should  be  the  outcome  of  market 
interactions  among  agents.  By  the  same  token,  since  credit  makes  sense  only  if 
agents can sign contracts in which one side promises future delivery of goods or 
services  to  the  other,  equilibrium  markets  for  debt  are  meaningless.  Both  the 
information  conditions  and  information  processing  requirements  are  not  properly 
defined and bankruptcy, for example, can be safely ignored. 

•  The  only  role  assigned  to  time  in  a  GE  model  is  that  of  dating  commodities. 
Products, technologies and preferences are exogenously given and fixed from the 
outset.  At  an  empirical  level  there  is  an  increasing  realization  that  the  major 
economic  theories  of  either  Keynes  or  the  monetarist  school  have  not  had  great 
success when trying to account for economic behaviour. 

The research methodology we endorse in seeking to move forward consists in discarding 
the Walrasian GE. Instead of trying to deductively prove the existence of an equilibrium 
price  vector  p*,  the  complexity  approach  aims  at  constructing  it  by  means  of  rules  and 
algorithms.  Clearly,  the  act  of  constructing  such  a  coordinated  state  requires  a 
description of goal-directed economic agents and their interactions. 

  21

 
 
 
 
 
 
 
 
 
Agent-based computational economics (ACE), that is, the use of computer simulations to 
study  evolving  complex  systems  composed  of  many  autonomous  interacting  agents 
represents  an  implementation  of  such  a  research  agenda.  With  modern  computer 
technology,  ACE  allows  an  explicit  modeling  of  identifiable,  goal-directed,  adapting 
agents,  situated  in  an  explicit  space  and  interacting  locally  in  it.  In  complex  adaptive 
systems, local interactions between the agents can lead to the spontaneous formation of 
macroscopic structure not evident by simple consideration of individual behaviours. 

Complexity then provides the essential step that takes economics from its position as 
an axiomatic discipline to being a falsifiable science at the micro, meso and macro levels. 
It also deals systematically with economic interactions and the aggregation of economic 
variables. 

2.2.1 Success stories 

Over  80  years  ago  in  ’Sozial  Physik’,  Lammel  showed  how  social  and  economic 
phenomena might be understood by applying simple physical concepts. In the last 20 years 
the  activity  of  a  few  has  become  a  global  activity  with  the  participation  of  many  groups 
from across the world. A second motivation for this activity by the physics community has 
been  the  availability  of  an  abundance  of  financial  data  that  now  covers  activity  down  to 
the level of transactions occurring every few seconds. This has allowed empirically inclined 
physicists with some economists to begin to gain new insights into these markets where trades 
take place at the level of seconds (Stanley, Farmer). The importance of this work cannot be 
overstated. If we can really understand what moves financial markets then much financial 
pain and misery that affects economies and ultimately the lives of citizens everywhere could 
be reduced. 

However not all markets are of this kind. For example, Weisbuch, Kirman and Herreiner (1998) 
have  studied  the  markets  for  perishable  foods  as  exemplified  by  the  Marseille  fish  market. 
They  showed  how  a  model  that  involved  customer  loyalty  or  preference  together  with  a 
learning  element  led  to  an  understanding  of  price  development.  This  model  illustrates  the 
emergence  of  order  in  the  sense  of  stable  trading  relationships  together  with  additional 
insights  into  the  way  fluctuations  could  break  down  that  behaviour.  Such  models  could 
have  application  in  the  wider  context  of  the  consumer  society  and  help  traders  and 
industrial businesses with purchasing and pricing strategies. 

Other  economic  problems  where  we  are  seeing  progress  are  concerned  with  aspects  of 
industrial  organization  including  distribution  and  growth  rates  of  firms  (e.g.  Stanley), 
income and wealth distributions (e.g. Chatterjee et al. 2005). Ideas first developed to study 
population dynamics, by Lotka-Volterra (Biham, Malcai, Richmond and Solomon, 2002) now 
vie with agent models first developed and applied to molecules (Richmond). Such models are 
challenging the concept of a simple rational agent and introducing heterogeneous agents that 
act  at  the  micro  level  and  which  when  aggregated  exhibit  behaviour  that  leads  to  non-
Gaussian  behaviour  with  ’fat  tails’  and  volatility  clustering.  With  modern  computers  it  is 
now  possible  to  simulate  increasingly  complex  models  that  incorporate  the  behavioural 
characteristics  of  the  interacting  agents.  This  offers  new  opportunities  for  the  physicist, 
economist and psychologist to cooperate when working on these challenging problems. 

Incomes  are  now  recorded  with  great  precision  and  frequency  in  countries  such  as  Japan. 
Unfortunately in many Western countries, data are not always available in a form that helps 
neither  detailed  analysis  nor  model  development.  This  is  unfortunate  since  it  is  self-
evident  that  if  the  structure  and  dynamics  of  both  incomes  of  individuals  and  the 
profitability of businesses can be properly understood, governments everywhere would be in a 
stronger position to apply fair and effective taxation policies.  

Emergence: a key concept inherent to all these problems and one that taxes the theorist is 
the question of ’emergence’. 

  22

 
 
 
 
 
 
 
Much  more  elusive  is  the  notion  of  intermediate  levels  (as  functional  mesoscopic  entities). 
Emergent  phenomena  are  composed  of  persistent  patterns.  They  emerge  from  the  low-level 
interactions and their emergence is recognized by the fact that they can be operated on by a 
separate  set  of  rules.  This  is  the  sense  in  which  emergent  phenomena  define  "levels". 
Analogies  with  physics  might  be  fruitful.  Consider,  say  interacting  electrons  in  the  solid 
state.  In  some materials the interactions lead to the formation of closely coupled pairs that 
give  rise  to  superconductivity  at  the  macroscopic  level.  Superconductivity  is  thus  an 
emergent state with properties determined by the electron pairs. Emergence may then be 
associated  with  persistence  of  some  kind  of  ’quasi-agent’  that  is  an  aggregate  of  the 
underlying agents. This concept of functional mesoscopic entities has been proven fruitful on 
several occasions under different designations such as motifs of well connected subgraphs in 
social networks or functional motifs in Genetic Regulatory networks. 

Economic policy issues 

RA  implies  the  existence  of  one  equilibrium  state  given  the  initial  conditions:  to  choose 
the "best" policy tool for obtaining a desired end would be quite trivial. By contrast, the 
characteristic  of  "emergence"  peculiar  to  complex  system  implies  the  possibility  of 
reaching one of many equilibria. This begs the question as to whether history and path of 
the state vector is important. 

If  economic  policy  operates  on  complex  environments,  ranging  from  telecommunication 
networks and financial markets to ecological to geophysical systems, the mainstream tools 
are, at best, misleading if not inappropriate. Methods developed for linear systems give rise 
to unintended consequences since implementation of policies can themselves not only change 
the  dynamics  associated  with  heterogeneous  agents,  but  also  change  the  overall  landscape 
within which these agents interact and evolve. 

Though the science and technology for the solution of complex adaptive systems have 
advanced  in  recent  years,  their  application  to  economic  policy  problems  seems  to  have 
lagged applications to the business and scientific worlds. (One noticeable exception was a 
simulation  of  the  influence  of  tic  size  on  the  Nasdaq  which  was  not  published;  the 
financial sphere is more discreet than the academics ...) 

Among suggestions that have been made for controlling complex economic systems: 

• 

• 

It will be necessary to develop a new decision theory based on "robustness"  vs.  the 
optimization principle (Lempert, R. J., 2002; Bankes, S. and Lempert, R. J., 1996). 
J-P Aubin’s viability theory (Birkauser Pub., 1991) goes along these lines. 

Ideas  of  ’control’  will  have  to  give  way  to  ’management’  of  complex  economic 
systems (Rihani, 2004). 

•  New  tools  such  as  those  based  on  ’visual  analysis  tracing’  will  be  necessary 
(Shneiderman, 2004) (the approaches of "Exploratory Modelling", Bankes, 1993 and 
"Adaptive Strategies"). 

Equally, the strong dependence of complex systems on the initial conditions suggests we shall 
move  away  from  "high  energy  control"  to  "small  energy  management"  of  the  economy. 
However, all these ideas and methodologies are still in their infancy and much more work is 
needed to bring them to maturity. 

Specific  areas  that  could  be  ripe  for  further  analysis  and  where  such  new  ideas  might  be 
further developed at this time include: 

•  The nature of income distributions and optimum approaches to redistribution within 

societies. 

•  Development  of  tools  for  identification  of  the  best  routes  that  ensure  control  of 
income dynamics during EC expansion and integration of new member states. 

  23

 
 
 
 
•  The  characterization  of  financial  instability  within  networks  of  firms,  banks  and 

other organization (see section 5.4). 

•  Methods  for  the  control  and  evolution  of  trade  and  income  distributions  across 

nations. 

2.2.2 Socio-economic networks 
By Gérard Weisbuch 

Since  socio-economic  networks  constitute  an  institutional  structure  allowing  production 
and trade, their investigation lies at the interface between social sciences and economics. 

The  concept  of  networks  is  pervasive  in  Complex  systems:  after  all,  any  interaction 
structure implies a network. Social networks as a vector for the propagation of information 
and decision among individuals are an old topic in social sciences since the 40’s. It has been 
active since that time and the Sunbelt Conferences now have participation in the thousands. 

The  interest  in  socio-economic  networks,  where  vertices  are  firms,  is  more  recent  and 
might have arisen from the Asian credit crisis of the late nineties. It contrasts with standard 
economics which: 

• 

consider firms as independent entities interacting with customers only through the 
market (General Equilibrium Theory) 

•  or discuss strategic interactions among a small set of firms (Game Theory). 

In  both  cases,  the  approach,  based  on  full  rationality  of  economic  actors  is  a  search  for 
equilibrium.  In  real  life,  firm  dynamics  are  far  from  equilibrium,  and  their  interaction 
structure  is  much  more  complex  than  the  hypotheses  of  General  Equilibrium  or  Game 
theories. 

Firms  interact  via  many  possible  channels,  which  constitute  as  many  edges  of  firm 

networks: 

•  The  most  straightforward  B2B  interaction  is  through  production:  the  output  of  a 

firm is used as an input by other firms. 

•  Firms also have capital cross-participations or credit relations. 

•  Firms  interact  via  their  personnel:  they  can  share  directors  on  their  boards; 
exchange  of  professionals  is  also  important  in  certain  industries  such  as 
innovation or the media industries. 

Industries are shaped by these interactions, especially new industries; understanding the 
consequences of these interactions is of fundamental importance for producers, investors, 
banks, national or international agencies. 

Many  recent  studies  concerned  the  static  interaction  structure  describing  firm 
networks.  Power  laws  scaling  describing  firm  size  and  wealth,  as  well  as  their  connection 
structure  were  empirically  observed  from  public  data  obtained  for  instance  from  stock 
exchange. 

The scale free structure of firms connectivity, -namely the fact that some firms  are  far 
more connected than others- whether it concerns trading relationships, partial ownership, 
sharing directors, etc. already gives a lot of information on strategic interactions and power 
relations. 

As in most network studies, the following issues are addressed in dynamical studies of 

economic networks: 

•  How  "smooth"  is  the  dynamics?  Should  one  expect  equilibrium  or  some  kind  of 
laminar  flow  of production  across the  network?  Or  a  richer  structure  with  cycles, 

  24

 
 
 
 
 
 
 
 
 
burst of activities, avalanches... Our experience of the real world (business cycles, 
bursts of volatility on the stock market, bubbles, etc.) evokes unstable dynamics, 
as  opposed  to  standard  views  of  economics,  which  discuss  any  irregularity  as 
driven by external factors (the so-called exogenous shocks). 

•  How is economic activity and wealth distributed across the net? Are any patterns 

observed? What is the stability of these patterns? 

•  Avalanches  are  among  spatio-temporal  patterns  of  interest:  they  concern 
avalanches  of  production  events  in  production  networks  seen  as  generalised 
supply chain, but also propagation of innovations or of bankruptcies. 

• 

“Meta"-dynamics of the network: how is the network structure itself evolving as a 
function  of  the  business  that  it  supports?  What  is  the  role  of  orders  and  actual 
exchanges on the growth and decay of existing links or in the emergence of new 
links? 

A  number  of  these  issues  were  raised  in  evolutionary  economics,  in  practice  mostly 
concerned  with  innovation  and  its  interplay  with  firm  economics;  or  in  geographical 
economics:  how  to  explain  the  strong  localization  of  economic  activity?  The  localization 
issue was soon brought to the attention of the observers of the industrial revolution, but 
the tremendous re-enforcement of localization with the New Industries makes the topics 
very relevant.  

Another domain of economics which should be enlightened by the network approach 
is the theory of the firm. Although firms are the most important actors of the economical 
world, we still don’t have formal model(s) of the firm. For instance, the mere existence of 
firms  is  simply  explained  in  standard  economics  by  transaction  costs:  a  firm  with  its 
permanent structure is more efficient than a labour market where entrepreneurs would hire 
workers  on  a  project  basis  because  of  the  costs  associated  with  hiring  and  firing  workers. 
The case of firms is typical of many problems where there exists a deep gap between the 
approaches  used  by  different  scientific  communities;  in  this  particular  case  economics, 
management science, sociology. 

The  meta-dynamics  of  production  networks  where  links  are  evolving  according  to 
business transactions is a rich dynamical path to a theory of the firm. Network vertices can 
be  interpreted  as  production  units;  the  evolution  of some edges towards strong and stable 
preferential  links  can  be  interpreted  as  merging  and  acquisitions.  Loosening  and  decreasing 
relative strength of a link as outsourcing. 

All these scientific challenges are fundamental issues faced by modern economies. 

Bottlenecks 

The most important present bottleneck is access to individual business transactions. It is 
connected  with  the  gaps  between  academics  and  the  private  practitioners  of  firm 
management,  financial  officers,  consulting  firms  and  even,  to  a  certain  extent,  business 
schools. 

  25

 
 
 
 
 
 
 
 
3 BIOLOGY 

From  the  early  days  of  complex  systems  research,  in  the  40’s  and  50’s,  biological 
systems  were  considered  as  an  inspiration  for  the  design  of  complex  artificial  systems. 
But  of  course,  understanding  the  self-organization  properties  of  biological  systems  was 
itself a major challenge. 

We  will  not  describe  here  in  detail  the  bio-inspired  applications  such  as  the  many 
applications  of  neural  nets  research  to  signal  processing:  the  reader  might  check  Mark 
Buchanan’s  document,  or  the  standard  literature  on  neural  nets.  We  similarly  skip  DNA 
computation, immunocomputing, etc. Bio-inspired algorithms will be used in section 3.6. 

We  will  rather  concentrate  on  complex  system  research  motivated  by  the 
understanding  of  biological  systems  such  as  cognition,  genome  expression,  the  immune 
system  and  ecology.  This  basic  research,  often  referred  to  as  systems  biology,  poses 
fundamental  scientific  questions;  furthermore,  its  application  to  health,  medicine,  drug 
design  and  environmental  issues  is  of  the  highest  importance.  For  instance  a  better 
understanding  of  the  interactions  that  control  gene  expression  would  considerably 
facilitate the design of new drugs, both in terms of inventing the drug and synthesizing 
it, but it would also help to check for possible negative side effects. 

The year 2000 has been a turning point in the application of complex system research 

to biology. 

3.1 Theoretical biology  
By Gérard Weisbuch 

Before 2000 the major effort was the understanding of functional properties of biological 
organs:  for  instance  how  can  neuron  assemblies  give  rise  to  cognitive  properties  in  the 
brain?  Hopfield  1982  PNAS  paper  on  associative  memories  of  assemblies  of  formal 
neurons is a typical example. Hopfield demonstrated formally that sets of formal neurons 
educated  by  a  simple  delocalised  algorithm,  Hebb’s  rule,  could  later  recognize  the 
patterns they had been taught; this recognition does not even request a presentation of 
the original pattern: even a presentation of a part of the pattern would suffice. 

Most of the research of the 40’s to year 2000 was along these lines: 

•  The  cellular  automata  of  Von  Neumann  were  proposed  as  models  of  self-

reproduction. 

•  S. Kauffman (1969) modeled phenotypic expression based on interactions among 

gene expression; 

•  R. Thomas, M. Kaufmann, A. S. Perelson et al. from the 70’s modeled the immune 
response as a result of idiotypic interactions among antibodies and cell receptors. 

•  A large fraction of the research interpreting the origin of life (Eigen, 1972; P. W. 
Anderson,  1983;  S.  Kauffman,  1989)  as  due  to  the  emergence  of  a  set  of 
autocatalytic polymers belongs to this line of research. 

•  The gradualism/catastrophism debate. Punctuated equilibria (the genotype/ 

  phenotype/population dynamics). 

•  Population ecology (Red Queen paradox, co-evolution, game theory and replicator 
the  Self-organised  Criticality 

from 

dynamics,  massive  extinctions  seen 
perspective). 

  26

 
 
 
 
 
 
 
 
 
 
 
 
 
At  that  time,  the  complex  systems  approach  was  an  alternative  to  the  reductionist 
approach  which  considered  biological  functions  as  the  result  of  a  finely  tuned  selection 
and  proned  a  major  effort  at  specifying  the  details  of  all  involved  components  and  of 
their  interactions.  The  complex  system  scientists  established  that  functional  properties 
could  be  the  result  of  interactions among  rather  simple  entities.  Functional  organization 
was shown to be a generic property of the attractors of the dynamics of the interacting 
system  rather  than  the  result  of  highly  tuned  natural  selection.  These  earlier  efforts 
greatly improved our insight in biological organization. 

3.2 Systems Biology  
By François Képès 

Standard approaches and their limits 

Molecular biology, a field initiated and developed by the interactions between biologists, 
biochemists, mathematicians and physicists, has provided a wealth of detailed knowledge 
about  molecular  mechanisms  at  work  in  organisms.  Most  recently,  the  contributions  of 
computer  scientists  have  enabled  breakthroughs  in  the  acquisition  and  interpretation  of 
genomic  data.  As  yet,  however,  none  of  these  critical  achievements  has  allowed  us  to 
obtain  an  integrated  understanding  of  the  functional  modules  and  regulatory  networks 
involved in cell and organismal physiology. 

The  promises  raised  by  the  identification  of  genes  involved  in  multifactorial  diseases 
have not turned into efficient therapies because most molecular biologists have focused 
on  individual  genes  and  proteins  rather  than  on  systems,  and  have  not  addressed 
questions such as: 

•  What  is  the  functional  architecture  of  these  interaction  networks  and  their 
modules, what are their dynamic properties? How do different levels of regulation 
intermingle? What are the organizing principles at play? 

•  How do robust behaviours emerge amidst stochastic molecular events? 

•  How  is  the  expression  coordinated  of  genes  involved  in  the  same  physiological 

process? 

•  How do cells tolerate, control or use noise in regulatory networks? 

•  How has evolution shaped these networks? 

•  How can results obtained in model systems be used to improve human therapy? 

•  How  can  regulatory  networks  be  deciphered  in  a  way  that  would  allow  the 
diagnosis  and  prognosis  of  multifactorial  diseases  and  the  design  of  new 
therapeutic strategies? 

In  order  to  tackle  these  questions,  biologists,  physicists,  chemists,  computer  scientists 
and mathematicians are needed. Together, they pave the way to a new approach in life 
sciences  dubbed  "systems  biology".  This  renewal  of  integrative  approaches  in  biology 
takes its roots in the legacy of quantitative and theoretical biology, and in the conceptual 
developments on self-organizing systems in the 1980’s. In the past 10 years, it has been 
fueled  by  the  availability  of  huge  datasets  produced  by  the  "-omics"  methodologies.  As 
these  methodologies  are  the  daughters  of  biochemistry  and  molecular  biology,  the 
datasets  have  a  marked  molecular  grounding,  hence  the  molecular  slant  of  systems 
biology in comparison to its ancestors. 

  27

 
 
 
 
 
 
 
 
 
 
 
 
 
As  an  emerging  discipline,  systems  biology  cannot  and should  not be  defined  in  a  strict 
way. Rather, it should be defined in an epistemic way, as a set of successful approaches 
that, together, constitute the first landmarks on a virgin territory. 

Gaps 

Several types of gaps must be considered in the case of systems biology. 

The  first  one  is  cultural.  Several  scientific  communities  must  closely  interact  for 
success, from bench-work to theoretical biology, the latter often being held in suspicion 
by bench biologists. For most molecular biologists, modern biology roadblocks are on the 
experimental side, while the vision from Systems Biology is how to build biological insight 
and transferable knowledge from a huge amount of experimental data. Still, to cut down 
on  costly  bench-work,  it  would  probably  be  a  good  idea  to  organize  and  improve  the 
synergy between conventional and computational experimentations. 

The second gap is ontogenic. One of the major challenges ahead of us will be to make 
the  best  use  of  the  massive  amount  of  molecular  data  generated  by  the  tools  of  post-
genomics. It is clear that the abundance of such data has increased tremendously in the 
recent  past.  Yet  a  closer  look  reveals  that,  with the  exception  of  genome  sequencing  in 
most  cases,  such  data  are  not  truly  exhaustive,  and  their  quality  is  generally  poor, 
although slow improvements can be foreseen. Thus, for a long time to come, the lack of 
exhaustivity  and  the  poor  quality  of  the  data  will  be  a  serious  ontogenic  obstacle  to 
quantitative  predictions.  Other  approaches  may  sometimes  permit  one  to  make  useful 
predictions from qualitative or semi-quantitative results. Importantly, it often suffices to 
be able to give the evolutive trend of the final parameter to determine the outcome. For 
example,  if  spontaneous  cell  death  outweighs  division  in  the  tumor  cell,  cancer  will 
regress, which is the single most important fact. Besides, it would be wasteful to convert 
the  few  available  quantitative  data  into  qualitative  results  for  the  sake  of  format 
homogeneity. It will therefore be crucial to succeed in combining, in the same simulation, 
the use of quantitative and qualitative results. 

The  third  gap  is  epistemologic.  The temptation  to  build  a  cell  and  an  organism  from 
their genomes and related molecular data implicitly relies on the conception that all the 
cellular information lies in the genome. This viewpoint is not warranted by available facts, 
yet it is widespread, thus creating an epistemologic obstacle. An obvious counterexample 
is  that  two  human  cells  endowed  with  an  identical  genome  may  exhibit  extremely 
different  phenotypes  (compare,  for  instance,  a  stomach  cell  and  a  neuron).  It  is  thus 
clear  that  part  of  the  cellular  information  is  held  in  its  genetic  material,  while  another 
part is distributed elsewhere in the cell. The genetic information is easier to identify, as it 
is contained mostly in one DNA molecule and is relatively accessible to us in the form of 
the genome sequence. This may explain why the genetic part is so strongly emphasized. 

Success stories 

Expectedly,  there  are  few  success  stories  in  such  a  recent  field  of  investigation.  Yet, 
three  examples  will  illustrate  a  variety  of  potential  approaches.  However,  let  us  first 
sketch some landmark developments in this field. 

The  first  surprise  came  when  it  was  demonstrated  that  biological  systems  ranging 
from food webs in ecology to biochemical interactions in molecular biology could benefit 
greatly  from  being  analyzed  as  networks.  In  particular,  within  the  cell,  the  variety  of 
interactions  between  genes,  proteins  and  metabolites  are  well  captured  by  network 
representations  and  associated  measures  including  degree  distribution,  node  clustering, 
hierarchy  and  assortativity  (Barabási  and  Albert,  1999;  Ravasz  et  al.,  2002;  Watts  and 
Strogatz,  1998).  The  global  topology  of  these  networks  showed  similarities  among 
themselves  as  well  as  with  respect  to  sociological  and  technological  networks  (Jeong  et 
al., 2000; Guelzim et al., 2002; Shen-Orr et al., 2002). 

In a second step, the issue of local topology, subgraphs and motifs was addressed. A 
number  of  biological  networks  were  found  to  contain  network  motifs,  representing 
elementary  interaction  patterns  between  small  groups  of  nodes  (subgraphs)  that  occur 

  28

 
 
 
 
 
 
substantially more often than would be expected in a random network of similar size and 
connectivity. Theoretical and experimental evidence indicates that at least some of these 
recurring  elementary  interaction  patterns  carry  significant  information  about  the  given 
network’s function and overall organization (Guelzim et al., 2002; Shen-Orr et al., 2002; 
Milo et al., 2002; 2004). Feed-back loops, feed-forward loops and other motifs were thus 
uncovered in real-world networks, and were attributed a qualitative dynamics. 

In  a  third  step,  such  dynamics  were  shown  to  be  effective  by  monitoring  them  in  a 
synthetic network with the same topology that had been implemented in live cells (early 
attempts:  e.g.  Becksei  and  Serrano,  2000;  Elowitz  and  Leibler,  2000).  In  reverse, 
network  design  could  be  automated  by  evolution  in  the  computer  towards  a  fixed  goal 
such as behaving like a toggle switch (François and Hakim, 2004). 

The  following  two  examples  illustrate  successes  using  the  discrete  and  differential 

approaches, respectively. 

The first example testifies to the usefulness of a discrete logical approach relying on 
few  available  data  and  drawing  from  the  corpus  of  formal  methods  from  computer 
science.  The  bacterial  population  that  opportunistically  invades  the  lungs  of  patients 
afflicted  with  cystic  fibrosis  often  switches  several  years  later  to  producing  mucus, 
thereby  becoming  more  resistant  to  antibiotics  and  making  breathing  more  difficult  for 
the  patient.  Two  hypotheses  with  different  therapeutical  prospects,  genetic  and 
epigenetic,  have  been  proposed  to  explain  this  mucoidal  switch.  The  generalized  logical 
method proposed by René Thomas, coupled to temporal validation (Bernot et al., 2004), 
allowed  to  validate  plausible  models  and  to  formulate  the  most  discriminatory 
experimental plan for choosing among the genetic and epigenetic hypotheses to explain 
the  mucoidal  switch  (Guespin-Michel  et  al.,  2004).  The  experimental  plan  has  been 
carried out successfully, with useful feed-back for the model. 

Modeling  of  chemotaxis  in  bacteria  exemplifies  differential  or  stochastic  approaches 
applied to understanding a phenomenon that exceeds human intuition. Chemotaxis refers 
to  the  cell  ability  to  swim  or  move  towards  a  chemical  attractant  or  away  from  a 
repellent.  The  mechanisms  of  chemo-taxis  in  eubacteria  (Shimizu  et  al.,  2003)  and 
archaebacteria (Nutsch et al., 2005) turned out to be principally different, although they 
are  both  based  on  a  random  walk  that  is  biased  by  comparing  the  actual  chemical 
concentration  to  that  memorized  at  a  previous  time.  In  eubacteria  for  instance,  the 
model not only matches experimental observations, but shows an unexpected emergence 
of  spatial  patterns  of  methylation,  the  chemical  modification  involved  in  the  memory 
effect (Shimizu et al., 2003). 

A last example shows how the coupling of bench and computer experimentation may 
provide answers to fundamental questions. Here, the issue is evolutionary optimization of 
fitness  to  environment  by  adjusting  a  certain  protein  level.  Bacteria  were  challenged 
during  several  generations  with  various  external  concentrations  of  a  sugar,  and  the 
cellular  production  of  the  sugar-metabolizing  protein  was  correspondingly  monitored.  A 
predictive  cost-benefit  model  was  considered,  in  which  the  growth  burden  of  producing 
the  specific  protein  was  balanced  by  the  growth  advantage  of  utilizing  the  sugar  when 
and  as  available.  In  a  few  hundred  generations,  cells  evolved  to  reach  the  predicted 
optimal  protein  production  level.  Thus,  protein  production  appears  to  be  a  solution  to  a 
cost-benefit  optimization  problem,  and  to  be  rapidly  tuned  by  evolution  to  function 
optimally in new environments (Dekel and Alon, 2005). 

Future challenges 

Globally,  one  of  the  major  challenges  associated  with  systems  biology  is  to  try  and 
understand  the  behaviours  of  biological  networks  of  interactions,  in  particular  their 
dynamic  aspects  and  spatial  developments,  often  with  a  goal  to  later  control  or  even 
design  them.  More  immediate  objectives  would  include  for  instance  dealing  with  their 
natural  heterogeneity  and  size,  including  spatial  aspects,  usefully  re-composing  the 
subnetwork  motifs  into  a  grand  network.  These  challenges  typically  require  cross-
disciplinary import of concepts, and crosstalk between experimentations through bench-
work and through modeling and simulation. 

  29

 
 
 
 
The success of this emerging discipline will rely upon new techniques and concepts. From 
the biological perspective, these techniques and concepts will come from areas including 
the  following:  -  multidimensional  and  quantitative  imaging  of  molecular  events;  - 
modeling,  simulating  and  mimicking  signal  transduction  pathways  and  regulatory 
networks  both  for  the  conception  of  experiments  and  the  interpretation  of  data  derived 
from  these  dynamic  images  and  from  high-throughput  techniques;  -  bio-inspiring 
evolutionary  algorithms,  which  reflect  back  into  improved  biological  models  (see  also 
section 3.4); - using micro- and nano-technologies to explore, manipulate and mimic the 
cellular nanoenvironment and to build new bio-sensors. 

Big  pharmaceutical  companies  in  Northern  America,  unlike  those  in  Europe,  are 
embarking  on  systems  biology,  with  various  goals  that  generally  include  several  of  the 
following: 

•  Personalized healthcare 

•  Cost-effective treatment (economic benefit) 

•  Personalized intervention with a model of the patient (individual benefit). 

•  Model-based intervention strategies 

•  Combined drug targets (addressing cases where more than one target should be 

hit at once to reverse the pathology) 

•  Drug-drug interaction (assessing the combined effects of multiple drug therapies) 

•  Chronotherapy (process-based time-dependent drug administration) 

•  Disease reclassification (based on molecular evidences). 

•  Streamlining therapeutic approval 

•  Shortening clinical trials 

•  Reducing animal testing 

From a more mathematical point of view, several new techniques and concepts are likely 
to stem from the so-called "inverse" problem. The availability of huge datasets since the 
1990’s such as transcriptomes obtained from biochips, multi-neuron recording, and new 
imaging techniques for instance, opens a new era in complex systems methods. Can we 
meet  the  challenge  of  this  data  driven  biology  and  extract  sensible  information  from 
these very large data sets? To be more specific, can we for instance extract the specific 
sets  of  interactions  among  genes  which  control  gene  expression  in  the  cell?  In 
mathematics,  such  a  problem  is  called  an  inverse  problem:  rather  than  finding  a 
trajectory  knowing  the  dynamics  governing  the  system,  we  here  have  to  solve  the 
inverse problem, getting the dynamics from the observation of successive configurations 
of expressed genes. 

Inverse  problems  are  known  to  be  much  harder  to  solve  than  direct  problems. 
Moreover,  in  systems  biology  one  has  to  solve  a  problem  with  a  very  large  number  of 
unknown  parameters.  Even  when  supposing  that  the  set  of  interactions  among  an 
ensemble  of  N  elements  is  sparse  rather  than  complete,  we  obtain  a  number  of 
parameters to be determined that scales as N. Furthermore, in general, the structure of 
the network is a priori unknown, and so is the nature of the interaction function. 

Fortunately,  inverse  problems  relate  to  a  number  of  problems  already  treated  in 
complex systems research. Learning by formal neuron networks is an inverse problem: it 
simply  means  finding  the  set  of  interactions  which  associates  output  patterns  to  input 
patterns.  Variants  include  pattern  sequence  generators.  An  exciting  prospect  is  to  use 

  30

 
 
 
 
 
 
 
 
 
 
 
 
 
 
and  generalise  learning  techniques  to  e.g.  decode  gene  regulatory  networks  using 
transcriptomic  data  that  provide  time  series  of  gene  expression  levels.  Among  the 
methods inspired from complex systems research that can be used to solve this problem, 
one of the most successful ones in the past years relies on the Bayesian framework (e.g. 
Friedman  et  al.,  2000).  Alternative  methods  are  likely  to  be  evaluated  in  the  coming 
years,  such  as  genetic  algorithms  or  the  survey  propagation  algorithm  developed  for 
constraint satisfaction problems. 

Finally, it should be stressed that the development of systems biology will be guided 
by historical and epistemological analyses of the interactions between biology and other 
disciplines.  It  will  also  be  important  to  recognize  the  ethical  questions  raised  by  the 
development  of  systems  biology,  and  to  answer  these  questions  by  challenging  human 
creativity rather than by dictating laws. 

3.3 Cognitive Science  
By Jean-Pierre Nadal 

Cognitive  science  is  about  understanding  both  natural  and  artificial  intelligence,  and 
requires interdisciplinary approaches. At the intersection of biology and human sciences, 
it  borrows  techniques  and  concepts  from  many  scientific  domains  -  psychology, 
neuroscience,  linguistics,  philosophy,  anthropology,  ethology,  social  science,  computer 
science,  mathematics  and  theoretical  physics.  The  RIKEN  Brain  Science  Institute 
(http://www.brain.riken.go.jp/)  in  Japan  is  one  of  the  best  examples  of  interdisciplinary 
institutes which have been created in recent years all over the world, with departments 
on  several  aspects  of  cognitive  science:  Understanding  the  Brain,  Protecting  the  Brain, 
Creating  the  Brain  (artificial  intelligence,  robotics),  and  Nurturing  the  Brain  (brain  and 
cognitive development). Interdisciplinary laboratories and institutes can also be found in 
Europe:  one  may  mention  the  Cognitive  Neuroscience  Sector  at  SISSA,  Trieste;  the 
GATSBY  Computational  Neuroscience  Unit  at  UCL,  London;  the  EPFL’s  Brain  and  Mind 
Institute in Lausanne; The Cognitive Science Institute (ISC) in Lyon and the Department 
of Cognitive Studies at École Normale Supérieure in Paris. 

Several  important  topics  in  cognitive  science  are  concerned  by  the  field  of  complex 

systems. Here are a few examples. 

•  Modeling  and  simulating  brain  functions  requires  the  mathematical  analysis  of 

large interconnected neural networks. 

•  The  study  of  collective  behaviour,  in  social  animals  and  in  human  societies 

requires similar tools. 

•  The  analysis  of  data  from  brain  imaging  leads  to  difficult  problems  in  artificial 

vision, data analysis, and modeling. 

An important complex systems topic concerning cognitive science and many other fields 
is the one of learning. This name evokes different but related aspects. 

•  On one side, the theoretical and experimental study of learning and adaptation, at 
all  possible  scales:  at  the  cellular  level,  the  network  level,  the  agent  level 
(analysis of human behaviour), at the collective level. 

•  On  the  other  side,  solving  inverse  problems  requires  the  development  of 
algorithms  which  can  be  understood  as  having  a  system  learning  a  rule  (a 
function, a task) from examples. 

Learning  theory,  statistical  (Bayesian)  inference,  optimal  control,  learning  in  formal  and 
natural  neural  networks,  supervised  or  unsupervised  learning,  reinforcement  learning, 
are  all  different  aspects  of  this  same  general  topic.  On  the  computer  science  side,  the 

  31

 
 
 
 
 
 
 
 
 
 
 
name Machine Learning denotes this general approach of learning a task from examples 
making  use  of  any  relevant  algorithm.  Machine  Learning  is  proving  an  increasingly 
important tool in many fields, such as Machine Vision, Speech, Haptics, Brain Computer 
Interfaces,  Bioinformatics,  and  Natural  Language  Processing.  The  EU  has  supported 
specific  actions  related  to  Machine  Learning.  For  instance,  the  PASCAL  network  of 
excellence of the FP6 program (see http://www.pascal-network.org) was created in order 
to  build  a Europe-wide distributed  institute, which  goal  is  to  pioneer  principled  methods 
of  pattern  analysis,  statistical  modeling  and  computational  learning.  Combinations  of 
concepts  and  tools  taken  from  learning  theory  and  statistical  physics  have  allowed  to 
address the modeling of dynamical networks, such as neural networks, genetic networks, 
metabolic  networks,  social  networks,  communication  networks...  In  such  domain,  one 
has to both, solve inverse problems (finding the network parameters from the empirical 
observation  of  the  network  activity),  analyse  and/or  simulate  the  network  dynamics,  in 
particular when the network components (cells, proteins, human agents.) are allowed to 
adapt to the environment and to the behaviour of the other components. 

3.4 Engineering emergence in self-assembling systems 
By Norman Packard 

Self  assembly  is  the  spontaneous  organization  of  components  into  larger-scale 
structures.  At  the  molecular  level,  this  process  is  "automatic",  in  the  sense  that  the 
components  are  driven  by  the  laws  of  thermodynamics  to  organize  themselves  into  a 
minimum  free-energy  state,  which  happens  to  be  a  complex  structure.  The  molecular 
domain is particularly powerful and interesting for exploring self-assembly because forces 
between  charged  molecules  and  surrounding  substances  (e.g.  water  or  other  solvents) 
create the appropriate thermodynamic conditions for complex self-assembly. 

Self-assembly  is  a  bottom-up  process,  defined  by  local  properties  of  the  self-
assembling  components  interacting  with  each  other  and  their  environment.  These  local 
properties  in  turn  determine  the  form  of  the  self-assembled  structures,  but  the  self-
assembly  process  may  be  complex,  in  the  sense  that  the  detailed  form  of  the  self-
assembled  objects  is  not  predictable  or  derivable  from  knowledge  of  the  component 
properties.  This  bottom-up  process  is  to  be  contrasted  with  top-down  design  processes 
that specify  a  target form  in  detail,  and  then use  a  highly  controllable  process  (such  as 
photo-lithography) to create it. 

Self-assembly  is  now  recognized  as  the  primary  path  for  the  construction  of 
nanodevices.  Other  approaches  based  on  transporting  traditional  top-down  engineering 
to the nano-scale, such as a programmable universal constructor envisioned by Drexler, 
appear  difficult  for  various  reasons,  including  the  effects  of  thermal  noise  at  the  nano-
scale. 

3.4.1 Control and programming of self-assembly 

Given  the  bottom-up  nature  of  self-assembly,  the  final  product  may  be  difficult,  if  not 
impossible,  to  control  if  the  dynamics  of  self-assembly  process  are  complex.  This  is 
typically the case in self-assembly of amphiphilic structures such as micelles or vesicles, 
and any time the self-assembly process includes nontrivial chemical reactions. 

There are, however, some self-assembly processes that are not complex, and that are 
in  fact  controllable  to  the  point  that  they  are  explicitly  programmable,  either  by 
synthesizing polymers (e.g. DNA, cf. Rothmans (2006), Nature 440, p. 297) so that they 
will  fold  automatically  into  particular  structures,  or  else  by  imposing  strong  boundary 
conditions on the self-assembly process that determine the final form (cf. D. Dendukuri, 
D.C. Pregibon, J. Collins, T.A. Aatton, P.S. Doyle (2006) "Continuous-flow lithography for 
high-throughput microparticle synthesis", Nature Materials, April). These processes have 

  32

 
 
 
 
 
 
been  very  successful  in  producing  nano-scale  modules,  but  have  yet  to  become 
integrated into systems with full target functionality. 

The  problem  of  programming  self-assembly  becomes  a  true  complex  systems 
problem  when  the  components  are  not  strongly  controllable,  because  the  self-assembly 
process  has  multiple  dynamic  pathways  with  strong  nonlinear  interactions  between 
components. In such cases, the final form of the self-assembled objects is not knowable. 
Thus, traditional approaches of programming by planning placement of modules explicitly 
cannot  work.  Instead,  the  space  of  self-assembled  objects  must  be  explored  by 
sophisticated search and optimization algorithms to achieve a programming goal.  

Examples of complex self-assembly processes include: 

•  Amphiphilic  self-assembly  of  fatty  acids  and  other  lipids  into  micelles,  vesicles, 
tubes,  perforated  sheets,  etc.  depending  on  constituent  amphiphiles  and  their 
thermodynamic phase (e.g. work of Luisi, Walde, Sczostak, and Hanczyc). 

•  Vesicle  formation  from  novel  inorganic  substances  (e.g.  Tianbo  Liu,  Ekkehard 
Diemann,  Huilin  Li,  Andreas  W.  M.  Dress  and  Achim  Mueller  (2003)  "Self-
assembly  in  aqueous  solution  of  wheel-shaped  Mo154  oxide  clusters  into 
vesicles", Nature 426, pp. 59-62). 

•  Nanostructures  from  organic  synthesis  (e.g.  work  of  G.  von  Kiedrowski,  L. 

Cronin). 

•  Surface functionality, either surface energetic or surface patterning, in the context 

of nano-electronics (inorganic) and functionalized organic molecular layers. 

•  DNA  scaffolding:  extensive  library  of  structures  formed  by  DNA,  including  bar-

codes, wires, complex matrices for attachment of reactants. 

•  Nano-gold  attached  to  various  structures  (e.g.  DNA,  Rubidium),  usable  for 

electronic functionality or local heating of a nano-structure. 

•  Molecular  motors  and  muscles:  components  for  moving  molecules  as  well  as 

aggregates have been developed at the component level. 

•  Fused-polymer shapes. 

Communities  spanned:  synthetic  chemistry,  MEMS  (micro  electromechanical  systems), 
molecular  computing,  physics,  numerical  computation  (molecular  dynamics,  dissipative 
particle dynamics). 

Potential research and application areas: molecular circuitry, computation, molecular 

robotics, biosensors, energy, artificial living cells. 

Future challenges: specific research area targets. These target areas could span research 
and application areas listed above. 

•  Extracting electrical energy from nano-objects. 

•  Extracting mechanical energy from nano-objects (muscles and motors). 

•  Functionalizing nano-objects by coupling to chemical reactions. 

•  Achieving multiple functionality with multiple co-existing assembly processes and 

chemical reactions. 

•  Programmed interactions with living organisms. 

  33

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
3.5 Epidemic modeling and complex realities  
By Alessandro Vespignani 

A  wide  range  of  modeling  approaches  are  crucially  depending  upon  the  accurate  and 
realistic  description  of  social/infrastructural  and  behavioural  data  in  spatially  extended 
systems. This includes the movement of individuals at  various different levels, from the 
global  scale  of  transportation  flows  to  the  local  scale  of  the  activities  and  contacts  of 
individuals,  interrelations  among  infrastructure  networks  (cyber/physical  levels)  and  the 
complex  feedback  mechanisms  regulating  traffic  and  behaviour.  These  factors  are 
determinant  in  a  wide  range  of  problems  related  to  understanding  and  forecasting  the 
system behaviour in epidemiology, population biology, transportation and traffic analysis, 
infrastructure planning and social behaviour. 

In  this  context,  mathematical  epidemiology  approaches  has  evolved  from  simple 
compartmental models into structured models in which the heterogeneities and details of 
the population and system under study are becoming increasingly important features. In 
the case of spatially extended systems, modeling approaches have evolved into schemes 
which explicitly include spatial structures and consist of multiple sub-populations coupled 
by movement among them. This patch or meta-population modeling framework has then 
evolved  into  a  multi-scale  framework  in  which  different  granularities  of  the  system 
(country,  inter-city,  intra-city)  are  considered  through  different  approximations  and 
coupled  through  interaction  networks  describing  the  flows  of  agents  (people,  animals, 
merchandise,  parcels  of  information,  technology).  In  addition,  the  introduction  of  agent 
based  models  (ABM)  has  enabled  to  stretch  even  more  the  usual  modeling  perspective, 
by simulating these systems at the level of the single individual. 

  34

 
 
 
Figure  5:  Different  scales  structure  used  in  epidemic  modelling.  Circled  symbols 
represent  individuals  and  the  different  shades  of  gray  correspond  to a  specific  stage 
of  the  disease.  From  left  to  right:  homogeneous  mixing,  in  which  individuals  are 
divided  into  compartments  and  assumed  to  homogeneously  interact  with  each  other 
at  random;  social  structure,  where  people  are  classified  according  to  demographic 
information (age, gender, etc.); contact network models, in which the detailed social 
interactions between individuals provide the possible virus propagation paths; multi-
scale  models  which  consider  sub-population  coupled  by  movements  of  individuals, 
while homogeneous mixing is assumed on the lower scale; agent based models which 
recreate  the  movements  and  interactions  of  any  single  individual  on  a  very  detailed 
scale (a schematic representation of a city is shown).  

  35

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
The above modeling approaches are based on actual and detailed data on the activity of 
individuals,  their  interactions  and  movement,  as  well  as  the  spatial  structure  of  the 
environment,  transportation  infrastructures,  traffic  networks,  etc.  While  for  a  long  time 
this  kind  of  data  was  limited  and  scant,  recent  years  have  witnessed  a  tremendous 
progress  in  data  gathering  thanks  to  the  development  of  new  informatics  tools  and  the 
increase  in  computational  power.  A  huge  amount  of  data,  collected  and  meticulously 
catalogued, has finally become available for scientific analysis and study. 

Networks  which  trace  the  activities  and  interactions  of  individuals,  social  patterns, 
transportation  fluxes  and  population  movements  on  a  local  and  global  scale  have  been 
analyzed  and  found  to  exhibit  complex  features  encoded  in  large  scale  heterogeneity, 
self-organization  and  other  properties  typical  of  complex  systems.  Along  with  the 
advances  in  our  understanding  and  characterization  of  systems  complexities,  the 
increased CPU power has led to the possibility of modeling multi-scale dynamical models 
by  using  thousands  of  coupled  stochastic  equations  and  allows  agent  based  approaches 
which  include  millions  of  individuals.  This  prompts  to  the  definition  of  a  modern 
computational  epidemiology  area  that  integrates  mathematical  and  computational 
sciences and informatics tools and aims at providing a new approach to the forecast and 
risk assessment for emerging disease. 

Key  elements  in  the  development  of  such  an  approach  are  the  integration  of 
information  technology  tools  and  techniques  with  the  perspective  coming  from  complex 
systems  analysis.  By  one  side  this  computational  approach  needs  to  integrate  GIS 
techniques,  on-line  data  analysis,  petabyte  data  handling  and  simulations,  with  the 
creation  of  the  necessary  infrastructures.  On  the  other  hand  such  an  approach  has  to 
deal  with  all  the  complexity  features  emerging  in  the  analysis  of  large  scale  systems 
made  by  a  massive  amount  of  elements/individuals.  Non-linear  behaviour,  cooperative 
and emergent phenomena, complex networks, etc. cannot be neglected and will be at the 
basis  of  the  interpretation  and  understanding  of  results  as  well  as  in  the  formulation  of 
the opportune computational techniques. 

Meeting  this  challenge  however  requires  to  adapt  and  complement  the  basic 
approaches  developed  in  mathematical  and  statistical  epidemiology  to  large  scale 

4

6

 to 10

 degrees of freedom) and to investigate in a systematic fashion the 
systems (10
impact  of  the  various  complexity  features  of  real  systems  on  the  basic  properties  of 
epidemic  spreading.  In  particular  this  implies  filling  some  major  theoretical  and 
methodological  gaps.  The  first  one  concerns  basic  theoretical  foundations  and  analytical 
understanding  of  multi-scale  epidemic  models  with  many  degrees  of  freedom  and  their 
interplay  with  the  complex  societal  networks.  What  are  the  basic  principles  and  theory 
that  govern  epidemic  behaviour  in  large  scale  complex  multi-scale  network  and  Agent 
Based  epidemic  models?  How  do  the  large  scale  complex  features  (scale  invariance, 
extreme  heterogeneity,  and  unbounded  fluctuations)  of  interaction  and  communication 
networks affect the behaviour of spatially extended epidemic models? A further challenge 
is  that  even  in  the  assumption  that  the  models  used  provide  an  exact  description  of 
reality  and  captures  all  the  features  of  the  system,  it  is  clear  that  our  predictive  power 
will  be  limited  by  the  impossibility  of  an  exact  knowledge  of  the  precise  state  of  the 
system. In addition, quantitative data on the social response to emergency and crisis are 
needed in order to have correct epidemic forecast, risk assessment, scenario evaluation. 
New experiments should therefore be devised in order to provide the correct data driven 
inputs necessary in large scale simulations. 

Despite such an integrated computational approach is still in its  infancy, the level of 
realism and detail achievable today allows us for the first time to ambitiously imagine the 
creation  of  computational  infrastructures  able  to  provide  reliable,  detailed  and 
quantitatively  accurate  predictions  for  disease  spreading.  These  will  be  based  on  real 
time  data  collection  and  large  computational  models  as  it  is  now  done  in  the  case  of 
weather  forecast.  In  other  words  computational  approaches  are  now  ready  to  interface 
with  the  complex  features  of  infrastructures  and  social  dynamics,  entering  the  era  in 
which it may become a major predictive tool. 

  36

 
 
 
 
Grand challenge 

Large  computational/modeling  infrastructure  (petabyte-computation,  billions  individual 
agents)  Modern  Computational  approaches  and  infrastructures  as  sophisticate  and 
effective  as  the  weather  forecast  approach  in  modern  meteorology.  Meeting  these 
challenges  requires  to  adapt  and  complement  the  basic  approaches  developed  in 
mathematical and computational methods, as well as the data gathering infrastructures, 

degrees of freedom) and to 
to the detailed description of large scale systems (10
investigate in a systematic fashion the impact of the various complexity features of real 
systems on the basic properties of epidemic spreading. 

to 10

4

8

Intermediate challenges: 

•  Data  collection/integration  infrastructures  and  projects.  Quantitative  level. 
Establishment  of  monitoring  infrastructures  able  to  provide  a  constant  output  of 
longitudinal data. 

•  Next  frontier  of  network  science.  Theoretical  foundations  of  network  interfacing; 
multi-scale, multi-layer networks understanding; mutual feedback representation. 
Theoretical and data gathering effort. 

•  Conceptual  (intermediate  theoretical  understanding).  While  extremely  powerful, 
however,  these  numerical  tools  are  often  not  transparent,  being  extremely 
difficult,  if  possible  at  all,  to  discriminate  the  impact  of  any  given  modeling 
assumption  or  ingredient.  In  addition,  complexity  is  not  the  same  as  the  merely 
complicated  elements  accounted  for  in  sophisticate  computational  approaches. 
There  is  a  need  to  investigate  in  a  systematic  way  the  impact  of  the  various 
complex  features  of  real  systems  on  the  basic  features  of  the  phenomenon/ 
process at hand. 

Important key factors for success: 

•  Global effort (multi-country, data sharing) 

• 

Inter-disciplinary effort 

3.6 Bio-inspired strategies for new computing architectures and 
algorithms paradigms 
By François Képès  

Rationale 

In  contrast  to  purely  technological  systems,  life  forms  show  a  high  capacity  to  self-
organize, replicate, grow, heal, adapt and evolve. This is why biology was and remains a 
major  source  of  inspiration  for  the  design  of  new  hardware,  computing  architectures, 
algorithms  and  software  programming  paradigms.  Such  inspiration  mostly  comes  from 
the following biological processes: evolution, development, and growth. These processes 
share highly refined regulations but strongly differ in their mechanisms and in their time 
scales. 

Evolution has inspired algorithms that efficiently solve difficult optimization problems. 
In the past two decades, such algorithms have successfully found applications in science, 
engineering and humanities. In the field of genetic and evolutionary computation (GEC), 
as  in  biological  evolution,  variation,  selection  and  amplification  steps  are  sequentially 
repeated to trace a path towards an improved solution to the problem at hand. 

  37

 
 
 
 
 
 
 
 
 
 
 
 
 
Development  is  not  directly  encoded  by  the  genotype.  Rather,  development  unfolds  in 
time  and  space  a  network  of  interactions  which  in  turn  is  orchestrated  by  genotypic 
information. Interestingly, this genotypic information is interpreted in ways that vary as 
the  developmental  process  unfolds  and  modifies  its  own  environment.  Among  other 
things,  development  is  therefore  a  good  inspiration  for  designing  systems  with  an 
enriched genotype-to-phenotype mapping. 

Growth and cell division constitute a prime example of how a distributed system may 
operate, bounded only by finite resources. Even in modern cells, division is a process of 
fracture and stochastic distribution of constituents among the daughter cells. Even large 
unique  bodies  in  a  cell  such  as  the  animal  Golgi  apparatus  are  broken  into  numerous 
pieces before division occurs. The only exception to this rule is the genetic material which 
is quantitatively duplicated and faithfully segregated. Both this exception and the general 
process  of  fracture  and  growth  could  be  harnessed  in  environment-sensitive  systems 
such as growing and dividing hardware. 

Present bottlenecks 

Examples  of  bio-inspired  computational  approaches  now  span  a  whole  range  from 
behavioural  approaches  like  ant  algorithms  to  molecular  approaches  like  genetic 
algorithms, genetic programming or artificial chemistries. However, most GEC techniques 
were designed on the basis of biological knowledge of the ’80s and earlier times. In the 
meantime,  biology  has  brought  a  wealth  of  new  knowledge  that  could  fuel  advances  in 
GEC.  Another  current  shortcoming  originates  from  the  fact  that  genotype-phenotype 
mapping is still rudimentary in most applications. 

Impact 

Past  experience  with  bio-inspiration  indicates  that  this  interdisciplinary  exploration  of 
self-organization,  adaptation,  evolution  and  other  emergent  functionalities  of  living 
systems will further improve our ability to design new computing models, algorithms and 
software  programming  paradigms.  These  improvements  will  indeed  be  of  a  quantitative 
nature,  but  a  qualitative  jump  is  also  to  be  expected,  as  the  problems  addressed  by 
information  technology  are  insidiously  bounded  by  common  knowledge  of  what  can 
currently be tackled. Moreover, there is enormous potential for applying the outcome of 
this  exploration  at  the  physical  level,  in  particular  at  the  nano-  and  micro-scale,  to 
develop new types of growing and evolving hardware and intelligent materials that could 
be applied in a variety of ambient interfaces. 

Main research objectives 

To tackle problems that were intractable thus far, that are multi-objective, or that cannot 
even  be  anticipated,  it  may  be  foreseen  that  algorithms  must  be  complexified.  Such 
future  problems  share  a  few  features,  including  the  following:  they  cannot  be  fully 
specified  beforehand;  they  vary  with  time;  the  relevant  data  are  available  but  are  not 
sorted  from  irrelevant  ones;  the  solving  process  must  harness  emergence  to  overcome 
the "complexity" ceiling; it must not presume human intervention. 

Complexification  of  the  algorithms  would  often  involve  allowing  new  degrees  of 
freedom.  Merely  adding  degrees  of  freedom  does  not  constitute  a  solution  however,  as 
the searching process looses efficiency. Therefore, it is clear that allowing new degrees of 
freedom  should  be  accompanied  by  restrictions  either  in  the  authorized  processes  or  in 
the  parameter  ranges.  In  this  delicate  balance  between  restriction  and  freedom,  bio-
inspiration  has  proven  a  fruitful  guide,  and  the  objective  here  is  to  resort  again  to  bio-
inspiration to reach the above main objectives. 

  38

 
 
 
 
 
 
 
 
 
Specific objectives 

Achieving useful complexification will require research in several directions, including: 
-  Enriching  the  genotype-phenotype  mapping  (e.g.  making  it  emergent)  with  concepts 
such  as  distributed  causality  or  feedback  control,  inspired  e.g.  by  the  sophisticated 
behaviour afforded by development or individual variability. 

-  Implementing  open-endedness,  e.g.  where  evolution  moves  its  own  target,  or  fitness       

function evolves. 

- Moving from single-objective to multi-objective optimization goals. 

- Maintaining a vast repertoire of potential algorithms or solutions and means to mobilize 
  it. 

-Implementing a simplified physical model in appropriate cases, e.g. where a micro- 
  dynamics and a macrostructure influence each other. 

- Evolving large complex systems from a lineage of less complex systems. 

- Continuous data mining from ever growing databases. 

- Innovative design involving the creation or deletion of variables. 

- Generation of "surprising" hypotheses, bridging the gap with Artificial Intelligence. 

- Feature selection in data-rich environments that vary as a result of internal dynamics. 

Timeliness 

While  an  increasing  number  of  bio-inspired  optimization  methods  are  now  claiming 
human-superior  quality  of  solutions,  while  the  fields  of  bio-inspired  applications  are 
numerous  in  science, engineering  and  humanities,  we  are  still  far  from  tackling  real-life 
complex  systems.  This  research  and  development  will  contribute  to  the  design  of 
algorithms  and  methods  that  incorporate  strategies  from  the  living  matter  and  that  can 
tackle problems that were intractable so far. 

Relevant fields 

ICT  (optimization  algorithms,  artificial  evolution,  artificial 
intelligence,  artificial 
chemistry),  life  sciences  (molecular  biology,  cell  biology,  physiology,  systems  biology), 
engineering (optimization). 

  39

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
4 INFORMATION AND COMMUNICATION TECHNOLOGIES 

4.1 Optimization and Complexity 
By Rémi Monasson 

Optimization  is  a  task  of  crucial  importance  in  industrial  and  social  processes.  Basically 
the  problem  is  to  find  the  minimum  (or  the  maximum)  of  a  function  called  cost  over  a 
large number of variables. Perhaps the most famous example of optimization problem is 
the  so-called  travelling  salesman  problem  (tsp),  where  a  person  has  to  visit  a  set  of 
towns  and  come  back  to  its  starting  point.  The  cost  function  is  the  total  length  of  the 
tour,  the  variables  are  the  order  (permutation)  of  the  towns  to  be  visited.  Another 
celebrated  problem  is  the  constraint  satisfaction  problem  (csp):  given  a  set  of  logical 
constraints  over,  say,  Boolean  variables,  what  is  the  largest  number  of  constraints  that 
can be satisfied altogether? 

Tsp, csp, and hundreds of other problems have been studied for decades in computer 
science. A major result, which emerged in the seventies, is the concept of computational 
complexity.  Problems  were  classified  in  terms  of  the  growth  of  the  running  time  of 
resolution algorithms. Briefly speaking easy problems are the ones for which there exist 
algorithms finding the optimum in a time growing only polynomially with the number of 
data  (e.g.  the  number  of  towns  in  tsp,  of  constraints  in  csp).  The  other  problems,  for 
which  no  such  polynomial  algorithms  are  known  and  all  known  algorithms  can  take 
exponentially growing times, are called hard. 

This classification has played and is still playing an enormous role in computer science 
but suffers from some weaknesses. The most important one is that it is a mathematical 
concept  based  on  the  idea  of  worst  case.  To  be  more  precise  consider  again  the  tsp 
problem. Tsp is considered to be hard since there is no algorithm (so far) guaranteed to 
find the shortest tour over ANY set of N towns in a time polynomial in N. But finding the 
shortest tour can be easy for some, not to say, most sets of towns! In other words the 
worst case classification can be too pessimistic. Another criticism is that, while finding the 
true optimum can be hard, it can be much easier to find very good approximations of this 
optimum, of sufficient quality in practical applications. 

Based on these considerations people in artificial intelligence and practitioners as well 
as theoreticians in computer science have started to study the hardness of optimization 
problems when the input data are randomly chosen from distributions mimicking as close 
as possible realistic data or more academic distributions easy to generate (but not solve!) 
on computers. An important heuristic finding was done at the beginning of the 90’s when 
people  discovered  the  existence  of  phase  transitions,  very  similar  to  the  ones 
encountered in the physics of condensed matter, in the problem of Random Satisfiability 
(sat), a particular case of csp. 

Briefly  speaking  sat  is  defined  as  follows.  One  is  given  a  set  of  N  Boolean  variables 
and a set of M constraints. Each constraint involves exactly three variables and is of the 
type variable number 1 is true or variable number 4 is false or variable number 5 is true. 
The labels (from 1 to N) of the variables in each constraint are chosen randomly and 
each  variable  is  required  to  be  true  or  false  by  the  constraint  with  probability  one  half. 
Surprisingly  when  the  number  N  of  variables  and  the  number  M  of  constraints  go  to 
infinity at fixed ratio 

α= M/N 

when  the  ratio  of  constraints  per  variable  is  smaller  than 

there  appears  a  phase  transition  at  some  critical  value  of  α, 

cα =  4.26,  such  that 
cα   a  randomly  chosen  set  of 
constraints admits almost surely at least one solution while above this critical ratio there 
is almost never any solution. 

  40

 
 
 
 
 
 
This  phase  transition  is  interesting  since  it  coincides  with  the  instances  which  are  the 
hardest  to  solve  with  existing  algorithms,  such  as  branch-and-cut  procedures  or  local 
search  algorithms.  We  have  thus  at  our  disposal  a  very  easy  way  of  generating 
seemingly hard problems! 

Statistical  physicists  have  studied  this  phase  transition  in  detail  in  the  past  decade, 
and more generally the behaviour of the sat problem at any ratio. Here are a few results 
which were found: 

-the value of the critical ratio locating the phase transition was calculated extending 
techniques invented by G. Parisi in the field of spin glasses at the beginning of the 80’s. 
In  addition  another  phase  transition  was  discovered  in  the  phase  where  solutions  exist 
cα ).  This  phase  transition  corresponds  to  the  clustering  of  solutions  in  groups  of 
(α  < 
solutions  far  from  each  other  in  the  variable  configuration  space.  It  has  some  deep 
consequence on the behaviour of local search algorithms. 

-these  physical  techniques  were  in  addition  used  to  build  a  new  algorithm  to  find 
solutions  to  random  sat  problems  close  to  the  phase  transition.  This  algorithm,  a  new 
member  of  the  family  of  message-passing  algorithms  (as  Belief  Propagation  used  in 
cα  in average time polynomial 
communication theory), finds a solution for ratios close to 

in the number of variables, while from the worst-case point of view, sat is hard. 

-the performances of classical algorithms, as branch-and-cut procedures, local search 
algorithms,  has  been  characterized  and  understood  to  a  large  extent  with  statistical 
physics  ideas  and  techniques.  In  particular  the  ideas  of  dynamical  phase  transitions, 
metastability, universality, have been shown to play an important role. 

After one decade of intensive research and successes it is time to think about what is 
needed  to  go  forward.  As  a  first  step  it  is  certainly  important  to  extend  the  above 
researches  to  less  academic  and  more  practical  distributions  of  data.  Distributions 
corresponding  to  industrial  applications  are  available  on  large  databases  and  existing 
algorithms are being tested upon those. Phase transitions are likely to take place, but the 
nature  of  the  transition  will  be  more  complex  than  in  academic,  purely  random 
distributions. 

Another important direction is the understanding of finite size effects. Mathematical or 
physical  theories  are  often  based  on  the  idea  that  "the  size  of  the  problem  goes  to 
infinity".  While  this  assumption  can  give  qualitatively  excellent  results,  it  never  holds  in 
practice  and  one  needs  to  understand  what  happens  for  large  albeit  finite  problems. 
Statistical  physicists  have  answered 
for  physical  systems  at 
thermodynamical  equilibrium  but  what  happens  in  dynamically  evolving  systems  is  far 
less understood. 

this  question 

On the long term the most important direction could be to understand in a better way 
how  algorithms  as  message-passing  procedures  work  and  what  tasks  they  can  really 
achieve.  The  fundamental  problem  is  to  make  work  together  many  small  processors 
located  at  the  node  of  a  network,  with  information  flowing  through  the  edges  of  those 
networks.  While  every  processor  is  fed  with  local  information  (i.e.  coming  from  its 
neighbours)  the  set  of  processors  is  capable  of  achieving  a  global  task  (i.e.  to  find  a 
solution  to  the  set  of  constraints).  This  kind  of  distributed  architecture  is  ubiquitous  in 
natural (biological) and artificial (e.g. the Internet) networks. The results obtained so far 
in  the  field  of  random  optimization  problems  suggest  that  these  algorithms  are  very 
powerful. 

4.2 Networks, especially computer   
By Guido Caldarelli 

One  of  the  descriptions  of  complexity  on  which  most  of  the  scientists  agree  is  that 
complexity  arises  when  many  independent  parts  of  a  system  interact  in  such  a  way  to 
produce a novel global behaviour. Put in this way, it becomes natural to think of network 
theory as one of the most natural tools  in order to describe complex systems. Probably 
for  this  reason,  the  approach  of  complex  network  emerged  spontaneously  in  different 

  41

 
 
 
 
areas  and  it  now  represents  one  of  the  few  really  interdisciplinary  areas  of  research. 
Mathematically, all these systems used to be considered as haphazard sets of points and 
connections,  mathematically  in  the  random  graph  paradigm  (Bollobás,  1985;  Erdös  and 
Rényi, 1960). This situation has radically changed in the last few years, during which the 
study  of  complex  networks  has  received  a boost  from  the  ever-increasing  availability  of 
large  data  sets  and  the  increasing  computer  power  for  storage  and  manipulation.  In 
particular,  mapping  projects  of  the  WWW  (Adamic  and  Huberman,  2000)  and  the 
physical Internet (Faloutsos, Faloutsos and Faloutsos, 1999) represented the first chance 
to  study  the  topology  of  large  complex  networks.  Gradually,  other  maps  followed 
describing  many  networks  of  practical  interest  in  social  science,  critical  infrastructures 
and  biology.  Researchers  thus  have  started  to  have  a  systematic  look  at  these  large 
datasets,  searching  for  hidden  regularities  and  patterns  that  can  be  considered  as 
manifestations  of  underlying  laws  governing  the  dynamics  and  evolution  of  these 
complex systems (Pastor-Satorras and Vespignani, 2004; Albert and Barabási, 2001). 

Amongst the regularities that have been found we list the following: 

•  Many  of  these  systems  show  the  small-world  property,  which  implies  that  in  the 
network  the  average  topological  distance  between  the  various  nodes  increases 
very slowly with the number of nodes (logarithmically or even slower) (Barrat and 
Weigt, 2000). 

•  A  particularly  important  finding  is  the  realization  that  many  networks  are 
characterized  by  the  statistical  abundance  of  "hubs";  i.e.  nodes  with  a  large 
number of connections to other elements. This feature has its mathematical roots 
in  the  observation  that  the  number  of  elements  with  k  links  follows  a  power-law 
distribution,  indicating  the  lack  of  any  characteristic  scale.  This  has  allowed  the 
identification  of  the  class  of  scale-free  networks  which  topological  features  turn 
out to be extremely relevant in assessing the physical properties of the system as 
a  whole,  such  as  its  robustness  to  damages  or  vulnerability  to  malicious  attacks 
(Caldarelli, Marchetti and Pietronero, 2000; Albert, Jeong and Barabási, 2001). 

The attempt to model and understand the origin of the observed topological properties of 
real  networks  has  led  to  a  radical  change  of  perspective,  shifting  the  focus  from  static 
graphs,  aiming  to  reproduce  the  structure  of  the  network  in  a  certain  moment,  to 
modeling  network  evolution.  This  new  approach  is  the  outcome  of  the  realization  that 
most complex networks are the result of a growth process. As a result, we currently view 
networks as dynamical systems that evolve through the subsequent addition and deletion 
of vertices and edges. 

Network Applications (so far) 

The applications of network theory are several, here we restrict only on those related to 
computer  science  and  biology,  for  which  many  progresses  have  been  made.  Different 
technological  networks  as  the  Internet  (Faloutsos,  Faloutsos  and  Faloutsos,  1999; 
Caldarelli,  Marchetti  and  Pietronero,  2000)  WWW  (Adamic  and  Huberman,  2000), 
Wikipedia (Capocci et al., 2006) have been analysed with the tools of graph theory. One 
classical  result  is  that  the  authority  of  a  page  on  the  web  can  be  established  by  its 
PageRank  (Brin,  Page,  Motwami  and  Winograd,  1998)  that  roughly  corresponds  to  the 
probability  for  a  random  walker  to  visit  it.  This  algorithm  is  at  the  basis  of  the  search 
engine  Google  and  triggered  even  more  activity  in  the  field.  A  particular  important 
application can also be found in the field of cell biology. Both protein interaction and the 
interconnected  series  of  reactions  present  in  signaling  have  their  natural  description  in 
the  framework  of  complex  networks.  Apart  from  the  obvious  importance  of  these 
applications  for  medical  science  it  has  to  be  noticed  that  these  two  networks  are 
interconnected, since complexes of interacting proteins can act as enzymes and develop 
a  series  of  reactions  that  results  in  a  signaling  network.  In  this  way  we  have  one 
paradigmatic  example  of  different  networks  related  by  a  feedback.  A  similar  situation 

  42

 
 
 
 
 
 
 
arises  also  in  computer  science  where  Internet  and  WWW  are  related  by  a  similar 
relationship.  Consequently  theoretical  progresses  in  the  modeling  of  networks  results  in 
an increased understanding in both fields. 

Challenges 

A  key  problem  in  the  present  society  is  the  study  of  the  formation  and  evolution  of 
communities within the web and other social and technological systems. The knowledge 
of  such  communities  is  crucial  to  design  better  techniques  for  exploring  those  networks 
and  retrieving  specific  information.  As  a  particular  case  of  social  system  can  be 
considered those formed by financial  institutions. In such a case a structure of complex 
networks  with  interconnected  communities  is  at  the  base  of  lobbying  in  boards  of 
directors (Battiston, Bonabeau and Weisbuch, 2003; Caldarelli and Catanzaro, 2004) and 
various correlations in stock prices and ownerships (Bonanno et al., 2005). Similarly the 
presence  of  communities  in  technological  networks  has  also  immediate  and  important 
meanings. The currently most successful strategy for web search relies on the Page Rank 
algorithm, which navigates the web by exploiting only its most basic link structure - how 
pages link to one another via hypertext links. But web documents (texts, images, media 
files and data) are also connected to each other by virtue of their membership in larger 
communities. Such communities - evident as clusters of densely interlinked pages -often 
have  a  thematic  meaning  based  on  some  shared  property.  By  focusing  on  the 
identification  of  such  communities,  we  believe  it  will  be  possible  to  provide  a  thematic 
division of the web that will facilitate web crawling and information retrieval. Doing so will 
require  an  effective  combination  of  the  mathematics  of  graph  theory  and  computer 
science  with  the  traditional  behavioural  perspective  of  the  social  sciences,  while  also 
bringing  in  the  modern  techniques  of  statistical  physics  which  are  specifically  suited  for 
dealing with large systems such as the World Wide Web. Similar interdisciplinary efforts 
toward  community  characterization  have  already  been  successful  in  studies  of  the 
electronic  communications  infrastructure  of  large  institutions.  Communities  are  also  the 
fingerprint  of  the  presence  of  protein  complexes  (Gavin  et  al.,  2002)  and  could  play  a 
great  role  in  the  identification  of  the  development  of  signaling  networks  in  the cell.  The 
possibility  to  control  such  processes  would  have  a  series  of  immediate  applications  in 
medical science to cite only one example. Under this respect a "man on the moon" goal 
would  be  the  mathematical  characterization  of  complexity  in  the  social,  biological  and 
technological structures. 

  43

 
 
 
 
5 COMPLEX SYSTEMS, BUSINESS AND SOCIETY 
By Stefano Battiston 

The  environment  of  business  and  government  is  obviously  complex.  But  understanding 
their  environment  is  not  the  only  challenge  of  decision  makers:  they  have  to  take 
decisions  to  deal  with  it  and  eventually  to  modify  it.  Fortunately,  they  did  not  have  to 
wait until the 20th century and the emergence of complex systems science to adapt. In 
fact economics in the 18th century, operational research and management science in the 
mid 20th century, were born as answers to these challenges. 

The strong increase in the complexity of our environment, the fastest rates of change, 
the  necessity  of  delocalised  and  democratic  decisions  are  now  common  wisdom.  The 
limitations of standard approaches are related to the present situation: a strong increase 
in  the  complexity  of  our  environment,  a  faster  rate  of  change,  the  necessity  of 
delocalised and democratic decisions. 

•  Standard approaches suppose full rationality and centralised decisions. 

•  They apply to independent or linearly dependant entities. 

•  The environment is static or supposed so. 

The present situation clearly calls for a Complex Systems approach. 

5.1 Econophysics and Finance as a success story 

Finance  became  attractive  to  physicists  because  of  the  availability  of  large  sets  of 
financial data, which could remind them of the situation in physics where data are not a 
limiting  factor.  Financial  time  series  were  discussed  and  analysed  by  Mandelbrot  et  al. 
(1997),  Mantegna  and  Stanley  (1999),  Bouchaud  and  Potters  (2003)  and  the  Santa  Fe 
"school",  Farmer  (1999),  Packard,  etc.  (which  does  not  imply  that  economists  did  not 
also  react).  Any  serious  processing  of  these  data  yields  results  in  contradiction  with 
standard  economics:  e.g.  fat  tails  in  the  distribution  of  returns  imply  non  Gaussian 
statistics. 

A  number  of  physicists  went  into  real  finance:  banks,  brokerage  and  investment 
firms,  and  some  even  incorporate,  creating  successful  start-up:  Prediction  Company  in 
the  US,  Capital  Fund  Management  in  Europe,  etc.  Their  successes  based  on  techniques 
and concepts from complex system science concerned for instance portfolio management 
and foreign exchange markets. 

These  accomplishments  were  soon  recognised  by  the  academic  community  and  by 
business,  because  they  were  fast  and  directly  measurable  as  financial  successes! 
Unfortunately  the  success  of  a  long  term  policy  in  environment  for  instance  is  not  so 
easily estimated. 

Econophysics also brought new problems to the attention of academics, e.g. bubbles 

in financial markets, and new models, e.g. the minority game. 

5.2 Present challenges 

We  shall  now  discuss,  as  examples,  three  domains  in  which  CS  offers  significant 
contribution to economic and societal challenges: 

• 

• 

supply networks; 

credit and risk management; 

  44

 
 
 
 
 
 
 
 
 
 
 
 
 
• 

collective evaluation and trust-based networks. 

The last part of this section will concern the barriers to the adoption of complex systems 
methods in the business and policy world. 

5.3 Supply Networks Management 

A  manufacturing  system  can  be  viewed  as  a  network  of  buffers  and  machines  through 
which  several  kinds  of  products  flow.  Ideally,  the  system  should  follow  a  stationary 
optimal regime. But, dependent on available information or forecasts, decisions  need to 
be made which product is produced next on which machine. Even when simple heuristics 
are  being  used  for  making  these  decisions,  the  overall  dynamics  of  a  manufacturing 
system  is  complex  and  still  not  well  understood.  Variables  of  main  interest  are 
throughput  (number  of  products  produced  per  unit  time),  WIP  (number  of  products  in 
system), and cycle time (the time products stay in the system). Information and material 
flows  in  production  and  logistics  systems  suffer  from  a  combination  of  the  following 
characteristics:  competition  for  scarce  or  expensive  capacities,  nonlinear  effects  and 
interactions,  congestion,  unpredictable  dynamics,  stochasticity,  heterogeneity,  local 
failures or breakdowns, network structures. 

These features make the above systems highly complex, hard to describe, difficult to 
optimize,  and  almost  impossible  to  control  in  real-time.  This  causes  considerable 
inefficiencies  in  the  use  of  hardware  infrastructures  as  well  as  high  investment  and 
operation  costs,  which  obstruct  the  implementation  of  new  technologies.  At  the  same 
time, an efficient use of new technologies is the key to competitiveness on a world-wide 
scale. The situation in the semiconductor industry is characteristic for the situation today: 
while there is steady progress in hardware technology, operational and logistic problems 
have  been  largely  neglected.  INTEL  has  identified  the  problem  and  invests  into  the 
optimization of their logistics, since an improvement by 3% only would save the company 
1  billion  US$  each  year.  In  order  to  make  optimal  use  of  newly  available  sensor, 
communication, and data processing technologies, one first has to gain an understanding 
of  dynamic  queuing  networks  and  find  ways  to  optimally  control  them.  There  are  no 
suitable classical approaches to tackle this. 

Classical  approaches  to  production  systems  are  based  on  Operational  Research  and 
Queuing  Theory.  These  approaches  have  basically  failed  to  describe  the  non-linear 
interactions  between  their  various  elements  and  the  response  to  variations  in  demand. 
The fact that cycle times are large and non-linearly dependent on the load is one of the 
most difficult aspects in supply chain management; in particular as these systems suffer 
from  inherent  instabilities.  Small  variations  of  production  parameters  can  generate  a 
completely different dynamic behaviour. At certain critical parameter thresholds, one can 
observe  discontinuous  phase  transitions  from  one  dynamic  behaviour  to  another  one, 
including  oscillatory  patterns  and  chaos.  The  phase  space  of  the  system  may  even  be 
fractal,  which  makes  complex  production  systems  particularly  difficult  to  understand,  to 
measure  and  control.  Suitable  modeling  approaches  have  been  formulated  only  very 
recently.  Approximate,  heuristic  optimization  methods  such  as  genetic/evolutionary 
algorithms  are  too  time-consuming  as  well.  Instead,  the  optimization  problems  we  face 
are more likely to be solved by decentralized control approaches in the spirit of collective 
or  swarm  intelligence.  In  principle,  it  is  known  that  suitable  local  interaction  rules  can 
lead  to  coordination  and  optimization  throughout  the  overall  system.  However,  in 
contrast  to systems  close  to  equilibrium,  there  is  no  general  theory  for  the  evolution  of 
stochastic, nonlinear, dynamic systems with network effects. 

An example of a successful application of complex systems methods in this domain is 
the  so  called  ’slower-faster’  effect  discovered  by  Helbing  and  collaborators.  Their 
approach consists in modeling manufacturing processes as driven many-particle systems, 
where the discrete products and transport devices play the role of particles. For instance, 
the  method  was  able  to  increase  the  throughput  of  a  production  chain  in  a  major 

  45

 
 
 
 
 
 
semiconductor  factory  by  up  to  39%.  In  such  a  supply  chain,  silicon  wafers,  somehow 
similarly  to  photographic  film,  require  a  series  of  chemical  processes.  Treatment  times 
can be shortened or prolonged only to a certain extent. The main problem in this system 
is  the  limited  transport  capacity  of  the  handler,  i.e.  the  device  which  has  to  move  the 
wafers  around.  If  several  sets  of  wafers  had  to  be  moved  at  the  same  time,  the 
treatment  times  for  one  of  these  would  probably  exceed  the  critical  time  threshold. 
Therefore,  the  challenge  is  to  find  a  schedule  that  resolves  conflicts.  Interestingly,  the 
problem of achieving coordination among several elements is similar to the coordination 
of  pedestrians  in  the  merging  area  in  front  of  a  door.  The  problem  has  been  solved  by 
the  counterintuitive  policy  of  increasing  the  treatment  times.  In  fact  with  longer 
treatment times, the waiting times between successive runs are significantly decreased, 
resulting  in  higher  throughput.  That  is,  instead  of  stop-and-go  patterns  (waiting  and 
usage periods of the chemical or water basins), a smoother output pattern was reached. 

5.4 Credit networks and Systemic Risk 

Supply networks are subject to occasional production failures. Because supplier-customer 
relations often imply credit relations, production failures can also cause financial failures. 
The  symmetrical  causation,  from  credit  to  production  failures,  also  exists.  Due  to  the 
growing  interdependence  of  supply  and  credit  networks,  both  in  terms  of  sector  and 
geography, a natural question is do we predict and control the onset of failure cascades? 

Quantitative  study  of  risk  is  typically  the  realm  of  financial  mathematics,  but  more 
recently  also  of  physics  (Bouchaud  and  Potters,  2003).  The  purpose  of  investigations  is 
typically answering the question of how to minimize risk of individual firms or institutions, 
by optimizing a portfolio of actions. However, there is usually no concern for the so called 
systemic  risk  (Fecht  and  Gruener,  2005),  the  risk  of  collective  damage  in  an  economic 
system  such  as  for  instance  the  banking  system,  but  also  the  network  of  suppliers  and 
customers  in  a  industry  sector.  One  could  expect  that  addressing  this  kind  of  questions 
with  modern  tools  would  be  of  concern  of  central  banks  since  long  ago.  Surprisingly, 
even the UK central bank has started research on networks of banks only very recently 
(Yang, 2005). 

In  general,  economic  theory  is  not  prepared  to  investigate  avalanches  in  large 
heterogeneous networks. The common view on financial contagion is that connectivity is 
beneficial  because  it  is  a  way  of  distributing  risk.  This  is  proven  formally  in  some 
contexts:  the  optimal  graph  is  found  to  be  the  fully  connected  one  (Allen  and  Carletti, 
2005). 

However, in presence of a drift on the fragility, the opposite can occur. In fact, if each 
unit  redistributes  risk  to  the  others,  on  one  hand  it  delays  its  own  default,  but  on  the 
other hand the risk becomes very homogeneously distributed across units. If the general 
level  of  fragility  increases,  when  eventually  one  unit  defaults,  all  the  others  are  very 
close  to  the  threshold  for  defaulting themselves  and  a  major  collapse  occurs  (Battiston, 
Peters, Helbing and Schweitzer, 2006). 

This  kind  of  dynamics  are  suitable  to  be  investigated  with  the  methods  of  Complex 
Systems,  capitalizing  on  the  experience  gained  in  the  study  on  critical  phenomena  on 
systems  such  as  sand  pile  and  alike.  However,  it  is  important  to  stress  the  fact  that 
economic  systems  have  their  own  specificity  and  that  theories  cannot  be  simply 
transferred  from  sand  pile  to  credit  network.  Brand  new  models  have  to  be  developed. 
Therefore future calls might emphasize that physicists have to team up with specialists of 
the discipline in order to develop models together. 

An example of this desirable teaming up is the collaboration, in the study of systemic 
risk,  of  some  researchers  from  the  complex  network  fields  with  economists  who  have 
strong  influence  at  policy  design  level  in  macro-economy  (Battiston,  Delli  Gatti  et  al., 
2006). 

  46

 
 
 
 
 
5.5 Collective Evaluation and Trust-based Networks 

5.5.1 Overview of emerging technologies 

We witness today a booming of new ways of marketing, trading and sharing information, 
which  are  made  possible  by  a  set  of  related  emerging  technologies.  A  first  revolution 
occurred  during  the  past  century  due  to  the  availability  of  new  techniques  such  as 
telephone, radio and especially TV. The present new wave is carried by the Internet. 

Present  day  economic  actors,  firms  and  customers,  can  in  principle  retrieve  a  lot  of 
information  -  in  fact,  most  often,  too  much  information  to  be  usefully  processed  during 
the window of opportunity when decisions have to be taken. 

Computerised information processing and data mining were developed as an answer 
to  the  information  overflow,  and  the  first  commercial  applications,  such  as  customers' 
management,  were  used  by  firms.  More  recently,  new  applications  were  proposed  to 
facilitate  information  retrieval  and  estimation  of  the  quality  of  products  and  services  to 
potential customers. These techniques are often based on the processing of information 
generated  by  customers  who  already  acquired  the  product  and  tried  it.  They  basically 
implement a reputation dynamics on computer; they also relate to more standard "ants 
algorithms". 

Recommendation systems based on collaborative filtering suggest users items based 
on the similarity of their preferences to other users. For example, on amazon.com a user 
receives the message that "people who bought this book also bought these other books". 
This kind of recommendation systems works quite well for low-involvement items such as 
movies  or  alike.  Many  scientific  teams  are  working  on  the  data  mining  aspect,  but  the 
few works based on CS seem particularly promising (Laureti et al., 2002; Lauretti et al., 
2006).  The  combination  of  collaborative  filtering  with  trust  is  one  the  hot  topics  in 
computer  science  in  the  near  future  (Ziegler  and  Golbeck,  2006),  and  again  the  CS 
approach  is  proving  to  be  quite  successful  (Battiston,  Walter  and  Schweitzer,  2006; 
Walter,  Battiston  and  Schweitzer,  2006).  The  fact  that  information  is  processed  in  a 
centralized  way  raises  scalability  problems.  But  more  importantly,  if  ratings  would 
concern high-involvement services, such as health care for instance, centralization raises 
also  confidentiality  issues.  As  we  will  see  in  the  following,  these  limitations  can  be 
overcome with Trust-Based Networks. 

The important aspect for complex systems science is that these technologies give rise 
to large-scale collective phenomena. While computer science research in this field focus 
either  on  the  aspects  of  technological  compatibility  or  security,  the  theoretical 
understanding  of  the  large-scale  emerging  properties  is  poor.  CS  can  and  should  give 
important contributions. 

5.5.2 Potential Impact 

The emerging technologies around the concept of reputation, trust, collaborative filtering 
and  P2P,  make  possible,  for  the  first  time  in  history,  a  large-scale  real-time  self-
organization of citizens in completely new forms. For instance, these technologies make it 
easier  for  consumers  to  reach  and  share  rating  of  products,  independently  of  the 
producers. But it is also possible,  for instance, that consumers form buying groups that 
negotiate  with  firms  the  delivery  of  products  or  services  with  specific  features.  Market 
diversity,  which  is  today  producer-driven,  could  become  consumer-driven,  a  major 
change  of  perspective.  In  particular,  the  market  share  for  sustainable  products  could 
increase  significantly.  The  field  of  recommendation  systems  and  akin  does  not  reduce 
itself  to  targeted  marketing.  On  the  contrary,  there  is  an  unprecedented  potential  for 
empowering citizens to make more informed choices in their daily life in a vast range of 
domains, from purchases to political support. Some people even see it as a possible way 
of  coping,  not  only  with  information  overload,  but  also  with  stringent  social  dilemmas 

  47

 
 
 
 
 
 
such as those related to sustainable development. In fact, information overload and the 
tendency  towards  information  monopolies  interfere  with  today’s  EU  Information  Society 
commitment to preserve and manage the diversity of preferences and needs of citizens. 

5.5.3 Trust-based Networks 

Trust-Based Networks (TBN) can be defined as information processing systems in which 
interconnected  agents  (citizens,  firms,  organizations)  share  knowledge  in  their  domains 
of  interest.  Each  user  has  a  list  of  buddies  with  which  he  decides  to  share  lists  of 
products,  services,  people,  experts,  etc.,  accompanied  by  his  rating.  Trust  is  built-on 
dynamically,  based  on  the  satisfaction  experienced  following  the  recommendations 
received  from  the  buddies.  Paths  of  high  trust  soon  build  up  in  the  network,  and  each 
user is able to reach and rely on -filtered- information, even if coming from another user 
faraway in the network. This emerging property has some reminiscence to the building of 
optimal  paths  in  ant  algorithms.  Some  recent  works  have  proved  the  overwhelming 
superiority  of  such  trust  based  recommendation  systems  over  those  based  on  the 
frequency  of  the  recommendations  (Battiston,  Walter  and  Schweitzer,  2006).  From  the 
point of view of scalability, TBN is naturally distributed and does not require centralized 
information. 

There is no current established approach for investigating TBN. Some projects under 
IST deal with P2P networks, but here the CS approach is mandatory. Indeed, by means 
of  a  complex  system  approach,  recent  works  have  shown  analytically  that  the 
performance  of  a  TBN  is  robust  within  a  wide  range  of  crucial  parameters  such  as  link 
density  among  peers,  heterogeneity  of  user  preferences  and  sparsity  of  knowledge 
among users (Battiston, Walter and Schweitzer, 2006). 

However,  this  is  just  the  beginning  of  a  quite  dense  research  program.  The  main 

research objectives can be grouped as follows: 

•  Foundation from the perspective of Information and Network Theory: 

– small world properties to reach many domains of knowledge; 
– robustness against abuse and side-effects of herding and panic (e.g. decline of 

     trust in health authorities due to food safety crisis around mad cow disease). 

•  Requirements  of  a  distributed  infrastructure  supporting  the  TBN:  performances, 

robustness, search engines; 

•  Design interaction mechanisms in order to: 
  – encourage sharing and honest reporting; 
  – discourage abuse and free-riding. 

• 

Investigation of the social benefit of: 

  – allowing users to assign different levels of privacy to their information (this has   
     important applications in health-care and fields where confidentiality and  
     management of sensitive data is a safety issue); 
  - allowing the formation of coalitions, thus providing negotiation power on  
     product/service features. 

A  TBN  can  be  regarded  as  an  IT  support  tool  for  decision  making  shaped  around  the 
natural behaviour of individuals in society. Today’s search engines allow the user to find 
a  range  of  information/products/services  from  a  centralized  source,  corresponding  to  a 
set  of  keywords.  Through  a  TBN  instead,  the  citizen  can  search  relevant  items  from 
specialized  sources  and  evaluate  the  trustworthiness  of  the  items  with  respects  to  her 
preferences. 

In  line  with  EU  policy  objectives  (i2010),  TBN  empower  citizens  to  make  better-
informed decisions on products and services, thus contributing to a competition based on 
quality.  Not  only  consumers  are  concerned;  also  firms  would  be  able  to  make  more 

  48

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
  
 
 
informed choices on suppliers and partners. TBN can potentially increase the diffusion of 
knowledge as well as the transparency of products and services, with significant benefit 
for  EU  cultural  development  and  economic  competitiveness.  It  is  hard  to  overestimate 
the benefit from such a system in terms of quality of life and satisfaction of citizens. TBN 
could be the future way in which interactions take place within sustainable societies and 
the  EU  has  the  chance  to  become  the  world  wide  leader  and  standard-setter  in  this 
initiative. 

5.6 Penetration of CS science in the business world 

Despite  several  success  stories  (some  of  which  reported  above),  the  penetration  of  CS 
science  in  the  business  world  is  still  limited.  Nonetheless,  curiously  enough,  complex 
systems concepts are recognised at the corporate level. 

An  interesting  evidence  of  this  fact  can  be  found  in  the  report  from  annual  IBM’s 
Global  Innovation  Outlook  (GIO),  a  forum  organized  by  IBM,  attended  by  around  250 
leaders  from  business,  academia,  the  public  sector,  NGOs  and  other  influential 
constituents  of  the  world  community.  The  GIO  takes  a  "deep  look  at  some  of  the  most 
pressing  issues  facing  the  world  and  works  toward  providing  solutions  to  those  needs". 
The report, which is worth reading, shows that the participants express themselves using 
concepts from  CS  science.  Some  are  now  relatively  old,  as self-organization,  others  are 
not  originally  from  CS  but  have  recently  become  prominent  topics  in  CS,  as  social 
networks  and  supply  networks.  Finally,  others  are  right  now  the  subject  of  several  on-
going  projects  in  CS,  especially  in  the  domain  of  ICT,  as  trust,  reputation,  collaborative 
environments.  Very  innovative  visions  have  emerged  from  this  forum  of  leaders,  in 
particular regarding the future of enterprises and production networks. 

But  when  it  comes  to  applying  complex  systems  solutions,  recruiting  personnel  or 
consulting,  the  traditional  perspective  is  still  predominant.  The  issue  is  largely  in  the 
differences in language and culture between CS scientists and businessmen. Application 
of CS to business requires close collaboration  and trust between the consultant and the 
customer.  While  traditional  consultants  and  managers  belong  to  the  same  culture 
(typically they both did an MBA in some business school), CS scientists have completely 
different  language  and  mind  setting.  Consultant  and  managers  are  generally  taught 
traditional approaches and are not competent in CS. It would be hard for consultants to 
educate  themselves  in  CS,  and even  if  they would  do  so,  it  would  remain  more  difficult 
for them to sell CS solutions, compared to selling traditional ones. As a result, as long as 
they  are  able  to  make  the  customer  believe  that  they  are  providing  the  best  solution 
available,  they  do  not  have  incentives  in  proposing  CS-based  solutions.  It  is  hard  to 
expect  that  business  schools  will  teach  managers  to  hire  physicists  to  solve  problems! 
The  weight  of  culture  and  traditions  might  be  lighter  in  Eastern  Europe  and  indeed  the 
success of start-up companies selling CS methods to business is encouraging. 

  49

 
 
 
 
6 LIST OF CONTRIBUTORS AND EXPERTS 

6.1 Editor 
Gérard Weisbuch: École Normale Supérieure, Fr. 

6.2 Contributors to specific parts of the document 

Stefano  Battiston,  Business,  ETH  Zurich.  (Section  5  reflects  the  outcome  of  Budapest 
meeting on "Potentials of Complexity Science for Business, Governments and the Media", 
organised by Dirk Helbing (8/3-5/2006)) 
Guido Caldarelli, Physics, Roma, La Sapienza. 
Mauro Gallegati, Economics, Univ. Politecnica delle Marche, It. 
Francois Kepes, Biology, Genopole Evry, Fr. 
Rémi Monasson, Physics, ENS, Fr. 
Jean-Pierre Nadal, Physics, ENS, Fr. 
Norman Packard, European center for Living Technology. 
Peter Richmond, Physics, Trinity College, Dublin. 
Massimo Salzano, Economics, U. Salerno, It. 
Alessandro Vespignani, Physicist, Notre-Dame U., USA. 

6.3 Participants to think tank meetings 

6.3.1 Jerusalem. 26 May 2006 

Leader Sorin Solomon, Physics, HUJI (Hebrew University of Jerusalem).  
Richard Laster: Environmental Law, HUJI.  
Scott Kirkpatrick: School of Engineering and CS, HUJI.  
Gérard Weisbuch: Physics, École Normale Supérieure.  
George Szpiro: news correspondent, Neue Zürcher Zeitung.  
Irun Cohen: Department of Immunology, Weizmann Institute  
Yancu Goldenberg: Business School, HUJI.  
Moshe Idel: Jewish Thought, HUJI. 
Esti Adi-Japha, School of Education, BIU (Bar Ilan University).  
Claudia V. Goldman, Computer Science, BIU. 

6.3.2 Paris, 6 and 8 June 2006 
Leader Sorin Solomon, Physics, HUJI.  
Annick Vignes, Economics, Paris 2.  
Gérard Ballot, Economics, Paris 2.  
Zahia Guessoum, Computer Science, Paris 6.  
Rémi Monasson, Physics, ENS.  
Jean-Pierre Nadal, Physics, ENS.  
Vincent Hakim, Physics, ENS. 
Denise Pumain, Geography, Paris. 

  50

 
 
 
 
 
 
 
 
 
 
6.3.3 Torino, Villa Gualino, 25-26 July 2006 
Leader Gérard Weisbuch. 
Mauro Gallegati, Economics, Univ. politecnica delle Marche, It. 
Michael Ghil, Geophysics and Applied Maths, ENS. 
Francois Kepes, Biology, Genopole Evry, FR. 
Markus Kirkilionis, Applied Maths, UK. 
Andrzej Nowak, Psychology and Sociology, Warsaw University. 
Norman Packard, European center for Living Technology. 
Felix Reed Tsochas, Said Business School, Oxford. 
Peter Richmond, Physics, Trinity College, Dublin. 
Massimo Salzano, Economics, U. Salerno, It. 
Sorin Solomon, Physics, HUJI. 
Pietro Terna, Economist, Torino University. 
Alessandro Vespignani, physicist, Notre-Dame U., USA. 

6.4 Acknowledgment 

The present document is a deliverable of GIACS (General Integration of the Applications 
of  Complexity  in  Science)  Coordination  Action  of  the  Complexity  Pathfinder  initiative  in 
NEST (New and Emerging Science and Technology). 

Apart from the above mentioned participants, the editors thank Jean Vannimenus and 

Diana Mangalagiu for checking the manuscript. 

  51

 
 
 
 
7 REFERENCES 

Section 3.2 

Barabási, A.-L. and Albert, R. (1999). Emergence of scaling in random networks. Science, 
286: 509-512. 

Becsksei,  A.  and  Serrano,  L.  (2000).  Engineering  stability  in  gene  networks  by 
autoregulation. Nature, 405: 590-593. 

Bernot, G., Comet, JP., Richard, A. and Guespin, J. (2004). Application of formal methods 
to biological regulatory networks: extending Thomas’ asynchronous logical approach with 
temporal logic. J Theor Biol, 229: 339-347. 

Dekel, E. and Alon, U. (2005). Optimality and evolutionary tuning of the expression level 
of a protein. Nature, 436: 588-592. 

Elowitz,  MB  and  Leibler,  S.  (2000).  A  synthetic  oscillatory  network  of  transcriptional 
regulators. Nature, 403: 335-338. 

François, P. and Hakim, V. (2004). Design of genetic networks with specified functions by 
evolution in silico. Proc Natl Acad Sci USA, 101: 580-585. 

Friedman, N., Linial,  M., Nachman, I. and Pe’er, D. (2000). Using Bayesian networks to 
analyze expression data. J Comput Biol, 7: 601-620. 

Guelzim,  N.,  Bottani,  S.,  Bourgine,  P.  and  Képès,  F.  (2002).  Topological  and  causal 
structure of the yeast genetic network. Nature Genetics, 31: 60-63. 

Guespin-Michel,  J.,  Bernot,  G.,  Comet,  JP.  et  al.  (2004).  Epigenesis  and  dynamic 
similarity  in  two  regulatory  networks  in  Pseudomonas  aeruginosa.  Acta  Biotheor,  52: 
379-390. 

Jeong, H., Tombor, B., Albert, R., Oltvai, Z.N. and Barabási, A.-L. (2000). The large-scale 
organization of metabolic networks. Nature, 407: 651-654. 

Milo,  R.,  Itzkovitz,  S.,  Kashtan,  N.,  Levitt,  R.,  Shen-Orr,  S.,  Ayzenshtat,  I.,  Sheffer,  M. 
and Alon, U. (2004). Science, 303: 1538-1542. 

Milo,  R.,  Shen-Orr,  S.S.,  Itzkovitz,  S.,  Kashtan,  N.  and  Alon,  U.  (2002).  Science,  298: 
824-827. 

Nutsch, T., Oesterhelt,  D., Gilles, E.D. and Marwan, W. (2005). A quantitative model of 
the  switch  cycle  of  an  archeal  flagellar  motor  and  its  sensory  control.  Biophys  J,  89: 
2307-2323. 

Ravasz,  E.,  Somera,  A.L.,  Mongru,  D.A.,  Oltvai,  Z.N.  and  Barabási,  A.-L.  (2002). 
Hierarchical organization of modularity in metabolic networks. Science, 297: 1551-1555. 

Shen-Orr, S., Milo, R., Mangan, S. and Alon, U. (2002). Nat Genet, 31: 64-68. 

Shimizu, T.S., Aksenov, S.V. and Bray, D. (2003). A spatially extended stochastic model 
of the bacterial chemotaxis signalling pathway. J Mol Biol, 329: 291-309. 
Watts,  D.J.  and  Strogatz,  S.H.  (1998).  Collective  dynamics  of  small-world  networks. 
Nature, 393: 440-442. 

  52

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Section 4.2 

Adamic,  L.A.  and  Huberman,  B.A.  (2000).  Power-Law  Distribution  of  the  World  Wide 
Web. Science, 287: 2115. 

Albert, R. and Barabási, A.-L. (2001). Statistical Mechanics of Complex Networks, Review 
of Modern Physics, 74: 47-97. 

Albert,  R.,  Jeong,  H.  and  Barabási,  A-L.  (2000).  Error  and  attack  tolerance  of  Complex 
Networks.  Nature,  406:  378-382.  (Errata  2001).  Error  and  attack  tolerance  of  Complex 
Networks. Nature, 409: 542. 

Barrat,  A.  and  Weigt,  M.  (2000).  On  the  properties  of  small-world  Networks.  European 
Physical Journal B, 13: 547-560. 

Battiston,  S.,  Bonabeau,  E.  and  Weisbuch,  G.  (2003).  Decision  making  dynamics  in 
corporate boards. Physica A, 322: 567-582. 

Bollobás, B. (1985). Random Graphs. Academic Press, London. 

Bonanno, G., Caldarelli, G., Lillo, F. and Mantenga, R.N. (2003). Topology of correlation-
based minimal spanning trees in real and model market. Physical Review E, 68: 046130. 

Brin, S., Page, L., Motwami, R. and Winograd, T. (1998). The PageRank citation ranking: 
bringing  order  to  the  web.  Technical  Report.  Computer  Science  Department,  Stanford 
University. Available at http://www-db.stanford.edu/ back-rub/google.html. 

Caldarelli, G. and Catanzaro, M. (2004). The corporate Boards Networks. Physica A, 338: 
98-106. 

Caldarelli, G., Marchetti, R. and Pietronero, L. (2000). The Fractal Properties of Internet. 
Europhysics Letters, 52: 386-391. 

Capocci,  A.,  Servedio,  V.D.P.,  Colaiori,  F.,  Buriol,  L.S.,  Donato,  D.,  Leopardi,  S.  and 
Caldarelli, G. (2006). Preferential attachment in the growth of social networks: the case 
of Wikipedia. Physical Review E, 74: 036116. 

Erdös,  P.  and  Rényi,  A.  (1960).  On  the  evolution  of  random  graphs,  Publications  of  the 
Mathematical Institute of the Hungarian Academy of Sciences, 5: 17-61. 

Faloutsos, M. Faloutsos, P. and Faloutsos, C. (1999). On Power-law Relationships of the 
Internet  Topology,  Proc.  ACM  SIGCOMM,  Computer  Communication  Review,  29:  251-
262. 

Garlaschelli, D., Battiston, S., Castri, M., Servedio, V.D.P. and Caldarelli, G. (2005). The 
scale free topology of market investments. Physica A, 350: 491-499. 

Gavin,  A.C.  et  al.  (2002).  Functional  organization  of  the  yeast  proteome  by  systematic 
analysis of protein complexes. Nature, 415: 141-147. 

Pastor-Satorras,  R.  and  Vespignani,  A.  (2004).  Evolution  and  Structure  of  Internet:  A 
Statistical Physics Approach. Cambridge University Press. 

  53

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Section 5 

Allen, F. and Carletti, E. (October 2005). Credit risk transfer and contagion. CFS Working 
Paper 
at 
for 
http://ideas.repec.org/p/cfs/cfswop/wp200525.html. 

2005/25. 

Available 

Financial 

Studies. 

Center 

Series 

Battiston,  S.,  Delli  Gatti,  D.,  Gallegati,  M.,  Greenwald,  B.  and  Stiglitz,  J.E.  (2006,  in 
press).  Credit  chains  and  bankruptcies  avalanches  in  supply  networks.  Journal  of 
Economic Dynamics and Control. 

Battiston,  S.,  Peters,  K.,  Helbing,  D.  and  Schweitzer,  F.  (2006,  in  preparation).  
Avalanches and robustness in evolving networks. 

Battiston, S., Walter, F.E. and Schweitzer, F. (2006). Impact of trust on the performance 
of a recommendation system in a social network. Proceedings AAMAS 2006. 

Bouchaud, J-P. and Potters, M. (2003).  Theory of Financial Risk and Derivative Pricing. 
Cambridge Univ. Press, second edition. ISBN 0 521 81916 4. 

Doyne  Farmer,  J.  (1999).  Physicists  attempt  to  scale  the  ivory  towers  of  finance. 
Computing in Science and Engineering, 1:26–39. 

i2010  -  a  European  information  society  for  growth  and  employment.  Available  at 
http://europa.eu.int. 

Fecht, F. and Gruener, H. P. (September 2005).  Financial integration and systemic risk. 
at 
C.E.P.R. 
http://ideas.repec.org/p/cpr/ceprdp/5253.htm. 

September 

Discussion 

Available 

Papers 

2005. 

5253, 

Laureti, P., Moret, L., Zhang, Y.C. and Yu, Y.-K. (2006). Information filtering via iterative 
refinement. Europhysics Letters, 75: 1006. 

Laureti,  P.,  Slanina,  F.,  Yu,  Y.K.  and  Zhang,  Y.-C.  (2002).  Buyer  feedback  as  a  filtering 
mechanism for reputable sellers. Physica A, 316:413. 

Mandelbrot,  B.,  Fisher,  A.  and  Calvet,  L.  (1997).  A  multifractal  model  of  asset  returns. 
Cowles Foundation for Research and Economics. Manuscript. 

Mantegna, R.N. and Stanley, H.E.  (1999). Introduction to econophysics: correlations and 
complexity in finance. Cambridge University Press, Cambridge. 

Walter,  F.E.,  Battiston,  S.  and  Schweitzer,  F.  (2006).  A  model  of  trust-based 
recommendation system in a social network. Submitted to AAMAS 2007. 

Yang,  J.  (2005).  Network  theory  and  financial  instability.  Representative  of  Bank  of 
England, 
at 
wehia 
speech 
http://www.essex.ac.uk/wehia05/Program/Tuesday.htm. 

available 

invited 

Slides 

2005. 

at 

Ziegler,  C.-N.  and  Golbeck,  J.  (2006,  to  appear).  Investigating  correlations  of  trust  and 
interest similarity. Decision Support System. 

  54

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
B5_tackling  13/07/07  13:02  Page 5

European Commission

Tackling Complexity in Science - General Integration of the Application of Complexity in Science

Luxembourg: Office for Official Publications of the European Communities

2007 — 54 pp. — 17,6 x 25 cm

ISBN 978-92-79-05504-1

Price (excluding VAT) in Luxembourg: 15 EUR

B5_tackling  13/07/07  13:02  Page 6