"In this paper we define what we call an affinity system, which is a set of individuals, each with a vector characterizing its preference for all other individuals in the set. The preference of a member can be given either by a ranking of all members or by a weighted vector that defines the degrees of its affinity to others. Affinity systems are useful for modeling social systems as well as general data sets, as social interactions are often determined by affinities among the members. We also define a natural notion of (potentially overlapping) communities in an affinity system, in which the members of a given community collectively prefer each other to anyone else outside the community. Thus these communities are "self-determined" or "self-certified" by the affinity system. We provide a tight polynomial bound on the number of self-determined communities as a function of the robustness of the community. Moreover, we present a polynomial-time algorithm for enumerating these communities, as well as a local algorithm with a strong stochastic performance guarantee that can find a community in time nearly linear in the of size the community.…"

"We review the observations and the basic laws describing the essential aspects of collective motion -- being one of the most common and spectacular manifestation of coordinated behavior. Our aim is to provide a balanced discussion of the various facets of this highly multidisciplinary field, including experiments, mathematical methods and models for simulations, so that readers with a variety of background could get both the basics and a broader, more detailed picture of the field. The observations we report on include systems consisting of units ranging from macromolecules through metallic rods and robots to groups of animals and people. Some emphasis is put on models that are simple and realistic enough to reproduce the numerous related observations and are useful for developing concepts for a better understanding of the complexity of systems consisting of many simultaneously moving entities. As such, these models allow the establishing of a few fundamental principles of flocking. In particular, it is demonstrated, that in spite of considerable differences, a number of deep analogies exist between equilibrium statistical physics systems and those made of self-propelled (in most cases living) units. In both cases only a few well defined macroscopic/collective states occur and the transitions between these states follow a similar scenario, involving discontinuity and algebraic divergences."

"We analyze emotionally annotated massive data from IRC (Internet Relay Chat) and model the dialogues between its participants by assuming that the driving force for the discussion is the entropy growth of emotional probability distribution. This process is claimed to be correlated to the emergence of the power-law distribution of the discussion lengths observed in the dialogues. We perform numerical simulations based on the noticed phenomenon obtaining a good agreement with the real data. Finally, we propose a method to artificially prolong the duration of the discussion that relies on the entropy of emotional probability distribution."

"In a recent paper, we analyzed the self-assembly of a complex cooperation network. The network was shown to approach a state, where every agent invests the same amount of resources. Nevertheless, highly-connected agents arise that extract extra-ordinarily high payoffs while contributing comparably little to any of their cooperations. Here, we investigate a variant of the model, in which highly-connected agents have access to additional resources. We study analytically and numerically whether these resources are invested in existing collaborations, leading to a fairer load distribution, or in establishing new collaborations, leading to an even less fair distribution of loads and payoffs."

"We study instabilities and pattern formation in reaction-diffusion layers that are diffusively coupled. For two-layer systems of identical two-component reactions, we analyze the stability of homogeneous steady states by exploiting the block symmetric structure of the linear problem. There are eight possible primary bifurcation scenarios, including a Turing-Turing bifurcation that involves two disparate length scales whose ratio may be tuned via the inter-layer coupling. For systems of $n$-component layers and non-identical layers, the linear problem's block form allows approximate decomposition into lower-dimensional linear problems if the coupling is sufficiently weak. As an example, we apply these results to a two-layer Brusselator system. The competing length scales engineered within the linear problem are readily apparent in numerical simulations of the full system. Selecting a $sqrt{2}$:1 length scale ratio produces an unusual steady square pattern."

Many natural processes occur over characteristic spatial and temporal scales. This paper presents tools for (i) flexibly and scalably coarse-graining cellular automata and (ii) identifying which coarse-grainings express an automaton's dynamics well, and which express its dynamics badly. We apply the tools to investigate a range of examples in Conway's Game of Life and Hopfield networks and demonstrate that they capture some basic intuitions about emergent processes. Finally, we formalize the notion that a process is emergent if it is better expressed at a coarser granularity.

We propose a nonlinear voter model to study the emergence of global consensus in opinion dynamics. In our model, agent $i$ agrees with one of binary opinions with the probability that is a power function of the number of agents holding this opinion among agent $i$ and its nearest neighbors, where an adjustable parameter $alpha$ controls the effect of herd behavior on consensus. We find that there exists an optimal value of $alpha$ leading to the fastest consensus for lattices, random graphs, small-world networks and scale-free networks. Qualitative insights are obtained by examining the spatiotemporal evolution of the opinion clusters.

This article analyses a game where players sequentially choose either to become insiders and pick one of finitely many locations or to remain outsiders. They will only become insiders if a minimum distance to the next player can be assured; their secondary objective is to maximize the minimal distance to other players. This is illustrated by considering the strategic behavior of men choosing from a set of urinals in a public lavatory. However, besides very similar situations (e.g. settling of residents in a newly developed area, the selection of food patches by foraging animals, choosing seats in waiting rooms or lines in a swimming pool), the game might also relevant to the problem of placing billboards attempting to catch the attention of passers-by or similar economic situations. In the non-cooperative equilibrium, all insiders behave as if they cooperated with each other and minimized the total number of insiders. It is shown that strategic behavior leads to an equilibrium with substantial under utilization of available locations. Increasing the number of locations tends to decrease utilization. The removal of some locations which leads to gaps can not only increase relative utilization but even absolute maximum capacity.

