Collective dynamics of phase-repulsive oscillators solves graph coloring problem.

We show how to couple phase-oscillators on a graph so that collective dynamics "searches" for the coloring of that graph as it relaxes toward the dynamical equilibrium. This translates a combinatorial optimization problem (graph coloring) into a functional optimization problem (finding and evaluating the global minimum of dynamical non-equilibrium potential, done by the natural system's evolution). Using a sample of graphs, we show that our method can serve as a viable alternative to the traditional combinatorial algorithms. Moreover, we show that, with the same computational cost, our method efficiently solves the harder problem of improper coloring of weighed graphs.

A practical method for estimating coupling functions in complex dynamical systems.

A foremost challenge in modern network science is the inverse problem of reconstruction (inference) of coupling equations and network topology from the measurements of the network dynamics. Of particular interest are the methods that can operate on real (empirical) data without interfering with the system. One such earlier attempt (Tokuda et al. 2007 Phys. Rev. Lett. 99, 064101. (doi:10.1103/PhysRevLett.99.064101)) was a method suited for general limit-cycle oscillators, yielding both oscillators' natural frequencies and coupling functions between them (phase equations) from empirically measured time series. The present paper reviews the above method in a way comprehensive to domain-scientists other than physics. It also presents applications of the method to (i) detection of the network connectivity, (ii) inference of the phase sensitivity function, (iii) approximation of the interaction among phase-coherent chaotic oscillators, and (iv) experimental data from a forced Van der Pol electric circuit. This reaffirms the range of applicability of the method for reconstructing coupling functions and makes it accessible to a much wider scientific community. This article is part of the theme issue 'Coupling functions: dynamical interaction mechanisms in the physical, biological and social sciences'.

Reconstructing dynamical networks via feature ranking.

Empirical data on real complex systems are becoming increasingly available. Parallel to this is the need for new methods of reconstructing (inferring) the structure of networks from time-resolved observations of their node-dynamics. The methods based on physical insights often rely on strong assumptions about the properties and dynamics of the scrutinized network. Here, we use the insights from machine learning to design a new method of network reconstruction that essentially makes no such assumptions. Specifically, we interpret the available trajectories (data) as "features" and use two independent feature ranking approaches-Random Forest and RReliefF-to rank the importance of each node for predicting the value of each other node, which yields the reconstructed adjacency matrix. We show that our method is fairly robust to coupling strength, system size, trajectory length, and noise. We also find that the reconstruction quality strongly depends on the dynamical regime.

Ergodic theory and visualization. II. Fourier mesochronic plots visualize (quasi)periodic sets.

We present an application and analysis of a visualization method for measure-preserving dynamical systems introduced by I. Mezic and A. Banaszuk [Physica D 197, 101 (2004)], based on frequency analysis and Koopman operator theory. This extends our earlier work on visualization of ergodic partition [Z. Levnajic and I. Mezic, Chaos 20, 033114 (2010)]. Our method employs the concept of Fourier time average [I. Mezic and A. Banaszuk, Physica D 197, 101 (2004)], and is realized as a computational algorithms for visualization of periodic and quasi-periodic sets in the phase space. The complement of periodic phase space partition contains chaotic zone, and we show how to identify it. The range of method's applicability is illustrated using well-known Chirikov standard map, while its potential in illuminating higher-dimensional dynamics is presented by studying the Froeschlé map and the Extended Standard Map.

Self-organization in Slovenian public spending.

Private businesses are often entrusted with public contracts, wherein public money is allocated to a private company. This process raises concerns about transparency, even in the most developed democracies. But are there any regularities guiding this process? Do all private companies benefit equally from the state budgets? Here, we tackle these questions focusing on the case of Slovenia, which keeps excellent records of this kind of public spending. We examine a dataset detailing every transfer of public money to the private sector from January 2003 to May 2020. During this time, Slovenia has conducted business with no less than 248 989 private companies. We find that the cumulative distribution of money received per company can be reasonably well explained by a power-law or lognormal fit. We also show evidence for the first-mover advantage, and determine that companies receive new funding in a way that is roughly linear over time. These results indicate that, despite all human factors involved, Slovenian public spending is at least to some extent regulated by emergent self-organizing principles.

Terrorist attacks sharpen the binary perception of "Us" vs. "Them".

Terrorist attacks not only harm citizens but also shift their attention, which has long-lasting impacts on public opinion and government policies. Yet measuring the changes in public attention beyond media coverage has been methodologically challenging. Here we approach this problem by starting from Wikipedia's répertoire of 5.8 million articles and a sample of 15 recent terrorist attacks. We deploy a complex exclusion procedure to identify topics and themes that consistently received a significant increase in attention due to these incidents. Examining their contents reveals a clear picture: terrorist attacks foster establishing a sharp boundary between "Us" (the target society) and "Them" (the terrorist as the enemy). In the midst of this, one seeks to construct identities of both sides. This triggers curiosity to learn more about "Them" and soul-search for a clearer understanding of "Us". This systematic analysis of public reactions to disruptive events could help mitigate their societal consequences.

Network reconstruction from random phase resetting.

We propose a novel method of reconstructing the topology and interaction functions for a general oscillator network. An ensemble of initial phases and the corresponding instantaneous frequencies is constructed by repeating random phase resets of the system dynamics. The desired details of network structure are then revealed by appropriately averaging over the ensemble. The method is applicable for a wide class of networks with arbitrary emergent dynamics, including full synchrony.

Ergodic theory and visualization. I. Mesochronic plots for visualization of ergodic partition and invariant sets.

We present a computational study of a visualization method for invariant sets based on ergodic partition theory, first proposed by Mezic (Ph.D. thesis, Caltech, 1994) and Mezic and Wiggins [Chaos 9, 213 (1999)]. The algorithms for computation of the time averages of observables on phase space are developed and used to provide an approximation of the ergodic partition of the phase space. We term the graphical representation of this approximation--based on time averages of observables--a mesochronic plot (from Greek: meso--mean, chronos--time). The method is useful for identifying low-dimensional projections (e.g., two-dimensional slices) of invariant structures in phase spaces of dimensionality bigger than two. We also introduce the concept of the ergodic quotient space, obtained by assigning a point to every ergodic set, and provide an embedding method whose graphical representation we call the mesochronic scatter plot. We use the Chirikov standard map as a well-known and dynamically rich example in order to illustrate the implementation of our methods. In addition, we expose applications to other higher dimensional maps such as the Froéschle map for which we utilize our methods to analyze merging of resonances and, the three-dimensional extended standard map for which we study the conjecture on its ergodicity [I. Mezic, Physica D 154, 51 (2001)]. We extend the study in our next paper [Z. Levnajic and I. Mezic, e-print arXiv:0808.2182] by investigating the visualization of periodic sets using harmonic time averages. Both of these methods are related to eigenspace structure of the Koopman operator [I. Mezic and A. Banaszuk, Physica D 197, 101 (2004)].

Stability and chaos in coupled two-dimensional maps on gene regulatory network of bacterium E. coli.

The collective dynamics of coupled two-dimensional chaotic maps on complex networks is known to exhibit a rich variety of emergent properties which crucially depend on the underlying network topology. We investigate the collective motion of Chirikov standard maps interacting with time delay through directed links of gene regulatory network of bacterium Escherichia coli. Departures from strongly chaotic behavior of the isolated maps are studied in relation to different coupling forms and strengths. At smaller coupling intensities the network induces stable and coherent emergent dynamics. The unstable behavior appearing with increase of coupling strength remains confined within a connected subnetwork. For the appropriate coupling, network exhibits statistically robust self-organized dynamics in a weakly chaotic regime.

Chaotic dephasing in a double-slit scattering experiment.

We design a computational experiment in which a quantum particle tunnels into a billiard of variable shape and scatters out of it through a double-slit opening on the billiard's base. The interference patterns produced by the scattered probability currents for a range of energies are investigated in relation to the billiard's geometry which is connected to its classical integrability. Four billiards with hierarchical integrability levels are considered: integrable, pseudointegrable, weak-mixing, and strongly chaotic. In agreement with the earlier result by Casati and Prosen [Phys. Rev. A 72, 032111 (2005)], we find the billiard's integrability to have a crucial influence on the properties of the interference patterns. In the integrable case, most experiment outcomes are found to be consistent with the constructive interference occurring in the usual double-slit experiment. In contrast to this, nonintegrable billiards typically display asymmetric interference patterns of smaller visibility characterized by weakly correlated wave function values at the two slits. Our findings indicate an intrinsic connection between the classical integrability and the quantum dephasing, which is responsible for the destruction of interference.

Synchronization in time-varying random networks with vanishing connectivity.

A sufficiently connected topology linking the constituent units of a complex system is usually seen as a prerequisite for the emergence of collective phenomena such as synchronization. We present a random network of heterogeneous phase oscillators in which the links mediating the interactions are constantly rearranged with a characteristic timescale and, possibly, an extremely low instantaneous connectivity. We show that with strong coupling and sufficiently fast rewiring the network reaches partial synchronization even in the vanishing connectivity limit. In particular, we provide an approximate analytical argument, based on the comparison between the different characteristic timescales of our system in the low connectivity regime, which is able to predict the transition to synchronization threshold with satisfactory precision beyond the formal fast rewiring limit. We interpret our results as a qualitative mechanism for emergence of consensus in social communities. In particular, our result suggest that groups of individuals are capable of aligning their opinions under extremely sparse exchanges of views, which is reminiscent of fast communications that take place in the modern social media. Our results may also be relevant to characterize the onset of collective behavior in engineered systems of mobile units with limited wireless capabilities.

Heart Rhythm Analyzed via Shapelets Distinguishes Sleep From Awake.

Automatically determining when a person falls asleep from easily available vital signals is important, not just for medical applications but also for practical ones, such as traffic safety or smart homes. Heart dynamics and respiration cycle couple differently during sleep and awake. Specifically, respiratory modulation of heart rhythm or respiratory sinus arrhythmia (RSA) is more prominent during sleep, as both sleep and RSA are connected to strong vagal activity. The onset of sleep can be recognized or even predicted as the increase of cardio-respiratory coupling. Here, we employ this empirical fact to design a method for detecting the change of consciousness status (sleep/awake) based only on heart rate variability (HRV) data. Our method relies on quantifying the (self)similarity among shapelets - short chunks of HRV time series - whose "shapes" are related to the respiration cycle. To test our method, we examine the HRV data of 75 healthy individuals recorded with microsecond precision. We find distinctive patterns stable across age and sex, that are not only indicative of sleep and awake, but allow to pinpoint the change from awake to sleep almost immediately. More systematic analysis along these lines could lead to a reliable prediction of sleep.

Humans best judge how much to cooperate when facing hard problems in large groups.

We report the results of a game-theoretic experiment with human players who solve problems of increasing complexity by cooperating in groups of increasing size. Our experimental environment is set up to make it complicated for players to use rational calculation for making the cooperative decisions. This environment is directly translated into a computer simulation, from which we extract the collaboration strategy that leads to the maximal attainable score. Based on this, we measure the error that players make when estimating the benefits of collaboration, and find that humans massively underestimate these benefits when facing easy problems or working alone or in small groups. In contrast, when confronting hard problems or collaborating in large groups, humans accurately judge the best level of collaboration and easily achieve the maximal score. Our findings are independent on groups' composition and players' personal traits. We interpret them as varying degrees of usefulness of social heuristics, which seems to depend on the size of the involved group and the complexity of the situation.

Dynamics of Vagal Activity Due to Surgery and Subsequent Rehabilitation.

BACKGROUND: Vagal activity is critical for maintaining key body functions, including the stability of inflammatory control. Its weakening, such as in the aftermatch of a surgery, leaves the body vulnerable to diverse inflammatory conditions, including sepsis. METHODS: Vagal activity can be measured by the cardiorespiratory interaction known as respiratory sinus arrhythmia or high-frequency heart-rate variability (HRV). We examined the vagal dynamics before, during and after an orthopedic surgery. 39 patients had their HRV measured around the period of operation and during subsequent rehabilitation. Measurements were done during 24 h circadian cycles on ten specific days. For each patient, the circadian vagal activity was calculated from HRV data. RESULTS: Our results confirm the deteriorating effect of surgery on vagal activity. Patients with stronger pre-operative vagal activity suffer greater vagal withdrawal during the peri-operative phase, but benefit from stronger improvements during post-operative period, especially during the night. Rehabilitation seems not only to efficiently restore the vagal activity to pre-operative level, but in some cases to actually improve it. DISCUSSION: Our findings indicate that orthopedic rehabilitation has the potential to strengthen the vagal activity and hence boost inflammatory control. We conclude that providing a patient with a vagal reinforcement procedure prior to the surgery ("pre-habilitation") might be a beneficial strategy against post-operative complications. The study also shows the clinical usefulness of quantifying the cardiorespiratory interactions.

Inferring directed networks using a rank-based connectivity measure.

Inferring the topology of a network using the knowledge of the signals of each of the interacting units is key to understanding real-world systems. One way to address this problem is using data-driven methods like cross-correlation or mutual information. However, these measures lack the ability to distinguish the direction of coupling. Here, we use a rank-based nonlinear interdependence measure originally developed for pairs of signals. This measure not only allows one to measure the strength but also the direction of the coupling. Our results for a system of coupled Lorenz dynamics show that we are able to consistently infer the underlying network for a subrange of the coupling strength and link density. Furthermore, we report that the addition of dynamical noise can benefit the reconstruction. Finally, we show an application to multichannel electroencephalographic recordings from an epilepsy patient.

Robust clustering of languages across Wikipedia growth.

Wikipedia is the largest existing knowledge repository that is growing on a genuine crowdsourcing support. While the English Wikipedia is the most extensive and the most researched one with over 5 million articles, comparatively little is known about the behaviour and growth of the remaining 283 smaller Wikipedias, the smallest of which, Afar, has only one article. Here, we use a subset of these data, consisting of 14 962 different articles, each of which exists in 26 different languages, from Arabic to Ukrainian. We study the growth of Wikipedias in these languages over a time span of 15 years. We show that, while an average article follows a random path from one language to another, there exist six well-defined clusters of Wikipedias that share common growth patterns. The make-up of these clusters is remarkably robust against the method used for their determination, as we verify via four different clustering methods. Interestingly, the identified Wikipedia clusters have little correlation with language families and groups. Rather, the growth of Wikipedia across different languages is governed by different factors, ranging from similarities in culture to information literacy.

Algebraic Topology of Multi-Brain Connectivity Networks Reveals Dissimilarity in Functional Patterns during Spoken Communications.

Human behaviour in various circumstances mirrors the corresponding brain connectivity patterns, which are suitably represented by functional brain networks. While the objective analysis of these networks by graph theory tools deepened our understanding of brain functions, the multi-brain structures and connections underlying human social behaviour remain largely unexplored. In this study, we analyse the aggregate graph that maps coordination of EEG signals previously recorded during spoken communications in two groups of six listeners and two speakers. Applying an innovative approach based on the algebraic topology of graphs, we analyse higher-order topological complexes consisting of mutually interwoven cliques of a high order to which the identified functional connections organise. Our results reveal that the topological quantifiers provide new suitable measures for differences in the brain activity patterns and inter-brain synchronisation between speakers and listeners. Moreover, the higher topological complexity correlates with the listener's concentration to the story, confirmed by self-rating, and closeness to the speaker's brain activity pattern, which is measured by network-to-network distance. The connectivity structures of the frontal and parietal lobe consistently constitute distinct clusters, which extend across the listener's group. Formally, the topology quantifiers of the multi-brain communities exceed the sum of those of the participating individuals and also reflect the listener's rated attributes of the speaker and the narrated subject. In the broader context, the presented study exposes the relevance of higher topological structures (besides standard graph measures) for characterising functional brain networks under different stimuli.

Quantifying the consistency of scientific databases.

Science is a social process with far-reaching impact on our modern society. In recent years, for the first time we are able to scientifically study the science itself. This is enabled by massive amounts of data on scientific publications that is increasingly becoming available. The data is contained in several databases such as Web of Science or PubMed, maintained by various public and private entities. Unfortunately, these databases are not always consistent, which considerably hinders this study. Relying on the powerful framework of complex networks, we conduct a systematic analysis of the consistency among six major scientific databases. We found that identifying a single "best" database is far from easy. Nevertheless, our results indicate appreciable differences in mutual consistency of different databases, which we interpret as recipes for future bibliometric studies.

Modeling crowdsourcing as collective problem solving.

Crowdsourcing is a process of accumulating the ideas, thoughts or information from many independent participants, with aim to find the best solution for a given challenge. Modern information technologies allow for massive number of subjects to be involved in a more or less spontaneous way. Still, the full potentials of crowdsourcing are yet to be reached. We introduce a modeling framework through which we study the effectiveness of crowdsourcing in relation to the level of collectivism in facing the problem. Our findings reveal an intricate relationship between the number of participants and the difficulty of the problem, indicating the optimal size of the crowdsourced group. We discuss our results in the context of modern utilization of crowdsourcing.

What Motivates Us for Work? Intricate Web of Factors beyond Money and Prestige.

Efficiency at doing a certain task, at the workplace or otherwise, is strongly influenced by how motivated individuals are. Exploring new ways to motivate employees is often at the top of a company's agenda. Traditionally identified motivators in Western economies primarily include salary and prestige, often complemented by meaning, creation, challenge, ownership, identity, etc. We report the results of a survey conducted in Slovenia, involving an ensemble of highly educated employees from various public and private organizations. Employing new methodologies such as network analysis, we find that Slovenians are stimulated by an intricate web of interdependent factors, largely in contrast to the traditional understanding that mainly emphasizes money and prestige. In fact, these key motivators only weakly correlate with the demographic parameters. Unexpectedly, we found the evidence of a general optimism in Slovenian professional life - a tendency of the employees to look at the "bright side of things", thus seeing more clearly the benefits of having something than the drawbacks of not having it. We attribute these particularities to Slovenian recent history, which revolves around gradually embracing the Western (economic) values.