OPTIMAL TEMPORAL PATH ON SPATIAL DECAYING NETWORKS

Qu Chen; Jiang-Hai Qian; Liang Zhu; Ding-Ding Han

doi:10.11948/2016003

2016 Volume 6 Issue 1

Article Contents

Article navigation > Journal of Applied Analysis & Computation > 2016 > 6(1): 30-37

Next Article Previous Article

Qu Chen, Jiang-Hai Qian, Liang Zhu, Ding-Ding Han. OPTIMAL TEMPORAL PATH ON SPATIAL DECAYING NETWORKS[J]. Journal of Applied Analysis & Computation, 2016, 6(1): 30-37. doi: 10.11948/2016003

Citation:

Qu Chen, Jiang-Hai Qian, Liang Zhu, Ding-Ding Han. OPTIMAL TEMPORAL PATH ON SPATIAL DECAYING NETWORKS[J]. Journal of Applied Analysis & Computation, 2016, 6(1): 30-37. doi: 10.11948/2016003

OPTIMAL TEMPORAL PATH ON SPATIAL DECAYING NETWORKS

1 Shanghai Key Laboratory of Multidimensional Information Processing, East China Normal University, Shanghai 200241, China;
2 School of Information Science and Technology, East China Normal University, Shanghai 200241, China;
3 School of Mathematics and Physics, Shanghai University of Electric Power, Shanghai 200090, China;
4 Shanghai Institute of Applied Physics, Chinese Academy of Sciences, Shanghai 201800, China

Abstract

Abstract

We introduce temporal effect to the classical Kleinberg model and study how it affects the spatial structure of optimal transport network. The initial network is built from a regular d-dimensional lattice added by shortcuts with probability p(r_ij) ∼ r_ij^-α, where r_ij is the geometric distance between node i and j. By assigning each shortcut an energy E=r·τ, a link with length r survives within period τ, which leads the network to a decaying dynamics of constantly losing long-range links. We find new optimal transport in the dynamical system for α=3/4 d, in contrast to any other result in static systems. The conclusion does not depend on the information used for navigation, being based on local or global knowledge of the network, which indicates the possibility of the optimal design for general transport dynamics in the time-varying network.
- Optimal transport /
- time-varying /
- small-world
MSC: 06B30;30L05;37Fxx

FullText(HTML)

References

