"A system comprised of a (usually large) number of (usually strongly) interacting entities, processes, or agents, the understanding of which requires the development, or the use of, new scientific tools, nonlinear models, out-of equilibrium descriptions and computer simulations." [Advances in Complex Systems Journal]
"A system that can be analyzed into many components having relatively many relations among them, so that the behavior of each component depends on the behavior of others. [Herbert Simon]"
"A system that involves numerous interacting agents whose aggregate behaviors are to be understood. Such aggregate activity is nonlinear, hence it cannot simply be derived from summation of individual components behavior." [Jerome Singer]
A complex system is any system featuring a large number of interacting components (agents, processes, etc.) whose aggregate activity is nonlinear (not derivable from the summations of the activity of individual components) and typically exhibits hierarchical self-organization under selective pressures. This definition applies to systems from a wide array of scientific disciplines. Indeed, the sciences of complexity are necessarily based on interdisplinary research. Not surprisingly, the heart of this research area is the Santa Fe Institute in Santa Fe, New Mexico, which was founded initially by researchers from the Los Alamos National Laboratory such as George A. Cowan, a LANL Senior Fellow Emeritus. In fact, LANL has produced or attracted many of the researchers associated with this center and research area: Nicholas Metropolis, Chris Langton, Stephanie Forrest, Alan Lapedes, Steen Rassmussen, Alan Perelson, Hans Frauenfelder, among others. However, this research did not originate recently nor here; it is a direct offspring of the Cybernetics and Systems Research movements which started in the 1940's with people like Norbert Wiener, Warren McCulloch, Margaret Mead, Ross Ashby, John von Neuman, Heinz von Foerster, and others (1).
Almost all interesting processes in nature are highly cross linked. In many systems, however, we can distinguish a set of fundamental building blocks, which interact nonlinearly to form compound structures or functions with an identity that requires more explanatory devices than those used to explain the building blocks. This process of emergence of the need for new, complementary, modes of description is known as hierarchical self-organization, and systems that observe this characteristic are defined as complex (2). Examples of these systems are gene networks that direct developmental processes, immune networks that preserve the identity of organisms, social insect colonies, neural networks in the brain that produce intelligence and consciousness, ecological networks, social networks comprised of transportation, utilities, and telecommunication systems, as well as economies.
The Complex Systems Modeling Research Focus Area at the Modeling, Algorithms, and Informatics Group (CCS-3) is concerned with basic and applied research on simulations and analysis of complex systems, as well as development of applications to understand and control such systems. Our focus is on the study of Networks and Multi-Agent Systems, such as social, knowledge and biological. Currently, our premier application areas are Computational Biology -- with ongoing projects in gene and protein networks -- and Network and Multi-Agent Modeling -- with ongoing projects in Recommendation Systems for the Web and Digital Libraries, and Knowledge Discovery in Networks of social agents such as terrorist networks. Some of this research is described below.
Biological regulatory mechanisms, including gene expression, are inherently complex systems as defined above. As such, they cannot be understood by mere identification of components, products, ensembles and connections. Therefore, we wish to supplement the surplus of gene and protein sequence information now available, with informational and developmental means to model and understand evolutionary systems. This includes understanding the representation and communication of information in living systems, predicting protein function from gene sequence, structure and even textual information, discovering interactions in gene regulatory networks, and the computer modeling of RNA Editing. We are also considering algorithmic implications of biological problems, such as in the development of efficient DNA sequencing procedures and pooling designs.
Next to the gene sequencing projects, we are now faced with the challenge of mapping a molecular identity from different sources of information such as gene expression, protein sequence and structural data. In the case of gene expression, we can analyze mircroarray measurements. Such an array contains the expression intensities of different genes in a cell under certain experimental conditions. We can also construct a matrix of such arrays under different conditions, e.g. stages of infection. These matrices contain tremendous amounts of information about the complex interactions between genes, and ultimately characterize a cell's behavior.
To discover these patterns of interaction, we are employing pattern recognition algorithms specifically designed to tackle this problem. We are using data-mining techniques such as Association Rules, Fuzzy Clustering, and Singular Value Decomposition. We have also embarked on understanding the characteristics of gene regulatory circuits one may identify from microarray data.
Related to this research, we are also investigating combinatorial optimization in biology. This research addresses theoretical and practical aspects of optimization problems arising in a biologically-motivated setting. Major efforts include algorithms for optimizing the DNA sequencing process, and pooling designs for maximally efficient group testing. Details also in our web site.
The term agent is used today to mean anything between a mere subroutine and a conscious entity. There are "helper" agents for web retrieval and computer maintenance, robotic agents to venture into inhospitable environments, agents in an economy, etc. Intuitively, for an object to be referred to as an agent it must possess some degree of autonomy, that is, it must be in some sense distinguishable from its environment by some kind of spatial, temporal, or functional boundary. It must possess some kind of identity to be identifiable in its environment. To make the definition of agent useful, we often further require that agents must have some autonomy of action, that they can engage in tasks in an environment without direct external control.
Traditionally, Agent-Based Models (ABM) draw on examples of phenomena from biology such as social insects and immune systems. These systems are distributed collections of interacting entities (agents) that function without a "leader." From simple agents, who interact locally with simple rules of behavior, merely responding befittingly to environmental cues, and not necessarily striving for an overall goal, we observe a synergy which leads to a higher-level whole with much more intricate behavior than the component agents, e.g. insect colonies and immune responses. The field of Artificial Life (AL) [Langton, 1989] produced a number of models based on simple agent rules capable of producing a higher-level identity, such as the flocking behavior of birds, which were called Swarms (3) or ABM. In these models, agents are typically described by state-determined automata: that is, they function by reaction to input and present state using some iterative mapping in a state space. Such ABM can be used, for instance, to simulate massively parallel computing systems, a research interest of several members of our team.
However, it has become clear in recent years, that the modeling of some phenomena, particularly, ecological and social phenomena, requires agents whose behavior is not simply dictated by local, state-determined interaction. In a society empowered by language and hyperlinked by information channels, which in turn impacts planetary ecology, agents have access and rely on accumulated knowledge which escapes local constraints (via communication) and is stored in media beyond the agent itself and its state. Indeed, many if not most researchers in Artificial Intelligence (AI), Cognitive Science and Psychology, have come to pursue the idea that intelligence is not solely an autonomous characteristic of agents, but heavily depends on social, linguistic, and organizational knowledge which exists beyond individual agents. Such agents are often known as situated [Clark, 1997] or semiotic [Rocha, 1999] agents. It has also been shown that agent simulations which rely on shared social knowledge, can model social choice more effectively [Richards, et al, 1998].
Because most of our research projects deal with modeling social networks, we are interested in studying how agents trade and employ knowledge in their decision making. We are particularly interested in studying the structure of social networks that arise out of agents who exchange knowledge, as well as the dynamics of trends observed in such multi-agent systems. We also use existing networks of documets (e.g. the WWW and databases with scientific publications), to discover the dynamics of knowledge in user communities. We have developed methods to predict trends and identify latent associations between agents, documents, or keyterms. Latent associations are associations (say between agents) that have not occurred, but which are strongly implied by indirect network connections, and thus have a high chance of occurring in the future. This methodology has been used in a recommendation system for the MyLibray Portal at Los Alamos and to study terrorist networks in Homeland Defense projects.
Our team pursues other related research exploring metaphors from Nature, particularly in the areas of adaptive computation and optimization. The key notion of complex systems, that of many simple processes, under selective pressures, synergistically interacting to produce desirable global behavior, can be applied successfully to different problems. In the area of optimization, we are developing heuristic algorithms inspired by non-equilibrium physical processes. The development of non-equilibrium optimization methods is likely to lead to the next generation of general-purpose algorithms - intended, like simulated annealing, for broad application. We expect that this analysis will lead us to new insights into the role criticality plays in combinatorial optimization, as well as to a deeper (and more applied) understanding of computational complexity.
Similarly, we are developing biologically motivated designs for Adaptive Knowledge Management. Distributed designs that draw from immune system metaphors and other aspects of biological systems can largely improve existing information retrieval and knowledge management in networked information resources. We have developed a recommendation system for LANL's Research Library that allows different databases to learn new and adapt existing keywords to the categories recognized by different communities, using algorithms inspired by biological and cultural evolution.
For more details on our research, please refer to our projects, competencies, and research list on this web site.
Cariani, Peter [1992]."Emergence and Artificial Life." In: Artificial Life II. C. Langton, C. Taylor, J.D. Farmer, and S. Rasmussen (eds.). SFI Series in the Sciences of Complexity. Addison-Wesley, pp. 775-797.
Clark, Andy [1997]. Being There: Putting Brain, Body, and World Together Again . MIT Press.
Klir, George, J. [1991]. Facets of Systems Science. Plenum Press.
Langton, C.G. [1989]."Artificial life." In: Artificial Life. C. Langton (ed.). Addison-Wesley.
Pattee, Howard H. [1978]."The complementary principle in biological and social structures." Journal of Social and Biological Structures. Vol. 1, pp. 191-200.
Richards, D., B.D. McKay, and W.A. Richards [1998]."Collective choice and mutual knowledge structures." Advances in Complex Systems. Vol. 1, pp. 221-236.
Rocha, Luis M. [1999]."Syntactic Autonomy: or why there is no autonomy without symbols and how self-organizing systems might evolve them." New York Academy of Sciences. In Press.
Rosen, Robert [1993]."Bionics revisited." In: The Machine as a Metaphor and Tool. H. Haken, A. Karlqvist, and U. Svedin (eds.). Springer-Verlag, pp. 87-100.
1. For more details on Cybernetics and Systems Research please refer to Klir [1991] or the web pages of the Principia Cybernetica Project.
2. Hierarchical self-organization and emergence have been discussed in detail by Pattee[1978], Rosen [1993], and Cariani [1992].
3. This research led to the development of an agent-based simulation language called Swarm, which we use in several of our projects.
