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 that characterizes the degree of linkage. These nets are homogeneous: a randomly chosen node will have a number of links of order . Examples of these nets (within the theory) are given by Kauffman random Boolean networks (S. Kauffman, J. Theor. Biol. 22 (1969) 437) or May's random ecological networks (R. M. May, Nature 238 (1972) 413). Some extreme types of network models assume a fully connected system, as in some types of neural networks (J. Hopfield, Proc. Natl. Acad. Sci. USA 79 (1982) 2554) and randomness is introduced at the level of synaptic strengths.

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

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.

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.

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


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)


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


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