Stigmergy, collective actions, and animal social spacing

A new paper by Giuggioli et al. in PNAS September 30, 2013

Abstract:

Collective animal behavior studies have led the way in developing models that account for a large number of individuals, but mostly have considered situations in which alignment and attraction play a key role, such as in schooling and flocking. By quantifying how animals react to one another’s presence, when interaction is via conspecific avoidance rather than alignment or attraction, we present a mechanistic insight that enables us to link individual behavior and space use patterns. As animals respond to both current and past positions of their neighbors, the assumption that the relative location of individuals is statistically and history independent is not tenable, underscoring the limitations of traditional space use studies. We move beyond that assumption by constructing a framework to analyze spatial segregation of mobile animals when neighbor proximity may elicit a retreat, and by linking conspecific encounter rate to history-dependent avoidance behavior. Our approach rests on the knowledge that animals communicate by modifying the environment in which they live, providing a method to analyze social cohesion as stigmergy, a form of mediated animal–animal interaction. By considering a population of animals that mark the terrain as they move, we predict how the spatiotemporal patterns that emerge depend on the degree of stigmergy of the interaction processes. We find in particular that nonlocal decision rules may generate a nonmonotonic dependence of the animal encounter rate as a function of the tendency to retreat from locations recently visited by other conspecifics, which has fundamental implications for epidemic disease spread and animal sociality.

Conceptual Framework:

The delayed response between mark deposition, the action of an individual, and conspecific retreat, the reaction of another conspecific, is a basic ingredient of stigmergy (10, 11), a mediated interaction mechanism whereby the changes produced endogenously in the environment by the marks of one individual elicit a response in the neighbors, which in turn respond, affecting their nearest neighbors. This cascade of events creates a feedback mechanism for the entire population, which self-organizes into a dynamic spatiotemporal pattern.

The shrinking and growth of Si are controlled, respectively, by the aging of the marks and the movement of the animals. The transience of the deposited cues tends to reduce the size of a marked area, because inactive marks are ignored by conspecifics. An aging mark at a given location reduces the propensity of other conspecifics to retreat from that location, which in turn increases the pressure onto individual i to move further inside its own marked area, reducing even further the spatial extent of Si. Because a decrease in the size of Si further reduces its spatial extent, the decay of the marks acts as a positive feedback. The other positive feedback is the movement of the animals, which helps the growth of Si. As animals deposit marks by exploring regions beyond their inner-core areas, they increase the extent of Si and pressure neighbors into moving away to avoid confrontation. This in turn allows them to explore even larger areas, thus further increasing the size of their marked areas. Positive feedback mechanisms act to reinforce a given process and are the key to explaining various forms of aggregation and pattern formation (see, e.g., ref. 12 for the application of reinforced random walks to represent some types of positive feedback). On the other hand, the negative feedback acts in the opposite direction of the variation of Si whether it is a decrease or increase in its spatial extent. As marked areas get smaller, animals may traverse them quicker and thus slow their shrinking. Similarly, as marked areas get bigger, animals take longer to move across them, preventing individuals from re-marking aging marks. This results in a reduction of the growth rate of Si.

We choose to interpret the space use of marking animals as a stigmergic interaction for three reasons. The first is that animal marking is a widespread behavior in the animal kingdom, and although each species has evolved specialized means of communication by depositing cues on the terrain, it serves the general function of broadcasting an animal’s presence. Marks contain information about identity and relative dominance (13), with many vertebrates (14) and eusocial insects (15) making use of chemical signals but also with examples in which visual marks are used, such as feathers and feces by birds. Stigmergy represents a well-developed concept that would help in studying animal space use from a general theoretical perspective, independent of the types of signals present in the marks that get deposited or the sensory modalities required for the detection of those signals. The second reason is that stigmergy makes interactive processes history dependent, which captures the fact—often neglected in quantitative analyses of animal space use—that individuals do not respond simply to the current position of other conspecifics, but also to where they have been in the recent past. A mark, when detected, represents a record of an individual’s past activity in a specific location to which other conspecifics eventually respond. The third reason is that stigmergic stimulus–response association relies upon modification of the environment. As environmental heterogeneity may also affect how individuals move in space, our approach yields a method to quantify another form of spatial heterogeneity, the one generated endogenously from animal interactions. It thus may be possible to extend our current framework to provide a common currency to interpret animal space use as a function of the most important endogenous and exogenous features of the ecosystem, respectively, conspecific avoidance and environmental covariates. Promising approaches in that respect already are available and may help link population spatial distribution to animal spatial memory and landscape persistence (16), as well as to prey distribution and terrain steepness (17, 18).

