The Diffusion of Smoking: Association Between School Tobacco Policies and the Diffusion of Adolescent Smoking in 38 Schools in 6 Countries.

Social network research has evidenced the role of peer effects in the adoption of behaviours. Little is known, however, about whether policies affect how behaviours are shared in a network. To contribute to this literature, we apply the concept of diffusion centrality to school tobacco policies and adolescent smoking. Diffusion centrality is a measure of centrality which refers to a person's ability to diffuse a given property-in our case, smoking-related behaviours. We hypothesized that stronger school tobacco policies are associated with less diffusion centrality of smoking on school premises and of smoking in general. A whole network study was carried out in 2013 and 2016 among adolescents (n = 18,805) in 38 schools located in six European cities. Overall, diffusion centrality of smoking in general and of smoking on school premises significantly decreased over time. Diffusion centrality of smoking significantly decreased both in schools where the policy strengthened or softened over time, but for diffusion of smoking on school premises, this decrease was only significant in schools where it strengthened. Finally, stronger school tobacco policies were associated with lower diffusion centrality of smoking on school premises and of smoking in general, though to a lesser extent. With such policies, smoking may, therefore, become less prevalent, less popular, and less clustered, thereby lowering the risk of it spreading within networks in, and even outside the school.

State Aggregations in Markov Chains and Block Models of Networks.

We consider state-aggregation schemes for Markov chains from an information-theoretic perspective. Specifically, we consider aggregating the states of a Markov chain such that the mutual information of the aggregated states separated by T time steps is maximized. We show that for T=1 this recovers the maximum-likelihood estimator of the degree-corrected stochastic block model as a particular case, which enables us to explain certain features of the likelihood landscape of this generative network model from a dynamical lens. We further highlight how we can uncover coherent, long-range dynamical modules for which considering a timescale T≫1 is essential. We demonstrate our results using synthetic flows and real-world ocean currents, where we are able to recover the fundamental features of the surface currents of the oceans.

Multiscale mixing patterns in networks.

Assortative mixing in networks is the tendency for nodes with the same attributes, or metadata, to link to each other. It is a property often found in social networks, manifesting as a higher tendency of links occurring between people of the same age, race, or political belief. Quantifying the level of assortativity or disassortativity (the preference of linking to nodes with different attributes) can shed light on the organization of complex networks. It is common practice to measure the level of assortativity according to the assortativity coefficient, or modularity in the case of categorical metadata. This global value is the average level of assortativity across the network and may not be a representative statistic when mixing patterns are heterogeneous. For example, a social network spanning the globe may exhibit local differences in mixing patterns as a consequence of differences in cultural norms. Here, we introduce an approach to localize this global measure so that we can describe the assortativity, across multiple scales, at the node level. Consequently, we are able to capture and qualitatively evaluate the distribution of mixing patterns in the network. We find that, for many real-world networks, the distribution of assortativity is skewed, overdispersed, and multimodal. Our method provides a clearer lens through which we can more closely examine mixing patterns in networks.

Category Theory for Autonomous and Networked Dynamical Systems.

In this discussion paper we argue that category theory may play a useful role in formulating, and perhaps proving, results in ergodic theory, topogical dynamics and open systems theory (control theory). As examples, we show how to characterize Kolmogorov-Sinai, Shannon entropy and topological entropy as the unique functors to the nonnegative reals satisfying some natural conditions. We also provide a purely categorical proof of the existence of the maximal equicontinuous factor in topological dynamics. We then show how to define open systems (that can interact with their environment), interconnect them, and define control problems for them in a unified way.

Graph partitions and cluster synchronization in networks of oscillators.

