Classical models of networks share the assumption that the connections
between units (neurons, species, genes or computers) occur at random.
More specifically, the graphs resulting from assuming random wiring
are of Erdos-Renyi type (B. Bollobas, "Random Graphs", Academic Press,
1985): each node can get connected to any other
arbitrary node with some probability p. If we look at the so called
degree distribution P(k) that gives the probability that a given node
is linked to k other nodes, it is a Poissonian one: there is a
characteristic, average connectivity
Random networks of Erdos-Renyi type including nonlinear dynamics
display some surprising properties derived from the presence of phase
transitions. One of them is the existence of well-defined boundaries
separating order from disorder (S. Kauffman, Origins of Order, Oxford U. Press, 1993; see also
,
R. V. Solé and B. C. Goodwin, SIGNS OF LIFE: how complexity pervades biology
Basic Books, New York 2001).
At these boundaries, a transition from
stability to instability and/or from order to disorder occurs and the system
displays very interesting properties, some of them qualitatively
similar to those displayed by their real counterparts. The
regularities observed at these critical points have been suggested to
explain different features exhibited by natural complex systems. An
example would be the observation that there is a vast difference
between the potential number of combinations of possible gene
expression states and those that actually exist in any organism. Given
just two inputs per gene (two genes regulating its expression) a
system of, say, 25000 genes has a hyperastronomic number of different
possible states. Yet, if cell-type number is used as as indicator of
gene expression states, only a small number 150-300 states are
realized. It has been suggested that a sparse graph of connections
would naturally display a small number of attractors (cell states)
that would be highly stable against perturbations (as seems to occur
in normal cell states).
Recent studies have revealed a surprising result: the interaction
networks displayed by most complex systems are highly heterogeneous
(S. H. Strogatz.
Exploring complex networks , Nature 410 (2001) 268-276).
An example of these type of network is shown in the figure below: the proteome map (b) of yeast (a).
Here the nodes are proteins and the links indicate physical interaction between proteins.
The degree distributions are skewed (i. e. show long tails) so that
most nodes are connected to a few ones and a small number are linked to
many other units. These distributions are thus very different from
the Poissonian shape expected from a simple (Erdos-Renyi) random
graph. Different types of networks are observed: from exponential to
scale-free (SF) (L. Amaral et al. Proc. Natl. Acad. Sci. USA, 97
(2000) 11149-11152) indicating different basic types of
organization. Additionally, complex nets also display the so-called small-world (SW) effect:
they are highly clustered (i.e. each node has a well-defined
neighborhood of ``close'' nodes) but the minimum distance between any
two randomly chosen nodes in the graph is short, a characteristic
feature of random graphs ( D. J. Watts and S. H. Strogatz. Nature 393
(1998) 440-442).
My research in this area explores the evolutionary origins of complex
biological networks. I am interested in understanding the evolutionary
pathways that lead to the observed topological properties and how they
relate to optimization, adaptation and robustness. Although many tools
used in our research are inspired in physics approaches to complexity,
one particularly relevant problem is to define possible scenarios of network evolution
that make sense in the biological context, where some features are
entirely foreign to physics (J. Hopfield, J. Theor. Biol. 71 (1994)
53-60). Biocomplexity includes a large amount of history, which can be
understood in terms of a large amount of broken
symmetry (see P. Anderson, Science 177 (1972) 393) and
also in terms of the evolutionary value of predicting the
future in a given environment that defines a particular
context. Besides, although natural selection has been capable in many
cases of searching in phenotype space for optimal structures (see for
example the work on allometric scaling in transport nets: J. Brown and J. West (eds.),
"Scaling in Biology", Oxford U. Press, NY 2000), evolution also
incorporates large amounts of tinkering (F. Jacob, Science 196 (1977)
1161-1166) and thus the final states might actually involve suboptimal
solutions.
How are these networks generated and what are the consequences of
their topologies? One of the simplest models involves preferential attachment
(A. L. Barabasi and R. Albert, Science 286 (1999) 509-512 ). In these
type of models, scale-free graphs are easily obtained provided that
the links to new nodes are made preferentially from
nodes that already have many links. A direct consequence is that
vertices with many connections are those that have been incorporated early.
This is a simple scenario that already incorporates history in its
simplest form, and some authors have suggested that this might be one
important component in the early evolution of metabolic networks
(A. Wagner and D. A. Fell, Proc. Roy. Soc. London B} 268 (2001)
1803-1810). But other scenarios have been suggested, including the
duplication of previous structures together with later re-wiring. This
would be the case, for example, of genome-proteome evolution, where
genome growth occurs through gene duplication plus further changes in
the connectivity matrix
(see our paper:
A Model of Large-Scale Proteome Evolution, Adv. Complex Syst. 5(1), 43-54 (2002).
A more detailed analysis is presented in our recent study:
Evolving protein interaction networks from gene duplication, J. Theor. Biol. 222, 199-210 (2003)).
Most real, complex networks strongly depart
from the Erdos-Renyi scenario, but they differ in different ways. The
research program under exploration by the Complex Systems Group (in
collaboration with researchers from very different areas, including
theorists and experimentalists) involves the study of different types
of biosystems. The common link here is to understand how evolution has
shaped these networks and the relative importance of dynamical
constraints, selection/optimization and emergent properties. The
theoretical approximations involve data mining as well as mathematical and
computer modeling.
Artificial systems, such as electronic circuits,
will be excellent reference models in order to test some
possible optimization-design alternatives. By finding the common patterns and the fundamental
differences between the following systems we hope to gain some insight into the
origins of biological complexity. In this context, we can explore Jacques
Monod's conjecture (J. Monod, Chance and Necessity, Editions du Seuil, 1970,
left picture) concerning the evolution of biological versus technologic objects.
REVIEW PAPERS ON SMALL WORLDS from American Scientist, by Brian Hayes:
Graph Theory in Practice: Part II
Graph Theory in Practice: Part I
SOCIAL SMALL WORLDS en la Vanguardia, by Ricard Solé:
Los seis apretones de manos y el potencial de la comunicación social
Both the small world phenomenon and the presence of highly
heterogeneous degree distributions have been suggested to have
adaptive meanings. The consequences of the SW and SF patterns can be
of great importance in recognizing evolutionary paths, the origins of
homeostatic stability and the sensibility to perturbations in biological
networks. Watts and Strogatz discuss some of these ideas in their
seminal work, suggesting that a SW architecture would play a
relevant role in enhancing synchronization, for example, in the visual cortex.
For SF nets, several authors suggest that it might play a relevant role in allowing to react
rapidly to perturbations thus displaying a very high homeostasis. SF
networks are in fact highly stable under random removal of nodes (here
the average distance between nodes is used as a fitness measure) thus
providing an extraordinary resilience against failure of individual
units, but also highly fragile under intentional attack directed to
highly-connected nodes ( R. A. Albert, H. Jeong, and
A.-L. Barabasi. Nature, 406 (2000) 378-382). The discovery of this
dual character of the robustness-fragility compromise in complex
systems opens a completely new perspective for complexity theory.
SMALL WORLDS in TECHNOLOGY GRAPHS:
Topology of Technology Graphs:
Small World Patterns in Electronic Circuits, Physical Review E 64 (2001) 46119
Featured in NATURE science update: "Circuits are small worlds" , by Phillip Ball
Scale-Free Networks from Optimal Design, S. Valverde and R. V. Solé, Europhysics Letters 60, 512-517 (2002))
Hierarchical small worlds in software architecture,
S. Valverde and R. V. Solé, Submitted to IEEE Software Engineering
Electronic circuits constitute an example of man-made artifacts that have
evolved towards non-random configurations in which minimization of both average path
length and physical distance are present.
Because of their particular design, standard electronic devices are highly
error prone: a single failure in one component typically leads to system
failure. This is not the case of biological systems, in which networks displaying
highly heterogeneous degree distributions with long tails have been shown to be
particularly resilient, perhaps due to functional degeneracy. Of course the difference comes largely form
the dynamical pattern of interactions among units. Redundancy and
modularity can help to overcome failure of a single unit by finding appropriate
pathways able to substitute the damaged unit. Is there any analogous scenario within
the context of technological nets?
How reliable systems can be built from unreliable components has been a very
important topic since Von Neumann's and McCulloch pioneering work.
Using formal approaches borrowed from automata theory and statistical
mechanics, these authors concluded that some amount of redundancy is required
in order to satisfy a number of lower bounds of system functioning. One
interesting framework in which our results might help to provide new ways of generating
reliable circuits is the emerging area of adaptive and evolutionary
hardware. A new generation of electronic devices is based on the possibility of
re-configuration of the circuits wiring.
Self-reconfiguration is needed to endow devices with the flexibility of
in-situ challenges, adaptation to unforeseen conditions and with
enhanced fault-tolerance. This is the case, for example, of planetary
space missions.
Review paper on evolution of complex networks:
Selection, Tinkering, and Emergence in Complex Networks, Complexity vol. 8(1), 20-33 (2003)
A general discussion about the evolution of complex networks and the relevance of different mechanisms
from selective forces to tinkering, is presented:
Ricard Solé's Homepage
POPULAR SCIENCE BOOKS ON COMPLEX NETWORKS:
LINKED: The New Science of Networks, A. L. Barabàsi
(Massachusetts: Persus Publishing, 2002)
Nexus: Small Worlds and the Groundbreaking Science of Networks, Mark Buchanan (New York: Norton, 2002)
TECHNICAL BOOKS ON COMPLEX NETWORKS:
Evolution of Networks: From Biological Nets to the Internet and WWW
S. N. Dorogovtsev and J. F. F. Mendes
(New York: Oxford University Press, 2003)
Handbook of Graphs and Networks: From the Genome to the Internet, Stefan Bornholdt and Heinz Georg Schuster (Eds.)
LINKS TO COMPLEX NETWORKS RESEARCH GROUPS:
Network dynamics at the Santa Fe Institute
Self-organized networks at Notre
Dame
Small World and
evolving networks, University of Porto
Statistical physics of complex networks: Luis Amaral Lab
Networks and graph theory: Mark Newman's homepage
Complex Networks: Sidney Redner's Lab
Ecological networks at Tiburon Center
Networks and
evolution at Leipzig: Stefan Bornholdt's Group
Complex networks
and cognitive systems,Ecole Normale Supérieure
Gene and protein Networks: Wagner's
Lab
Graph theory, Neutral and Catalytic networks: Peter Stadler's Lab
Networks and Chaos: Kaneko's Lab
Information traffic and
the Web: Bernardo Huberman's Lab
Selforganization and Complex Nets: Guido Caldarelli at Rome
Signal transduction networks, Weizmann Institute: Uri Alon Lab
Statistical Physics of Networks: Serguei Maslov's page
Traffic in complex networks: Bosiljka Tadic homepage
Selforganization in road networks: Frank Schweitzer
Mapping Internet: ATlas of Cyberspace