Random walks on temporal networks

Balancing mobility behaviors to avoid global epidemics from local outbreaks

Human interactions and mobility shape epidemic dynamics by facilitating disease outbreaks and their spatial spread across regions. Traditional models often isolate commuting and random mobility as separate behaviors, focusing either on short, recurrent trips or on random, exploratory movements. Here, we propose a unified formalism that allows a smooth transition between commuting and exploratory behavior based on travel and return probabilities. We derive an analytical expression for the epidemic threshold, revealing a nonmonotonic dependence on recurrence rates: while recurrence tends to lower the threshold by increasing agent concentration in high-contact hubs, it counterintuitively raises the invasion threshold in low-mobility scenarios, suggesting that allowing recurrence may foster local outbreaks while suppressing global epidemics. These results provide a comprehensive understanding of the interplay between human mobility patterns and epidemic spread, with implications for containment strategies in structured populations.

Structure, motion, and multiscale search of traveling networks

Network models are widely applied to describe connectivity and flow in diverse systems. In contrast, the fact that many connected systems move through space as the result of dynamic restructuring has received little attention. Therefore, we introduce the concept of 'traveling networks', and we analyze a tree-based model where the leaves are stochastically manipulated to grow, branch, and retract. We derive how these restructuring rates determine key attributes of network structure and motion, enabling a compact understanding of higher-level network behaviors such as multiscale search. These networks self-organize to the critical point between exponential growth and decay, allowing them to detect and respond to environmental signals with high sensitivity. Finally, we demonstrate how the traveling network concept applies to real-world systems, such as slime molds, the actin cytoskeleton, and human organizations, exemplifying how restructuring rules and rates in general can select for versatile search strategies in real or abstract spaces.

A Parrondo paradox in susceptible-infectious-susceptible dynamics over periodic temporal networks

Many social and biological networks periodically change over time with daily, weekly, and other cycles. Thus motivated, we formulate and analyze susceptible-infectious-susceptible (SIS) epidemic models over temporal networks with periodic schedules. More specifically, we assume that the temporal network consists of a cycle of alternately used static networks, each with a given duration. We observe a phenomenon in which two static networks are individually above the epidemic threshold but the alternating network composed of them renders the dynamics below the epidemic threshold, which we refer to as a Parrondo paradox for epidemics. We find that network structure plays an important role in shaping this phenomenon, and we study its dependence on the connectivity between and number of subpopulations in the network. We associate such paradoxical behavior with anti-phase oscillatory dynamics of the number of infectious individuals in different subpopulations.

Higher-order correlations reveal complex memory in temporal hypergraphs

Many real-world complex systems are characterized by interactions in groups that change in time. Current temporal network approaches, however, are unable to describe group dynamics, as they are based on pairwise interactions only. Here, we use time-varying hypergraphs to describe such systems, and we introduce a framework based on higher-order correlations to characterize their temporal organization. The analysis of human interaction data reveals the existence of coherent and interdependent mesoscopic structures, thus capturing aggregation, fragmentation and nucleation processes in social systems. We introduce a model of temporal hypergraphs with non-Markovian group interactions, which reveals complex memory as a fundamental mechanism underlying the emerging pattern in the data.

Patterns in Temporal Networks with Higher-Order Egocentric Structures

The analysis of complex and time-evolving interactions, such as those within social dynamics, represents a current challenge in the science of complex systems. Temporal networks stand as a suitable tool for schematizing such systems, encoding all the interactions appearing between pairs of individuals in discrete time. Over the years, network science has developed many measures to analyze and compare temporal networks. Some of them imply a decomposition of the network into small pieces of interactions; i.e., only involving a few nodes for a short time range. Along this line, a possible way to decompose a network is to assume an egocentric perspective; i.e., to consider for each node the time evolution of its neighborhood. This was proposed by Longa et al. by defining the "egocentric temporal neighborhood", which has proven to be a useful tool for characterizing temporal networks relative to social interactions. However, this definition neglects group interactions (quite common in social domains), as they are always decomposed into pairwise connections. A more general framework that also allows considering larger interactions is represented by higher-order networks. Here, we generalize the description of social interactions to hypergraphs. Consequently, we generalize their decomposition into "hyper egocentric temporal neighborhoods". This enables the analysis of social interactions, facilitating comparisons between different datasets or nodes within a dataset, while considering the intrinsic complexity presented by higher-order interactions. Even if we limit the order of interactions to the second order (triplets of nodes), our results reveal the importance of a higher-order representation.In fact, our analyses show that second-order structures are responsible for the majority of the variability at all scales: between datasets, amongst nodes, and over time.

Constructing temporal networks with bursty activity patterns

Human social interactions tend to vary in intensity over time, whether they are in person or online. Variable rates of interaction in structured populations can be described by networks with the time-varying activity of links and nodes. One of the key statistics to summarize temporal patterns is the inter-event time, namely the duration between successive pairwise interactions. Empirical studies have found inter-event time distributions that are heavy-tailed, for both physical and digital interactions. But it is difficult to construct theoretical models of time-varying activity on a network that reproduce the burstiness seen in empirical data. Here we develop a spanning-tree method to construct temporal networks and activity patterns with bursty behavior. Our method ensures any desired target inter-event time distributions for individual nodes and links, provided the distributions fulfill a consistency condition, regardless of whether the underlying topology is static or time-varying. We show that this model can reproduce burstiness found in empirical datasets, and so it may serve as a basis for studying dynamic processes in real-world bursty interactions.

