title: Lévy Walk Navigation in Complex Networks: A Distinct Relation between Optimal Transport Exponent and Network Dimension.
abstract: We investigate, for the first time, navigation on networks with a Lévy walk strategy such that the step probability scales as pij ~ dij(-α), where dij is the Manhattan distance between nodes i and j, and α is the transport exponent. We find that the optimal transport exponent α(opt) of such a diffusion process is determined by the fractal dimension df of the underlying network. Specially, we theoretically derive the relation α(opt) = df + 2 for synthetic networks and we demonstrate that this holds for a number of real-world networks. Interestingly, the relationship we derive is different from previous results for Kleinberg navigation without or with a cost constraint, where the optimal conditions are α = df and α = df + 1, respectively. Our results uncover another general mechanism for how network dimension can precisely govern the efficient diffusion behavior on diverse networks.
authors.affiliation: HKUST-DT System and Media Laboratory, Hong Kong University of Science and Technology, HongKong.
authors.forename: Tongfeng
authors.initials: T
authors.lastname: Weng
authors.affiliation: The University of Western Australia, Crawley, WA 6009, Australia.
authors.forename: Michael
authors.initials: M
authors.lastname: Small
authors.affiliation: Centre for Computational Systems Biology, Fudan University, China.
authors.forename: Jie
authors.initials: J
authors.lastname: Zhang
authors.affiliation: HKUST-DT System and Media Laboratory, Hong Kong University of Science and Technology, HongKong.
authors.forename: Pan
authors.initials: P
authors.lastname: Hui