In this framework of socially interacting animals, we are interested in determining how the individual movement response to the presence of conspecifics shapes the degree of segregation in the population. A useful tool to characterize the emerging spatiotemporal pattern of the population is the encounter rate of mobile animals, an instrument of broad ecological applicability (19). Most encounter estimates have relied upon basic animal movement models, in which displacement is ballistic and individuals are completely independent, which amounts to considering animals as “ideal gas” particles. This approach has been taken as a null model to estimate the frequency of meeting or associations among mobile animals (20) and has been used recently to estimate, with the help of allometric considerations in a spatially implicit context, how home range size scales with body mass (21). Here, to capture the key biological features of the movement and interaction processes that underlie animal spacing, we consider a spatially explicit scenario to determine how individual behavior affects animal space use. The focus of our analysis is the quantification of the average encounter rate, home range size, and degree of exclusivity as a function of the degree of stigmergy.

Image

Fig. 1. Schematic representation of stigmergy in marking animals. When the animal i detects the presence of active foreign marks, it responds by retreating from the locations of the foreign marks (Ri). At the same time, the animal i itself deposits marks over the terrain, whose active set constitutes the stimulus Si that another member j of the population detects, inducing the response Rj. In turn, animal j deposits its own marks (Sj), whose locations affect animal i again or individual k, which will react and itself produce a stimulus. The number of individuals involved in this feedback loop may be as a large as the entire population or as small as just individuals i and j, depending on the locations the animals visit after their response. The dashed lines around Rk and Sk represent the fact that the number of steps necessary to affect individual i may vary because of the random nature of the movement process and, thus, of the probability of animal i encountering the stimulus (Sj).

Stigmergic epistemology, stigmergic cognition

Here is the intro and conclusion to Chris and my paper:

To know is to cognize, to cognize is to be a culturally bounded, rationality-bounded and environmentally located agent. Knowledge and cognition are thus dual aspects of human sociality. If social epistemology has the formation, acquisition, mediation, transmission and dissemination of knowledge in complex communities of knowers as its subject matter, then its third party character is essentially stigmergic. In its most generic formulation, stigmergy is the phenomenon of indirect communication mediated by modifications of the environment. Extending this notion one might conceive of stigmergy as the extra-cranial analog of artificial neural networks or the extended mind. With its emphasis on coordination, it acts as the binding agent for the epistemic and the cognitive. Coordination is, as David Kirsh (2006, p. 250) puts it, “the glue of distributed cognition”. This paper, therefore, recommends a stigmergic framework for social epistemology to account for the supposed tension between individual action, wants and beliefs and the social corpora: paradoxes associated with complexity and unintended consequences. A corollary to stigmergic epistemology is stigmergic cognition, again running on the idea that modifiable environmental considerations need to be factored into cognitive abilities. In this sense, we take the extended mind thesis to be essentially stigmergic in character.

This paper proceeds as follows. In Section 2, we set out the formal specifications of stigmergy. In Section 3, we illustrate the essentially stigmergic characteristics of social epistemology. In Section 4, we examine extended mind externalism as the preeminent species of stigmergic cognition. In Section 5 we illustrate how the particle swarm optimization (PSO) algorithm for the optimization of a function could be understood as a useful tool for different processes of social cognition, ranging from the learning of publicly available knowledge by an individual knower, to the evolution of scientific knowledge. In Section 6, we offer some concluding remarks.

drawing-hands.jpg!Blog

A great deal of ground has been covered in the course of which we have made a case for two central claims:

