Understanding individual human mobility patterns

We present a general, physically motivated non-linear and non-local advection equation in which the diffusion of interacting random walkers competes with a local drift arising from a kind of peer pressure. We show, using a mapping to an integrable dynamical system, that on varying a parameter, the steady state behaviour undergoes a transition from the standard diffusive behavior to a localized stationary state characterized by a tailed distribution. Finally, we show that recent empirical laws on economic growth can be explained as a collective phenomenon due to peer pressure interaction.

The dynamics of many social, technological and economic phenomena are driven by individual human actions, turning the quantitative understanding of human behavior into a central question of modern science. Current models of human dynamics, used from risk assessment to communications, assume that human actions are randomly distributed in time and thus well approximated by Poisson processes. In contrast, there is increasing evidence that the timing of many human activities, ranging from communication to entertainment and work patterns, follow non-Poisson statistics, characterized by bursts of rapidly occurring events separated by long periods of inactivity. Here we show that the bursty nature of human behavior is a consequence of a decision based queuing process: when individuals execute tasks based on some perceived priority, the timing of the tasks will be heavy tailed, most tasks being rapidly executed, while a few experience very long waiting times. In contrast, priority blind execution is well approximated by uniform interevent statistics. These findings have important implications from resource management to service allocation in both communications and retail.

Complex networks have been studied extensively due to their relevance to many real systems as diverse as the World-Wide-Web (WWW), the Internet, energy landscapes, biological and social networks \cite{ab-review,mendes,vespignani,newman,amaral}. A large number of real networks are called ``scale-free'' because they show a power-law distribution of the number of links per node \cite{ab-review,barabasi1999,faloutsos}. However, it is widely believed that complex networks are not {\it length-scale} invariant or self-similar. This conclusion originates from the ``small-world'' property of these networks, which implies that the number of nodes increases exponentially with the ``diameter'' of the network \cite{erdos,bollobas,milgram,watts}, rather than the power-law relation expected for a self-similar structure. Nevertheless, here we present a novel approach to the analysis of such networks, revealing that their structure is indeed self-similar. This result is achieved by the application of a renormalization procedure which coarse-grains the system into boxes containing nodes within a given "size". Concurrently, we identify a power-law relation between the number of boxes needed to cover the network and the size of the box defining a finite self-similar exponent. These fundamental properties, which are shown for the WWW, social, cellular and protein-protein interaction networks, help to understand the emergence of the scale-free property in complex networks. They suggest a common self-organization dynamics of diverse networks at different scales into a critical state and in turn bring together previously unrelated fields: the statistical physics of complex networks with renormalization group, fractals and critical phenomena.

How long does it take a random walker to reach a given target point? This quantity, known as a first-passage time (FPT), has led to a growing number of theoretical investigations over the past decade. The importance of FPTs originates from the crucial role played by first encounter properties in various real situations, including transport in disordered media, neuron firing dynamics, spreading of diseases or target search processes. Most methods of determining FPT properties in confining domains have been limited to effectively one-dimensional geometries, or to higher spatial dimensions only in homogeneous media. Here we develop a general theory that allows accurate evaluation of the mean FPT in complex media. Our analytical approach provides a universal scaling dependence of the mean FPT on both the volume of the confining domain and the source-target distance. The analysis is applicable to a broad range of stochastic processes characterized by length-scale-invariant properties. Our theoretical predictions are confirmed by numerical simulations for several representative models of disordered media, fractals, anomalous diffusion and scale-free networks.

