• ### Cover time for random walks on arbitrary complex networks(1706.02356)

Aug. 1, 2018 cond-mat.stat-mech, cs.DM, cs.SI
We present an analytical method for computing the mean cover time of a random walk process on arbitrary, complex networks. The cover time is defined as the time a random walker requires to visit every node in the network at least once. This quantity is particularly important for random search processes and target localization in network topologies. Based on the global mean first passage time of target nodes we derive an estimate for the cumulative distribution function of the cover time based on first passage time statistics. We show that our result can be applied to various model networks, including Erd\H{o}s-R\'enyi and Barab\'asi-Albert networks, as well as various real-world networks. Our results reveal an intimate link between first passage and cover time statistics in networks in which structurally induced temporal correlations decay quickly and offer a computationally efficient way for estimating cover times in network related applications.
• ### Temporal dynamics of online petitions(1705.04202)

May 11, 2017 physics.soc-ph
Online petitions are an important avenue for direct political action, yet the dynamics that determine when a petition will be successful are not well understood. Here we analyze the temporal characteristics of online-petition signing behavior in order to identify systematic differences between popular petitions, which receive a high volume of signatures, and unpopular ones. We find that, in line with other temporal characterizations of human activity, the signing process is typically non-Poissonian and non-homogeneous in time. However, this process exhibits anomalously high memory for human activity, possibly indicating that synchronized external influence or contagion play and important role. More interestingly, we find clear differences in the characteristics of the inter-event time distributions depending on the total number of signatures that petitions receive, independently of the total duration of the petitions. Specifically, popular petitions that attract a large volume of signatures exhibit more variance in the distribution of inter-event times than unpopular petitions with only a few signatures, which could be considered an indication that the former are more bursty. However, petitions with large signature volume are less bursty according to measures that consider the time ordering of inter-event times. Our results, therefore, emphasize the importance of accounting for time ordering to characterize human activity.
• ### Fundamental properties of cooperative contagion processes(1603.09082)

We investigate the effects of cooperativity between contagion processes that spread and persist in a host population. We propose and analyze a dynamical model in which individuals that are affected by one transmissible agent $A$ exhibit a higher than baseline propensity of being affected by a second agent $B$ and vice versa. The model is a natural extension of the traditional SIS (Susceptible-Infected-Susceptible) model used for modeling single contagion processes. We show that cooperativity changes the dynamics of the system considerably when cooperativity is strong. The system exhibits discontinuous phase transitions not observed in single agent contagion, multi-stability, a separation of the traditional epidemic threshold into different thresholds for inception and extinction as well as hysteresis. These properties are robust and are corroborated by stochastic simulations on lattices and generic network topologies. Finally, we investigate wave propagation and transients in a spatially extended version of the model and show that especially for intermediate values of baseline reproduction ratios the system is characterized by various types of wave-front speeds. The system can exhibit spatially heterogeneous stationary states for some parameters and negative front speeds (receding wave fronts). The two agent model can be employed as a starting point for more complex contagion processes, involving several interacting agents, a model framework particularly suitable for modeling the spread and dynamics of microbiological ecosystems in host populations.
• ### Effective Distances for Epidemics Spreading on Complex Networks(1608.06201)

Jan. 17, 2017 physics.soc-ph, q-bio.PE
We show that the recently introduced logarithmic metrics used to predict disease arrival times on complex networks are approximations of more general network-based measures derived from random walks theory. Using the daily air-traffic transportation data we perform numerical experiments to compare the infection arrival time with this alternative metric that is obtained by accounting for multiple walks instead of only the most probable path. The comparison with direct simulations of arrival times reveals a higher correlation compared to the shortest path approach used previously. In addition our method allows to connect fundamental observables in epidemic spreading with the cumulant generating function of the hitting time for a Markov chain. Our results provides a general and computationally efficient approach to the problem using only algebraic methods.
• ### Saving Human Lives: What Complexity Science and Information Systems can Contribute(1402.7011)

May 22, 2014 physics.soc-ph, nlin.AO, cs.SI
We discuss models and data of crowd disasters, crime, terrorism, war and disease spreading to show that conventional recipes, such as deterrence strategies, are often not effective and sufficient to contain them. Many common approaches do not provide a good picture of the actual system behavior, because they neglect feedback loops, instabilities and cascade effects. The complex and often counter-intuitive behavior of social systems and their macro-level collective dynamics can be better understood by means of complexity science. We highlight that a suitable system design and management can help to stop undesirable cascade effects and to enable favorable kinds of self-organization in the system. In such a way, complexity science can help to save human lives.
• ### Robustness of skeletons and salient features in networks(1309.3797)

Sept. 15, 2013 physics.soc-ph, cs.SI
Real world network datasets often contain a wealth of complex topological information. In the face of these data, researchers often employ methods to extract reduced networks containing the most important structures or pathways, sometimes known as skeletons' or backbones'. Numerous such methods have been developed. Yet data are often noisy or incomplete, with unknown numbers of missing or spurious links. Relatively little effort has gone into understanding how salient network extraction methods perform in the face of noisy or incomplete networks. We study this problem by comparing how the salient features extracted by two popular methods change when networks are perturbed, either by deleting nodes or links, or by randomly rewiring links. Our results indicate that simple, global statistics for skeletons can be accurately inferred even for noisy and incomplete network data, but it is crucial to have complete, reliable data to use the exact topologies of skeletons or backbones. These results also help us understand how skeletons respond to damage to the network itself, as in an attack scenario.
• ### Perturbative solution to the SIS epidemic on networks(1304.3008)