Characterization of interactions' persistence in time-varying networks

Many complex networked systems exhibit volatile dynamic interactions among their vertices, whose order and persistence reverberate on the outcome of dynamical processes taking place on them. To quantify and characterize the similarity of the snapshots of a time-varying network-a proxy for the persistence,-we present a study on the persistence of the interactions based on a descriptor named temporality. We use the average value of the temporality, [Formula: see text], to assess how "special" is a given time-varying network within the configuration space of ordered sequences of snapshots. We analyse the temporality of several empirical networks and find that empirical sequences are much more similar than their randomized counterparts. We study also the effects on [Formula: see text] induced by the (time) resolution at which interactions take place.

The interplay between disease spreading and awareness diffusion in multiplex networks with activity-driven structure

The interplay between disease and awareness has been extensively studied in static networks. However, most networks in reality will evolve over time. Based on this, we propose a novel epidemiological model in multiplex networks. In this model, the disease spreading layer is a time-varying network generated by the activity-driven model, while the awareness diffusion layer is a static network, and the heterogeneity of individual infection and recovery ability is considered. First, we extend the microscopic Markov chain approach to analytically obtain the epidemic threshold of the model. Then, we simulate the spread of disease and find that stronger heterogeneity in the individual activities of a physical layer can promote disease spreading, while stronger heterogeneity of the virtual layer network will hinder the spread of disease. Interestingly, we find that when the individual infection ability follows Gaussian distribution, the heterogeneity of infection ability has little effect on the spread of disease, but it will significantly affect the epidemic threshold when the individual infection ability follows power-law distribution. Finally, we find the emergence of a metacritical point where the diffusion of awareness is able to control the onset of the epidemics. Our research could cast some light on exploring the dynamics of epidemic spreading in time-varying multiplex networks.

Time-varying graph representation learning via higher-order skip-gram with negative sampling

Representation learning models for graphs are a successful family of techniques that project nodes into feature spaces that can be exploited by other machine learning algorithms. Since many real-world networks are inherently dynamic, with interactions among nodes changing over time, these techniques can be defined both for static and for time-varying graphs. Here, we show how the skip-gram embedding approach can be generalized to perform implicit tensor factorization on different tensor representations of time-varying graphs. We show that higher-order skip-gram with negative sampling (HOSGNS) is able to disentangle the role of nodes and time, with a small fraction of the number of parameters needed by other approaches. We empirically evaluate our approach using time-resolved face-to-face proximity data, showing that the learned representations outperform state-of-the-art methods when used to solve downstream tasks such as network reconstruction. Good performance on predicting the outcome of dynamical processes such as disease spreading shows the potential of this method to estimate contagion risk, providing early risk awareness based on contact tracing data.

SUPPLEMENTARY INFORMATION

The online version contains supplementary material available at 10.1140/epjds/s13688-022-00344-8.

Temporal exponential random graph models of longitudinal brain networks after stroke

Plasticity after stroke is a complex phenomenon. Functional reorganization occurs not only in the perilesional tissue but throughout the brain. However, the local connection mechanisms generating such global network changes remain largely unknown. To address this question, time must be considered as a formal variable of the problem rather than a simple repeated observation. Here, we hypothesized that the presence of temporal connection motifs, such as the formation of temporal triangles (T) and edges (E) over time, would explain large-scale brain reorganization after stroke. To test our hypothesis, we adopted a statistical framework based on temporal exponential random graph models (tERGMs), where the aforementioned temporal motifs were implemented as parameters and adapted to capture global network changes after stroke. We first validated the performance on synthetic time-varying networks as compared to standard static approaches. Then, using real functional brain networks, we showed that estimates of tERGM parameters were sufficient to reproduce brain network changes from 2 weeks to 1 year after stroke. These temporal connection signatures, reflecting within-hemisphere segregation (T) and between hemisphere integration (E), were associated with patients' future behaviour. In particular, interhemispheric temporal edges significantly correlated with the chronic language and visual outcome in subcortical and cortical stroke, respectively. Our results indicate the importance of time-varying connection properties when modelling dynamic complex systems and provide fresh insights into modelling of brain network mechanisms after stroke.

Network rewiring and plasticity promotes synchronization of suprachiasmatic nucleus neurons

In mammals, circadian rhythms throughout the body are orchestrated by the master clock in the hypothalamic suprachiasmatic nucleus (SCN), where SCN neurons are coupled with neurotransmitters to generate a uniform circadian rhythm. How the SCN circadian rhythm is so robust and flexible is, however, unclear. In this paper, we propose a temporal SCN network model and investigate the effects of dynamical rewiring and flexible coupling due to synaptic plasticity on the synchronization of the neural network in SCN. In networks consisting of simple Poincaré oscillators and complex circadian clocks, we found that dynamical rewiring and coupling plasticity enhance the synchronization in inhomogeneous networks. We verified the effect of enhanced synchronization in different architectures of random, scale-free, and small-world networks. A simple mean-field analysis for synchronization in plastic networks is proposed. Intuitively, the synchronization is greatly enhanced because both the random rewiring and coupling plasticity in the heterogeneous network have effectively increased the coupling strength in the whole network. Our results suggest that a proper network model for the master SCN circadian rhythm needs to take into account the effects of dynamical changes in topology and plasticity in neuron interactions that could help the brain to generate a robust circadian rhythm for the whole body.

Phase transition in the majority-vote model on time-varying networks

