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.

DELIS WEB SITE at Universitńt Paderborn.

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

 

Many 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: Network Motifs 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

 

A way 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.


REFERENCES