"We propose distributed algorithms to automatically deploy a team of mobile robots to partition and provide coverage of a non-convex environment. To handle arbitrary non-convex environments, we represent them as graphs. Our partitioning and coverage algorithm requires only short-range, unreliable pairwise "gossip" communication. The algorithm has two components: (1) a motion protocol to ensure that neighboring robots communicate at least sporadically, and (2) a pairwise partitioning rule to update territory ownership when two robots communicate. By studying an appropriate dynamical system on the space of partitions of the graph vertices, we prove that territory ownership converges to a pairwise-optimal partition in finite time. This new equilibrium set represents improved performance over common Lloyd-type algorithms. Additionally, we detail how our algorithm scales well for large teams in large environments and how the computation can run in anytime with limited resources. Finally, we report on large-scale simulations in complex environments and hardware experiments using the Player/Stage robot control system."

"We present a procedure to solve the inverse Ising problem, that is to find the interactions between a set of binary variables from the measure of their equilibrium correlations. The method consists in constructing and selecting specific clusters of variables, based on their contributions to the cross-entropy of the Ising model. Small contributions are discarded to avoid overfitting and to make the computation tractable. The properties of the cluster expansion and its performances on synthetic data are studied. To make the implementation easier we give the pseudo-code of the algorithm."

"Disease awareness in infection dynamics can be modeled with adaptive contact networks whose rewiring rules reflect the attempt by susceptibles to avoid infectious contacts. Simulations of this type of models show an active phase with constant infected node density in which the interplay of disease dynamics and link rewiring prompts the convergence towards a well defined degree distribution, irrespective of the initial network topology. We develop a method to study this dynamic equilibrium and give an analytic description of the structure of the characteristic degree distributions and other network measures. The method applies to a broad class of systems and can be used to determine the steady-state topology of many other adaptive networks."

"Biology presents many examples of planar distribution and structural networks having dense sets of closed loops. An archetype of this form of network organization is the vasculature of dicotyledonous leaves, which showcases a hierarchically-nested architecture containing closed loops at many different levels. Although a number of methods have been proposed to measure aspects of the structure of such networks, a robust metric to quantify their hierarchical organization is still lacking. We present an algorithmic framework, the hierarchical loop decomposition, that allows mapping loopy networks to binary trees, preserving in the connectivity of the trees the architecture of the original graph. We apply this framework to investigate computer generated graphs, such as artificial models and optimal distribution networks, as well as natural graphs extracted from digitized images of dicotyledonous leaves and vasculature of rat cerebral neocortex. We calculate various metrics based on the Asymmetry, the cumulative size distribution and the Strahler bifurcation ratios of the corresponding trees and discuss the relationship of these quantities to the architectural organization of the original graphs. This algorithmic framework decouples the geometric information (exact location of edges and nodes) from the metric topology (connectivity and edge weight) and it ultimately allows us to perform a quantitative statistical comparison between predictions of theoretical models and naturally occurring loopy graphs."

"Network or graph structures are ubiquitous in the study of complex systems. Often, we are interested in complexity trends of these system as it evolves under some dynamic. An example might be looking at the complexity of a food web as species enter an ecosystem via migration or speciation, and leave via extinction.

In a previous paper, a complexity measure of networks was proposed based on the {em complexity is information content} paradigm. To apply this paradigm to any object, one must fix two things: a representation language, in which strings of symbols from some alphabet describe, or stand for the objects being considered; and a means of determining when two such descriptions refer to the same object. With these two things set, the information content of an object can be computed in principle from the number of equivalent descriptions describing a particular object.

The previously proposed representation language had the deficiency that the fully connected and empty networks were the most complex for a given number of nodes. A variation of this measure, called zcomplexity, applied a compression algorithm to the resulting bitstring representation, to solve this problem. Unfortunately, zcomplexity proved too computationally expensive to be practical.
In this paper, I propose a new representation language that encodes the number of links along with the number of nodes and a representation of the linklist. This, like zcomplexity, exhibits minimal complexity for fully connected and empty networks, but is as tractable as the original measure."

"Two different conceptions of emergence are reconciled as two instances of the phenomenon of detection. In the process of comparing these two conceptions, we find that the notions of complexity and detection allow us to form a unified definition of emergence that clearly delineates the role of the observer."

"We have developed a Nagel-Schreckenberg cellular automata model for describing of vehicular traffic flow at a single intersection. A set of traffic lights operating in fixed-time scheme controls the traffic flow. Open boundary condition is applied to the streets each of which conduct a uni-directional flow. Streets are single-lane and cars can turn upon reaching to the intersection with prescribed probabilities. Extensive Monte Carlo simulations are carried out to find the model flow characteristics. In particular, we investigate the flows dependence on the signalisation parameters, turning probabilities and input rates. It is shown that for each set of parameters, there exist a plateau region inside which the total outflow from the intersection remains almost constant. We also compute total waiting time of vehicles per cycle behind red lights for various control parameters."

"Consider a large Boolean network with a feed forward structure. Given a probability distribution for the inputs, can one find-possibly small-collections of input nodes that determine the states of most other nodes in the network?…"

"The response of complex networks to perturbations is of utmost importance in areas as diverse as ecosystem management, emergency response, and cell reprogramming. A fundamental property of networks is that the perturbation of one node can affect other nodes, in a process that may cause the entire or substantial part of the system to change behavior and possibly collapse. Recent research in metabolic and food-web networks has demonstrated the concept that network damage caused by external perturbations can often be mitigated or reversed by the application of compensatory perturbations. Compensatory perturbations are constrained to be physically admissible and amenable to implementation on the network. However, the systematic identification of compensatory perturbations that conform to these constraints remains an open problem. Here, we present a method to construct compensatory perturbations that can control the fate of general networks under such constraints. Our approach accounts for the full nonlinear behavior of real complex networks and can bring the system to a desirable target state even when this state is not directly accessible. Applications to genetic networks show that compensatory perturbations are effective even when limited to a small fraction of all nodes in the network and that they are far more effective when limited to the highest-degree nodes. The approach is conceptually simple and computationally efficient, making it suitable for the rescue, control, and reprogramming of large complex networks in various domains."