Synchronization over networks depends strongly on the structure of the coupling between the oscillators. When the coupling presents certain regularities, the dynamics can be coarse-grained into clusters by means of External Equitable Partitions of the network graph and their associated quotient graphs. We exploit this graph-theoretical concept to study the phenomenon of cluster synchronization, in which different groups of nodes converge to distinct behaviors. We derive conditions and properties of networks in which such clustered behavior emerges and show that the ensuing dynamics is the result of the localization of the eigenvectors of the associated graph Laplacians linked to the existence of invariant subspaces. The framework is applied to both linear and non-linear models, first for the standard case of networks with positive edges, before being generalized to the case of signed networks with both positive and negative interactions. We illustrate our results with examples of both signed and unsigned graphs for consensus dynamics and for partial synchronization of oscillator networks under the master stability function as well as Kuramoto oscillators.

Thermokinetic relations.

Thermokinetic relations bound thermodynamic quantities, such as entropy production of a physical system over a certain time interval, with statistics of kinetic (or dynamical) observables, such as mean total variation of the observable over the time interval. We introduce a thermokinetic relation to bound the entropy production or the nonadiabatic (or excess) entropy production for overdamped Markov jump processes, possibly with time-varying rates and nonstationary distributions. For stationary cases, this bound is akin to a thermodynamic uncertainty relation, only involving absolute fluctuations rather than the mean square, thereby offering a better lower bound far from equilibrium. For nonstationary cases, this bound generalizes (classical) speed limits, where the kinetic term is not necessarily the activity (number of jumps) but any trajectory observable of interest. As a consequence, in the task of driving a system from a given probability distribution to another, we find a tradeoff between nonadiabatic entropy production and housekeeping entropy production: the latter can be increased to decrease the former, although to a limited extent. We also find constraints specific to constant-rate Markov processes. We illustrate our thermokinetic relations on simple examples from biophysics and computing devices.

Flow stability for dynamic community detection.

Many systems exhibit complex temporal dynamics due to the presence of different processes taking place simultaneously. An important task in these systems is to extract a simplified view of their time-dependent network of interactions. Community detection in temporal networks usually relies on aggregation over time windows or consider sequences of different stationary epochs. For dynamics-based methods, attempts to generalize static-network methodologies also face the fundamental difficulty that a stationary state of the dynamics does not always exist. Here, we derive a method based on a dynamical process evolving on the temporal network. Our method allows dynamics that do not reach a steady state and uncovers two sets of communities for a given time interval that accounts for the ordering of edges in forward and backward time. We show that our method provides a natural way to disentangle the different dynamical scales present in a system with synthetic and real-world examples.

Structure-informed functional connectivity driven by identifiable and state-specific control regions.

Describing how the brain anatomical wiring contributes to the emergence of coordinated neural activity underlying complex behavior remains challenging. Indeed, patterns of remote coactivations that adjust with the ongoing task-demand do not systematically match direct, static anatomical links. Here, we propose that observed coactivation patterns, known as functional connectivity (FC), can be explained by a controllable linear diffusion dynamics defined on the brain architecture. Our model, termed structure-informed FC, is based on the hypothesis that different sets of brain regions controlling the information flow on the anatomical wiring produce state-specific functional patterns. We thus introduce a principled framework for the identification of potential control centers in the brain. We find that well-defined, sparse, and robust sets of control regions, partially overlapping across several tasks and resting state, produce FC patterns comparable to empirical ones. Our findings suggest that controllability is a fundamental feature allowing the brain to reach different states.

The impact of human mobility data scales and processing on movement predictability.

Predictability of human movement is a theoretical upper bound for the accuracy of movement prediction models, which serves as a reference value showing how regular a dataset is and to what extent mobility can be predicted. Over the years, the predictability of various human mobility datasets was found to vary when estimated for differently processed datasets. Although attempts at the explanation of this variability have been made, the extent of these experiments was limited. In this study, we use high-precision movement trajectories of individuals to analyse how the way we represent the movement impacts its predictability and thus, the outcomes of analyses made on these data. We adopt a number of methods used in the last 11 years of research on human mobility and apply them to a wide range of spatio-temporal data scales, thoroughly analysing changes in predictability and produced data. We find that spatio-temporal resolution and data processing methods have a large impact on the predictability as well as geometrical and numerical properties of human mobility data, and we present their nonlinear dependencies.

Network constraints on the mixing patterns of binary node metadata.