The highly pathogenic H5N1 avian influenza virus, which is now widespread in Southeast Asia and which diffused recently in some areas of the Balkans region and Western Europe, has raised a public alert toward the potential occurrence of a new severe influenza pandemic. Here we study the worldwide spread of a pandemic and its possible containment at a global level taking into account all available information on air travel.We studied a metapopulation stochastic epidemic model on a global scale that considers airline travel flow data among urban areas. We provided a temporal and spatial evolution of the pandemic with a sensitivity analysis of different levels of infectiousness of the virus and initial outbreak conditions (both geographical and seasonal). For each spreading scenario we provided the timeline and the geographical impact of the pandemic in 3,100 urban areas, located in 220 different countries. We compared the baseline cases with different containment strategies, including travel restrictions and the therapeutic use of antiviral (AV) drugs. We investigated the effect of the use of AV drugs in the event that therapeutic protocols can be carried out with maximal coverage for the populations in all countries. In view of the wide diversity of AV stockpiles in different regions of the world, we also studied scenarios in which only a limited number of countries are prepared (i.e., have considerable AV supplies). In particular, we compared different plans in which, on the one hand, only prepared and wealthy countries benefit from large AV resources, with, on the other hand, cooperative containment scenarios in which countries with large AV stockpiles make a small portion of their supplies available worldwide.We show that the inclusion of air transportation is crucial in the assessment of the occurrence probability of global outbreaks. The large-scale therapeutic usage of AV drugs in all hit countries would be able to mitigate a pandemic effect with a reproductive rate as high as 1.9 during the first year; with AV supply use sufficient to treat approximately 2% to 6% of the population, in conjunction with efficient case detection and timely drug distribution. For highly contagious viruses (i.e., a reproductive rate as high as 2.3), even the unrealistic use of supplies corresponding to the treatment of approximately 20% of the population leaves 30%-50% of the population infected. In the case of limited AV supplies and pandemics with a reproductive rate as high as 1.9, we demonstrate that the more cooperative the strategy, the more effective are the containment results in all regions of the world, including those countries that made part of their resources available for global use.

We introduce a class of stochastic process, the truncated L\'evy flight (TLF), in which the arbitrarily large steps of a L\'evy flight are eliminated. We find that the convergence of the sum of $n$ independent TLFs to a Gaussian process can require a remarkably large value of $n$---typically $n\ensuremath{\approx}{10}^{4}$ in contrast to $n\ensuremath{\approx}10$ for common distributions. We find a well-defined crossover between a L\'evy and a Gaussian regime, and that the crossover carries information about the relevant parameters of the underlying stochastic process.

Abstract We explore the idea of endogenous hub location on a network. In contrast to much of the literature, we propose that hub networks may emerge naturally out of a set of assumptions and conditions borrowed from equilibrium traffic assignment. To this end, we focus on applying a nonlinear cost function that rewards economies of scale on all network links. A model is presented and implemented in a GIS environment using both a 100-node intercity matrix and several synthesized interaction matrices. We compare solutions for different assumptions about network costs, and visualize the results. We find that under discounted conditions, network flow is re-routed to take advantage of the cost savings for amalgamation and that several cities emerge as centers through which large amounts of flow pass. Larger cities such as Los Angeles, New York and Chicago serve gateway functions. We also find that smaller cities such as Oklahoma City, Pittsburgh, Indianapolis, and Knoxville serve major gateway functions because of their locational advantages. Our paper should be of interest to the planner of a surface transportation system, or those interested in nodal concepts such as gateways and transport geography. Results are discussed in light of hub and spoke networks and suggestions are made for future research.

Newtonian physics began with an attempt to make precise predictions about natural phenomena, predictions that could be accurately checked by observation and experiment. The goal was to understand nature as a deterministic, “clockwork” universe. The application of probability distributions to physics developed much more slowly. Early uses of probability arguments focused on distributions with well‐defined means and variances. The prime example was the Gaussian law of errors, in which the mean traditionally represented the most probable value from a series of repeated measurements of a fixed quantity, and the variance was related to the uncertainty of those measurements.

The dynamic spatial redistribution of individuals is a key driving force of various spatiotemporal phenomena on geographical scales. It can synchronise populations of interacting species, stabilise them, and diversify gene pools [1-3]. Human travelling, e.g. is responsible for the geographical spread of human infectious disease [4-9]. In the light of increasing international trade, intensified human mobility and an imminent influenza A epidemic [10] the knowledge of dynamical and statistical properties of human travel is thus of fundamental importance. Despite its crucial role, a quantitative assessment of these properties on geographical scales remains elusive and the assumption that humans disperse diffusively still prevails in models. Here we report on a solid and quantitative assessment of human travelling statistics by analysing the circulation of bank notes in the United States. Based on a comprehensive dataset of over a million individual displacements we find that dispersal is anomalous in two ways. First, the distribution of travelling distances decays as a power law, indicating that trajectories of bank notes are reminiscent of scale free random walks known as Levy flights. Secondly, the probability of remaining in a small, spatially confined region for a time T is dominated by algebraically long tails which attenuate the superdiffusive spread. We show that human travelling behaviour can be described mathematically on many spatiotemporal scales by a two parameter continuous time random walk model to a surprising accuracy and conclude that human travel on geographical scales is an ambivalent effectively superdiffusive process.