Social interactions may affect the update of individuals' opinions. The existing models such as the majority-vote (MV) model have been extensively studied in different static networks. However, in reality, social networks change over time and individuals interact dynamically. In this work, we study the behavior of the MV model on temporal networks to analyze the effects of temporality on opinion dynamics. In social networks, people are able to both actively send connections and passively receive connections, which leads to different effects on individuals' opinions. In order to compare the impact of different patterns of interactions on opinion dynamics, we simplify them into two processes, that is, the single directed (SD) process and the undirected (UD) process. The former only allows each individual to adopt an opinion by following the majority of actively interactive neighbors, while the latter allows each individual to flip opinion by following the majority of both actively interactive and passively interactive neighbors. By borrowing the activity-driven time-varying network with attractiveness (ADA model), the two opinion update processes, i.e., the SD and the UD processes, are related with the network evolution. With the mean-field approach, we derive the critical noise threshold for each process, which is also verified by numerical simulations. Compared with the SD process, the UD process reaches a larger consensus level below the same critical noise. Finally, we also verify the main results in real networks.

Impact of individual behavioral changes on epidemic spreading in time-varying networks

Changes in individual behavior often entangle with the dynamic interaction of individuals, which complicates the epidemic process and brings great challenges for the understanding and control of the epidemic. In this work, we consider three kinds of typical behavioral changes in epidemic process, that is, self-quarantine of infected individuals, self-protection of susceptible individuals, and social distancing between them. We connect the behavioral changes with individual's social attributes by the activity-driven network with attractiveness. A mean-field theory is established to derive an analytical estimate of epidemic threshold for susceptible-infected-susceptible models with individual behavioral changes, which depends on the correlations between activity, attractiveness, and the number of generative links in the susceptible and infected states. We find that individual behaviors play different roles in suppressing the epidemic. Although all the behavioral changes could delay the epidemic by increasing the epidemic threshold, self-quarantine and social distancing of infected individuals could effectively decrease the epidemic outbreak size. In addition, simultaneous changes in these behaviors and the timing of implement of them also play a key role in suppressing the epidemic. These results provide helpful significance for understanding the interaction of individual behaviors in the epidemic process.

Burstiness and Stochasticity in the Malleability of Physical Activity

This study examined whether patterns of self-organization in physical activity (PA) predicted long-term success in a yearlong PA intervention. Increased moderate to vigorous PA (MVPA) was targeted in insufficiently active adults (N = 512) via goal setting and financial reinforcement. The degree to which inverse power law distributions, which are reflective of self-organization, summarized (a) daily MVPA and (b) time elapsed between meeting daily goals (goal attainment interresponse times) was calculated. Goal attainment interresponse times were also used to calculate burstiness, the degree to which meeting daily goals clustered in time. Inverse power laws accurately summarized interresponse times, but not daily MVPA. For participants with higher levels of MVPA early in the study, burstiness in reaching goals was associated with long-term resistance to intervention, while stochasticity in meeting goals predicted receptiveness to intervention. These results suggest that burstiness may measure self-organizing resistance to change, while PA stochasticity could be a precondition for behavioral malleability.

Designing temporal networks that synchronize under resource constraints

Being fundamentally a non-equilibrium process, synchronization comes with unavoidable energy costs and has to be maintained under the constraint of limited resources. Such resource constraints are often reflected as a finite coupling budget available in a network to facilitate interaction and communication. Here, we show that introducing temporal variation in the network structure can lead to efficient synchronization even when stable synchrony is impossible in any static network under the given budget, thereby demonstrating a fundamental advantage of temporal networks. The temporal networks generated by our open-loop design are versatile in the sense of promoting synchronization for systems with vastly different dynamics, including periodic and chaotic dynamics in both discrete-time and continuous-time models. Furthermore, we link the dynamic stabilization effect of the changing topology to the curvature of the master stability function, which provides analytical insights into synchronization on temporal networks in general. In particular, our results shed light on the effect of network switching rate and explain why certain temporal networks synchronize only for intermediate switching rate.

The ability of complex networks to synchronize themselves is limited by available coupling resources. Zhang and Strogatz show that allowing temporal variation in the network structure can lead to synchronization even when stable synchrony is impossible in any static network under the fixed budget.

Impact of environmental changes on the dynamics of temporal networks

Dynamics of complex social systems has often been described in the framework of temporal networks, where links are considered to exist only at the moment of interaction between nodes. Such interaction patterns are not only driven by internal interaction mechanisms, but also affected by environmental changes. To investigate the impact of the environmental changes on the dynamics of temporal networks, we analyze several face-to-face interaction datasets using the multiscale entropy (MSE) method to find that the observed temporal correlations can be categorized according to the environmental similarity of datasets such as classes and break times in schools. By devising and studying a temporal network model considering a periodically changing environment as well as a preferential activation mechanism, we numerically show that our model could successfully reproduce various empirical results by the MSE method in terms of multiscale temporal correlations. Our results demonstrate that the environmental changes can play an important role in shaping the dynamics of temporal networks when the interactions between nodes are influenced by the environment of the systems.

Explicit and implicit network connectivity: Analytical formulation and application to transport processes

Connectivity is a fundamental structural feature of a network that determines the outcome of any dynamics that happens on top of it. However, an analytical approach to obtain connection probabilities between nodes associated with to paths of different lengths is still missing. Here, we derive exact expressions for random-walk connectivity probabilities across any range of numbers of steps in a generic temporal, directed, and weighted network. This allows characterizing explicit connectivity realized by causal paths as well as implicit connectivity related to motifs of three nodes and two links called here pitchforks. We directly link such probabilities to the processes of tagging and sampling any quantity exchanged across the network, hence providing a natural framework to assess transport dynamics. Finally, we apply our theoretical framework to study ocean transport features in the Mediterranean Sea. We find that relevant transport structures, such as fluid barriers and corridors, can generate contrasting and counterintuitive connectivity patterns bringing novel insights into how ocean currents drive seascape connectivity.