We consider the network constraints on the bounds of the assortativity coefficient, which aims to quantify the tendency of nodes with the same attribute values to be connected. The assortativity coefficient can be considered as the Pearson's correlation coefficient of node metadata values across network edges and lies in the interval [-1,1]. However, properties of the network, such as degree distribution and the distribution of node metadata values, place constraints upon the attainable values of the assortativity coefficient. This is important as a particular value of assortativity may say as much about the network topology as about how the metadata are distributed over the network-a fact often overlooked in literature where the interpretation tends to focus simply on the propensity of similar nodes to link to each other, without any regard on the constraints posed by the topology. In this paper we quantify the effect that the topology has on the assortativity coefficient in the case of binary node metadata. Specifically, we look at the effect that the degree distribution, or the full topology, and the proportion of each metadata value has on the extremal values of the assortativity coefficient. We provide the means for obtaining bounds on the extremal values of assortativity for different settings and demonstrate that under certain conditions the maximum and minimum values of assortativity are severely limited, which may present issues in interpretation when these bounds are not considered.

Stable biomarker identification for predicting schizophrenia in the human connectome.

Schizophrenia, as a psychiatric disorder, has recognized brain alterations both at the structural and at the functional magnetic resonance imaging level. The developing field of connectomics has attracted much attention as it allows researchers to take advantage of powerful tools of network analysis in order to study structural and functional connectivity abnormalities in schizophrenia. Many methods have been proposed to identify biomarkers in schizophrenia, focusing mainly on improving the classification performance or performing statistical comparisons between groups. However, the stability of biomarkers selection has been for long overlooked in the connectomics field. In this study, we follow a machine learning approach where the identification of biomarkers is addressed as a feature selection problem for a classification task. We perform a recursive feature elimination and support vector machines (RFE-SVM) approach to identify the most meaningful biomarkers from the structural, functional, and multi-modal connectomes of healthy controls and patients. Furthermore, the stability of the retrieved biomarkers is assessed across different subsamplings of the dataset, allowing us to identify the affected core of the pathology. Considering our technique altogether, it demonstrates a principled way to achieve both accurate and stable biomarkers while highlighting the importance of multi-modal approaches to brain pathology as they tend to reveal complementary information.

Multiscale dynamical embeddings of complex networks.

Complex systems and relational data are often abstracted as dynamical processes on networks. To understand, predict, and control their behavior, a crucial step is to extract reduced descriptions of such networks. Inspired by notions from control theory, we propose a time-dependent dynamical similarity measure between nodes, which quantifies the effect a node-input has on the network. This dynamical similarity induces an embedding that can be employed for several analysis tasks. Here we focus on (i) dimensionality reduction, i.e., projecting nodes onto a low-dimensional space that captures dynamic similarity at different timescales, and (ii) how to exploit our embeddings to uncover functional modules. We exemplify our ideas through case studies focusing on directed networks without strong connectivity and signed networks. We further highlight how certain ideas from community detection can be generalized and linked to control theory, by using the here developed dynamical perspective.

Outbreak of multidrug-resistant tuberculosis in South Africa undetected by WHO-endorsed commercial tests: an observational study.