"Under neutral reciprocal sign epistasis, two genetic changes are jointly neutral, even though their individual effects are deleterious. By using the widely studied mapping from an RNA sequence to secondary structure, we investigate the effect of this kind of epistasis on neutral spaces corresponding to networks of genotypes that fold to the same secondary structure. Neutral networks for RNA structures with n bonds are typically fragmented into at least 2^n different neutral components that cannot be connected by single point mutations. By exhaustive enumeration of all RNA secondary structures of sequences of length 15 we show that most networks are not dominated by one neutral component, but are rather broken up into multiple large components. Although they generate the same phenotype, components of a single neutral network are heterogeneous, showing wide variations in their robustness and their evolvability. Both properties are correlated with component size, rather than with the size of their underlying neutral network. In particular, sets of accessible phenotypes can vary quite strongly between components. Thus, the potential for future innovation is contingent on which neutral component a population occupies. We further argue that neutral reciprocal sign epistasis may have similar consequences for neutral evolution of other biological systems as well."

"More broadly, a simple dictum such as ‘listen to the experts’ isn’t going to work, precisely because our most powerful methods of generating new knowledge (viz. the sciences) are not so much based on listening to individual experts, as on including these experts (and many others) in broader social systems which expose them continually to the ideas of others and vice-versa. Designing (or – perhaps better- nurturing) such systems is hard to think about and hard to do – but it has to be the way forward."

'While Adam Smith may be known as the philosopher who first promoted the idea that “greed is good,” his earlier work suggests we are not condemned to exploit others for the benefit of a few. In his book The Theory of Moral Sentiments, written in 1759, Smith proposed that sympathy for the plight of those who suffer is an inherent part of human nature.

“When we see one man oppressed or injured by another,” he wrote, “the sympathy which we feel with the distress of the sufferer seems to serve only to animate our fellow-feeling with his resentment against the offender.”

With the current occupation of Wall Street and the international condemnation of an economic model that would take advantage of those most in need, we are witnessing Smith’s prediction in action. It is only when the reality of people’s suffering is hidden that greed is allowed to dictate policy. While our current system has chosen the greed of the few over the needs of the many, the intellectual founder of modern capitalism suggests it doesn’t need to be this way. “When we think of the anguish of the sufferers, we take part with them more earnestly against their oppressors.”'

"The Peter principle has been recently investigated by means of an agent-based simulation and its validity has been numerically corroborated. It has been confirmed that, within certain conditions, it can really influence in a negative way the efficiency of a pyramidal organization adopting meritocratic promotions. It was also found that, in order to bypass these effects, alternative promotion strategies should be adopted, as for example a random selection choice. In this paper, within the same line of research, we study promotion strategies in a more realistic hierarchical and modular organization and we show the robustness of our previous results, extending their validity to a more general context. We discuss also why the adoption of these strategies could be useful for real organizations."

"We consider a network of coupled agents playing the Prisoner's Dilemma game, in which players are allowed to pick a strategy in the interval [0,1], with 0 corresponding to defection, 1 to cooperation, and intermediate values representing mixed strategies in which each player may act as a cooperator or a defector over a large number of interactions with a certain probability. Our model is payoff-driven, i.e., we assume that the level of accumulated payoff at each node is a relevant parameter in the selection of strategies. Also, we consider that each player chooses his/her strategy in a context of limited information. We present a deterministic nonlinear model for the evolution of strategies. We show that the final strategies depend on the network structure and on the choice of the parameters of the game. We find that polarized strategies (pure cooperator/defector states) typically emerge when (i) the network connections are sparse, (ii) the network degree distribution is heterogeneous, (iii) the network is assortative, and surprisingly, (iv) the benefit of cooperation is high."

"Computational complexity is one of the most beautiful fields of modern mathematics, and it is increasingly relevant to other sciences ranging from physics to biology. This book gives a lucid and playful explanation of the field, starting with P and NP-completeness. The authors explain why the P vs. NP problem is so fundamental, and why it is so hard to resolve. They then lead the reader through the complexity of mazes and games; optimization in theory and practice; randomized algorithms, interactive proofs, and pseudorandomness; Markov chains and phase transitions; and the outer reaches of quantum computing. At every turn, they use a minimum of formalism, providing explanations that are both deep and accessible. The book is intended for graduates and undergraduates, scientists from other areas who have long wanted to understand this subject, and experts who want to fall in love with this field all over again."

"We investigate the evolutionary dynamics of an idealised model for the robust self-assembly of two-dimensional structures called polyominoes. The model includes rules that encode interactions between sets of square tiles that drive the self-assembly process. The relationship between the model's rule set and its resulting self-assembled structure can be viewed as a genotype-phenotype map and incorporated into a genetic algorithm."

"We understand the dynamics of the world around us as by associating pairs of events, where one event has some influence on the other. These pairs of events can be aggregated into a web of memories representing our understanding of an episode of history. The events and the associations between them need not be directly experienced-they can also be acquired by communication. In this paper we take a network approach to study the dynamics of memories of history. First we investigate the network structure of a data set consisting of reported events by several individuals and how associations connect them. We focus our measurement on degree distributions, degree correlations, cycles (which represent inconsistencies as they would break the time ordering) and community structure.…"

"Zipf's law seems to be ubiquitous in human languages and appears to be a universal property of complex communicating systems. Following an early proposal made by Zipf concerning the presence of a tension between the efforts of speaker and hearer in a communication system, we introduce evolution by means of a variational approach to the problem based on Kullback's Minimum Discrimination of Information Principle. Using a formalism fully embedded in the framework of information theory, we demonstrate that Zipf's law is the only expected outcome of an evolving, communicative system under a rigorous definition of the communicative tension described by Zipf."

