The behavior of many real-world phenomena can be modeled by non-linear dynamical systems whereby a latent system state is observed through a filter. We are interested in interacting subsystems of this form, which we model by a set of coupled maps as a synchronous update graph dynamical system. Specifically, we study the structure learning problem for spatially distributed dynamical systems coupled via a directed acyclic graph. Unlike established structure learning procedures that find locally maximum posterior probabilities of a network structure containing latent variables, our work exploits the properties of dynamical systems to compute globally optimal approximations of these distributions. We arrive at this result by the use of time delay embedding theorems. Taking an information-theoretic perspective, we show that the log-likelihood has an intuitive interpretation in terms of information transfer.

 

 

An Information Criterion for Inferring Coupling of Distributed Dynamical Systems

Oliver M. Cliff, Mikhail Prokopenko and Robert Fitch

Front. Robot. AI, 28 November 2016 | http://dx.doi.org/10.3389/frobt.2016.00071

Source: journal.frontiersin.org

Community detection, the decomposition of a graph into meaningful building blocks, has been a core research topic in network science over the past years. Since a precise notion of what constitutes a community has remained evasive, community detection algorithms have often been compared on benchmark graphs with a particular form of community structure, and classified based on the mathematical techniques they employ. However, this can be misleading because apparent similarities in their mathematical machinery can disguise entirely different objectives. Here we provide a focused review of the different motivations that underpin community detection. This problem-driven classification is useful in applied network science, where it is important to select an appropriate algorithm for the given purpose. Moreover, highlighting the different facets of community detection also delineates the many lines of research, and points out open directions and avenues for future research.

 

The many facets of community detection in complex networks
Michael T. Schaub, Jean-Charles Delvenne, Martin Rosvall, Renaud Lambiotte

Source: arxiv.org

Ties between individuals on a social network can represent different dimensions of interactions, and the spreading of information and innovations on these networks could potentially be driven by some dimensions more than by others. In this paper we investigate this issue by studying the diffusion of microfinance within rural India villages and accounting for the whole multilayer structure of the underlying social networks. We define a new measure of node centrality, diffusion versatility, and show that this is a better predictor of microfinance participation rate than previously introduced measures defined on aggregated single-layer social networks. Moreover, we untangle the role played by each social dimension and find that the most prominent role is played by the nodes that are central on layers concerned with trust, shedding new light on the key triggers of the diffusion of microfinance.

 

Untangling the role of diverse social dimensions in the diffusion of microfinance
Elisa Omodei and Alex Arenas
Applied Network Science20161:14
DOI: 10.1007/s41109-016-0016-x

Source: appliednetsci.springeropen.com

The flocking of animals is often modelled as a dynamical system, in which individuals are represented as particles whose interactions are determined by the current state of the system. Many animals, however, including humans, have predictive capabilities, and presumably base their behavioural decisions—at least partially—upon an anticipated state of their environment. We explore a minimal version of this idea in the context of particles that interact according to a pairwise potential. Anticipation enters the picture by calculating the interparticle forces from linear extrapolation of the positions some time τ into the future. Our analysis shows that for intermediate values of τ the particles rapidly form milling structures, induced by velocity alignment that emerges from the prediction. We also show that for τ>0, any dynamical system governed by an even potential becomes dissipative. These results suggest that anticipation could play an important role in collective behaviour, since it induces pattern formation and stabilises the dynamics of the system.

 

 

The impact of anticipation in dynamical systems
P. Gerlee, K. Tunstrøm, T. Lundh, B. Wennberg

Source: arxiv.org

Many networks are used to transfer information or goods, in other words, they are navigated. The larger the network, the more difficult it is to navigate efficiently. Indeed, information routing in the Internet faces serious scalability problems due to its rapid growth, recently accelerated by the rise of the Internet of Things. Large networks like the Internet can be navigated efficiently if nodes, or agents, actively forward information based on hidden maps underlying these systems. However, in reality most agents will deny to forward messages, which has a cost, and navigation is impossible. Can we design appropriate incentives that lead to participation and global navigability? Here, we present an evolutionary game where agents share the value generated by successful delivery of information or goods. We show that global navigability can emerge, but its complete breakdown is possible as well. Furthermore, we show that the system tends to self-organize into local clusters of agents who participate in the navigation. This organizational principle can be exploited to favor the emergence of global navigability in the system.

 

Collective navigation of complex networks: Participatory greedy routing

Kaj-Kolja Kleineberg, Dirk Helbing

Source: arxiv.org