[1]	A.-L. Barabási, The origin of bursts and heavy tails in human dynamics, Nature, 435(2005)(7039), 207-211. Google Scholar
[2]	M. Boguñá, D. Krioukov and K. C. Claffy, Navigability of complex networks, Nat. Phys., 5(2008)(1), 74-80. Google Scholar
[3]	S. Carmi, S. Carter, J. Sun and D. Ben-Avraham, Asymptotic behavior of the kleinberg model, Phys. Rev. Lett., 102(2009)(23), 238702. Google Scholar
[4]	C. C. Cartozo and P. De Los Rios, Extended navigability of small world networks:exact results and new insights, Phys. Rev. Lett., 102(2009)(23), 238703. Google Scholar
[5]	Q. Chen, J.-H. Qian and D.-D. Han, Non-Gaussian behavior of the internet topological fluctuations, Int. J. Mod Phys C, 25(2014)(05), 1440012. Google Scholar
[6]	A. P. de Moura, A. E. Motter and C. Grebogi, Searching in small-world networks, Phys. Rev. E, 68(2003)(3), 036106. Google Scholar
[7]	M. T. Gastner and M. Newman, Optimal design of spatial distribution networks, Phys. Rev. E, 74(2006)(1), 016117. Google Scholar
[8]	A. Gautreau, A. Barrat and M. Barthelemy, Microdynamics in stationary complex networks, Proc. Natl. Acad. Sci. U.S.A., 106(2009)(22), 8847-8852. Google Scholar
[9]	M. C. González, C. A. Hidalgo and A.-L. Barabási, Understanding individual human mobility patterns, Nature, 453(2008)(7196), 779-782. Google Scholar
[10]	S. A. Hill and D. Braha, Dynamic model of time-dependent complex networks, Phys. Rev. E, 82(2010)(4), 046105. Google Scholar
[11]	P. Holme, Network reachability of real-world contact sequences, Phys. Rev. E, 71(2005)(4), 046119. Google Scholar
[12]	P. Holme and J. Saramäki, Temporal networks, Phys. Rep., 519(2012)(3), 97-125. Google Scholar
[13]	Y. Hu, Y. Wang, D. Li et al., Possible origin of efficient navigation in small worlds, Phys. Rev. Lett., 106(2011)(10), 108701. Google Scholar
[14]	W. Huang, S. Chen and W. Wang, Navigation in spatial networks:A survey, Physica A, 393(2014), 132-154. Google Scholar
[15]	H. Kim and R. Anderson, Temporal node centrality in complex networks, Phys. Rev. E, 85(2012)(2), 026107. Google Scholar
[16]	J. M. Kleinberg, Navigation in a small world, Nature, 406(2000)(6798), 845-845. Google Scholar
[17]	J. M. Kleinberg, The small-world phenomenon:An algorithmic perspective, in Proceedings of the thirty-second annual ACM symposium on Theory of computing, ACM, New York, 2000, 163-170. Google Scholar
[18]	K. Kosmidis, S. Havlin and A. Bunde, Structural properties of spatially embedded networks, EPL (Europhysics Letters), 82(2008)(4), 48005. Google Scholar
[19]	G. Li, S. Reis, A. Moreira et al., Towards design principles for optimal transport networks, Phys. Rev. Lett., 104(2010)(1), 018701. Google Scholar
[20]	G. Li, S. Reis, A. Moreira et al., Optimal transport exponent in spatially embedded networks, Phys. Rev. E, 87(2013)(4), 042810. Google Scholar
[21]	Y. Li, D. Zhou, Y. Hu et al., Exact solution for optimal navigation with total cost restriction, EPL (Europhysics Letters), 92(2010)(5), 58002. Google Scholar
[22]	W. Liu, A. Zeng and Y. Zhou, Degree heterogeneity in spatial networks with total cost constraint, EPL (Europhysics Letters), 98(2012)(2), 28003. Google Scholar
[23]	C. F. Moukarzel and M. A. de Menezes, Shortest paths on systems with powerlaw distributed long-range connections, Phys. Rev. E, 65(2002)(5), 056709. Google Scholar
[24]	C. L. Oliveira, P. A. Morais, A. A. Moreira and J. S. Andrade Jr, Enhanced flow in small-world networks, Phys. Rev. Lett., 112(2014)(14), 148701. Google Scholar
[25]	R. K. Pan and J. Saramäki, Path lengths, correlations, and centrality in temporal networks, Phys. Rev. E, 84(2011)(1), 016105. Google Scholar
[26]	N. Perra, A. Baronchelli, D. Mocanu et al., Random walks and search in timevarying networks, Phys. Rev. Lett., 109(2012)(23), 238701. Google Scholar
[27]	N. Perra, B. Gonçalves, R. Pastor-Satorras and A. Vespignani, Activity driven modeling of time varying networks, Sci. Rep., 2(2012)(469). Google Scholar
[28]	J.-H. Qian, Q. Chen, D.-D. Han et al., Origin of gibrat law in internet:Asymmetric distribution of the correlation, Phys. Rev. E, 89(2014)(6), 062808. Google Scholar
[29]	A. Riascos and J. L. Mateos, Long-range navigation on complex networks using lévy random walks, Phys. Rev. E, 86(2012)(5), 056110. Google Scholar
[30]	M. R. Roberson and D. Ben-Avraham, Kleinberg navigation in fractal smallworld networks, Phys. Rev. E, 74(2006)(1), 017101. Google Scholar
[31]	D. Rybski, S. V. Buldyrev, S. Havlin et al., Scaling laws of human interaction activity, Proc. Natl. Acad. Sci. U.S.A., 106(2009)(31), 12640-12645. Google Scholar
[32]	M. Starnini, A. Baronchelli and R. Pastor-Satorras, Modeling human dynamics of face-to-face interaction networks, Phys. Rev. Lett., 110(2013)(16), 168701. Google Scholar
[33]	J. Tang, S. Scellato, M. Musolesi et al., Small-world behavior in time-varying graphs, Phys. Rev. E, 81(2010)(5), 055101. Google Scholar
[34]	S. Trajanovski, S. Scellato and I. Leontiadis, Error and attack vulnerability of temporal networks, Phys. Rev. E, 85(2012)(6), 066105. Google Scholar
[35]	D. J. Watts and S. H. Strogatz, Collective dynamics of small-world networks, Nature, 393(1998)(6684), 440-442. Google Scholar
[36]	H. Zhu and Z.-X. Huang, Navigation in a small world with local information, Phys. Rev. E, 70(2004)(3), 036117. Google Scholar