"Using frequency distributions of daily closing price sequences of several stock markets, we investigate whether the bias away from an equiprobable sequence distribution, predicted by algorithmic probability, may account for some of the deviation of financial markets from log-normal, and if so for how much of said deviation and over what sequence lengths. Our discussion might constitute a potential starting point for a further investigation of the market as a rule-based system with an 'algorithmic' component, despite its apparent randomness. The use of the theory of algorithmic complexity may supply a set of probing new tools that can be applied to the study of the market price phenomenon. Moreover, the main discussion is cast in terms of assumptions common to areas of economics consistent with an algorithmic view of the market."

"We study equilibrium configurations of swarming biological organisms subject to exogenous and pairwise endogenous forces. Beginning with a discrete dynamical model, we derive a variational description of the corresponding continuum population density. Equilibrium solutions are extrema of an energy functional, and satisfy a Fredholm integral equation. We find conditions for the extrema to be local minimizers, global minimizers, and minimizers with respect to infinitesimal Lagrangian displacements of mass. In one spatial dimension, for a variety of exogenous forces, endogenous forces, and domain configurations, we find exact analytical expressions for the equilibria.…"

"We have shown that there exists a large ensemble of minimal Boolean networks that show reliable and robust dynamics. The networks are minimal in the respect that the number of connections of a node is not larger than necessary for obtaining a desired reliable trajectory. A reliable trajectory is an attractor of the dynamics of the network that does not change when the update schedule is changed or randomized. This means that under parallel update, at each time step only one node changes its state. The reliable trajectories were chosen at random, given a fixed average number of flips per node. High robustness was achieved by using an evolutionary algorithm that modifies the update functions and that accepts only those changes that do not decrease robustness.…"

"We study the dynamics of the Naming Game [Baronchelli et al., (2006) J. Stat. Mech.: Theory Exp. P06014] in empirical social networks. This stylized agent-based model captures essential features of agreement dynamics in a network of autonomous agents, corresponding to the development of shared classification schemes in a network of artificial agents or opinion spreading and social dynamics in social networks. Our study focuses on the impact that communities in the underlying social graphs have on the outcome of the agreement process. We find that networks with strong community structure hinder the system from reaching global agreement; the evolution of the Naming Game in these networks maintains clusters of coexisting opinions indefinitely. Further, we investigate agent-based network strategies to facilitate convergence to global consensus."

"In the present article we emphasize the importance of modeling time in the context of agent-based models. To this end, we present a (selective) survey of the Cellular Automata-literature on updating and draw parallels to the issue of agent activation in agent-based models. By means of two simple models, Schelling's segregation model and Epstein's demographic prisoner's dilemma we investigate the influence of choosing different regimes of agent activation. Our experiments indicate that timing is not a critical issue for very simple models but bears huge influence on model behavior and results as soon as the degree of complexity increases only so slightly. After a brief review of the way commonly used ABM simulation environments handle the issue of timing, we draw some tentative conclusions about the importance of timing and the need for more research towards that direction, similar to the concerted effort on updating in cellular automata."

"Many complex systems present an intrinsic bipartite nature and are often described and modeled in terms of networks [1-5]. Examples include movies and actors [1, 2, 4], authors and scientific papers [6-9], email accounts and emails [10], plants and animals that pollinate them [11, 12]. Bipartite networks are often very heterogeneous in the number of relationships that the elements of one set establish with the elements of the other set. … Here we introduce an unsupervised method to statistically validate each link of the projected network against a null hypothesis taking into account the heterogeneity of the system. We apply our method to three different systems…. In all these systems, both different in size and level of heterogeneity, we find that our method is able to detect network structures which are informative about the system…"

"We discuss the complex dynamics of a non-linear random networks model, as a function of the connectivity k between the elements of the network. We show that this class of networks exhibit an order-chaos phase transition for a critical connectivity k = 2. Also, we show that both, pairwise correlation and complexity measures are maximized in dynamically critical networks. These results are in good agreement with the previously reported studies on random Boolean networks and random threshold networks, and show once again that critical networks provide an optimal coordination of diverse behavior."

"A parameterisation of generalised network clustering, in the form of four-motif prevalences, is presented. This involves three real parameters that are conditional on one- two- and three-motif prevalences. Interpretations of these real parameters are presented that motivate a set of rewiring schemes to create appropriately clustered networks. Finally, the dynamical implications of higher order structure, as parameterised, for a contact process are considered."

"We have developed a framework to study the struc- ture and function of complex networks in purely geomet- ric terms. In this framework, two common properties of complex network topologies, strong heterogeneity and clustering, turn out to be simple reflections of the basic properties of an underlying hyperbolic geometry. Heterogeneity, measured in terms of the power-law degree distribution exponent, is a function of the negative curvature of the hyperbolic space, while clustering reflects its metric property."

"In this paper, we tackle the problem of innovation spreading from a modeling point of view. We consider a networked system of individuals, with a competition between two groups. We show its relation to the innovation spreading issues. We introduce an abstract model and show how it can be interpreted in this framework, as well as what conclusions we can draw form it. We further explain how model-derived conclusions can help to investigate the original problem, as well as other, similar problems. The model is an agent-based model assuming simple binary attributes of those agents. It uses a majority dynamics (Ising model to be exact), meaning that individuals attempt to be similar to the majority of their peers, barring the occasional purely individual decisions that are modeled as random. We show that this simplistic model can be related to the decision-making during innovation adoption processes. …"

