"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.”'