Optimal network topology for responsive collective behavior.
ABSTRACT: Animals, humans, and multi-robot systems operate in dynamic environments, where the ability to respond to changing circumstances is paramount. An effective collective response requires suitable information transfer among agents and thus critically depends on the interaction network. To investigate the influence of the network topology on collective response, we consider an archetypal model of distributed decision-making and study the capacity of the system to follow a driving signal for varying topologies and system sizes. Experiments with a swarm of robots reveal a nontrivial relationship between frequency of the driving signal and optimal network topology. The emergent collective response to slow-changing perturbations increases with the degree of the interaction network, but the opposite is true for the response to fast-changing ones. These results have far-reaching implications for the design and understanding of distributed systems: a dynamic rewiring of the interaction network is essential to effective collective operations at different time scales.
Project description:We study how the structure of the interaction network affects self-organized collective motion in two minimal models of self-propelled agents: the Vicsek model and the Active-Elastic (AE) model. We perform simulations with topologies that interpolate between a nearest-neighbour network and random networks with different degree distributions to analyse the relationship between the interaction topology and the resilience to noise of the ordered state. For the Vicsek case, we find that a higher fraction of random connections with homogeneous or power-law degree distribution increases the critical noise, and thus the resilience to noise, as expected due to small-world effects. Surprisingly, for the AE model, a higher fraction of random links with power-law degree distribution can decrease this resilience, despite most links being long-range. We explain this effect through a simple mechanical analogy, arguing that the larger presence of agents with few connections contributes localized low-energy modes that are easily excited by noise, thus hindering the collective dynamics. These results demonstrate the strong effects of the interaction topology on self-organization. Our work suggests potential roles of the interaction network structure in biological collective behaviour and could also help improve decentralized swarm robotics control and other distributed consensus systems.
Project description:Across physics, biology, and engineering, the collective dynamics of oscillatory networks often evolve into self-organized operating states. How such networks respond to external fluctuating signals fundamentally underlies their function, yet is not well understood. Here, we present a theory of dynamic network response patterns and reveal how distributed resonance patterns emerge in oscillatory networks once the dynamics of the oscillatory units become more than one-dimensional. The network resonances are topology specific and emerge at an intermediate frequency content of the input signals, between global yet homogeneous responses at low frequencies and localized responses at high frequencies. Our analysis reveals why these patterns arise and where in the network they are most prominent. These results may thus provide general theoretical insights into how fluctuating signals induce response patterns in networked systems and simultaneously help to develop practical guiding principles for real-world network design and control.
Project description:Social networks continuously change as new ties are created and existing ones fade. It is widely acknowledged that our social embedding has a substantial impact on what information we receive and how we form beliefs and make decisions. However, most empirical studies on the role of social networks in collective intelligence have overlooked the dynamic nature of social networks and its role in fostering adaptive collective intelligence. Therefore, little is known about how groups of individuals dynamically modify their local connections and, accordingly, the topology of the network of interactions to respond to changing environmental conditions. In this paper, we address this question through a series of behavioral experiments and supporting simulations. Our results reveal that, in the presence of plasticity and feedback, social networks can adapt to biased and changing information environments and produce collective estimates that are more accurate than their best-performing member. To explain these results, we explore two mechanisms: 1) a global-adaptation mechanism where the structural connectivity of the network itself changes such that it amplifies the estimates of high-performing members within the group (i.e., the network "edges" encode the computation); and 2) a local-adaptation mechanism where accurate individuals are more resistant to social influence (i.e., adjustments to the attributes of the "node" in the network); therefore, their initial belief is disproportionately weighted in the collective estimate. Our findings substantiate the role of social-network plasticity and feedback as key adaptive mechanisms for refining individual and collective judgments.
Project description:Social interaction increases significantly the performance of a wide range of cooperative systems. However, evidence that natural swarms limit the number of interactions suggests potentially detrimental consequences of excessive interaction. Using a canonical model of collective motion, we find that the collective response to a dynamic localized perturbation-emulating a predator attack-is hindered when the number of interacting neighbors exceeds a certain threshold. Specifically, the effectiveness in avoiding the predator is enhanced by large integrated correlations, which are known to peak at a given level of interagent interaction. From the network-theoretic perspective, we uncover the same interplay between number of connections and effectiveness in group-level response for two distinct decision-making models of distributed consensus operating over a range of static networks. The effect of the number of connections on the collective response critically depends on the dynamics of the perturbation. While adding more connections improves the response to slow perturbations, the opposite is true for fast ones. These results have far-reaching implications for the design of artificial swarms or interaction networks.
Project description:Revealing physical interactions in complex systems from observed collective dynamics constitutes a fundamental inverse problem in science. Current reconstruction methods require access to a system's model or dynamical data at a level of detail often not available. We exploit changes in invariant measures, in particular distributions of sampled states of the system in response to driving signals, and use compressed sensing to reveal physical interaction networks. Dynamical observations following driving suffice to infer physical connectivity even if they are temporally disordered, are acquired at large sampling intervals, and stem from different experiments. Testing various nonlinear dynamic processes emerging on artificial and real network topologies indicates high reconstruction quality for existence as well as type of interactions. These results advance our ability to reveal physical interaction networks in complex synthetic and natural systems.
Project description:The default mode network (DMN) is a complex dynamic network that is critical for understanding cognitive function. However, whether dynamic topological reconfiguration of the DMN occurs across different brain states, and whether this potential reorganization is associated with prior learning or experience is unclear. To better understand the temporally changing topology of the DMN, we investigated both nodal and global dynamic DMN-topology metrics across different brain states. We found that DMN topology changes over time and those different patterns are associated with different brain states. Further, the nodal and global topological organization can be rebuilt by different brain states. These results indicate that the post-task, resting-state topology of the brain network is dynamically altered as a function of immediately prior cognitive experience, and that these modulated networks are assembled in the subsequent state. Together, these findings suggest that the changing topology of the DMN may play an important role in characterizing brain states.
Project description:Organizations create networks with one another, and these networks may in turn shape the organizations involved. Until recently, such complex dynamic processes could not be rigorously empirically analyzed because of a lack of suitable modeling and validation methods. Using stochastic actor-oriented models and unique longitudinal survey data on the changing structure of interfirm production networks in the automotive industry in Japan, this paper illustrates how to quantitatively assess and validate (1) the dynamic micro-mechanism by which organizations form their networks and (2) the role of the dynamic network structures in organizational performance. The applied model helps to explain the endogenous processes behind the recent diversification of Japanese automobile production networks. Specifically, testing the effects of network topology and network diffusion on organizational performance, the novel modeling framework enables us to discern that the restructuring of interorganizational networks led to the increase of Japanese automakers' production per employee, and not the reverse. Traditional models that do not allow for interaction between interorganizational structure and organizational agency misrepresent this mechanism.
Project description:The need to make fast decisions under risky and uncertain conditions is a widespread problem in the natural world. While there has been extensive work on how individual organisms dynamically modify their behavior to respond appropriately to changing environmental conditions (and how this is encoded in the brain), we know remarkably little about the corresponding aspects of collective information processing in animal groups. For example, many groups appear to show increased "sensitivity" in the presence of perceived threat, as evidenced by the increased frequency and magnitude of repeated cascading waves of behavioral change often observed in fish schools and bird flocks under such circumstances. How such context-dependent changes in collective sensitivity are mediated, however, is unknown. Here we address this question using schooling fish as a model system, focusing on 2 nonexclusive hypotheses: 1) that changes in collective responsiveness result from changes in how individuals respond to social cues (i.e., changes to the properties of the "nodes" in the social network), and 2) that they result from changes made to the structural connectivity of the network itself (i.e., the computation is encoded in the "edges" of the network). We find that despite the fact that perceived risk increases the probability for individuals to initiate an alarm, the context-dependent change in collective sensitivity predominantly results not from changes in how individuals respond to social cues, but instead from how individuals modify the spatial structure, and correspondingly the topology of the network of interactions, within the group. Risk is thus encoded as a collective property, emphasizing that in group-living species individual fitness can depend strongly on coupling between scales of behavioral organization.
Project description:Cellular networks are highly dynamic in their function, yet evolutionarily conserved in their core network motifs or topologies. Understanding functional tunability and robustness of network motifs to small perturbations in function and structure is vital to our ability to synthesize controllable circuits. In establishing core sets of network motifs, we selected topologies that are overrepresented in mammalian networks, including the linear, feedback, feed-forward, and bifan circuits. Static and dynamic tunability of network motifs were defined as the motif ability to respectively attain steady-state or transient outputs in response to pre-defined input stimuli. Detailed computational analysis suggested that static tunability is insensitive to the circuit topology, since all of the motifs displayed similar ability to attain predefined steady-state outputs in response to constant inputs. Dynamic tunability, in contrast, was tightly dependent on circuit topology, with some motifs performing superiorly in achieving observed time-course outputs. Finally, we mapped dynamic tunability onto motif topologies to determine robustness of motif structures to changes in topology and identify design principles for the rational assembly of robust synthetic networks.
Project description:Complex networks characterize the nature of internal/external interactions in real-world systems including social, economic, biological, ecological, and technological networks. Two issues keep as obstacles to fulfilling control of large-scale networks: structural controllability which describes the ability to guide a dynamical system from any initial state to any desired final state in finite time, with a suitable choice of inputs; and optimal control, which is a typical control approach to minimize the cost for driving the network to a predefined state with a given number of control inputs. For large complex networks without global information of network topology, both problems remain essentially open. Here we combine graph theory and control theory for tackling the two problems in one go, using only local network topology information. For the structural controllability problem, a distributed local-game matching method is proposed, where every node plays a simple Bayesian game with local information and local interactions with adjacent nodes, ensuring a suboptimal solution at a linear complexity. Starring from any structural controllability solution, a minimizing longest control path method can efficiently reach a good solution for the optimal control in large networks. Our results provide solutions for distributed complex network control and demonstrate a way to link the structural controllability and optimal control together.