Random multi-hopper model: super-fast random walks on graphs. (3rd October 2017)

• Record Type: Journal Article
• Authors: Estrada, Ernesto; Delvenne, Jean-Charles; Hatano, Naomichi; Mateos, José L; Metzler, Ralf; Riascos, Alejandro P; Schaub, Michael T
• Is Part Of: Journal of complex networks. Volume 6:Number 3(2018)
• Page Start: 382
• Page End: 403
• Publication Date: 2017-10-03
• Subjects: Numerical analysis -- Periodicals; Computer networks -- Periodicals; Social networks -- Periodicals; 518.05
• DOI: 10.1093/comnet/cnx043
• Languages: English
• ISSNs: 2051-1310

Abstract

Abstract: We develop a mathematical model considering a random walker with long-range hops on arbitrary graphs. The random multi-hopper can jump to any node of the graph from an initial position, with a probability that decays as a function of the shortest-path distance between the two nodes in the graph. We consider here two decaying functions in the form of Laplace and Mellin transforms of the shortest-path distances. We prove that when the parameters of these transforms approach zero asymptotically, the hitting time in the multi-hopper approaches the minimum possible value for a normal random walker. We show by computational experiments that the multi-hopper explores a graph with clusters or skewed degree distributions more efficiently than a normal random walker. We provide computational evidences of the advantages of the random multi-hopper model with respect to the normal random walk by studying deterministic, random and real-world networks.