Long-Range Navigation on Complex Networks using L\'evy Random Walks

There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

Abstract

We introduce a strategy of navigation in undirected networks, including regular, random, and complex networks, that is inspired by L\'evy random walks, generalizing previous navigation rules. We obtained exact expressions for the stationary probability distribution, the occupation probability, the mean first passage time, and the average time to reach a node on the network. We found that the long-range navigation using the L\'evy random walk strategy, compared with the normal random walk strategy, is more efficient at reducing the time to cover the network. The dynamical effect of using the L\'evy walk strategy is to transform a large-world network into a small world. Our exact results provide a general framework that connects two important fields: L\'evy navigation strategies and dynamics on complex networks.

Related collections

Most cited references 10

Record: found
Abstract: found
Article: found

Is Open Access

The scaling laws of human travel

L Hufnagel, T Geisel, D Brockmann (2006)

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.

0 comments Cited 408 times – based on 0 reviews

Preprint

     Review now

Bookmark

Record: found
Abstract: found
Article: not found

Identifying influential and susceptible members of social networks.

Sinan Aral, Dylan Walker (2012)

Identifying social influence in networks is critical to understanding how behaviors spread. We present a method that uses in vivo randomized experimentation to identify influence and susceptibility in networks while avoiding the biases inherent in traditional estimates of social contagion. Estimation in a representative sample of 1.3 million Facebook users showed that younger users are more susceptible to influence than older users, men are more influential than women, women influence men more than they influence other women, and married individuals are the least susceptible to influence in the decision to adopt the product offered. Analysis of influence and susceptibility together with network structure revealed that influential individuals are less susceptible to influence than noninfluential individuals and that they cluster in the network while susceptible individuals do not, which suggests that influential people with influential friends may be instrumental in the spread of this product in the network.

0 comments Cited 288 times – based on 0 reviews      Review now

Bookmark

Record: found
Abstract: found
Article: found

Is Open Access

A universal model for mobility and migration patterns

Amos Maritan, Albert-László Barabási, Marta González … (2011)

Introduced in its contemporary form by George Kingsley Zipf in 1946, but with roots that go back to the work of Gaspard Monge in the 18th century, the gravity law is the prevailing framework to predict population movement, cargo shipping volume, inter-city phone calls, as well as bilateral trade flows between nations. Despite its widespread use, it relies on adjustable parameters that vary from region to region and suffers from known analytic inconsistencies. Here we introduce a stochastic process capturing local mobility decisions that helps us analytically derive commuting and mobility fluxes that require as input only information on the population distribution. The resulting radiation model predicts mobility patterns in good agreement with mobility and transport patterns observed in a wide range of phenomena, from long-term migration patterns to communication volume between different regions. Given its parameter-free nature, the model can be applied in areas where we lack previous mobility measurements, significantly improving the predictive accuracy of most of phenomena affected by mobility and transport processes.