Temporal network embedding using graph attention network

Graph convolutional network (GCN) has made remarkable progress in learning good representations from graph-structured data. The layer-wise propagation rule of conventional GCN is designed in such a way that the feature aggregation at each node depends on the features of the one-hop neighbouring nodes. Adding an attention layer over the GCN can allow the network to provide different importance within various one-hop neighbours. These methods can capture the properties of static network, but is not well suited to capture the temporal patterns in time-varying networks. In this work, we propose a temporal graph attention network (TempGAN), where the aim is to learn representations from continuous-time temporal network by preserving the temporal proximity between nodes of the network. First, we perform a temporal walk over the network to generate a positive pointwise mutual information matrix (PPMI) which denote the temporal correlation between the nodes. Furthermore, we design a TempGAN architecture which uses both adjacency and PPMI information to generate node embeddings from temporal network. Finally, we conduct link prediction experiments by designing a TempGAN autoencoder to evaluate the quality of the embedding generated, and the results are compared with other state-of-the-art methods.

Random walks in time-varying networks with memory

Random walks process on networks plays a fundamental role in understanding the importance of nodes and the similarity of them, which has been widely applied in PageRank, information retrieval, and community detection, etc. An individual's memory has been proved to be crucial to affect network evolution and dynamical processes unfolding on the network. In this work, we study the random-walk process on an extended activity-driven network model by taking account of an individual's memory. We analyze how an individual's memory affects random-walk process unfolding on the network when the timescales of the processes of the random walk and the network evolution are comparable. Under the constraints of long-time evolution, we derive analytical solutions for the distribution of walkers at the stationary state and the mean first-passage time of the random-walk process. We find that, compared with the memoryless activity-driven model, an individual's memory enhances the activity fluctuation and leads to the formation of small clusters of mutual contacts with high activity nodes, which reduces a node's capability of gathering walkers, especially for the nodes with large activity, and memory also delays the mean first-passage time. The results on real networks also support the theoretical analysis and numerical results with artificial networks.

Generative models of simultaneously heavy-tailed distributions of interevent times on nodes and edges

Intervals between discrete events representing human activities, as well as other types of events, often obey heavy-tailed distributions, and their impacts on collective dynamics on networks such as contagion processes have been intensively studied. The literature supports that such heavy-tailed distributions are present for interevent times associated with both individual nodes and individual edges in networks. However, the simultaneous presence of heavy-tailed distributions of interevent times for nodes and edges is a nontrivial phenomenon, and its origin has been elusive. In the present study, we propose a generative model and its variants to explain this phenomenon. We assume that each node independently transits between a high-activity and low-activity state according to a continuous-time two-state Markov process and that, for the main model, events on an edge occur at a high rate if and only if both end nodes of the edge are in the high-activity state. In other words, two nodes interact frequently only when both nodes prefer to interact with others. The model produces distributions of interevent times for both individual nodes and edges that resemble heavy-tailed distributions across some scales. It also produces positive correlation in consecutive interevent times, which is another stylized observation for empirical data of human activity. We expect that our modeling framework provides a useful benchmark for investigating dynamics on temporal networks driven by non-Poissonian event sequences.

Random walks on hypergraphs

In the past 20 years network science has proven its strength in modeling many real-world interacting systems as generic agents, the nodes, connected by pairwise edges. Nevertheless, in many relevant cases, interactions are not pairwise but involve larger sets of nodes at a time. These systems are thus better described in the framework of hypergraphs, whose hyperedges effectively account for multibody interactions. Here we propose and study a class of random walks defined on such higher-order structures and grounded on a microscopic physical model where multibody proximity is associated with highly probable exchanges among agents belonging to the same hyperedge. We provide an analytical characterization of the process, deriving a general solution for the stationary distribution of the walkers. The dynamics is ultimately driven by a generalized random-walk Laplace operator that reduces to the standard random-walk Laplacian when all the hyperedges have size 2 and are thus meant to describe pairwise couplings. We illustrate our results on synthetic models for which we have full control of the high-order structures and on real-world networks where higher-order interactions are at play. As the first application of the method, we compare the behavior of random walkers on hypergraphs to that of traditional random walkers on the corresponding projected networks, drawing interesting conclusions on node rankings in collaboration networks. As the second application, we show how information derived from the random walk on hypergraphs can be successfully used for classification tasks involving objects with several features, each one represented by a hyperedge. Taken together, our work contributes to unraveling the effect of higher-order interactions on diffusive processes in higher-order networks, shedding light on mechanisms at the heart of biased information spreading in complex networked systems.

Spreading dynamics in a cattle trade network: Size, speed, typical profile and consequences on epidemic control strategies