1. Social epistemology has the formation, acquisition, mediation, transmission and dissemination of knowledge in complex communities of knowers as its subject matter. Such knowledge is, for the most part, third party and as such it is knowledge that is conditioned and modified. Understood thus, social epistemology is essentially stigmergic.

2. One might conceive of social connectionism as the extra-cranial analog of an artificial neural network providing epistemic structure. The extended mind thesis (at least the Clarkean variant) runs on the idea that modifiable environmental considerations need to be factored into cognitive abilities. This notion of cognition is thus essentially stigmergic.

With 1 and 2 in mind, two disclaimers are in order. First, a stigmergical socio-cognitive view of knowledge and mind should not be construed as (a) the claim that mental states are somewhere other than in the head or, (b) the corollary, that as individualists, we do not think that what is outside the head has nothing to do with what ends up in the head. A stigmergic approach, necessarily dual aspect, does not require one to dispense with one or the other. There is no methodological profit whatsoever to throwing out the Cartesian baby along with the bath water. Second, a socio-cognitive view of mind and knowledge be not be mistaken as a thesis for strong social constructivism, the idea all facts are socially constructed (a denial that reality in some way impinges upon mind) – again, it would be inconsistent with the environmental emphasis entailed by stigmergy.

For Clark, “[M]uch of what goes on in the complex world of humans, may thus, somewhat surprisingly, be understood in terms of so-called stigmergic algorithms.” (Clark, 1996, p. 279). Traditional cases of stigmergic systems include stock markets, economies, traffic patterns, supply logistics and resource allocation (Hadeli, Valckenaers, Kollingbaum, & Van Brussel, 2004), urban sprawl, and cultural memes. New forms of stigmergy have been exponentially expanded through the affordances of digital technology: we’ve expounded upon Google’s RP and Amazon’s CF but of course include wiki, open source software, weblogs, and a whole range of “social media” that comprise the World Wide Web. These particular examples serve to make the wider stigmergical point that the Janus-like aspect of knowledge and cognition must be set against a background fabric of cultural possibility: individuals draw their self-understanding from what is conceptually to hand in historically specific societies or civilizations, a preexisting complex web of linguistic, technological, social, political and institutional constraints.

It is no surprise then that it has been claimed that stigmergic systems are so ubiquitous a feature of human sociality, it would be more difficult to find institutions that are not stigmergic ( Parunak, 2005 and Tummolini and Castelfrananchi, 2007). If stigmergy were merely coextensive with “the use of external structures to control, prompt, and coordinate individual actions” (Clark, 1997, p. 186), then the concept would amount to a claim about situated cognition in all its dimensionality Solomon, 2006b. While stigmergy includes these aspects, it distinctively emphasizes the cybernetic loop of agent → environment → agent → enviro nment through an ongoing and mutual process of modification and conditioning, appearing to dissolve the supposed tension between the self-serving individual and the social corpora at large through indirect interaction. Though this process of behavior modification has long since been identified by both PSE and SSE theorists, only recently has there begun a concerted effort ( Turner, 2001 and Turner, 2003) to, as Ron Sun puts it (Sun, 2006) “cognitivize” human sociality. Social theory and cognitive science must now recognize the virtues of a “cognitivized” approach to all things social.

Microsoft Word - COGSYS-RS-_STIG_-_2012_-_6_

Stigmergic dimensions of online creative interaction

Extracts from Jimmy’s paper:

The web has experienced a recent proliferation of design expert communities in domains from software engineering (e.g. Sourceforge and Github) to art (DeviantArt and others). These communities have become hotbeds of creative interaction, with users posting their projects, closely interacting on new endeavors, and engaging in spirited discussion about their craft. With users in these communities constantly generating out new software, images, music and any other artifact imaginable, it is hard to deny that there is significant creative interaction happening. Members of these communities often possess widely varying degrees of proficiency, but more often than not, they have some baseline amount of talent that allows them to enter the community.