Herein we provide a closed form perturbative solution to a general $M$-node network SIS model using the transport rates between nodes as a perturbation parameter. We separate the dynamics into a short-time regime and a medium/long-time regime. We solve the short-time dynamics of the system and provide a limit before which our explicit, analytical result of the first-order perturbation for the medium/long-time regime is to be employed. These stitched calculations provide an approximation to the full temporal dynamics for rather general initial conditions. To further corroborate our results, we solve the mean-field equations numerically for an infectious SIS outbreak in New Zealand (NZ, \emph{Aotearoa}) recomposed into 23 subpopulations where the virus is spread to different subpopulations via (documented) air traffic data, and the country is internationally quarantined. We demonstrate that our analytical predictions compare well to the numerical solution.
• ### Natural emergence of clusters and bursts in network evolution(1209.3307)

Network models with preferential attachment, where new nodes are injected into the network and form links with existing nodes proportional to their current connectivity, have been well studied for some time. Extensions have been introduced where nodes attach proportionally to arbitrary fitness functions. However, in these models, attaching to a node always increases the ability of that node to gain more links in the future. We study network growth where nodes attach proportionally to the clustering coefficients, or local densities of triangles, of existing nodes. Attaching to a node typically lowers its clustering coefficient, in contrast to preferential attachment or rich-get-richer models. This simple modification naturally leads to a variety of rich phenomena, including aging, non-Poissonian bursty dynamics, and community formation. This theoretical model shows that complex network structure can be generated without artificially imposing multiple dynamical mechanisms and may reveal potentially overlooked mechanisms present in complex systems.
• ### The seasonal flight of influenza: a unified framework for spatiotemporal hypothesis testing(1210.5877)

Oct. 22, 2012 q-bio.PE
Global mobility flow data are at the heart of spatial epidemiological models used to predict infectious disease behavior but this wealth of data on human mobility has been largely neglected by reconstructions of pathogen evolutionary dynamics using viral genetic data. Although stochastic models of viral evolution may potentially be informed by such data, a major challenge lies in deciding which mobility processes are critical and to what extent they contribute to shaping contemporaneous distributions of pathogen diversity. Here, we develop a framework to integrate predictors of viral diffusion with phylogeographic inference and estimate human influenza H3N2 migration history while simultaneously testing and quantifying the factors that underly it. We provide evidence for air travel governing the global dynamics of human influenza whereas other processes act at a more local scale.
• ### The role of caretakers in disease dynamics(1209.2419)

Sept. 11, 2012 physics.soc-ph, nlin.AO, q-bio.PE, cs.SI
One of the key challenges in modeling the dynamics of contagion phenomena is to understand how the structure of social interactions shapes the time course of a disease. Complex network theory has provided significant advances in this context. However, awareness of an epidemic in a population typically yields behavioral changes that correspond to changes in the network structure on which the disease evolves. This feedback mechanism has not been investigated in depth. For example, one would intuitively expect susceptible individuals to avoid other infecteds. However, doctors treating patients or parents tending sick children may also increase the amount of contact made with an infecteds, in an effort to speed up recovery but also exposing themselves to higher risks of infection. We study the role of these caretaker links in an adaptive network models where individuals react to a disease by increasing or decreasing the amount of contact they make with infected individuals. We find that pure avoidance, with only few caretaker links, is the best strategy for curtailing an SIS disease in networks that possess a large topological variability. In more homogeneous networks, disease prevalence is decreased for low concentrations of caretakers whereas a high prevalence emerges if caretaker concentration passes a well defined critical value.
• ### Robust classification of salient links in complex networks(1110.3864)

May 31, 2012 physics.soc-ph
Complex networks in natural, social, and technological systems generically exhibit an abundance of rich information. Extracting meaningful structural features from data is one of the most challenging tasks in network theory. Many methods and concepts have been proposed to address this problem such as centrality statistics, motifs, community clusters, and backbones, but such schemes typically rely on external and arbitrary parameters. It is unknown whether generic networks permit the classification of elements without external intervention. Here we show that link salience is a robust approach to classifying network elements based on a consensus estimate of all nodes. A wide range of empirical networks exhibit a natural, network-implicit classification of links into qualitatively distinct groups, and the salient skeletons have generic statistical properties. Salience also predicts essential features of contagion phenomena on networks, and points towards a better understanding of universal features in empirical networks that are masked by their complexity.
• ### Recurrent host mobility in spatial epidemics: beyond reaction-diffusion(1106.3461)