BACKGROUND: Global roll-out of rapid molecular assays is revolutionising the diagnosis of rifampicin resistance, predictive of multidrug-resistance, in tuberculosis. However, 30% of the multidrug-resistant (MDR) strains in an eSwatini study harboured the Ile491Phe mutation in the rpoB gene, which is associated with poor rifampicin-based treatment outcomes but is missed by commercial molecular assays or scored as susceptible by phenotypic drug-susceptibility testing deployed in South Africa. We evaluated the presence of Ile491Phe among South African tuberculosis isolates reported as isoniazid-monoresistant according to current national testing algorithms. METHODS: We screened records of 37 644 Mycobacterium tuberculosis positive cultures from four South African provinces, diagnosed at the National Health Laboratory Service-Dr George Mukhari Tertiary Laboratory, to identify isolates with rifampicin sensitivity and isoniazid resistance according to Xpert MTB/RIF, GenoType MTBDRplus, and BACTEC MGIT 960. Of 1823 isolates that met these criteria, 277 were randomly selected and screened for Ile491Phe with multiplex allele-specific PCR and Sanger sequencing of rpoB. Ile491Phe-positive strains (as well as 17 Ile491Phe-bearing isolates from the eSwatini study) were then tested by Deeplex-MycTB deep sequencing and whole-genome sequencing to evaluate their patterns of extensive resistance, transmission, and evolution. FINDINGS: Ile491Phe was identified in 37 (15%) of 249 samples with valid multiplex allele-specific PCR and sequencing results, thus reclassifying them as MDR. All 37 isolates were additionally identified as genotypically resistant to all first-line drugs by Deeplex-MycTB. Six of the South African isolates harboured four distinct mutations potentially associated with decreased bedaquiline sensitivity. Consistent with Deeplex-MycTB genotypic profiles, whole-genome sequencing revealed concurrent silent spread in South Africa of a MDR tuberculosis strain lineage extending from the eSwatini outbreak and at least another independently emerged Ile491Phe-bearing lineage. Whole-genome sequencing further suggested acquisition of mechanisms compensating for the Ile491Phe fitness cost, and of additional bedaquiline resistance following the introduction of this drug in South Africa. INTERPRETATION: A substantial number of MDR tuberculosis cases harbouring the Ile491Phe mutation in the rpoB gene in South Africa are missed by current diagnostic strategies, resulting in ineffective first-line treatment, continued amplification of drug resistance, and concurrent silent spread in the community. FUNDING: VLIR-UOS, National Research Foundation (South Africa), and INNOVIRIS.

Dissipative open systems theory as a foundation for the thermodynamics of linear systems.

In this paper, we advocate the use of open dynamical systems, i.e. systems sharing input and output variables with their environment, and the dissipativity theory initiated by Jan Willems as models of thermodynamical systems, at the microscopic and macroscopic level alike. We take linear systems as a study case, where we show how to derive a global Lyapunov function to analyse networks of interconnected systems. We define a suitable notion of dynamic non-equilibrium temperature that allows us to derive a discrete Fourier law ruling the exchange of heat between lumped, discrete-space systems, enriched with the Maxwell-Cattaneo correction. We complete these results by a brief recall of the steps that allow complete derivation of the dissipation and fluctuation in macroscopic systems (i.e. at the level of probability distributions) from lossless and deterministic systems.This article is part of the themed issue 'Horizons of cybernetical physics'.

The many facets of community detection in complex networks.

Community detection, the decomposition of a graph into essential 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 assortative community structure and classified based on the mathematical techniques they employ. However, this comparison can be misleading because apparent similarities in their mathematical machinery can disguise different goals and reasons for why we want to employ community detection in the first place. Here we provide a focused review of these 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.

Diffusion on networked systems is a question of time or structure.

Network science investigates the architecture of complex systems to understand their functional and dynamical properties. Structural patterns such as communities shape diffusive processes on networks. However, these results hold under the strong assumption that networks are static entities where temporal aspects can be neglected. Here we propose a generalized formalism for linear dynamics on complex networks, able to incorporate statistical properties of the timings at which events occur. We show that the diffusion dynamics is affected by the network community structure and by the temporal properties of waiting times between events. We identify the main mechanism--network structure, burstiness or fat tails of waiting times--determining the relaxation times of stochastic processes on temporal networks, in the absence of temporal-structure correlations. We identify situations when fine-scale structure can be discarded from the description of the dynamics or, conversely, when a fully detailed model is required due to temporal heterogeneities.

Maximum work extraction and implementation costs for nonequilibrium Maxwell's demons.

We determine the maximum amount of work extractable in finite time by a demon performing continuous measurements on a quadratic Hamiltonian system subjected to thermal fluctuations, in terms of the information extracted from the system. The maximum work demon is found to apply a high-gain continuous feedback involving a Kalman-Bucy estimate of the system state and operates in nonequilibrium. A simple and concrete electrical implementation of the feedback protocol is proposed, which allows for analytic expressions of the flows of energy, entropy, and information inside the demon. This let us show that any implementation of the demon must necessarily include an external power source, which we prove both from classical thermodynamics arguments and from a version of Landauer's memory erasure argument extended to nonequilibrium linear systems.