Infections can spread among livestock notably because infected animals can be brought to uncontaminated holdings, therefore exposing a new group of susceptible animals to the disease. As a consequence, the structure and dynamics of animal trade networks is a major focus of interest to control zoonosis. We investigate the impact of the chronology of animal trades on the dynamics of the process. Precisely, in the context of a basic SI model spreading, we measure on the French database of bovine transfers to what extent a snapshot-based analysis of the cattle trade networks overestimates the epidemic risks. We bring into light that an analysis taking into account the chronology of interactions would give a much more accurate assessment of both the size and speed of the process. For this purpose, we model data as a temporal network that we analyze using the link stream formalism in order to mix structural and temporal aspects. We also show that in this dataset, a basic SI spreading comes down in most cases to a simple two-phases scenario: a waiting period, with few contacts and low activity, followed by a linear growth of the number of infected holdings. Using this portrait of the spreading process, we identify efficient strategies to control a potential outbreak, based on the identification of specific elements of the link stream which have a higher probability to be involved in a spreading process.

Spreading of computer viruses on time-varying networks

Social networks are the prime channel for the spreading of computer viruses. Yet the study of their propagation neglects the temporal nature of social interactions and the heterogeneity of users' susceptibility. Here, we introduce a theoretical framework that captures both properties. We study two realistic types of viruses propagating on temporal networks featuring Q categories of susceptibility and derive analytically the invasion threshold. We found that the temporal coupling of categories might increase the fragility of the system to cyber threats. Our results show that networks' dynamics and their interplay with users' features are crucial for the spreading of computer viruses.

Mobility helps problem-solving systems to avoid groupthink

Groupthink occurs when everyone in a group starts thinking alike, as when people put unlimited faith in a leader. Avoiding this phenomenon is a ubiquitous challenge to problem-solving enterprises and typical countermeasures involve the mobility of group members. Here we use an agent-based model of imitative learning to study the influence of the mobility of the agents on the time they require to find the global maxima of NK-fitness landscapes. The agents cooperate by exchanging information on their fitness and use this information to copy the fittest agent in their influence neighborhoods, which are determined by face-to-face interaction networks. The influence neighborhoods are variable since the agents perform random walks in a two-dimensional space. We find that mobility is slightly harmful for solving easy problems, i.e., problems that do not exhibit suboptimal solutions or local maxima. For difficult problems, however, mobility can prevent the imitative search being trapped in suboptimal solutions and guarantees a better performance than the independent search for any system size.

Epidemic spreading on time-varying multiplex networks

Social interactions are stratified in multiple contexts and are subject to complex temporal dynamics. The systematic study of these two features of social systems has started only very recently, mainly thanks to the development of multiplex and time-varying networks. However, these two advancements have progressed almost in parallel with very little overlap. Thus, the interplay between multiplexity and the temporal nature of connectivity patterns is poorly understood. Here, we aim to tackle this limitation by introducing a time-varying model of multiplex networks. We are interested in characterizing how these two properties affect contagion processes. To this end, we study susceptible-infected-susceptible epidemic models unfolding at comparable timescale with respect to the evolution of the multiplex network. We study both analytically and numerically the epidemic threshold as a function of the multiplexity and the features of each layer. We found that higher values of multiplexity significantly reduce the epidemic threshold especially when the temporal activation patterns of nodes present on multiple layers are positively correlated. Furthermore, when the average connectivity across layers is very different, the contagion dynamics is driven by the features of the more densely connected layer. Here, the epidemic threshold is equivalent to that of a single layered graph and the impact of the disease, in the layer driving the contagion, is independent of the multiplexity. However, this is not the case in the other layers where the spreading dynamics is sharply influenced by it. The results presented provide another step towards the characterization of the properties of real networks and their effects on contagion phenomena.

Predicting the mean first passage time (MFPT) to reach any state for a passive dynamic walker with steady state variability

Idealized passive dynamic walkers (PDW) exhibit limit cycle stability at steady state. Yet in reality, uncertainty in ground interaction forces result in variability in limit cycles even for a simple walker known as the Rimless Wheel (RW) on seemingly even slopes. This class of walkers is called metastable walkers in that they usually walk in a stable limit cycle, though guaranteed to eventually fail. Thus, control action is only needed if a failure state (i.e. RW stopping down the ramp) is imminent. Therefore, efficiency of estimating the time to reach a failure state is key to develop a minimal intervention controller to inject just enough energy to overcome a failure state when required. Current methods use what is known as a Mean First Passage Time (MFPT) from current state (rotary speed of RW at the most recent leg collision) to an arbitrary state deemed to be a failure in the future. The frequently used Markov chain based MFPT prediction requires an absorbing state, which in this case is a collision where the RW comes to a stop without an escape. Here, we propose a novel method to estimate an MFPT from current state to an arbitrary state which is not necessarily an absorbing state. This provides freedom to a controller to adaptively take action when deemed necessary. We demonstrate the proposed MFPT predictions in a minimal intervention controller for a RW. Our results show that the proposed method is useful in controllers for walkers showing up to 44.1% increase of time-to-fail compared to a PID based closed-loop controller.

Generalized voterlike model on activity-driven networks with attractiveness

We study the behavior of a generalized consensus dynamics on a temporal network of interactions, the activity-driven network with attractiveness. In this temporal network model, agents are endowed with an intrinsic activity a, ruling the rate at which they generate connections, and an intrinsic attractiveness b, modulating the rate at which they receive connections. The consensus dynamics considered is a mixed voter and Moran dynamics. Each agent, either in state 0 or 1, modifies his or her state when connecting with a peer. Thus, an active agent copies his or her state from the peer (with probability p) or imposes his or her state to him or her (with the complementary probability 1-p). Applying a heterogeneous mean-field approach, we derive a differential equation for the average density of voters with activity a and attractiveness b in state 1, which we use to evaluate the average time to reach consensus and the exit probability, defined as the probability that a single agent with activity a and attractiveness b eventually imposes his or her state to a pool of initially unanimous population in the opposite state. We study a number of particular cases, finding an excellent agreement with numerical simulations of the model. Interestingly, we observe a symmetry between voter and Moran dynamics in pure activity-driven networks and their static integrated counterparts that exemplifies the strong differences that a time-varying network can impose on dynamical processes.