Human mobility is a key factor in spatial disease dynamics and related phenomena. In computational models host mobility is typically modelled by diffusion in space or on metapolulation networks. Alternatively, an effective force of infection across distance has been introduced to capture spatial dispersal implicitly. Both approaches do not account for important aspects of natural human mobility, diffusion does not capture the high degree of predictability in natural human mobility patters, e.g. the high percentage of return movements to individuals' base location, the effective force of infection approach assumes immediate equilibrium with respect to dispersal. These conditions are typically not met in natural scenarios. We investigate an epidemiological model that explicitly captures natural individual mobility patterns. We systematically investigate generic dynamical features of the model on regular lattices as well as metapopulation networks and show that generally the model exhibits significant dynamical differences in comparison to ordinary diffusion and effective force of infection models. For instance, the natural human mobility model exhibits a saturation of wave front speeds and a novel type of invasion threshold that is a function of the return rate in mobility patterns. In the light of these new findings and with the availability of precise and pervasive data on human mobility our approach provides a framework for a more sophisticated modeling of spatial disease dynamics.
• ### Natural human mobility patterns and spatial spread of infectious diseases(1103.6224)

We investigate a model for spatial epidemics explicitly taking into account bi-directional movements between base and destination locations on individual mobility networks. We provide a systematic analysis of generic dynamical features of the model on regular and complex metapopulation network topologies and show that significant dynamical differences exist to ordinary reaction-diffusion and effective force of infection models. On a lattice we calculate an expression for the velocity of the propagating epidemic front and find that in contrast to the diffusive systems, our model predicts a saturation of the velocity with increasing traveling rate. Furthermore, we show that a fully stochastic system exhibits a novel threshold for attack ratio of an outbreak absent in diffusion and force of infection models. These insights not only capture natural features of human mobility relevant for the geographical epidemic spread, they may serve as a starting point for modeling important dynamical processes in human and animal epidemiology, population ecology, biology and evolution.
• ### Modularity maximization and tree clustering: Novel ways to determine effective geographic borders(1104.1200)

April 6, 2011 physics.soc-ph, cs.SI
Territorial subdivisions and geographic borders are essential for understanding phenomena in sociology, political science, history, and economics. They influence the interregional flow of information and cross-border trade and affect the diffusion of innovation and technology. However, most existing administrative borders were determined by a variety of historic and political circumstances along with some degree of arbitrariness. Societies have changed drastically, and it is doubtful that currently existing borders reflect the most logical divisions. Fortunately, at this point in history we are in a position to actually measure some aspects of the geographic structure of society through human mobility. Large-scale transportation systems such as trains and airlines provide data about the number of people traveling between geographic locations, and many promising human mobility proxies are being discovered, such as cell phones, bank notes, and various online social networks. In this chapter we apply two optimization techniques to a human mobility proxy (bank note circulation) to investigate the effective geographic borders that emerge from a direct analysis of human mobility.
• ### Complexity in human transportation networks: A comparative analysis of worldwide air transportation and global cargo ship movements(1103.5451)

We present a comparative network theoretic analysis of the two largest global transportation networks: The worldwide air-transportation network (WAN) and the global cargoship network (GCSN). We show that both networks exhibit striking statistical similarities despite significant differences in topology and connectivity. Both networks exhibit a discontinuity in node and link betweenness distributions which implies that these networks naturally segragate in two different classes of nodes and links. We introduce a technique based on effective distances, shortest paths and shortest-path trees for strongly weighted symmetric networks and show that in a shortest-path-tree representation the most significant features of both networks can be readily seen. We show that effective shortest-path distance, unlike conventional geographic distance measures, strongly correlates with node centrality measures. Using the new technique we show that network resilience can be investigated more precisely than with contemporary techniques that are based on percolation theory. We extract a functional relationship between node characteristics and resilience to network disruption. Finally we discuss the results, their implications and conclude that dynamic processes that evolve on both networks are expected to share universal dynamic characteristics.
• ### Accelerating random walks by disorder(cond-mat/0611530)

Nov. 20, 2006 cond-mat.stat-mech
We investigate the dynamic impact of heterogeneous environments on superdiffusive random walks known as L\'evy flights. We devote particular attention to the relative weight of source and target locations on the rates for spatial displacements of the random walk. Unlike ordinary random walks which are slowed down for all values of the relative weight of source and target, non-local superdiffusive processes show distinct regimes of attenuation and acceleration for increased source and target weight, respectively. Consequently, spatial inhomogeneities can facilitate the spread of superdiffusive processes, in contrast to common belief that external disorder generally slows down stochastic processes. Our results are based on a novel type of fractional Fokker-Planck equation which we investigate numerically and by perturbation theory for weak disorder.
• ### Levy Flights in External Force Fields: From Models to Equations(cond-mat/0210387)

Oct. 17, 2002 cond-mat.stat-mech
We consider different generalizations of the Fokker-Planck-equation devised to describe Levy processes in potential force fields. We show that such generalizations can proceed along different lines. On one hand, Levy statistics can emerge from the fractal temporal nature of the underlying process, i.e. a high variability in the rate of microscopic events. On the other hand, they may be a direct consequence of the scale-free spatial structure on which the process evolves. Although both forms considered lead to Boltzmann equilibrium, the relaxation patterns are quite different. As an example, generalized diffusion in a double-well potential is considered.