We propose a model of mobile agents to construct social networks, based on a system of moving particles by keeping track of the collisions during their permanence in the system. We reproduce not only the degree distribution, clustering coefficient and shortest path length of a large data base of empirical friendship networks recently collected, but also some features related with their community structure. The model is completely characterized by the collision rate and above a critical collision rate we find the emergence of a giant cluster in the universality class of two-dimensional percolation. Moreover, we propose possible schemes to reproduce other networks of particular social contacts, namely sexual contacts.

Data on the movement of people becomes ever more detailed, but robust models explaining the observed patterns are still needed. Mapping the problem onto a 'network of networks' could be a promising approach.

The rich set of interactions between individuals in society results in complex community structure, capturing highly connected circles of friends, families or professional cliques in a social network. Thanks to frequent changes in the activity and communication patterns of individuals, the associated social and communication network is subject to constant evolution. Our knowledge of the mechanisms governing the underlying community dynamics is limited, but is essential for a deeper understanding of the development and self-optimization of society as a whole. We have developed an algorithm based on clique percolation that allows us to investigate the time dependence of overlapping communities on a large scale, and thus uncover basic relationships characterizing community evolution. Our focus is on networks capturing the collaboration between scientists and the calls between mobile phone users. We find that large groups persist for longer if they are capable of dynamically altering their membership, suggesting that an ability to change the group composition results in better adaptability. The behaviour of small groups displays the opposite tendency-the condition for stability is that their composition remains unchanged. We also show that knowledge of the time commitment of members to a given community can be used for estimating the community's lifetime. These findings offer insight into the fundamental differences between the dynamics of small groups and large institutions.

Diffusion in disordered systems does not follow the classical laws which describe transport in ordered crystalline media, and this leads to many anomalous physical properties. Since the application of percolation theory, the main advances in the understanding of these processes have come from fractal theory. Scaling theories and numerical simulations are important tools to describe diffusion processes (random walks: the 'ant in the labyrinth') on percolation systems and fractals. Different types of disordered systems exhibiting anomalous diffusion are presented (the incipient infinite percolation cluster, diffusion-limited aggregation clusters, lattice animals, and random combs), and scaling theories as well as numerical simulations of greater sophistication are described. Also, diffusion in the presence of singular distributions of transition rates is discussed and related to anomalous diffusion on disordered structures.

The rapid worldwide spread of severe acute respiratory syndrome demonstrated the potential threat an infectious disease poses in a closely interconnected and interdependent world. Here we introduce a probabilistic model that describes the worldwide spread of infectious diseases and demonstrate that a forecast of the geographical spread of epidemics is indeed possible. This model combines a stochastic local infection dynamics among individuals with stochastic transport in a worldwide network, taking into account national and international civil aviation traffic. Our simulations of the severe acute respiratory syndrome outbreak are in surprisingly good agreement with published case reports. We show that the high degree of predictability is caused by the strong heterogeneity of the network. Our model can be used to predict the worldwide spread of future infectious diseases and to identify endangered regions in advance. The performance of different control strategies is analyzed, and our simulations show that a quick and focused reaction is essential to inhibiting the global spread of epidemics.

Abstract The empirical study of network dynamics has been limited by the lack of longitudinal data. Here we introduce a quantitative indicator of link persistence to explore the correlations between the structure of a mobile phone network and the persistence of its links. We show that persistent links tend to be reciprocal and are more common for people with low degree and high clustering. We study the redundancy of the associations between persistence, degree, clustering and reciprocity and show that reciprocity is the strongest predictor of tie persistence. The method presented can be easily adapted to characterize the dynamics of other networks and can be used to identify the links that are most likely to survive in the future.