Enter Picbreeder. Picbreeder is a web-based system for collaborative interactive evolution of images. The Picbreeder applet starts by randomly generating several images, which are then mated and mutated based on the user’s selections. The user can then publish the image to the Picbreeder website where other users can download and continue the image’s evolution. Within Picbreeder, one need not have artistic talent to contribute to the community, although good taste typically helps. As in more traditional design, new innovations are typically small modifications to the existing structure, which can change the design incrementally or effect a larger shift. Even though users followed their individual interests when evolving this phylogeny, new interesting directions emerged. Many users contributed repeatedly to an evolving lineage, using the design itself to encourage and facilitate collaboration.

Successful collaborative design in Picbreeder does not require shared intentions, suggesting that effective collaboration may be emergent rather than planned from the top down. The surprising result of this emergent process is the gradual discovery by untrained users of hidden treasures within a vast uncharted space. Picbreeder also serves as a fascinating, though initially unintentional, experiment in stigmergic creativity.

The concept of stigmergy was first introduced by Pierre-Paul Grassé, a zoologist, who used it to describe the activities of the termite mound. As he described it, “(s)tigmergy manifests itself in the termite mound by the fact that the individual labour of each construction worker stimulates and guides the work of its neighbour”. The concept of stigmergy can be extended to human endeavors if one expands the notion of the mound to human venues, and replaces “construction worker” with any type of worker. If such an extension is permitted to human creative communities, this description becomes even more apt. Part of the excitement inherent in creative pursuits, whether it is visual art, music or creating open source software, is the moment when the work of a colleague “stimulates and guides” ones own work. Add that “(in) an insect society individuals work as if they were alone while their collective activities appear to be coordinated.” This description too can apply to creative communities. Points out that “(s)tudies on creativity . . . have focused on the individual, obscuring the fact that creativity is a collective affair. The ideas and inventions an individual produces build on the ideas of others (the ratchet effect).” It is very easy to focus on individual creative luminaries, while forgetting the environment and social milieu that are a large part of their creative interaction.

The results of Picbreeder not only demonstrate the truth of creativity as collaboration, but that a large component of creativity can be stigmergic. By abstracting out almost all direct communication and collaboration, and allowing users to be stimulated only by their work and the work of others, Picbreeder demonstrates the extent to which stigmergic processes can yield astounding results. This paper expounds on this point by first describing in detail what Picbreeder is and how it works (section 2). Next, the paper casts creativity in general and Picbreeder specifically into the context of memetic evolution, a model of how ideas spread, change, evolve and die out (section 3). The point is then made in section 4 that these collaborative creative environments draw a great deal of their effectiveness from stigmergic interaction facilitated through creative artifacts. In sections 5, an analysis of the Picbreeder data is described that shows, despite the fact that Picbreeder users engage in almost no direct communication, it shares numerous properties with other collaborative creative environments. Finally, some conclusions and recommendations are made in section 6.

This paper has shown that Picbreeder, an almost fully stigmergic means of collaborative creative interaction, follows many of the same patterns as other collaborative creative networks. Picbreeder demonstrates that it is possible to facilitate creative collaboration through entirely stigmergic means, and this paper explored the mechansisms that gave rise to that stigmergy. Because in other creative communities, stigmergic and non-stigmergic components of creative interaction are difficult to separate, Picbreeder provided an ideal opportunity to study this dimension. It is hoped that future studies will be able to isolate and study the contribution of stigmergic components in other creative communities.

It is also hoped that more quantitative analysis will be done on other creative communities. Academic publishing bibliometrics were used because they are plentiful and easy to access. While it is difficult to trace influence in similar way in musical or visual arts communities, developing techniques to analyze these communities is a worthwhile pursuit. This analysis may provide answers of real economic value. For instance, to answer the question, what will create a broader, more economically viable base of musical development, a U.S. style system in which music distribution is dominated by a few large gatekeepers to the music industry, or a Canadian style system which frequently uses government sponsored incentives to encourage development in musical communities?

There is a great deal of analysis left to be done and questions to be answered with respect to the dynamics of creative communities. For instance, how can Axelrod’s model of cultural diffusion (1997) explain creative influence? Also, how can Friedkin’s analysis of weak ties versus strong ones in organization flows (1982) inform the analysis of how creativity develops within and between organizations. Picbreeder is currently a “flat” community, which does not fully represent the wide variety of social creative arrangements. The addition of this dimension to analysis will hopefully yield additional insight.

