1
|
Lee KJ, Lee KA, Kook W, Lee T. Fractional centralities on networks: Consolidating the local and the global. Phys Rev E 2022; 106:034310. [PMID: 36266875 DOI: 10.1103/physreve.106.034310] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 03/30/2022] [Accepted: 08/23/2022] [Indexed: 06/16/2023]
Abstract
We propose a new centrality incorporating two classical node-level centralities, the degree centrality and the information centrality, which are considered as local and global centralities, respectively. These two centralities have expressions in terms of the graph Laplacian L, which motivates us to exploit its fractional analog L^{γ} with a fractional parameter γ. As γ varies from 0 to 1, the proposed fractional version of the information centrality makes intriguing changes in the node centrality rankings. These changes could not be generated by the fractional degree centrality since it is mostly influenced by the local aspect. We prove that these two fractional centralities behave similarly when γ is close to 0. This result provides its complete understanding of the boundary of the interval in which γ lies since the fractional information centrality with γ=1 is the usual information centrality. Moreover, our computation for the correlation coefficients between the fractional information centrality and the degree centrality reveals that the fractional information centrality is transformed from a local centrality into being a global one as γ changes from 0 to 1.
Collapse
Affiliation(s)
- Kang-Ju Lee
- Research Institute of Mathematics, Seoul National University, Seoul 08826, Korea
| | - Ki-Ahm Lee
- Department of Mathematical Sciences, Seoul National University, Seoul 08826, Korea
| | - Woong Kook
- Department of Mathematical Sciences, Seoul National University, Seoul 08826, Korea
| | - Taehun Lee
- School of Mathematics, Korea Institute for Advanced Study, Seoul 02455, Korea
| |
Collapse
|
2
|
The influence of a transport process on the epidemic threshold. J Math Biol 2022; 85:62. [PMID: 36307593 PMCID: PMC9616790 DOI: 10.1007/s00285-022-01810-7] [Citation(s) in RCA: 1] [Impact Index Per Article: 0.5] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 12/09/2021] [Revised: 04/27/2022] [Accepted: 07/05/2022] [Indexed: 12/29/2022]
Abstract
By generating transient encounters between individuals beyond their immediate social environment, transport can have a profound impact on the spreading of an epidemic. In this work, we consider epidemic dynamics in the presence of the transport process that gives rise to a multiplex network model. In addition to a static layer, the (multiplex) epidemic network consists of a second dynamic layer in which any two individuals are connected for the time they occupy the same site during a random walk they perform on a separate transport network. We develop a mean-field description of the stochastic network model and study the influence the transport process has on the epidemic threshold. We show that any transport process generally lowers the epidemic threshold because of the additional connections it generates. In contrast, considering also random walks of fractional order that in some sense are a more realistic model of human mobility, we find that these non-local transport dynamics raise the epidemic threshold in comparison to a classical local random walk. We also test our model on a realistic transport network (the Munich U-Bahn network), and carefully compare mean-field solutions with stochastic trajectories in a range of scenarios.
Collapse
|
3
|
González FH, Riascos AP, Boyer D. Diffusive transport on networks with stochastic resetting to multiple nodes. Phys Rev E 2021; 103:062126. [PMID: 34271672 DOI: 10.1103/physreve.103.062126] [Citation(s) in RCA: 9] [Impact Index Per Article: 3.0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 04/01/2021] [Accepted: 05/27/2021] [Indexed: 01/30/2023]
Abstract
We study the diffusive transport of Markovian random walks on arbitrary networks with stochastic resetting to multiple nodes. We deduce analytical expressions for the stationary occupation probability and for the mean and global first passage times. This general approach allows us to characterize the effect of resetting on the capacity of random walk strategies to reach a particular target or to explore the network. Our formalism holds for ergodic random walks and can be implemented from the spectral properties of the random walk without resetting, providing a tool to analyze the efficiency of search strategies with resetting to multiple nodes. We apply the methods developed here to the dynamics with two reset nodes and derive analytical results for normal random walks and Lévy flights on rings. We also explore the effect of resetting to multiple nodes on a comb graph, Lévy flights that visit specific locations in a continuous space, and the Google random walk strategy on regular networks.
Collapse
Affiliation(s)
- Fernanda H González
- Instituto de Física, Universidad Nacional Autónoma de México, Apartado Postal 20-364, 01000 Ciudad de México, México
| | - Alejandro P Riascos
- Instituto de Física, Universidad Nacional Autónoma de México, Apartado Postal 20-364, 01000 Ciudad de México, México
| | - Denis Boyer
- Instituto de Física, Universidad Nacional Autónoma de México, Apartado Postal 20-364, 01000 Ciudad de México, México
| |
Collapse
|
4
|
Riascos AP, Sanders DP. Mean encounter times for multiple random walkers on networks. Phys Rev E 2021; 103:042312. [PMID: 34005853 DOI: 10.1103/physreve.103.042312] [Citation(s) in RCA: 6] [Impact Index Per Article: 2.0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 08/28/2020] [Accepted: 03/23/2021] [Indexed: 01/18/2023]
Abstract
We introduce a general approach for the study of the collective dynamics of noninteracting random walkers on connected networks. We analyze the movement of R independent (Markovian) walkers, each defined by its own transition matrix. By using the eigenvalues and eigenvectors of the R independent transition matrices, we deduce analytical expressions for the collective stationary distribution and the average number of steps needed by the random walkers to start in a particular configuration and reach specific nodes the first time (mean first-passage times), as well as global times that characterize the global activity. We apply these results to the study of mean first-encounter times for local and nonlocal random walk strategies on different types of networks, with both synchronous and asynchronous motion.
Collapse
Affiliation(s)
- Alejandro P Riascos
- Instituto de Física, Universidad Nacional Autónoma de México, Ciudad Universitaria, Ciudad de México 04510, Mexico
| | - David P Sanders
- Departamento de Física, Facultad de Ciencias, Universidad Nacional Autónoma de México, Ciudad Universitaria, Ciudad de México 04510, Mexico and Department of Mathematics, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139, USA
| |
Collapse
|
5
|
Systemic States of Spreading Activation in Describing Associative Knowledge Networks II: Generalisations with Fractional Graph Laplacians and q-Adjacency Kernels. SYSTEMS 2021. [DOI: 10.3390/systems9020022] [Citation(s) in RCA: 3] [Impact Index Per Article: 1.0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Indexed: 01/01/2023]
Abstract
Associative knowledge networks are often explored by using the so-called spreading activation model to find their key items and their rankings. The spreading activation model is based on the idea of diffusion- or random walk -like spreading of activation in the network. Here, we propose a generalisation, which relaxes an assumption of simple Brownian-like random walk (or equally, ordinary diffusion process) and takes into account nonlocal jump processes, typical for superdiffusive processes, by using fractional graph Laplacian. In addition, the model allows a nonlinearity of the diffusion process. These generalizations provide a dynamic equation that is analogous to fractional porous medium diffusion equation in a continuum case. A solution of the generalized equation is obtained in the form of a recently proposed q-generalized matrix transformation, the so-called q-adjacency kernel, which can be adopted as a systemic state describing spreading activation. Based on the systemic state, a new centrality measure called activity centrality is introduced for ranking the importance of items (nodes) in spreading activation. To demonstrate the viability of analysis based on systemic states, we use empirical data from a recently reported case of a university students’ associative knowledge network about the history of science. It is shown that, while a choice of model does not alter rankings of the items with the highest rank, rankings of nodes with lower ranks depend essentially on the diffusion model.
Collapse
|
6
|
Abstract
Existing graph filters, polynomial or rational, are mainly of integer order forms. However, there are some frequency responses which are not easily achieved by integer order approximation. It will substantially increase the flexibility of the filters if we relax the integer order to fractional ones. Motivated by fractional order models, we introduce the fractional order graph filters (FOGF), and propose to design the filter coefficients by genetic algorithm. In order to implement distributed computation on a graph, an FOGF can be approximated by the continued fraction expansion and transformed to an infinite impulse response graph filter.
Collapse
|
7
|
Abstract
We construct admissible circulant Laplacian matrix functions as generators for strictly increasing random walks on the integer line. These Laplacian matrix functions refer to a certain class of Bernstein functions. The approach has connections with biased walks on digraphs. Within this framework, we introduce a space-time generalization of the Poisson process as a strictly increasing walk with discrete Mittag-Leffler jumps time-changed with an independent (continuous-time) fractional Poisson process. We call this process ‘space-time Mittag-Leffler process’. We derive explicit formulae for the state probabilities which solve a Cauchy problem with a Kolmogorov-Feller (forward) difference-differential equation of general fractional type. We analyze a “well-scaled” diffusion limit and obtain a Cauchy problem with a space-time convolution equation involving Mittag-Leffler densities. We deduce in this limit the ‘state density kernel’ solving this Cauchy problem. It turns out that the diffusion limit exhibits connections to Prabhakar general fractional calculus. We also analyze in this way a generalization of the space-time Mittag-Leffler process. The approach of constructing good Laplacian generator functions has a large potential in applications of space-time generalizations of the Poisson process and in the field of continuous-time random walks on digraphs.
Collapse
|
8
|
Riascos AP, Michelitsch TM, Pizarro-Medina A. Nonlocal biased random walks and fractional transport on directed networks. Phys Rev E 2020; 102:022142. [PMID: 32942357 DOI: 10.1103/physreve.102.022142] [Citation(s) in RCA: 3] [Impact Index Per Article: 0.8] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 04/01/2020] [Accepted: 08/13/2020] [Indexed: 06/11/2023]
Abstract
In this paper, we study nonlocal random walk strategies generated with the fractional Laplacian matrix of directed networks. We present a general approach to analyzing these strategies by defining the dynamics as a discrete-time Markovian process with transition probabilities between nodes expressed in terms of powers of the Laplacian matrix. We analyze the elements of the transition matrices and their respective eigenvalues and eigenvectors, the mean first passage times and global times to characterize the random walk strategies. We apply this approach to the study of particular local and nonlocal ergodic random walks on different directed networks; we explore circulant networks, the biased transport on rings and the dynamics on random networks. We study the efficiency of a fractional random walker with bias on these structures. Effects of ergodicity loss which occur when a directed network is not any more strongly connected are also discussed.
Collapse
Affiliation(s)
- A P Riascos
- Instituto de Física, Universidad Nacional Autónoma de México, Apartado Postal 20-364, 01000 Ciudad de México, México
| | - T M Michelitsch
- Sorbonne Université, Institut Jean le Rond d'Alembert, CNRS UMR 7190,4 place Jussieu, 75252 Paris cedex 05, France
| | - A Pizarro-Medina
- Departamento de Física, Facultad de Ciencias, Universidad Nacional Autónoma de México, Ciudad Universitaria, Ciudad de México 04510, México
| |
Collapse
|
9
|
Estrada E. Fractional diffusion on the human proteome as an alternative to the multi-organ damage of SARS-CoV-2. CHAOS (WOODBURY, N.Y.) 2020; 30:081104. [PMID: 32872802 PMCID: PMC7585451 DOI: 10.1063/5.0015626] [Citation(s) in RCA: 5] [Impact Index Per Article: 1.3] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Subscribe] [Scholar Register] [Received: 05/29/2020] [Accepted: 07/15/2020] [Indexed: 05/16/2023]
Abstract
The coronavirus 2019 (COVID-19) respiratory disease is caused by the novel coronavirus SARS-CoV-2 (severe acute respiratory syndrome coronavirus 2), which uses the enzyme ACE2 to enter human cells. This disease is characterized by important damage at a multi-organ level, partially due to the abundant expression of ACE2 in practically all human tissues. However, not every organ in which ACE2 is abundant is affected by SARS-CoV-2, which suggests the existence of other multi-organ routes for transmitting the perturbations produced by the virus. We consider here diffusive processes through the protein-protein interaction (PPI) network of proteins targeted by SARS-CoV-2 as an alternative route. We found a subdiffusive regime that allows the propagation of virus perturbations through the PPI network at a significant rate. By following the main subdiffusive routes across the PPI network, we identify proteins mainly expressed in the heart, cerebral cortex, thymus, testis, lymph node, kidney, among others of the organs reported to be affected by COVID-19.
Collapse
Affiliation(s)
- Ernesto Estrada
- Instituto Universitario de Matemáticas y Aplicaciones, Universidad de Zaragoza, 50009 Zaragoza, Spain and ARAID Foundation, Government of Aragón, 50018 Zaragoza, Spain
| |
Collapse
|
10
|
Riascos AP, Boyer D, Herringer P, Mateos JL. Random walks on networks with stochastic resetting. Phys Rev E 2020; 101:062147. [PMID: 32688619 DOI: 10.1103/physreve.101.062147] [Citation(s) in RCA: 23] [Impact Index Per Article: 5.8] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 10/25/2019] [Accepted: 06/12/2020] [Indexed: 06/11/2023]
Abstract
We study random walks with stochastic resetting to the initial position on arbitrary networks. We obtain the stationary probability distribution as well as the mean and global first passage times, which allow us to characterize the effect of resetting on the capacity of a random walker to reach a particular target or to explore a finite network. We apply the results to rings, Cayley trees, and random and complex networks. Our formalism holds for undirected networks and can be implemented from the spectral properties of the random walk without resetting, providing a tool to analyze the search efficiency in different structures with the small-world property or communities. In this way, we extend the study of resetting processes to the domain of networks.
Collapse
Affiliation(s)
- Alejandro P Riascos
- Instituto de Física, Universidad Nacional Autónoma de México, Apartado Postal 20-364, 01000 Ciudad de México, México
| | - Denis Boyer
- Instituto de Física, Universidad Nacional Autónoma de México, Apartado Postal 20-364, 01000 Ciudad de México, México
| | - Paul Herringer
- Department of Physics and Astronomy, University of Calgary, Calgary, Alberta, Canada T2N 1N4
| | - José L Mateos
- Instituto de Física, Universidad Nacional Autónoma de México, Apartado Postal 20-364, 01000 Ciudad de México, México
- Centro de Ciencias de la Complejidad, Universidad Nacional Autónoma de México, 04510 Ciudad de México, México
| |
Collapse
|
11
|
Riascos AP, Mateos JL. Networks and long-range mobility in cities: A study of more than one billion taxi trips in New York City. Sci Rep 2020; 10:4022. [PMID: 32132592 PMCID: PMC7055277 DOI: 10.1038/s41598-020-60875-w] [Citation(s) in RCA: 15] [Impact Index Per Article: 3.8] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 12/03/2019] [Accepted: 02/07/2020] [Indexed: 11/16/2022] Open
Abstract
We analyze the massive data set of more than one billion taxi trips in New York City, from January 2009 to December 2015. With these records of seven years, we generate an origin-destination matrix that has information of a vast number of trips. The mobility and flow of taxis can be described as a directed weighted network that connects different zones of high demand for taxis. This network has in and out degrees that follow a stretched exponential and a power law with an exponential cutoff distributions, respectively. Using the origin-destination matrix, we obtain a rank, called "OD rank”, analogous to the page rank of Google, that gives the more relevant places in New York City in terms of taxi trips. We introduced a model that captures the local and global dynamics that agrees with the data. Considering the taxi trips as a proxy of human mobility in cities, it might be possible that the long-range mobility found for New York City would be a general feature in other large cities around the world.
Collapse
Affiliation(s)
- A P Riascos
- Instituto de Física, Universidad Nacional Autónoma de México, Apartado Postal 20-364, 01000, Ciudad de México, Mexico.
| | - José L Mateos
- Instituto de Física, Universidad Nacional Autónoma de México, Apartado Postal 20-364, 01000, Ciudad de México, Mexico. .,Centro de Ciencias de la Complejidad, Universidad Nacional Autónoma de México, Apartado Postal 04510, Ciudad de México, Mexico.
| |
Collapse
|
12
|
Capała K, Dybiec B, Gudowska-Nowak E. Peculiarities of escape kinetics in the presence of athermal noises. CHAOS (WOODBURY, N.Y.) 2020; 30:013127. [PMID: 32013513 DOI: 10.1063/1.5126263] [Citation(s) in RCA: 1] [Impact Index Per Article: 0.3] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 08/31/2019] [Accepted: 12/19/2019] [Indexed: 06/10/2023]
Abstract
Stochastic evolution of various dynamic systems and reaction networks is commonly described in terms of noise assisted escape of an overdamped particle from a potential well, as devised by the paradigmatic Langevin equation in which additive Gaussian stochastic force reproduces effects of thermal fluctuations from the reservoir. When implemented for systems close to equilibrium, the approach correctly explains the emergence of the Boltzmann distribution for the ensemble of trajectories generated by the Langevin equation and relates the intensity of the noise strength to the mobility. This scenario can be further generalized to include effects of non-Gaussian, burstlike forcing modeled by Lévy noise. In this case, however, the pulsatile additive noise cannot be treated as the internal (thermal) since the relation between the strength of the friction and variance of the noise is violated. Heavy tails of Lévy noise distributions not only facilitate escape kinetics, but also, more importantly, change the escape protocol by altering the final stationary state to a non-Boltzmann, nonequilibrium form. As a result, contrary to the kinetics induced by a Gaussian white noise, escape rates in environments with Lévy noise are determined not by the barrier height, but instead by the barrier width. We further discuss consequences of simultaneous action of thermal and Lévy noises on statistics of passage times and population of reactants in double-well potentials.
Collapse
Affiliation(s)
- Karol Capała
- Marian Smoluchowski Institute of Physics and Mark Kac Center for Complex Systems Research, Jagiellonian University, ul. St. Łojasiewicza 11, 30-348 Kraków, Poland
| | - Bartłomiej Dybiec
- Marian Smoluchowski Institute of Physics and Mark Kac Center for Complex Systems Research, Jagiellonian University, ul. St. Łojasiewicza 11, 30-348 Kraków, Poland
| | - Ewa Gudowska-Nowak
- Marian Smoluchowski Institute of Physics and Mark Kac Center for Complex Systems Research, Jagiellonian University, ul. St. Łojasiewicza 11, 30-348 Kraków, Poland
| |
Collapse
|
13
|
Volchenkov D. Memories of the Future. Predictable and Unpredictable Information in Fractional Flipping a Biased Coin. ENTROPY 2019; 21:e21080807. [PMID: 33267520 PMCID: PMC7515336 DOI: 10.3390/e21080807] [Citation(s) in RCA: 6] [Impact Index Per Article: 1.2] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Download PDF] [Figures] [Subscribe] [Scholar Register] [Received: 08/01/2019] [Accepted: 08/15/2019] [Indexed: 11/16/2022]
Abstract
Some uncertainty about flipping a biased coin can be resolved from the sequence of coin sides shown already. We report the exact amounts of predictable and unpredictable information in flipping a biased coin. Fractional coin flipping does not reflect any physical process, being defined as a binomial power series of the transition matrix for “integer” flipping. Due to strong coupling between the tossing outcomes at different times, the side repeating probabilities assumed to be independent for “integer” flipping get entangled with one another for fractional flipping. The predictable and unpredictable information components vary smoothly with the fractional order parameter. The destructive interference between two incompatible hypotheses about the flipping outcome culminates in a fair coin, which stays fair also for fractional flipping.
Collapse
Affiliation(s)
- Dimitri Volchenkov
- Department of Mathematics and Statistics, Texas Tech University, 1108 Memorial Circle, Lubbock, TX 79409, USA
| |
Collapse
|
14
|
Loaiza-Monsalve D, Riascos AP. Human mobility in bike-sharing systems: Structure of local and non-local dynamics. PLoS One 2019; 14:e0213106. [PMID: 30840674 PMCID: PMC6402762 DOI: 10.1371/journal.pone.0213106] [Citation(s) in RCA: 13] [Impact Index Per Article: 2.6] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 11/14/2018] [Accepted: 02/14/2019] [Indexed: 12/27/2022] Open
Abstract
The understanding of human mobility patterns in different transportation modes is an interdisciplinary research field with a direct impact in aspects as varied as urban planning, traffic optimization, sustainability, the reduction of operating costs as well as the mitigation of pollution in urban areas. In this paper, we study the global activity of users in bike-sharing systems operating in the cities of Chicago and New York. For this transportation mode, we explore the temporal and spatial characteristics of the mobility of cyclists. In particular, through the analysis of origin-destination matrices, we characterize the spatial structure of the displacements of users. We apply a mobility model for the global activity of the system that classifies the displacements between stations in local and non-local transitions. In local transitions, cyclists move in a region around each station whereas, in the non-local case, bike users travel with long-range displacements in a similar way to Lévy flights. We reproduce the spatial dynamics by using Monte Carlo simulations. The obtained results are similar to the observed in real data and reveal that the model implemented captures important characteristics of the global spatial dynamics in the systems analyzed.
Collapse
Affiliation(s)
- D. Loaiza-Monsalve
- Department of Civil Engineering, Universidad Mariana, San Juan de Pasto, Colombia
| | - A. P. Riascos
- Instituto de Física, Universidad Nacional Autónoma de México, Ciudad de México, México
- * E-mail:
| |
Collapse
|
15
|
Riascos AP, Mateos JL. Emergence of encounter networks due to human mobility. PLoS One 2017; 12:e0184532. [PMID: 29023458 PMCID: PMC5638260 DOI: 10.1371/journal.pone.0184532] [Citation(s) in RCA: 31] [Impact Index Per Article: 4.4] [Reference Citation Analysis] [Abstract] [MESH Headings] [Grants] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 05/04/2017] [Accepted: 08/25/2017] [Indexed: 11/18/2022] Open
Abstract
There is a burst of work on human mobility and encounter networks. However, the connection between these two important fields just begun recently. It is clear that both are closely related: Mobility generates encounters, and these encounters might give rise to contagion phenomena or even friendship. We model a set of random walkers that visit locations in space following a strategy akin to Lévy flights. We measure the encounters in space and time and establish a link between walkers after they coincide several times. This generates a temporal network that is characterized by global quantities. We compare this dynamics with real data for two cities: New York City and Tokyo. We use data from the location-based social network Foursquare and obtain the emergent temporal encounter network, for these two cities, that we compare with our model. We found long-range (Lévy-like) distributions for traveled distances and time intervals that characterize the emergent social network due to human mobility. Studying this connection is important for several fields like epidemics, social influence, voting, contagion models, behavioral adoption and diffusion of ideas.
Collapse
Affiliation(s)
- A. P. Riascos
- Department of Civil Engineering, Universidad Mariana, San Juan de Pasto, Colombia
- * E-mail:
| | - José L. Mateos
- Instituto de Física, Universidad Nacional Autónoma de México, Ciudad de México, México
| |
Collapse
|
16
|
de Nigris S, Carletti T, Lambiotte R. Onset of anomalous diffusion from local motion rules. Phys Rev E 2017; 95:022113. [PMID: 28297924 DOI: 10.1103/physreve.95.022113] [Citation(s) in RCA: 4] [Impact Index Per Article: 0.6] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 05/31/2016] [Indexed: 06/06/2023]
Abstract
Anomalous diffusion processes, in particular superdiffusive ones, are known to be efficient strategies for searching and navigation in animals and also in human mobility. One way to create such regimes are Lévy flights, where the walkers are allowed to perform jumps, the "flights," that can eventually be very long as their length distribution is asymptotically power-law distributed. In our work, we present a model in which walkers are allowed to perform, on a one-dimensional lattice, "cascades" of n unitary steps instead of one jump of a randomly generated length, as in the Lévy case, where n is drawn from a cascade distribution p_{n}. We show that this local mechanism may give rise to superdiffusion or normal diffusion when p_{n} is distributed as a power law. We also introduce waiting times that are power-law distributed as well and therefore the probability distribution scaling is steered by the two local distributions power-law exponents. As a perspective, our approach may engender a possible generalization of anomalous diffusion in context where distances are difficult to define, as in the case of complex networks, and also provide an interesting model for diffusion in temporal networks.
Collapse
Affiliation(s)
- Sarah de Nigris
- naXys, Namur Center for Complex Systems, UNamur, 5000, Namur, Belgium
- Univ Lyon, Cnrs, ENS de Lyon, Inria, UCB Lyon 1, LIP UMR 5668, 69342, Lyon, France
| | - Timoteo Carletti
- naXys, Namur Center for Complex Systems, UNamur, 5000, Namur, Belgium
| | - Renaud Lambiotte
- naXys, Namur Center for Complex Systems, UNamur, 5000, Namur, Belgium
| |
Collapse
|
17
|
Weng T, Zhang J, Khajehnejad M, Small M, Zheng R, Hui P. Navigation by anomalous random walks on complex networks. Sci Rep 2016; 6:37547. [PMID: 27876855 PMCID: PMC5120342 DOI: 10.1038/srep37547] [Citation(s) in RCA: 15] [Impact Index Per Article: 1.9] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 02/23/2016] [Accepted: 11/01/2016] [Indexed: 11/09/2022] Open
Abstract
Anomalous random walks having long-range jumps are a critical branch of dynamical processes on networks, which can model a number of search and transport processes. However, traditional measurements based on mean first passage time are not useful as they fail to characterize the cost associated with each jump. Here we introduce a new concept of mean first traverse distance (MFTD) to characterize anomalous random walks that represents the expected traverse distance taken by walkers searching from source node to target node, and we provide a procedure for calculating the MFTD between two nodes. We use Lévy walks on networks as an example, and demonstrate that the proposed approach can unravel the interplay between diffusion dynamics of Lévy walks and the underlying network structure. Moreover, applying our framework to the famous PageRank search, we show how to inform the optimality of the PageRank search. The framework for analyzing anomalous random walks on complex networks offers a useful new paradigm to understand the dynamics of anomalous diffusion processes, and provides a unified scheme to characterize search and transport processes on networks.
Collapse
Affiliation(s)
- Tongfeng Weng
- HKUST-DT System and Media Laboratory, Hong Kong University of Science and Technology, HongKong
| | - Jie Zhang
- Centre for Computational Systems Biology, Fudan University, China
| | - Moein Khajehnejad
- HKUST-DT System and Media Laboratory, Hong Kong University of Science and Technology, HongKong
| | - Michael Small
- The University of Western Australia, Crawley, WA 6009, Australia.,Mineral Resources, CSIRO, Kensington, WA, Australia
| | - Rui Zheng
- HKUST-DT System and Media Laboratory, Hong Kong University of Science and Technology, HongKong
| | - Pan Hui
- HKUST-DT System and Media Laboratory, Hong Kong University of Science and Technology, HongKong
| |
Collapse
|
18
|
Riascos AP, Mateos JL. Fractional quantum mechanics on networks: Long-range dynamics and quantum transport. Phys Rev E 2015; 92:052814. [PMID: 26651751 DOI: 10.1103/physreve.92.052814] [Citation(s) in RCA: 11] [Impact Index Per Article: 1.2] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 07/02/2015] [Indexed: 11/07/2022]
Abstract
In this paper we study the quantum transport on networks with a temporal evolution governed by the fractional Schrödinger equation. We generalize the dynamics based on continuous-time quantum walks, with transitions to nearest neighbors on the network, to the fractional case that allows long-range displacements. By using the fractional Laplacian matrix of a network, we establish a formalism that combines a long-range dynamics with the quantum superposition of states; this general approach applies to any type of connected undirected networks, including regular, random, and complex networks, and can be implemented from the spectral properties of the Laplacian matrix. We study the fractional dynamics and its capacity to explore the network by means of the transition probability, the average probability of return, and global quantities that characterize the efficiency of this quantum process. As a particular case, we explore analytically these quantities for circulant networks such as rings, interacting cycles, and complete graphs.
Collapse
Affiliation(s)
- A P Riascos
- Instituto de Física, Universidad Nacional Autónoma de México, Apartado Postal 20-364, 01000 México, D.F., México
| | - José L Mateos
- Instituto de Física, Universidad Nacional Autónoma de México, Apartado Postal 20-364, 01000 México, D.F., México
| |
Collapse
|