Network generators that capture the Internet's large-scale topology are crucial for the development of efficient routing protocols and modeling Internet traffic. Our ability to design realistic generators is limited by the incomplete understanding of the fundamental driving forces that affect the Internet's evolution. By combining several independent databases capturing the time evolution, topology, and physical layout of the Internet, we identify the universal mechanisms that shape the Internet's router and autonomous system level topology. We find that the physical layout of nodes form a fractal set, determined by population density patterns around the globe. The placement of links is driven by competition between preferential attachment and linear distance dependence, a marked departure from the currently used exponential laws. The universal parameters that we extract significantly restrict the class of potentially correct Internet models and indicate that the networks created by all available topology generators are fundamentally different from the current Internet.

Electronic databases, from phone to e-mails logs, currently provide detailed records of human communication patterns, offering novel avenues to map and explore the structure of social and communication networks. Here we examine the communication patterns of millions of mobile phone users, allowing us to simultaneously study the local and the global structure of a society-wide communication network. We observe a coupling between interaction strengths and the network's local structure, with the counterintuitive consequence that social networks are robust to the removal of the strong ties but fall apart after a phase transition if the weak ties are removed. We show that this coupling significantly slows the diffusion process, resulting in dynamic trapping of information in communities and find that, when it comes to information diffusion, weak and strong ties are both simultaneously ineffective.

The study of animal foraging behaviour is of practical ecological importance, and exemplifies the wider scientific problem of optimizing search strategies. Lévy flights are random walks, the step lengths of which come from probability distributions with heavy power-law tails, such that clusters of short steps are connected by rare long steps. Lévy flights display fractal properties, have no typical scale, and occur in physical and chemical systems. An attempt to demonstrate their existence in a natural biological system presented evidence that wandering albatrosses perform Lévy flights when searching for prey on the ocean surface. This well known finding was followed by similar inferences about the search strategies of deer and bumblebees. These pioneering studies have triggered much theoretical work in physics (for example, refs 11, 12), as well as empirical ecological analyses regarding reindeer, microzooplankton, grey seals, spider monkeys and fishing boats. Here we analyse a new, high-resolution data set of wandering albatross flights, and find no evidence for Lévy flight behaviour. Instead we find that flight times are gamma distributed, with an exponential decay for the longest flights. We re-analyse the original albatross data using additional information, and conclude that the extremely long flights, essential for demonstrating Lévy flight behaviour, were spurious. Furthermore, we propose a widely applicable method to test for power-law distributions using likelihood and Akaike weights. We apply this to the four original deer and bumblebee data sets, finding that none exhibits evidence of Lévy flights, and that the original graphical approach is insufficient. Such a graphical approach has been adopted to conclude Lévy flight movement for other organisms, and to propose Lévy flight analysis as a potential real-time ecosystem monitoring tool. Our results question the strength of the empirical evidence for biological Lévy flights.

First-passage properties underlie a wide range of stochastic processes, such as diffusion-limited growth, neuron firing and the triggering of stock options. This book provides a unified presentation of first-passage processes, which highlights its interrelations with electrostatics and the resulting powerful consequences. The author begins with a presentation of fundamental theory including the connection between the occupation and first-passage probabilities of a random walk, and the connection to electrostatics and current flows in resistor networks. The consequences of this theory are then developed for simple, illustrative geometries including the finite and semi-infinite intervals, fractal networks, spherical geometries and the wedge. Various applications are presented including neuron dynamics, self-organized criticality, diffusion-limited aggregation, the dynamics of spin systems and the kinetics of diffusion-controlled reactions. First-passage processes provide an appealing way for graduate students and researchers in physics, chemistry, theoretical biology, electrical engineering, chemical engineering, operations research and finance to understand all of these systems.

Abstract A variety of different social, natural and technological systems can be described by the same mathematical framework. This holds from the Internet to food webs and to boards of company directors. In all these situations, a graph of the elements of the system and their interconnections displays a universal feature. There are only a few elements with many connections and many elements with few connections. This book reports the experimental evidence of these ‘Scale-free networks’ and provides students and researchers with a corpus of theoretical results and algorithms to analyse and understand these features. The content of this book and the exposition makes it a clear textbook for beginners and a reference book for experts.