Dynamic topologies of activity-driven temporal networks with memory

We propose dynamic scaling in temporal networks with heterogeneous activities and memory and provide a comprehensive picture for the dynamic topologies of such networks, in terms of the modified activity-driven network model [H. Kim et al., Eur. Phys. J. B 88, 315 (2015)EPJBFY1434-602810.1140/epjb/e2015-60662-7]. Particularly, we focus on the interplay of the time resolution and memory in dynamic topologies. Through the random-walk (RW) process, we investigate diffusion properties and topological changes as the time resolution increases. Our results with memory are compared to those of the memoryless case. Based on the temporal percolation concept, we derive scaling exponents in the dynamics of the largest cluster and the coverage of the RW process in time-varying networks. We find that the time resolution in the time-accumulated network determines the effective size of the network, while memory affects relevant scaling properties at the crossover from the dynamic regime to the static one. The origin of memory-dependent scaling behaviors is the dynamics of the largest cluster, which depends on temporal degree distributions. Finally, we conjecture of the extended finite-size scaling ansatz for dynamic topologies and the fundamental property of temporal networks, which are numerically confirmed.

The fundamental advantages of temporal networks

Most networked systems of scientific interest are characterized by temporal links, meaning the network's structure changes over time. Link temporality has been shown to hinder many dynamical processes, from information spreading to accessibility, by disrupting network paths. Considering the ubiquity of temporal networks in nature, we ask: Are there any advantages of the networks' temporality? We use an analytical framework to show that temporal networks can, compared to their static counterparts, reach controllability faster, demand orders of magnitude less control energy, and have control trajectories, that are considerably more compact than those characterizing static networks. Thus, temporality ensures a degree of flexibility that would be unattainable in static networks, enhancing our ability to control them.

Automated monitoring of behavior reveals bursty interaction patterns and rapid spreading dynamics in honeybee social networks

Social networks mediate the spread of information and disease. The dynamics of spreading depends, among other factors, on the distribution of times between successive contacts in the network. Heavy-tailed (bursty) time distributions are characteristic of human communication networks, including face-to-face contacts and electronic communication via mobile phone calls, email, and internet communities. Burstiness has been cited as a possible cause for slow spreading in these networks relative to a randomized reference network. However, it is not known whether burstiness is an epiphenomenon of human-specific patterns of communication. Moreover, theory predicts that fast, bursty communication networks should also exist. Here, we present a high-throughput technology for automated monitoring of social interactions of individual honeybees and the analysis of a rich and detailed dataset consisting of more than 1.2 million interactions in five honeybee colonies. We find that bees, like humans, also interact in bursts but that spreading is significantly faster than in a randomized reference network and remains so even after an experimental demographic perturbation. Thus, while burstiness may be an intrinsic property of social interactions, it does not always inhibit spreading in real-world communication networks. We anticipate that these results will inform future models of large-scale social organization and information and disease transmission, and may impact health management of threatened honeybee populations.

Epidemic spreading in modular time-varying networks

We investigate the effects of modular and temporal connectivity patterns on epidemic spreading. To this end, we introduce and analytically characterise a model of time-varying networks with tunable modularity. Within this framework, we study the epidemic size of Susceptible-Infected-Recovered, SIR, models and the epidemic threshold of Susceptible-Infected-Susceptible, SIS, models. Interestingly, we find that while the presence of tightly connected clusters inhibits SIR processes, it speeds up SIS phenomena. In this case, we observe that modular structures induce a reduction of the threshold with respect to time-varying networks without communities. We confirm the theoretical results by means of extensive numerical simulations both on synthetic graphs as well as on a real modular and temporal network.

Optimal Quantum Spatial Search on Random Temporal Networks

To investigate the performance of quantum information tasks on networks whose topology changes in time, we study the spatial search algorithm by continuous time quantum walk to find a marked node on a random temporal network. We consider a network of n nodes constituted by a time-ordered sequence of Erdös-Rényi random graphs G(n,p), where p is the probability that any two given nodes are connected: After every time interval τ, a new graph G(n,p) replaces the previous one. We prove analytically that, for any given p, there is always a range of values of τ for which the running time of the algorithm is optimal, i.e., O(sqrt[n]), even when search on the individual static graphs constituting the temporal network is suboptimal. On the other hand, there are regimes of τ where the algorithm is suboptimal even when each of the underlying static graphs are sufficiently connected to perform optimal search on them. From this first study of quantum spatial search on a time-dependent network, it emerges that the nontrivial interplay between temporality and connectivity is key to the algorithmic performance. Moreover, our work can be extended to establish high-fidelity qubit transfer between any two nodes of the network. Overall, our findings show that one can exploit temporality to achieve optimal quantum information tasks on dynamical random networks.

Navigability of temporal networks in hyperbolic space

