- Physical Review Journals
All JournalsPhysics Magazine
Access Provided by Xinjiang University

Physical Review E

Export citation

Export citation

Choose format for download:

Download Citation
  • Access by Xinjiang University

Statistical inference approach to structural reconstruction of complex networks from binary time series

Chuang Ma1, Han-Shuang Chen2, Ying-Cheng Lai3, and Hai-Feng Zhang1,4,5,*

  • 1School of Mathematical Science, Anhui University, Hefei 230601, China
  • 2School of Physics and Material Science, Anhui University, Hefei 230601, China
  • 3School of Electrical, Computer and Energy Engineering, Arizona State University, Tempe, Arizona 85287, USA
  • 4Center of Information Support and Assurance Technology, Anhui University, Hefei 230601, China
  • 5Department of Communication Engineering, North University of China, Taiyuan, Shan'xi 030051, China

  • *haifengzhang1978@gmail.com
PDF

Phys. Rev. E 97, 022301 – Published 5 February, 2018

DOI: https://doi.org/10.1103/PhysRevE.97.022301

Abstract

Complex networks hosting binary-state dynamics arise in a variety of contexts. In spite of previous works, to fully reconstruct the network structure from observed binary data remains challenging. We articulate a statistical inference based approach to this problem. In particular, exploiting the expectation-maximization (EM) algorithm, we develop a method to ascertain the neighbors of any node in the network based solely on binary data, thereby recovering the full topology of the network. A key ingredient of our method is the maximum-likelihood estimation of the probabilities associated with actual or nonexistent links, and we show that the EM algorithm can distinguish the two kinds of probability values without any ambiguity, insofar as the length of the available binary time series is reasonably long. Our method does not require any a priori knowledge of the detailed dynamical processes, is parameter-free, and is capable of accurate reconstruction even in the presence of noise. We demonstrate the method using combinations of distinct types of binary dynamical processes and network topologies, and provide a physical understanding of the underlying reconstruction mechanism. Our statistical inference based reconstruction method contributes an additional piece to the rapidly expanding “toolbox” of data based reverse engineering of complex networked systems.

View figure in article

Physics Subject Headings (PhySH)

Article Text