Trade integration and trade imbalances in the European Union: a network perspective.

We study the ever more integrated and ever more unbalanced trade relationships between European countries. To better capture the complexity of economic networks, we propose two global measures that assess the trade integration and the trade imbalances of the European countries. These measures are the network (or indirect) counterparts to traditional (or direct) measures such as the trade-to-GDP (Gross Domestic Product) and trade deficit-to-GDP ratios. Our indirect tools account for the European inter-country trade structure and follow (i) a decomposition of the global trade flow into elementary flows that highlight the long-range dependencies between exporting and importing economies and (ii) the commute-time distance for trade integration, which measures the impact of a perturbation in the economy of a country on another country, possibly through intermediate partners by domino effect. Our application addresses the impact of the launch of the Euro. We find that the indirect imbalance measures better identify the countries ultimately bearing deficits and surpluses, by neutralizing the impact of trade transit countries, such as the Netherlands. Among others, we find that ultimate surpluses of Germany are quite concentrated in only three partners. We also show that for some countries, the direct and indirect measures of trade integration diverge, thereby revealing that these countries (e.g. Greece and Portugal) trade to a smaller extent with countries considered as central in the European Union network.

Markov dynamics as a zooming lens for multiscale community detection: non clique-like communities and the field-of-view limit.

In recent years, there has been a surge of interest in community detection algorithms for complex networks. A variety of computational heuristics, some with a long history, have been proposed for the identification of communities or, alternatively, of good graph partitions. In most cases, the algorithms maximize a particular objective function, thereby finding the 'right' split into communities. Although a thorough comparison of algorithms is still lacking, there has been an effort to design benchmarks, i.e., random graph models with known community structure against which algorithms can be evaluated. However, popular community detection methods and benchmarks normally assume an implicit notion of community based on clique-like subgraphs, a form of community structure that is not always characteristic of real networks. Specifically, networks that emerge from geometric constraints can have natural non clique-like substructures with large effective diameters, which can be interpreted as long-range communities. In this work, we show that long-range communities escape detection by popular methods, which are blinded by a restricted 'field-of-view' limit, an intrinsic upper scale on the communities they can detect. The field-of-view limit means that long-range communities tend to be overpartitioned. We show how by adopting a dynamical perspective towards community detection [1], [2], in which the evolution of a Markov process on the graph is used as a zooming lens over the structure of the network at all scales, one can detect both clique- or non clique-like communities without imposing an upper scale to the detection. Consequently, the performance of algorithms on inherently low-diameter, clique-like benchmarks may not always be indicative of equally good results in real networks with local, sparser connectivity. We illustrate our ideas with constructive examples and through the analysis of real-world networks from imaging, protein structures and the power grid, where a multiscale structure of non clique-like communities is revealed.

Centrality measures and thermodynamic formalism for complex networks.

In the study of small and large networks it is customary to perform a simple random walk where the random walker jumps from one node to one of its neighbors with uniform probability. The properties of this random walk are intimately related to the combinatorial properties of the network. In this paper we propose to use the Ruelle-Bowens random walk instead, whose probability transitions are chosen in order to maximize the entropy rate of the walk on an unweighted graph. If the graph is weighted, then a free energy is optimized instead of the entropy rate. Specifically, we introduce a centrality measure for large networks, which is the stationary distribution attained by the Ruelle-Bowens random walk; we name it entropy rank. We introduce a more general version, which is able to deal with disconnected networks, under the name of free-energy rank. We compare the properties of those centrality measures with the classic PageRank and hyperlink-induced topic search (HITS) on both toy and real-life examples, in particular their robustness to small modifications of the network. We show that our centrality measures are more discriminating than PageRank, since they are able to distinguish clearly pages that PageRank regards as almost equally interesting, and are more sensitive to the medium-scale details of the graph.