"Networks portray a multitude of interactions through which people meet, ideas are spread, and infectious diseases propagate within a society. Identifying the most efficient "spreaders" in a network is an important step to optimize the use of available resources and ensure the more efficient spread of information. Here we show that, in contrast to common belief, the most influential spreaders in a social network do not correspond to the best connected people or to the most central people (high betweenness centrality). Instead, we find: (i) The most efficient spreaders are those located within the core of the network as identified by the k-shell decomposition analysis. (ii) When multiple spreaders are considered simultaneously, the distance between them becomes the crucial parameter that determines the extend of the spreading.…"

"As we have shown, Cluster Reverberation is a mechanism available to neural systems for robust short-term memory without synaptic learning. To the best of our knowledge, this is the first mechanism proposed which has these charac- teristics – essential for, say, sensory memory or certain working-memory tasks. All that is needed is for the network topology to be highly clustered or modu- lar, and for small groups of neurons to store one bit of information, as opposed to the conventional view which assumes one bit per neuron. Considering the enormous number of neurons in the brain, and the fact that real individual neu- rons are probably too noisy to store information reliably, these hypotheses do not seem farfetched.…"

"Strategy changes are an essential part of evolutionary games. Here we introduce a simple rule that, depending on the value of a single parameter $w$, influences the selection of players that are considered as potential sources of the new strategy. For positive $w$ players with high payoffs will be considered more likely, while for negative $w$ the opposite holds. Setting $w$ equal to zero returns the frequently adopted random selection of the opponent. We find that increasing the probability of adopting the strategy from the fittest player within reach, i.e. setting $w$ positive, promotes the evolution of cooperation. The robustness of this observation is tested against different levels of uncertainty in the strategy adoption process and for different interaction network. Since the evolution to widespread defection is tightly associated with cooperators having a lower fitness than defectors, the fact that positive values of $w$ facilitate cooperation is quite surprising. …"

"In this work we study a weak Prisoner's Dilemma game in which both strategies and update rules are subjected to evolutionary pressure. Interactions among agents are specified by complex topologies, and we consider both homogeneous and heterogeneous situations. We consider deterministic and stochastic update rules for the strategies, which in turn may consider single links or full context when selecting agents to copy from. Our results indicate that the co-evolutionary process preserves heterogeneous networks as a suitable framework for the emergence of cooperation. Furthermore, on those networks, the update rule leading to a larger fraction of cooperation, replicator dynamics, is selected during co-evolution.…We conclude that for a variety of topologies, the fact that the dynamics coevolves with the strategies leads in general to more cooperation in the weak Prisoner's Dilemma game."

"Dynamics of evolutionary games strongly depend on underlying networks. We study the coevolutionary prisoner's dilemma in which players change their local networks as well as strategies (i.e., cooperate or defect). This topic has been increasingly explored by many researchers. On the basis of active linking dynamics [J. M. Pacheco et al., J. Theor. Biol. 243, 437 (2006), J. M. Pacheco et al., Phys. Rev. Lett. 97, 258103 (2006)], we show that cooperation is enhanced fairly robustly. In particular, cooperation evolves when the payoff of the player is normalized by the number of neighbors; this is not the case in the evolutionary prisoner's dilemma on static networks."

"Biological networks of interacting agents exhibit similar topological properties for a wide range of scales, from cellular to ecological levels, suggesting the existence of a common evolutionary origin. A general evolutionary mechanism based on global stability has been proposed recently [J I Perotti, O V Billoni, F A Tamarit, D R Chialvo, S A Cannas, Phys. Rev. Lett. 103, 108701 (2009)]. This mechanism is incorporated into a model of a growing network of interacting agents in which each new agent's membership in the network is determined by the agent's effect on the network's global stability. We show that, out of this stability constraint, several topological properties observed in biological networks emerge in a self organized manner. The influence of the stability selection mechanism on the dynamics associated to the resulting network is analyzed as well."

"We introduce the heterogeneous voter model (HVM), in which each agent has its own intrinsic rate to change state, reflective of the heterogeneity of real people, and the partisan voter model (PVM), in which each agent has an innate and fixed preference for one of two possible opinion states. For the HVM, the time until consensus is reached is much longer than in the classic voter model. For the PVM in the mean-field limit, a population evolves to a "selfish" state, where each agent tends to be aligned with its internal preference. For finite populations, discrete fluctuations ultimately lead to consensus being reached in a time that scales exponentially with population size."

"Rotor-router networks are discrete analogues of continuous linear systems such as electrical circuits; they are also deter- ministic analogues of stochastic systems such as random walk processes. These analogies permit one to design rotor-router networks to compute numerical quantities associated with lin- ear and/or stochastic systems. These distributed computations can behave stably even in the presence of significant disruption."

"The study of networks has grown into a substantial interdisciplinary endeavor across the natural, social, and information sciences. Yet there have been very few attempts to investigate the interrelatedness of the different classes of networks studied by different disciplines. Here, we introduced a framework to establish a taxonomy of networks from various origins. The provision of this family tree not only helps understand the kinship of networks, but also facilitates the transfer of empirical analysis, theoretical modeling, and conceptual developments across disciplinary boundaries. The framework is based on probing the mesoscopic properties of networks, an important source of heterogeneity for their structure and function. Using our method, we computed a taxonomy for 752 individual networks and a separate taxonomy for 12 network classes. We also computed three within-class taxonomies for political, fungal, and financial networks, and found them to be insightful in each case."

"Systems whose organization displays causal asymmetry constraints, from evolutionary trees to river basins or transport networks, can be often described in terms of directed paths (causal flows) on a discrete state space. Such a set of paths defines a feed-forward, acyclic network. A key problem associated with these systems involves characterizing their intrinsic degree of path reversibility: given an end node in the graph, what is the uncertainty of recovering the process backwards until the origin? Here we propose a novel concept, \textit{topological reversibility}, which rigorously weigths such uncertainty in path dependency quantified as the minimum amount of information required to successfully revert a causal path.…"