References (77)

  1. S. Gruen, M. Diesmann, and A. Aertsen, Neural Comput. 14, 43 (2002).
  2. R. Gütig, A. Aertsen, and S. Rotter, Neural Comput. 14, 121 (2002).
  3. T. S. Gardner, D. di Bernardo, D. Lorenz, and J. J. Collins, Science 301, 102 (2003).
  4. G. Pipa and S. Grün, J. Comp. Neurol. 52, 31 (2003).
  5. A. Brovelli, M. Ding, A. Ledberg, Y. Chen, R. Nakamura, and S. L. Bressler, Proc. Natl. Acad. Sci. USA 101, 9849 (2004).
  6. V. M. Eguiluz, D. R. Chialvo, G. A. Cecchi, M. Baliki, and A. V. Apkarian, Phys. Rev. Lett. 94, 018102 (2005).
  7. D. S. Bassett, A. Meyer-Lindenberg, S. Achard, T. Duke, and E. Bullmore, Proc. Natl. Acad. Sci. USA 103, 19518 (2006).
  8. D. Yu, M. Righero, and L. Kocarev, Phys. Rev. Lett. 97, 188701 (2006).
  9. J. Bongard and H. Lipson, Proc. Natl. Acad. Sci. USA 104, 9943 (2007).
  10. M. Timme, Phys. Rev. Lett. 98, 224101 (2007).
  11. W. K.-S. Tang, M. Yu, and L. Kocarev, in Proceedings of the IEEE International Symposium on Circuits and Systems (ISCAS 2007) (IEEE, New York, 2007), pp. 2646–2649.
  12. D. Napoletani and T. D. Sauer, Phys. Rev. E 77, 026103 (2008).
  13. E. Sontag, Essays Biochem. 45, 161 (2008).
  14. A. Clauset, C. Moore, and M. E. J. Newman, Nature (London) 453, 98 (2008).
  15. W.-X. Wang, Q. Chen, L. Huang, Y.-C. Lai, and Mary Ann F. Harrison, Phys. Rev. E 80, 016116 (2009).
  16. J. Donges, Y. Zou, N. Marwan, and J. Kurths, Europhys. Lett. 87, 48007 (2009).
  17. J. Ren, W.-X. Wang, B. Li, and Y.-C. Lai, Phys. Rev. Lett. 104, 058701 (2010).
  18. J. Chan, A. Holmes, and R. Rabadan, PLoS Comput. Biol. 6, e1001005 (2010).
  19. Y. Yuan, G.-B. Stan, S. Warnick, and J. Goncalves, in Proceedings of the 2010 49th IEEE Conference on Decision and Control (CDC) (IEEE, New York, 2010), pp. 810–815.
  20. Z. Levnajić and A. Pikovsky, Phys. Rev. Lett. 107, 034101 (2011).
  21. S. Hempel, A. Koseska, J. Kurths, and Z. Nikoloski, Phys. Rev. Lett. 107, 054101 (2011).
  22. S. G. Shandilya and M. Timme, New J. Phys. 13, 013004 (2011).
  23. D. Yu and U. Parlitz, PLoS One 6, e24333 (2011).
  24. W.-X. Wang, Y.-C. Lai, C. Grebogi, and J.-P. Ye, Phys. Rev. X 1, 021021 (2011).
  25. W.-X. Wang, R. Yang, Y.-C. Lai, V. Kovanis, and C. Grebogi, Phys. Rev. Lett. 106, 154101 (2011).
  26. W.-X. Wang, R. Yang, Y.-C. Lai, V. Kovanis, and M. A. F. Harrison, Europhys. Lett. 94, 48006 (2011).
  27. R. Yang, Y.-C. Lai, and C. Grebogi, Chaos 22, 033119 (2012).
  28. W. Pan, Y. Yuan, and G.-B. Stan, in Proceedings of the 2012 IEEE 51st Annual Conference on Decision and Control (CDC) (IEEE, New York, 2012), pp. 2334–2339.
  29. W.-X. Wang, J. Ren, Y.-C. Lai, and B. Li, Chaos 22, 033131 (2012).
  30. T. Berry, F. Hamilton, N. Peixoto, and T. Sauer, J. Neurosci. Methods 209, 388 (2012).
  31. O. Stetter, D. Battaglia, J. Soriano, and T. Geisel, PLoS Comput. Biol. 8, e1002653 (2012).
  32. R.-Q. Su, X. Ni, W.-X. Wang, and Y.-C. Lai, Phys. Rev. E 85, 056220 (2012).
  33. R.-Q. Su, W.-X. Wang, and Y.-C. Lai, Phys. Rev. E 85, 065201 (2012).
  34. F. Hamilton, T. Berry, N. Peixoto, and T. Sauer, Phys. Rev. E 88, 052715 (2013).
  35. D. Zhou, Y. Xiao, Y. Zhang, Z. Xu, and D. Cai, Phys. Rev. Lett. 111, 054102 (2013).
  36. E. S. C. Ching, P.-Y. Lai, and C. Y. Leung, Phys. Rev. E 88, 042817 (2013).
  37. M. Timme and J. Casadiego, J. Phys. A: Math. Theor. 47, 343001 (2014).
  38. R.-Q. Su, Y.-C. Lai, and X. Wang, Entropy 16, 3889 (2014).
  39. R.-Q. Su, Y.-C. Lai, X. Wang, and Y.-H. Do, Sci. Rep. 4, 3944 (2014).
  40. Z.-S. Shen, W.-X. Wang, Y. Fan, Z. Di, and Y.-C. Lai, Nat. Commun. 5, 4323 (2014).
  41. E. S. C. Ching, P.-Y. Lai, and C. Y. Leung, Phys. Rev. E 91, 030801 (2015).
  42. R.-Q. Su, W.-W. Wang, X. Wang, and Y.-C. Lai, R. Soc. Open Sci. 3, 150577 (2016).
  43. J.-W. Li, Z.-S. Shen, W.-X. Wang, C. Grebogi, and Y.-C. Lai, Phys. Rev. E 95, 032303 (2017).
  44. C. Ma, H.-F. Zhang, and Y.-C. Lai, Phys. Rev. E 96, 022320 (2017).
  45. O. Feinerman, A. Rotem, and E. Moses, Nat. Phys. 4, 967 (2008).
  46. J. Soriano, M. R. Martínez, T. Tlusty, and E. Moses, Proc. Natl. Acad. Sci. USA 105, 13758 (2008).
  47. K. J. Friston, NeuroImage 16, 513 (2002).
  48. S. Pajevic and D. Plenz, PLoS Comput. Biol. 5, e1000271 (2009).
  49. S. Foucart and H. Rauhut, A Mathematical Introduction to Compressive Sensing (Birkhäuser, New York, 2013).
  50. X. Han, Z.-S. Shen, W.-X. Wang, and Z.-R. Di, Phys. Rev. Lett. 114, 028701 (2015).
  51. W.-X. Wang, Y.-C. Lai, and C. Grebogi, Phys. Rep. 644, 1 (2016).
  52. R. Pastor-Satorras, C. Castellano, P. Van Mieghem, and A. Vespignani, Rev. Mod. Phys. 87, 925 (2015).
  53. A. Kumar, S. Rotter, and A. Aertsen, Nat. Rev. Neurosci. 11, 615 (2010).
  54. G. Szabó and G. Fath, Phys. Rep. 446, 97 (2007).
  55. W.-B. Du, X.-B. Cao, M.-B. Hu, and W.-X. Wang, Europhys. Lett. 87, 60004 (2009).
  56. Y. Wang, G. Xiao, and J. Liu, New J. Phys. 14, 013015 (2012).
  57. Y.-Z. Chen and Y.-C. Lai, arXiv:1611.01849.
  58. B. Ball, B. Karrer, and M. E. J. Newman, Phys. Rev. E 84, 036103 (2011).
  59. C. De Bacco, E. A. Power, D. B. Larremore, and C. Moore, Phys. Rev. E 95, 042317 (2017).
  60. X. Zhao, B. Yang, X. Liu, and H. Chen, Phys. Rev. E 95, 042313 (2017).
  61. X. Zhang, T. Martin, and M. E. J. Newman, Phys. Rev. E 91, 032803 (2015).
  62. M. E. J. Newman, Phys. Rev. E 94, 052315 (2016).
  63. M. E. J. Newman and G. Reinert, Phys. Rev. Lett. 117, 078301 (2016).
  64. B. Karrer and M. E. J. Newman, Phys. Rev. E 83, 016107 (2011).
  65. A. P. Dempster, N. M. Laird, and D. B. Rubin, J. R.l Stat. Soc., Ser. B 39, 1 (1977).
  66. T. Needham, Amer. Math. Monthly 100, 768 (1993).
  67. J. Davis and M. Goadrich, in Proceedings of the 23rd International Conference on Machine Learning (ACM, New York, 2006), pp. 233–240.
  68. P. Erdös and A. Rényi, Publ. Math. Inst. Hung. Acad. Sci. 5, 17 (1960).
  69. A.-L. Barabási and R. Albert, Science 286, 509 (1999).
  70. D. J. Watts and S. H. Strogatz, Nature (London) 393, 440 (1998).
  71. D. M. Powers, J. Mach. Learning Technol. 2, 37 (2011).
  72. V. Sood and S. Redner, Phys. Rev. Lett. 94, 178701 (2005).
  73. A. Kirman, Quart. J. Econ. 108, 137 (1993).
  74. P. L. Krapivsky, S. Redner, and E. Ben-Naim, A Kinetic View of Statistical Physics (Cambridge University Press, Cambridge, UK, 2010).
  75. D. M. Abrams and S. H. Strogatz, Nature (London) 424, 900 (2003).
  76. M. Granovetter, Amer. J. Sociol. 83, 1420 (1978).
  77. M. J. de Oliveira, J. Stat. Phys. 66, 273 (1992).

Outline

Information

Phys. Rev. E 97, 022301– Published 5 February, 2018
  • Received 26 August 2017
Article part of CHORUS
Crossmark - Check for updates button

©2018 American Physical Society

Sign In to Your Journals Account

Filter

Filter

Article Lookup

Enter a citation