Evolutionary tinkering: towards a bio-inspired network technology
Information dynamics on complex networks is becoming a major area of research
and technological applications. How information flows through these webs
(such as the Internet, mobile ad-hoc networks, or peer-to-peer networks) and how
efficient it is under different condiftions is an important problem with far-reaching
implications. In this context, biological networks provide a powerful inspiration when dealing
with issues such as the importance of robustness in information processing.
The integrated project
DELIS (Dynamically Evolving Large-scale Information Systems) ,
will explore the development of self-regulating
and self-repairing mechanisms that, on the one hand, are decentralized, scalable,
and adapt to changes in their environments. Such decentralized mechanisms have
to lead to a globally acceptable behavior, avoiding undesirable or unstable situations.
Our Lab is a main player within subproject 5,
Biology-Inspired Techniques for Organic IT.
Within DELIS, our Lab is exploring the structure of software networks at the
large and small (motif) scale, the robustness exhibited by evolved designs
using tinkered-based evolutionary rules, the structure of model networks evolved by using
local and global efficiency as fitness functions, and in general the
interplay between biologically-inspired and engineered designs.
One of our goals is to understand the origins of network complexity at different
scales in information networks. Different mechanisms of network evolution should give
in principle different patterns of network organization. But, as emphasized in DELIS,
the presence of multiple constraints actually reduces the number of degrees
of freedom effcetively available for a given evolving system made by many components.
As a consequence, similar (non-optimal) global structures might result from
common principles of network growth.
Recent research has frequently pointed out the analogies between biological
processes or organisms and large-scale information systems. Indeed, the term
"self-managing information systems" is not a bad definition of "life" itself.
In much of our engineering work we try to build technological systems with
lifelike properties. For example, their functionality should be robust against
partial damage to the system; we also want the system to be adaptive in the
face of environmental challenges to its functioning, self-organizing (able to
build itself and grow), and self-healing (able to repair large-scale damage).
Finally, it is desirable that systems should be scalable: they should
continue to function well, even when deployed on a worldwide scale. Society as
a whole benefits enormously from systems that manage themselves. Hence it is
important to develop the art of building self-managing information systems
to the point at which it becomes engineering.
SP5 is based on the hypothesis that important services and functions in human-built
information systems such as monitoring, routing, congestion control, discovery and searching
can be usefully seen as the emergent behaviour of a Complex Adaptive System (CAS)
and that knowledge from theoretical and experimental biology can provide useful
insight for the design, optimization and management of such services and functionality.
Application of biology-inspired metaphors to confront the challenges of dynamic evolving
networks and large-scale information systems will represent a radical shift from traditional
algorithmic techniques to that of obtaining the desired system properties as a result of
emergent behaviour that often involves evolution, adaptation, or learning. The challenge
is to develop the necessary understanding and techniques for achieving adaptation,
self-organization, self-regulation, self-management and robustness in large-scale
information systems by exploiting evolutionary processes, without explicit programming.
The resulting methodology is sometimes referred to as organic Information Technology
and offers a viable path for system design, deployment and management in very
large-scale dynamic environments.
The work to be conducted within this subproject will exploit existing biology-inspired
techniques (including swarm intelligence, artificial immune networks, evolutionary
computing) and will draw on different areas of biology that have not been previously
used as a source of engineering concepts (e.g. specific aspects of evo-lutionary
theory that have yet to be exploited by cevolutionary computing, the role
of developmental con-straints in evolution, ecology, biological and genetic systems
of damage detection and self-repair).
DELIS Research Projects at the Complex Systems Lab
Evolution of technology graphs: electronic circuits and software
Recent theoretical studies and extensive data analyses have revealed
a common feature displayed by biological, social and technological
networks: the presence of small world patterns and heterogenous, hierarchical
patterns of organization. Since technological structures are a source of inspiration
for evolutionary biologists (although the paths leading to similar architectures are
different) we are looking for emergent structures in technological design. Common principles
of organization might actually indicate universal organizing principles or, perhaps more likely,
similar types of constraints. We have analysed
this problem by using several graphs obtained from one of the most
common technological systems: electronic circuits. We have shown that
both analogic and digital circuits exhibit SW behavior (see our paper
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).
We conjecture that the SW pattern arises from the compact design in which
many elements share a small, close physical neighborhood plus the fact that
the system must define a single connected component (which requires shortcuts
connecting different integrated clusters). An interesting result is that the observed degree distributions display
the scaling behavior exhibited by other complex networks. Here single failure
of a given unit implies system failure. However, by exploiting these basic architecture
and adding some degree of redundancy and flexibility (as it is the case of autoconfigurable
circuits) we conjecture that reliable, highly robust circuits would be obtained.
We are also exploring the possible relevance of these results within the
context of energy transfer in ecological systems, where some surprising
analogies have been reported. Technology graphs offer a
very powerful quantitative framework in order to explore the roles played by
selection, history and tinkering in evolution. In a related context, we have
recently discovered that software graphs also display scale-free topology,
in spite that they are known to be "optimal" structures where optimal desing
plays a well defined role during software development. The outcome of this
process, however, is a scale-free, small world structure, which seem to
result from a conflict of constraints during the optimization process. See our paper on:
Scale-Free Networks from Optimal Design, S. Valverde, R. Ferrer Cancho and R. V. SolÚ,
Europhysics Letters 60, 512-517 (2002)) and our most recent work:
Hierarchical small worlds in software architecture.
Computation and noise in small world networks
Complex biosystems perform computations. Computation is actually a key ingredient that makes
ad difference between physical nonequilibrium systems and biological entities. Computing
inside a given environment is a fundamental property that is under evolutionary
pressures of different types and acting on different time and spatial scales.
Although computational theories of biocomplexity tipically involve deterministic components
behaving through standard logical operations, living beings actually compute under highly
noisy conditions (see the paper "It's a noisy business", by McAdams HH and Arkin A, downloadable at
Adam Arkin's Lab Homepage. Recent developments indicate
that using noise with appropriate network structure actually enhance the efficiency
of systems able to compute simple functions. We will explore the interplay between topology, noise and
computation by means of simple models. This work will be done in collaboration with
Alex Arenas, Universidad Rovira i Virgili, Tarragona.
Tinkering and modularity in complex networks
Modularity pervades biological complexity (se Hartwell et al. Nature, 1999). Many cell functions are
carried out by subsets of units that define functionally meaningful
entities. In spite that all biological complexity (and most artificial
complexity) involves modular patterns at many levels, its origins are so far poorly understood.
Modularity allows the adaptation of different functions with a small
amount of interference with other functions and is likely to
be a prerequisite for the adaptation of complex organisms, although it
arises most likely as a byproduct of adaptability rather than being an
adaptation itself. We are currently exploring different scenarios for the origin of modular
structures in both cellular and technological nets, particularly the evolution of modular
structures in gene interaction maps. By exploring growth models of genome evolution,
we have shown that a sharp transition exists
between a highly connected genome and a highly fragmented genome. At the transition domain,
modularity appears to emerge "for free" simply tuning the rate of link removal.
See also our book chapter:
The Role of Computation in Complex Regulatory Networks, by Pau Fernandez, Ricard V. SolÚ,
to appear in "Scale-free Networks and Genome Biology", E. Koonin et al. (eds.),
Landes Bioscience (2003)
Network Motifs in Computational Graphs
networks in nature and technology are scale-free and small-worlds. However, very
few studies focused on local topological features displayed by these networks. A
first step in our approach is the exploration of the subgraph structure present
in large software systems. Since software systems are assumed to be the result
of engineered design, a key assumption is that they should have been designed as
efficient systems. When looking at the subgraph level, we find a set of common
sub-graphs, some of them shared by all software systems and other more specific.
Although most of these common subgraphs are shared by some biological networks,
we have found evidence for general mechanims of subgraph generation. These are
new results concerning software structure which may have general applicability
and as such would completely transform and revolutionise many traditional
assumptions of software engineering, possibly leading to major advances in the
understanding of the software development process.
See our paper on:
in Computational Graphs: A Case Study in Software Architecture, by Sergi
Valverde, Ricard V. SolÚ,
submitted to Physical Review E, (2005).
Social Network Approaches to Software Development
to understand software structure is by looking at the structure of the
relationships between their modules (software network). Similarly, we can depict
the network of software developers constructing the software system. An
interesting question is how the previous networks relate to each other, that is,
how patterns of developer collaborations yield dependencies between software
entities? Is there any relationship between the small-world structure observed
in software networks and the structure of collaborations between software
developers? (see the paper:
A Social Network
Perspective on Conway's Law, by Amrit Chintan, Jos Hillegersberg & Kuldeep Kumar,
CSCW'04 Workshop on Social Networks, Chicago, IL, November 6-10, (2004)). In
this context, we plan to augment our own studies on software structure gathering
and analyzing data stored in CVS'es recording developer activities.