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)*.

Graph Theory in Practice: Part II

Graph Theory in Practice: Part I

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 (

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.

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.

Ricard Solé's Homepage

Nexus: Small Worlds and the Groundbreaking Science of Networks, Mark Buchanan (New York: Norton, 2002)

Handbook of Graphs and Networks: From the Genome to the Internet, Stefan Bornholdt and Heinz Georg Schuster (Eds.)

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