IDEAS home Printed from https://ideas.repec.org/a/eee/phsmap/v462y2016icp986-1002.html
   My bibliography  Save this article

MFPT calculation for random walks in inhomogeneous networks

Author

Listed:
  • Wijesundera, Isuri
  • Halgamuge, Malka N.
  • Nirmalathas, Ampalavanapillai
  • Nanayakkara, Thrishantha

Abstract

Knowing the expected arrival time at a particular state, also known as the mean first passage time (MFPT), often plays an important role for a large class of random walkers in their respective state-spaces. Contrasting to ideal conditions required by recent advancements on MFPT estimations, many naturally occurring random walkers encounter inhomogeneity of transport characteristics in the networks they walk on. This paper presents a heuristic method to divide an inhomogeneous network into homogeneous network primitives (NPs) optimized using particle swarm optimizer, and to use a ‘hop-wise’ MFPT calculation method. This methodology’s potential is demonstrated through simulated random walks and with a case study using the dataset of past cyclone tracks over the North Atlantic Ocean. Parallel processing was used to increase calculation efficiency. The predictions using the proposed method are compared to real data averages and predictions assuming homogeneous transport properties. The results show that breaking the problem into NPs reduces the average error from 18.8% to 5.4% with respect to the homogeneous network assumption.

Suggested Citation

  • Wijesundera, Isuri & Halgamuge, Malka N. & Nirmalathas, Ampalavanapillai & Nanayakkara, Thrishantha, 2016. "MFPT calculation for random walks in inhomogeneous networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 462(C), pages 986-1002.
  • Handle: RePEc:eee:phsmap:v:462:y:2016:i:c:p:986-1002
    DOI: 10.1016/j.physa.2016.06.015
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0378437116302837
    Download Restriction: Full text for ScienceDirect subscribers only. Journal offers the option of making the article available online on Science direct for a fee of $3,000

    File URL: https://libkey.io/10.1016/j.physa.2016.06.015?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Pu, Cun-Lai & Zhou, Si-Yuan & Wang, Kai & Zhang, Yi-Feng & Pei, Wen-Jiang, 2012. "Efficient and robust routing on scale-free networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 391(3), pages 866-871.
    2. Pu, Cun-Lai & Pei, Wen-Jiang, 2010. "Mixing search on complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 389(3), pages 587-594.
    3. Pu, Cunlai & Li, Siyuan & Yang, Jian, 2015. "Epidemic spreading driven by biased random walks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 432(C), pages 230-239.
    4. Isham, Valerie & Harden, Simon & Nekovee, Maziar, 2010. "Stochastic epidemics and rumours on finite random networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 389(3), pages 561-576.
    5. Pu, Cun-Lai & Yang, Jian & Pei, Wen-Jiang & Tao, Yu-Ting & Lan, Shao-Hua, 2013. "Robustness analysis of static routing on networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 392(15), pages 3293-3300.
    6. Gilles Celeux & Gilda Soromenho, 1996. "An entropy criterion for assessing the number of clusters in a mixture model," Journal of Classification, Springer;The Classification Society, vol. 13(2), pages 195-212, September.
    7. Chaoming Song & Shlomo Havlin & Hernán A. Makse, 2005. "Self-similarity of complex networks," Nature, Nature, vol. 433(7024), pages 392-395, January.
    8. S. Condamin & O. Bénichou & V. Tejedor & R. Voituriez & J. Klafter, 2007. "First-passage times in complex scale-invariant media," Nature, Nature, vol. 450(7166), pages 77-80, November.
    9. ., 2015. "Regional agglomeration and industrial clusters," Chapters, in: Introduction to Regional Economic Development, chapter 6, pages 85-95, Edward Elgar Publishing.
    10. Meese, Richard A. & Rogoff, Kenneth, 1983. "Empirical exchange rate models of the seventies : Do they fit out of sample?," Journal of International Economics, Elsevier, vol. 14(1-2), pages 3-24, February.
    11. Neil M. Ferguson & Matt J. Keeling & W. John Edmunds & Raymond Gani & Bryan T. Grenfell & Roy M. Anderson & Steve Leach, 2003. "Planning for smallpox outbreaks," Nature, Nature, vol. 425(6959), pages 681-685, October.
    12. Sun, Yu & Dai, Meifeng & Xi, Lifeng, 2014. "Scaling of average weighted shortest path and average receiving time on weighted hierarchical networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 407(C), pages 110-118.
    13. Pu, Cun-Lai & Pei, Wen-Jiang & Michaelson, Andrew, 2012. "Robustness analysis of network controllability," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 391(18), pages 4420-4425.
    14. Koren, T. & Chechkin, A.V. & Klafter, J., 2007. "On the first passage time and leapover properties of Lévy motions," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 379(1), pages 10-22.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Ma, Fei & Wang, Ping & Yao, Bing, 2021. "Random walks on Fibonacci treelike models," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 581(C).

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Le, Anbo & Gao, Fei & Xi, Lifeng & Yin, Shuhua, 2015. "Complex networks modeled on the Sierpinski gasket," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 436(C), pages 646-657.
    2. Chen, Ya-Shan & Yang, Han-Xin & Guo, Wen-Zhong, 2017. "Aspiration-induced dormancy promotes cooperation in the spatial Prisoner’s Dilemma games," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 469(C), pages 625-630.
    3. Huang, Liang & Zheng, Yu, 2023. "Asymptotic formula on APL of fractal evolving networks generated by Durer Pentagon," Chaos, Solitons & Fractals, Elsevier, vol. 167(C).
    4. Niu, Min & Song, Shuaishuai, 2018. "Scaling of average weighted shortest path and average receiving time on the weighted Cayley networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 506(C), pages 707-717.
    5. Zong, Yue & Dai, Meifeng & Wang, Xiaoqian & He, Jiaojiao & Zou, Jiahui & Su, Weiyi, 2018. "Network coherence and eigentime identity on a family of weighted fractal networks," Chaos, Solitons & Fractals, Elsevier, vol. 109(C), pages 184-194.
    6. Schaum, Alexander & Bernal Jaquez, Roberto, 2016. "Estimating the state probability distribution for epidemic spreading in complex networks," Applied Mathematics and Computation, Elsevier, vol. 291(C), pages 197-206.
    7. Stefan Mittnik & Nikolay Robinzonov & Klaus Wohlrabe, 2013. "The Micro Dynamics of Macro Announcements," CESifo Working Paper Series 4421, CESifo.
    8. Gürkaynak, Refet S. & Kısacıkoğlu, Burçin & Lee, Sang Seok, 2022. "Exchange rate and inflation under weak monetary policy: Turkey verifies theory," CFS Working Paper Series 679, Center for Financial Studies (CFS).
    9. Agnès Bénassy‐Quéré & Lionel Fontagné & Horst Raff, 2011. "Exchange‐rate Misalignments in Duopoly: The Case of Airbus and Boeing," The World Economy, Wiley Blackwell, vol. 34(4), pages 623-641, April.
    10. Marcos Álvarez-Díaz & Alberto Álvarez, 2002. "Predicción No-Lineal De Tipos De Cambio: Algoritmos Genéticos, Redes Neuronales Y Fusión De Datos," Working Papers 0205, Universidade de Vigo, Departamento de Economía Aplicada.
    11. Alberto Fuertes & Simón Sosvilla-Rivero, 2019. "“Forecasting emerging market currencies: Are inflation expectations useful?”," IREA Working Papers 201918, University of Barcelona, Research Institute of Applied Economics, revised Oct 2019.
    12. Goncalves, Silvia & Kilian, Lutz, 2004. "Bootstrapping autoregressions with conditional heteroskedasticity of unknown form," Journal of Econometrics, Elsevier, vol. 123(1), pages 89-120, November.
    13. Dal Bianco, Marcos & Camacho, Maximo & Perez Quiros, Gabriel, 2012. "Short-run forecasting of the euro-dollar exchange rate with economic fundamentals," Journal of International Money and Finance, Elsevier, vol. 31(2), pages 377-396.
    14. Niko Hauzenberger & Florian Huber, 2020. "Model instability in predictive exchange rate regressions," Journal of Forecasting, John Wiley & Sons, Ltd., vol. 39(2), pages 168-186, March.
    15. Ken Miyajima, 2013. "Foreign exchange intervention and expectation in emerging economies," BIS Working Papers 414, Bank for International Settlements.
    16. Julian Aichholzer & Sylvia Kritzinger & Carolina Plescia, 2021. "National identity profiles and support for the European Union," European Union Politics, , vol. 22(2), pages 293-315, June.
    17. van Amano, Robert A & Norden, Simon, 1998. "Exchange Rates and Oil Prices," Review of International Economics, Wiley Blackwell, vol. 6(4), pages 683-694, November.
    18. Adrian Bruhin & Ernst Fehr & Daniel Schunk, 2019. "The many Faces of Human Sociality: Uncovering the Distribution and Stability of Social Preferences," Journal of the European Economic Association, European Economic Association, vol. 17(4), pages 1025-1069.
    19. Anella Munro, 2014. "Exchange rates, expected returns and risk," Reserve Bank of New Zealand Discussion Paper Series DP2014/01, Reserve Bank of New Zealand.
    20. Neely, Christopher J. & Weller, Paul, 2000. "Predictability in International Asset Returns: A Reexamination," Journal of Financial and Quantitative Analysis, Cambridge University Press, vol. 35(4), pages 601-620, December.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:phsmap:v:462:y:2016:i:c:p:986-1002. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.journals.elsevier.com/physica-a-statistical-mechpplications/ .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.