"We consider the problem of computing a response curve for binary cellular automata -- that is, the curve describing the dependence of the density of ones after many iterations of the rule on the initial density of ones. We demonstrate how this problem could be approached using rule 130 as an example. For this rule, preimage sets of finite strings exhibit recognizable patterns, and it is therefore possible to compute both cardinalities of preimages of certain finite strings and probabilities of occurrence of these strings in a configuration obtained by iterating a random initial configuration $n$ times. Response curves can be rigorously calculated in both one- and two-dimensional versions of CA rule 130. We also discuss a special case of totally disordered initial configurations, that is, random configurations where the density of ones and zeros are equal to 1/2."

"We have embarked on a research program designed to develop universal models that can recreate empiri- cally observed phenomena in dynamic complex networks. We have shown that, using a suitable reinforced random walk on a “long-term” underlay network, one is able to produce instantaneous networks which reproduce qualitatively characteristic features of real world dynamic networks. This includes, in particular, the construc- tion of scale-free sub-networks of a scale-free “underlay” network, whose local hubs substantially differ from sub- network to sub-network and from those of the underlay.…"

"…For cyclic games with two players and three strategies, we show that the resulting deterministic dynamics crucially depends on the initial condition in a non–trivial way."

"The modeling of complex systems such as ecological or socio-economic systems can be very challenging. Although various modeling approaches exist, they are generally not compatible and mutually consistent, and empirical data often do not allow one to decide what model is the right one, the best one, or most appropriate one. Moreover, as the recent financial and economic crisis shows, relying on a single, idealized model can be very costly. This contribution tries to shed new light on problems that arise when complex systems are modeled. While the arguments can be transferred to many different systems, the related scientific challenges are illustrated for social, economic, and traffic systems. The contribution discusses issues that are sometimes overlooked and tries to overcome some frequent misunderstandings and controversies of the past.…"

"In real communication and transportation networks, the geographical positions of nodes are very important for the efficiency and the tolerance of connectivity. Considering spatially inhomogeneous positions of nodes according to a population, we introduce a multi-scale quartered (MSQ) network that is stochastically constructed by recursive subdivision of polygonal faces as a self-similar tiling. It has several advantages: the robustness of connectivity, the bounded short path lengths, and the shortest distance routing algorithm in a distributive manner. Furthermore, we show that the MSQ network is more efficient with shorter link lengths and more suitable with lower load for avoiding traffic congestion than other geographical networks which have various topologies ranging from river to scale-free networks. These results will be useful for providing an insight into the future design of ad hoc network infrastructures."

"We propose a degree-based coarse graining approach that not just accelerates the evaluation of dynamics on complex networks, but also satisfies the consistency conditions for both equilibrium statistical distributions and nonequilibrium dynamical flows. For the Ising model and susceptible-infected-susceptible epidemic model, we introduce these required conditions explicitly and further prove that they are satisfied by our coarse-grained network construction within the annealed network approximation. Finally, we numerically show that the phase transitions and fluctuations on the coarse-grained network are all in good agreements with those on the original one."

"Bacteria are the unseen majority on our planet, with millions of species and comprising most of the living protoplasm. While current methods enable in-depth study of a small number of communities, a simple tool for breadth studies of bacterial population composition in a large number of samples is lacking. We propose a novel approach for reconstruction of the composition of an unknown mixture of bacteria using a single Sanger-sequencing reaction of the mixture. This method is based on compressive sensing theory, which deals with reconstruction of a sparse signal using a small number of measurements. Utilizing the fact that in many cases each bacterial community is comprised of a small subset of the known bacterial species, we show the feasibility of this approach for determining the composition of a bacterial mixture.…"

"The Fermi Paradox is the apparent contradiction between the high probability extraterrestrial civilizations' existence and the lack of contact with such civilizations. In general, solutions to Fermi's paradox come down to either estimation of Drake equation parameters i.e. our guesses about the potential number of extraterrestrial civilizations or simulation of civilizations development in the universe. We consider a new type of cellular automata, that allows to analyze Fermi paradox. We introduce bonus stimulation model (BS-model) of development in cellular space (Universe) of objects (Civilizations). When civilizations get in touch they stimulate development each other, increasing their life time. We discovered nonlinear threshold behaviour of total volume of civilizations in universe and on the basis of our model we built analogue of Drake equation."

"Laboratory investigations have shown that a formal theory of fault-tolerance will be essential to harness nanoscale self-assembly as a medium of computation. Several researchers have voiced an intuition that self-assembly phenomena are related to the field of distributed computing. This paper formalizes some of that intuition. We construct tile assembly systems that are able to simulate the solution of the wait-free consensus problem in some distributed systems. (For potential future work, this may allow binding errors in tile assembly to be analyzed, and managed, with positive results in distributed computing, as a "blockage" in our tile assembly model is analogous to a crash failure in a distributed computing model.) …We show that solution of this strengthened consensus problem can be simulated by a two-dimensional tile assembly model only for two processes, whereas a three-dimensional tile assembly model can simulate its solution in a distributed system with any number of processes

"Genetic oscillators are a major theme of interest in the emerging field of synthetic biology. Until recently, most work has been carried out using intra-cellular oscillators, but this approach restricts the broader applicability of such systems. Motivated by a desire to develop large-scale, spatially-distributed cell-based computational systems, we present an initial design for a population-level oscillator which uses three different bacterial strains. Our system is based on the client-server model familiar to computer science, and uses quorum sensing for communication between nodes. We present the results of extensive in silico simulation tests, which confirm that our design is both feasible and robust."