Stigmergy is clearly involved in creativity. It is no accident that Silicon Valley is well known for technical innovation and Paris is a well known muse of artists. These physical locations host large collaborative and competent communities for one, but also frequently display and demonstrate the results of their interaction, to “stimulate and guide” other participants. Other creative communities might benefit by explicitly taking advantage of stigmergic concepts to improve their efficcacy. Imagine a paint studio where artists paint in a circle, with the paintings facing inward. Or a research lab where everybody’s latest work in progress is posted to a highly visible electronic board. The more we understand the role of stigmergy in creativity, the better we can shape and guide the process. Ultimately, every creative discipline, along with humanity itself, will be the beneficiaries of this advancement.

1-s2.0-S138904171200040X-gr2

Stigmergic self-organization and the improvisation of Ushahidi

Here are some excerpts from Janet’s fascinating paper.

In late 2007 in Kenya, US educated Kenyan journalist Ory Okolloh had become one of the main sources of information about the election and the violence that broke out soon after. Because of the government‟s ban on live reporting and censorship of the mainstream media, Okolloh solicited information about incidents of violence from ordinary people in the form of comments posted on her personal blog. The mainstream media was not reporting on the violence because of the government ban, and Okolloh was quickly overwhelmed by the numbers of emails and messages that she received. In order to focus on the “immediate need to get the information out”, in early January Okolloh posted a request on her blog for help to develop a website where people could post anonymously online or via mobile phone text messages, the most accessible type of communications technology in Kenya. Within a day the Ushahidi („testimony‟ in Swahili) domain was registered and the website went live within less than a week. Built by 15-20 mainly Kenyan volunteers using open source software, the project was funded entirely by donations. Immediately, over 250 people began using the site to share information, even including radio stations. The process of report verification was simple. If the reporter could be identified, they were contacted for verification; if anonymous, a certain volume of similar reports was considered verification. Within weeks hundreds of incidents of violence had been documented in detail that would have otherwise gone unreported, and the website received hundred of thousands of site visits from around the world, sparking increased global media attention.