Information routing is one of the main tasks in many complex networks with a communication function. Maps produced by embedding the networks in hyperbolic space can assist this task enabling the implementation of efficient navigation strategies. However, only static maps have been considered so far, while navigation in more realistic situations, where the network structure may vary in time, remains largely unexplored. Here, we analyze the navigability of real networks by using greedy routing in hyperbolic space, where the nodes are subject to a stochastic activation-inactivation dynamics. We find that such dynamics enhances navigability with respect to the static case. Interestingly, there exists an optimal intermediate activation value, which ensures the best trade-off between the increase in the number of successful paths and a limited growth of their length. Contrary to expectations, the enhanced navigability is robust even when the most connected nodes inactivate with very high probability. Finally, our results indicate that some real networks are ultranavigable and remain highly navigable even if the network structure is extremely unsteady. These findings have important implications for the design and evaluation of efficient routing protocols that account for the temporal nature of real complex networks.

Epidemic spreading on activity-driven networks with attractiveness

We study SIS epidemic spreading processes unfolding on a recent generalization of the activity-driven modeling framework. In this model of time-varying networks, each node is described by two variables: activity and attractiveness. The first describes the propensity to form connections, while the second defines the propensity to attract them. We derive analytically the epidemic threshold considering the time scale driving the evolution of contacts and the contagion as comparable. The solutions are general and hold for any joint distribution of activity and attractiveness. The theoretical picture is confirmed via large-scale numerical simulations performed considering heterogeneous distributions and different correlations between the two variables. We find that heterogeneous distributions of attractiveness alter the contagion process. In particular, in the case of uncorrelated and positive correlations between the two variables, heterogeneous attractiveness facilitates the spreading. On the contrary, negative correlations between activity and attractiveness hamper the spreading. The results presented contribute to the understanding of the dynamical properties of time-varying networks and their effects on contagion phenomena unfolding on their fabric.

Theory of Turing Patterns on Time Varying Networks

The process of pattern formation for a multispecies model anchored on a time varying network is studied. A nonhomogeneous perturbation superposed to an homogeneous stable fixed point can be amplified following the Turing mechanism of instability, solely instigated by the network dynamics. By properly tuning the frequency of the imposed network evolution, one can make the examined system behave as its averaged counterpart, over a finite time window. This is the key observation to derive a closed analytical prediction for the onset of the instability in the time dependent framework. Continuously and piecewise constant periodic time varying networks are analyzed, setting the framework for the proposed approach. The extension to nonperiodic settings is also discussed.

Multitarget search on complex networks: A logarithmic growth of global mean random cover time

We investigate multitarget search on complex networks and derive an exact expression for the mean random cover time that quantifies the expected time a walker needs to visit multiple targets. Based on this, we recover and extend some interesting results of multitarget search on networks. Specifically, we observe the logarithmic increase of the global mean random cover time with the target number for a broad range of random search processes, including generic random walks, biased random walks, and maximal entropy random walks. We show that the logarithmic growth pattern is a universal feature of multi-target search on networks by using the annealed network approach and the Sherman-Morrison formula. Moreover, we find that for biased random walks, the global mean random cover time can be minimized, and that the corresponding optimal parameter also minimizes the global mean first passage time, pointing towards its robustness. Our findings further confirm that the logarithmic growth pattern is a universal law governing multitarget search in confined media.

Network-Centric Interventions to Contain the Syphilis Epidemic in San Francisco

The number of reported early syphilis cases in San Francisco has increased steadily since 2005. It is not yet clear what factors are responsible for such an increase. A recent analysis of the sexual contact network of men who have sex with men with syphilis in San Francisco has discovered a large connected component, members of which have a significantly higher chance of syphilis and HIV compared to non-member individuals. This study investigates whether it is possible to exploit the existence of the largest connected component to design new notification strategies that can potentially contribute to reducing the number of cases. We develop a model capable of incorporating multiple types of notification strategies and compare the corresponding incidence of syphilis. Through extensive simulations, we show that notifying the community of the infection state of few central nodes appears to be the most effective approach, balancing the cost of notification and the reduction of syphilis incidence. Additionally, among the different measures of centrality, the eigenvector centrality reveals to be the best to reduce the incidence in the long term as long as the number of missing links (non-disclosed contacts) is not very large.

Random walks on activity-driven networks with attractiveness

Virtually all real-world networks are dynamical entities. In social networks, the propensity of nodes to engage in social interactions (activity) and their chances to be selected by active nodes (attractiveness) are heterogeneously distributed. Here, we present a time-varying network model where each node and the dynamical formation of ties are characterized by these two features. We study how these properties affect random-walk processes unfolding on the network when the time scales describing the process and the network evolution are comparable. We derive analytical solutions for the stationary state and the mean first-passage time of the process, and we study cases informed by empirical observations of social networks. Our work shows that previously disregarded properties of real social systems, such as heterogeneous distributions of activity and attractiveness as well as the correlations between them, substantially affect the dynamical process unfolding on the network.

Using the OASES-A to illustrate how network analysis can be applied to understand the experience of stuttering

PURPOSE

Network science uses mathematical and computational techniques to examine how individual entities in a system, represented by nodes, interact, as represented by connections between nodes. This approach has been used by Cramer et al. (2010) to make "symptom networks" to examine various psychological disorders. In the present analysis we examined a network created from the items in the Overall Assessment of the Speaker's Experience of Stuttering-Adult (OASES-A), a commonly used measure for evaluating adverse impact in the lives of people who stutter.

METHOD

The items of the OASES-A were represented as nodes in the network. Connections between nodes were placed if responses to those two items in the OASES-A had a correlation coefficient greater than ±0.5. Several network analyses revealed which nodes were "important" in the network.

RESULTS

Several centrally located nodes and "key players" in the network were identified. A community detection analysis found groupings of nodes that differed slightly from the subheadings of the OASES-A.