Frankly, I've alway thought this, especially after some early "confusing" experiments that never got published because they were part of my first Ph.D. thesis research: "…We argue that the presence of only the frozen phase in the work of Kauffman et al. was due simply to the specific parametrization used, and is not an inherent feature of this class of functions. However, these networks are significantly more stable than the variants where all possible Boolean functions are allowed."

"The study of evolution of networks has received increased interest with the recent discovery that many real-world networks possess many things in common, in particular the manner of evolution of such networks. By adding a dimension of time to graph analysis, evolving graphs present opportunities and challenges to extract valuable information. This paper introduces the Evolving Graph Markup Language (EGML), an XML application for representing evolving graphs and related results. Along with EGML, a software tool is provided for the study of evolving graphs. New evolving graph drawing techniques based on the force-directed graph layout algorithm are also explored. Our evolving graph techniques reduce vertex movements between graph instances, so that an evolving graph can be viewed with smooth transitions"

"Here we propose a generic mechanism - networked buffering - for generating robust traits in complex systems that requires two basic conditions to be satisfied: 1) agents are versatile enough to perform more than one single functional role within a system and 2) agents are degenerate, i.e. there exists partial overlap in the functional capabilities of agents. Given these prerequisites, degenerate systems can readily produce a distributed systemic response to local perturbations. Reciprocally, excess resources related to a single function can indirectly support multiple unrelated functions within a degenerate system.…"

"This paper presents a complex systems overview of a power grid network. In recent years, concerns about the robustness of the power grid have grown because of several cascading outages in different parts of the world. In this paper, cascading effect has been simulated on three different networks, the IEEE 300 bus test system, the IEEE 118 bus test system, and the WSCC 179 bus equivalent model, using the DC Power Flow Model. Power Degradation has been discussed as a measure to estimate the damage to the network, in terms of load loss and node loss. A network generator has been developed to generate graphs with characteristics similar to the IEEE standard networks and the generated graphs are then … have been suggested."

Sometimes physics is just pretty.

"The human immune system has numerous properties that make it ripe for exploitation in the computational domain, such as robustness and fault tolerance, and many different algorithms, collectively termed Artificial Immune Systems (AIS), have been inspired by it. Two generations of AIS are currently in use, with the first generation relying on simplified immune models and the second generation utilising interdisciplinary collaboration to develop a deeper understanding of the immune system and hence produce more complex models. Both generations of algorithms have been successfully applied to a variety of problems, including anomaly detection, pattern recognition, optimisation and robotics.…"

"… Using wireless sensor network technology, we obtained high-resolution data of CPIs during a typical day at an American high school, permitting the reconstruction of the social network relevant for infectious disease transmission. At a 94% coverage, we collected 762,868 CPIs at a maximal distance of 3 meters among 788 individuals. The data revealed a high density network with typical small world properties and a relatively homogenous distribution of both interaction time and interaction partners among subjects.…"

"We present a framework for simulating signal propagation in geometric networks (i.e. networks that can be mapped to geometric graphs in some space) and for developing algorithms that estimate (i.e. map) the state and functional topology of complex dynamic geometric net- works. Within the framework we define the key features typically present in such networks and of particular relevance to biological cellular neural networks: Dynamics, signaling, observation, and control. The framework is particularly well-suited for estimating functional connectivity in cellular neural networks from experimentally observable data, and has been implemented using graphics processing unit (GPU) high performance computing. Computationally, the framework can simulate cellular network signaling close to or faster than real time. We further propose a standard test set of networks to measure performance and compare different mapping algorithms."

"The prisoner's dilemma (PD) game is a simple model for understanding cooperative patterns in complex systems consisting of selfish individuals. Here, we study a PD game problem in scale-free networks containing hierarchically organized modules and controllable shortcuts connecting separated hubs. We find that cooperator clusters exhibit a percolation transition in the parameter space (p,b), where p is the occupation probability of shortcuts and b is the temptation payoff in the PD game. The cluster size distribution follows a power law at the transition point. Such a critical behavior, resulting from the combined effect of stochastic processes in the PD game and the heterogeneous structure of complex networks, illustrates the diversity of social relationships and the self-organization of cooperator communities in real-world systems."

"Evolutionary game dynamics in finite populations is typically subject to noise, inducing effects which are not present in deterministic systems, including fixation and extinction. In the first part of this paper we investigate the phenomenon of drift reversal in finite populations, taking into account that drift is a local quantity in strategy space. Secondly, we study a simple imitation dynamics, and show that it can lead to fixation at internal mixed-strategy fixed points even in finite populations. Imitation in infinite populations is adequately described by conventional replicator dynamics, and these equations are known to have internal fixed points. Internal absorption in finite populations on the other hand is a novel dynamic phenomenon. Due to an outward drift in finite populations this type of dynamic arrest is not found in other commonly studied microscopic dynamics, not even in those with the same deterministic replicator limit as imitation."

wondering if there are suitable strategies for autonomous vehicles in traffic which would postpone the transition to jamming, but not increase danger of collision…

ME: what would 'well-designed' biochemical nets look like, if you evolved them in silico?

"The reliability with which a network can transmit a particular frequency component of the input signal tra- jectory is determined by the gain-to-noise ratio of the net- work as a function of frequency. For systems that obey the spectral addition rule [32], that is those for which downstream reactions do not affect the input signal, the gain-to-noise ratio is an intrinsic property of the processing network. For networks that do not obey the spectral addition rule the gain-to-noise ratio will be dependent on the statistics of the input signal. The mutual information between input and output signals, which quantifies the information which can be transmitted about a particular input ensemble, also depends on the particular choice of the input signal.…"