Following the events in Kenya, Humanity United, a non-profit organization dedicated to ending modern slavery and mass atrocities, offered to fund redevelopment of Ushahidi as a broadly available platform for collecting and visualizing information. In late 2008 the alpha version was released and tested in the Democratic Republic of Congo, among other places. The beta version, utilizing FrontlineSMS, free software that turns a laptop and a mobile phone or modem into a central communications hub, was released in 2009. The Frontline SMS software can be used on a single laptop computer without the need for the internet, allowing users to send and receive text messages with large groups of people through mobile phones. Since its original release in 2005, it has been widely adopted in the grassroots non-profit community and nominated for several awards [Banks]. Today, Ushahidi defines itself as “a non-profit tech company that develops free and open source software for information collection, visualization and interactive mapping” [http://ushahidi.com], and the development of Ushahidi has continued. Presently, there are three free downloads available: the Ushahidi platform, the Crowdmap application, and the SwiftRiver application. In 2008, Ory Okollah said, “We anticipate that the platform will revolutionize how many organizations handle their data and also democratize how information is collected and shared in crisis situations” and characterized the Ushahidi development strategy as: “pushing the boundaries of Rapid Prototype Model, Crowdsourcing, Visualization, Mapping, and Mobile Phone Platforms.”

A study of the evolution of the Ushahidi software presents strong evidence of cognitive stigmergy at two levels. The first level is the development of the Ushahidi platform, both initially and through the creation of the enhancements. The development of the software using a Rapid Prototype model and crowdsourcing on widely available mobile phone platforms follows examples of some FLOSS development teams that have been shown to use cognitive stigmergy as a tool to organize and coordinate work. The utilization of the software by end users as volunteers and contributors also demonstrates the role of cognitive stigmergy at the level of group action. The occurrences of crowdsourcing demonstrate cognitive stigmergy. The reasons for the great success of Ushahidi lie precisely in its raison d‟etre: it was conceived as a way for people to give testimony to the world about a great crisis that was occurring. Ushahidi was meant to empower, to give voice, and was specifically designed to do so for all. Heylighen points out that the inexpensive cost of information via the internet is a major force for the increase in all forms of information, easy access to it and voluntary creation and sharing of forms of it. The combination of easy access, low cost, and a compelling social concern lead to powerful motivations for many to participate. The use of the Rapid Prototype Model meant that the functionality could be delivered while there was still an urgent need for it, before the crisis could pass and life returned to normal and that urgency was forgotten. The use of Visualization and Mapping was crucial. Human cognitive stigmergy is based on people perceiving changes in their environment and responding to them. Visual images and information are more meaningful even when the place is not known, even more powerful when it is. Testimony has more power when it is visualized. The dependence on Crowdsourcing as a resource for development, support and the generation of information is an obvious example of stigmergic self-organization. As a way to maximize participation and crowdsourcing, the use of Mobile Phone Platforms via FrontlineSMS is a clear success: “In Africa, cellphone penetration – the number of phones as a percentage of the population – is still the lowest in the world, but it is growing quickly. In 2010, an estimated 41 per cent of the population on the continent had cellphones, compared with 76 per cent globally. That’s double what it was in 2005”. Worldwide, it is estimated that there are five billion mobile phones in use as of 2010, and for many users, these are the only access they have to computing or telecommunications capability.

1-s2.0-S1389041712000381-gr1

Emergence in stigmergic and complex adaptive systems: A formal discrete event systems perspective

Some extracts from Saurabh Mittal’s paper.

A natural system is not a monolithic system but a heterogeneous system made up of disparity and dissimilarity, devoid of any larger goal. The system just “is.” Examples of such systems include ant colonies, the biosphere, the brain, the immune system, the biological cell, businesses, communities, social systems, stock markets etc. Such systems are adaptable systems where emergence and self-organization are factors that aid evolution. These systems are classified as complex adaptive systems. According to Holland (2006, 1): “CAS are systems that have a large number of components, often called agents that interact and adapt or learn.”

In this article, we investigate CAS by looking at the scale of components, interactions between the components, and emergent properties that are manifested by such CAS. We will attempt to understand some of the common underlying properties, address the adaptive nature of such complex systems and illustrate how resilience is an inherent property of CAS.

CAS is occasionally modeled by means of agent-based models and complex network-based models. Multi-agent systems (MAS) is the area of research that deals with such study. However, CAS is fundamentally different from MAS in portraying features like self-similarity (scale-free), complexity, emergence and self-organization that are at a level above the interacting agents. A CAS is a complex, scale-free collectivity of interacting adaptive agents, characterized by high degree of adaptive capacity, giving them resilience in the face of perturbation. Indeed, designing an artificial CAS requires formal attention to these specific features. We will address these features and the formalisms needed to model CAS.

The discipline of modeling originated to understand natural phenomena. By developing abstractions, we can manage the apparent complexity, reuse it and enable these complex phenomena in artificial systems to our advantage. The discipline of executing this model on a time base is “simulation.” The task of decoding the original structure from manifested behavior is the holy grail of the modeling and simulation (M & S) enterprise (Zeigler, Praehofer, & Kim, 2000). The need for M & S to make progress in understanding CAS has been well acknowledged by Holland (1992). The task is to understand the gamut of rules that exist within and without a component and understand how the component deals with such multidimensional rules in an interactive environment. M & S is the only way one can understand, mimic and recreate a natural system. Most artificially modeled systems that exhibit complex adaptive behavior are driven by multi-resolution bindings and interconnectivity at every level of system behavior. To understand life is to “model”; to adapt is to survive in an environment, where both survival and environment are loaded concepts based on the guiding discipline.

Complexity is a phenomenon that is multivariable and multi-dimensional in a space-time continuum. Therefore, what we need is a framework that helps develop system structure and behavior in an abstract manner and that is component oriented so that the system can define its interactions based on the composition of a multi-level environment.

Stigmergy, the study of indirect interaction between network components in a persistent environment, explains certain emergent properties of a system. The network components include both the environment and the agent and both are persistent, i.e. both are situated in a space-time continuum and have memory. We take Stigmergic systems to be a subset of CAS and argue that stigmergic behavior is an emergent phenomenon too. Ultimately, we are trying to get a handle on how to formalize the property of “emergence.”

Discrete event abstraction has been studied at length by Bernard Zeigler throughout his illustrious career and his pioneering work on Discrete Event Systems (DEVS) formalism in 1970s (Ziegler, 1976). As a student, his perspectives on CAS were influenced by Holland. Ziegler’s approach to CAS has been through the quantization of continuous phenomena and how quantization leads to abstraction. Any CAS must operate within the constraints imposed by space, time, and resources on its information processing (Pinker, 1997). Evidence from neuronal models and neuron processing architectures and from fast and frugal heuristics, provide further support to the centrality of discrete event abstraction in modeling CAS when the constraints of space, time and energy are taken into account. Zeigler stated that discrete event models are the right abstraction for capturing CAS structure and behavior (Zeigler, 2004). In this article, we take the discipline of modeling CAS forward, by looking at the emergence aspect of CAS. We introduce DEVS and demonstrate how recent extensions still fall a little short in modeling CAS.

We first focus on the study of network science and how scale-free networks are inherently important to study complex interactions and hierarchical systems. In Section 3 we look at various types of interactions in a complex network. Section 4 we address the concepts of emergence and self-organization in detail and examine how a complex dynamic network facilitates such behavior. Section 5, a slight digression, provides an overview of DEVS theory. We return to the subject of dynamism in a complex adaptive network in Section 6 and show how DEVS theory is positioned to give modeling and simulation support to the subject. We describe various existing formal DEVS extensions that help model various features of stigmergy, emergence and CAS. Finally, in Section 7, we present some conclusions and pointers for future research.

Complexity is a multifaceted topic and each complex system has its own properties. However, some of the properties like high interconnectedness, large number of components, and adaptive behavior are present in most natural complex systems. We looked at the mechanism behind interconnectedness using network science that describes many natural systems in the light of power laws and self-similar scale-free topologies. Such scale-free topologies bring their own inherent properties to the complex system such that the entire system is subjected to the network’s structural and functional affordances.

It is largely unknown what makes a network evolve into a scale-free network, whether it is a top-down goal-driven phenomena or bottom-up causation or just an outcome of natural interactions. Two conditions have to be present for a network to evolve into a scale-free network: 1. incremental growth and 2. preferential attachment. We explored the notions of scale-free nature, strong and weak emergence, self-organization and stigmergic behavior in a complex adaptive system with persistent agents and persistent environment. We also related the concept of emergence to network science and presented arguments on how hubs and connectors are formed when a complex system is going through a critical phase. We argued that under any occurrence of both self-organized and emergent behavior together, the properties of scale-free network exist and one has to look at right level of abstraction in a multi-level system to witness the instance based interactions. We established that stigmergy displays strong emergence and is a specialized case of CAS. We also enumerated 18 properties of a CAS, 11 of which were properties of stigmergic systems.

We presented a high level view of DEVS theory and how its formal rigor is able to specify complex hierarchical systems. We described variants of dynamic structure and multi-level DEVS, and mapped it to some of the identified properties of CAS and stigmergy. We detailed the adaptive nature of complex system with DEVS Level of system specification and what it means to have dynamic adaptive behavior at different levels of a system. During the mapping process, we found that the following capabilities warrant formal attention to extend DEVS theory of complex systems to a theory of complex adaptive systems:

  1. How clusters are formed, hubs appear and evolve.
  2. How multi-level self-organization occurs.
  3. How strong emergence results in self-organization with an embedded observer capable of causal behavior at lower levels of hierarchy.
  4. How formal attention to coupling specification may provide additional abstraction mechanisms to model dynamic interconnected environment.

Finally, we recommended the augmentation of as the foundation for Stigmergic-DEVS, and investigation of both and ML-DEVS augmented together as a foundation for CAS-DEVS.