CONCLUSIONS

Centrally located nodes and "key players" in the network may help clinicians prioritize treatment. The different community structure found for people who stutter suggests that the way people who stutter view stuttering may differ from the way that scientists and clinicians view stuttering. Finally, the present analyses illustrate how the network approach might be applied to other speech, language, and hearing disorders to better understand how those disorders are experienced and to provide insights for their treatment.

Lévy random walks on multiplex networks

Random walks constitute a fundamental mechanism for many dynamics taking place on complex networks. Besides, as a more realistic description of our society, multiplex networks have been receiving a growing interest, as well as the dynamical processes that occur on top of them. Here, inspired by one specific model of random walks that seems to be ubiquitous across many scientific fields, the Lévy flight, we study a new navigation strategy on top of multiplex networks. Capitalizing on spectral graph and stochastic matrix theories, we derive analytical expressions for the mean first passage time and the average time to reach a node on these networks. Moreover, we also explore the efficiency of Lévy random walks, which we found to be very different as compared to the single layer scenario, accounting for the structure and dynamics inherent to the multiplex network. Finally, by comparing with some other important random walk processes defined on multiplex networks, we find that in some region of the parameters, a Lévy random walk is the most efficient strategy. Our results give us a deeper understanding of Lévy random walks and show the importance of considering the topological structure of multiplex networks when trying to find efficient navigation strategies.

Asymptotic theory of time-varying social networks with heterogeneous activity and tie allocation

The dynamic of social networks is driven by the interplay between diverse mechanisms that still challenge our theoretical and modelling efforts. Amongst them, two are known to play a central role in shaping the networks evolution, namely the heterogeneous propensity of individuals to i) be socially active and ii) establish a new social relationships with their alters. Here, we empirically characterise these two mechanisms in seven real networks describing temporal human interactions in three different settings: scientific collaborations, Twitter mentions, and mobile phone calls. We find that the individuals’ social activity and their strategy in choosing ties where to allocate their social interactions can be quantitatively described and encoded in a simple stochastic network modelling framework. The Master Equation of the model can be solved in the asymptotic limit. The analytical solutions provide an explicit description of both the system dynamic and the dynamical scaling laws characterising crucial aspects about the evolution of the networks. The analytical predictions match with accuracy the empirical observations, thus validating the theoretical approach. Our results provide a rigorous dynamical system framework that can be extended to include other processes shaping social dynamics and to generate data driven predictions for the asymptotic behaviour of social networks.

Measuring burstiness for finite event sequences

Characterizing inhomogeneous temporal patterns in natural and social phenomena is important to understand underlying mechanisms behind such complex systems and, hence, even to predict and control them. Temporal inhomogeneities in event sequences have been described in terms of bursts that are rapidly occurring events in short time periods alternating with long inactive periods. The bursts can be quantified by a simple measure, called the burstiness parameter, which was introduced by Goh and Barabási [Europhys. Lett. 81, 48002 (2008)EULEEJ0295-507510.1209/0295-5075/81/48002]. The burstiness parameter has been widely used due to its simplicity, which, however, turns out to be strongly affected by the finite number of events in the time series. As the finite-size effects on burstiness parameter have been largely ignored, we analytically investigate the finite-size effects of the burstiness parameter. Then we suggest an alternative definition of burstiness that is free from finite-size effects and yet simple. Using our alternative burstiness measure, one can distinguish the finite-size effects from the intrinsic bursty properties in the time series. We also demonstrate the advantages of our burstiness measure by analyzing empirical data sets.

Aging and percolation dynamics in a Non-Poissonian temporal network model

We present an exhaustive mathematical analysis of the recently proposed Non-Poissonian Activity Driven (NoPAD) model [Moinet et al., Phys. Rev. Lett. 114, 108701 (2015)PRLTAO0031-900710.1103/PhysRevLett.114.108701], a temporal network model incorporating the empirically observed bursty nature of social interactions. We focus on the aging effects emerging from the non-Poissonian dynamics of link activation, and on their effects on the topological properties of time-integrated networks, such as the degree distribution. Analytic expressions for the degree distribution of integrated networks as a function of time are derived, exploring both limits of vanishing and strong aging. We also address the percolation process occurring on these temporal networks, by computing the threshold for the emergence of a giant connected component, highlighting the aging dependence. Our analytic predictions are checked by means of extensive numerical simulations of the NoPAD model.

Contagion processes on the static and activity-driven coupling networks

The evolution of network structure and the spreading of epidemic are common coexistent dynamical processes. In most cases, network structure is treated as either static or time-varying, supposing the whole network is observed in the same time window. In this paper, we consider the epidemics spreading on a network which has both static and time-varying structures. Meanwhile, the time-varying part and the epidemic spreading are supposed to be of the same time scale. We introduce a static and activity-driven coupling (SADC) network model to characterize the coupling between the static ("strong") structure and the dynamic ("weak") structure. Epidemic thresholds of the SIS and SIR models are studied using the SADC model both analytically and numerically under various coupling strategies, where the strong structure is of homogeneous or heterogeneous degree distribution. Theoretical thresholds obtained from the SADC model can both recover and generalize the classical results in static and time-varying networks. It is demonstrated that a weak structure might make the epidemic threshold low in homogeneous networks but high in heterogeneous cases. Furthermore, we show that the weak structure has a substantive effect on the outbreak of the epidemics. This result might be useful in designing some efficient control strategies for epidemics spreading in networks.