"Evolutionary adaptation is the process that increases the fit of a population to the fitness landscape it inhabits. As a consequence, evolutionary dynamics is shaped, constrained, and channeled, by that fitness landscape. Much work has been expended to understand the evolutionary dynamics of adapting populations, but much less is known about the structure of the landscapes. Here, we study the global and local structure of complex fitness landscapes of interacting loci that describe protein folds or sets of interacting genes forming pathways or modules. We find that in these landscapes, high peaks are more likely to be found near other high peaks, corroborating Kauffman's "Massif Central" hypothesis. We study the clusters of peaks as a function of the ruggedness of the landscape and find that this clustering allows peaks to form interconnected networks.…"

"The feed-forward relationship naturally observed in time-dependent processes and in a diverse number of real systems -such as some food-webs and electronic and neural wiring- can be described in terms of so-called directed acyclic graphs (DAGs). An important ingredient of the analysis of such networks is a proper comparison of their observed architecture against an ensemble of randomized graphs, thereby quantifying the {\em randomness} of the real systems with respect to suitable null models. This approximation is particularly relevant when the finite size and/or large connectivity of real systems make inadequate a comparison with the predictions obtained from the so-called {\em configuration model}. In this paper we analyze four methods of DAG randomization as defined by the desired combination of topological invariants (directed and undirected degree sequence and component distributions) aimed to be preserved.…"

"We give an algorithm that computes the final state of certain growth models without computing all intermediate states. Our technique is based on a "least action principle" which characterizes the odometer function of the growth process. Starting from an educated guess for the odometer, we successively correct under- and overestimates and provably arrive at the correct final state. The degree of speedup depends on the accuracy of the initial guess.
Determining the size of the boundary fluctuations in internal diffusion-limited aggregation is a long-standing open problem in statistical physics. As an application of our method, we calculate the size of fluctuations over two orders of magnitude beyond previous simulations. Our data strongly support the conjecture that the fluctuations are logarithmic in the radius."

"Thanks to recent technological advances, it is now possible to track with an unprecedented precision and for long periods of time the movement patterns of many living organisms in their habitat. The increasing amount of data available on single trajectories offers the possibility of understanding how animals move and of testing basic movement models. Random walks have long represented the main description for micro-organisms and have also been useful to understand the foraging behaviour of large animals. Nevertheless, most vertebrates, in particular humans and other primates, rely on sophisticated cognitive tools such as spatial maps, episodic memory and travel cost discounting. These properties call for other modeling approaches of mobility patterns. We propose a foraging framework where a learning mobile agent uses a combination of memory-based and random steps. We investigate how advantageous it is to use memory for exploiting resources in heterogeneous and changing environments.…"

"Many functions have been recently defined to assess the similarity among networks as tools for quantitative comparison. They stem from very different frameworks - and they are tuned for dealing with different situations. Here we show an overview of the spectral distances, highlighting their behavior in some basic cases of static and dynamic synthetic and real networks."

"The obtained results and trends suggest a number of further investigations. For instance, it would be interest- ing to consider other network models and measurements, as well as to assess the effect of different types of hard- ware, compilers and operating systems."

"In many networks, vertices have hidden attributes, or types, that are correlated with the networks topology. If the topology is known but these attributes are not, and if learning the attributes is costly, we need a method for choosing which vertex to query in order to learn as much as possible about the attributes of the other vertices. We assume the network is generated by a stochastic block model, but we make no assumptions about its assortativity or disassortativity. We choose which vertex to query using two methods: 1) maximizing the mutual information between its attributes and those of the others (a well-known approach in active learning) and 2) maximizing the average agreement between two independent samples of the conditional Gibbs distribution. Experimental results show that both these methods do much better than simple heuristics. They also consistently identify certain vertices as important by querying them early on."

"We propose a fluctuation analysis to quantify spatial correlations in complex networks. The approach considers the sequences of degrees along shortest paths in the networks and quantifies the fluctuations in analogy to time series. In this work, the Barabasi-Albert (BA) model, the Cayley tree at the percolation transition, a fractal network model, and examples of real-world networks are studied. While the fluctuation functions for the BA model show exponential decay, in the case of the Cayley tree and the fractal network model the fluctuation functions display a power-law behavior. The fractal network model comprises long-range anti-correlations. The results suggest that the fluctuation exponent provides complementary information to the fractal dimension."

"Community structure is one of the key properties of complex networks and plays a crucial role in their topology and function. While an impressive amount of work has been done on the issue of community detection, very little attention has been so far devoted to the investigation of communities in real networks. We present a systematic empirical analysis of the statistical properties of communities in large information, communication, technological, biological, and social networks. We find that the mesoscopic organization of networks of the same category is remarkably similar. This is reflected in several characteristics of community structure, which can be used as ``fingerprints'' of specific network categories.…"

"Adaptive networks have been recently introduced in the context of disease propagation on complex networks. They account for the mutual interaction between the network topology and the states of the nodes. Until now, existing models have been analyzed using low-complexity analytic formalisms, revealing nevertheless some novel dynamical features. However, current methods have failed to reproduce with accuracy the simultaneous time evolution of the disease and the underlying network topology. In the framework of the adaptive SIS model of Gross et al. [Gross et al., Phys. Rev. Lett. 96, 208701 (2006)], we introduce an improved compartmental formalism able to handle this coevolutionary task successfully. With this approach, we analyze the interplay and outcomes of both dynamical elements, process and structure, on adaptive networks featuring different degree distributions at the initial stage."

"Heterogeneity in the degree distribution is known to suppress global synchronization in complex networks of symmetrically coupled oscillators. Scale-free networks present strong heterogeneity, there are a few highly connected nodes, termed hubs, while the majority of nodes has only a few connections. We show that a stable partially synchronized state may take place in scale-free networks: hubs undergo a transition to synchronization while the remaining nodes are unsynchronized. This phenomenon may occur in any large heterogeneous network, regardless of the network global synchronization properties. We provide theory and numerical evidence to establish this phenomenon."