Display options
Cite
Hu ZL, Han X, Lai YC, et al. Optimal localization of diffusion sources in complex networks. R Soc Open Sci. 2017;4(4):170091doi: 10.1098/rsos.170091.
Hu, Z. L., Han, X., Lai, Y. C., & Wang, W. X. (2017). Optimal localization of diffusion sources in complex networks. Royal Society open science, 4(4), 170091. https://doi.org/10.1098/rsos.170091
Hu, Zhao-Long, et al. "Optimal localization of diffusion sources in complex networks." Royal Society open science vol. 4,4 (2017): 170091. doi: https://doi.org/10.1098/rsos.170091
Hu ZL, Han X, Lai YC, Wang WX. Optimal localization of diffusion sources in complex networks. R Soc Open Sci. 2017 Apr 12;4(4):170091. doi: 10.1098/rsos.170091. eCollection 2017 Apr. PMID: 28484635; PMCID: PMC5414272.
Copy Download .nbib Format: NLM
Share it on

R Soc Open Sci. 2017 Apr 12;4(4):170091. doi: 10.1098/rsos.170091. eCollection 2017 Apr.

Optimal localization of diffusion sources in complex networks.

Royal Society open science

Zhao-Long Hu, Xiao Han, Ying-Cheng Lai, Wen-Xu Wang

Affiliations

  1. School of Systems Science, Beijing Normal University, Beijing 100875, People's Republic of China.
  2. School of Electrical, Computer and Energy Engineering, Arizona State University, Tempe, AZ 85287, USA.
  3. Department of Physics, Arizona State University, Tempe, AZ 85287, USA.
  4. Business School, University of Shanghai for Science and Technology, Shanghai 200093, People's Republic of China.

PMID: 28484635 PMCID: PMC5414272 DOI: 10.1098/rsos.170091

Abstract

Locating sources of diffusion and spreading from minimum data is a significant problem in network science with great applied values to the society. However, a general theoretical framework dealing with optimal source localization is lacking. Combining the controllability theory for complex networks and compressive sensing, we develop a framework with high efficiency and robustness for optimal source localization in arbitrary weighted networks with arbitrary distribution of sources. We offer a minimum output analysis to quantify the source locatability through a minimal number of messenger nodes that produce sufficient measurement for fully locating the sources. When the minimum messenger nodes are discerned, the problem of optimal source localization becomes one of sparse signal reconstruction, which can be solved using compressive sensing. Application of our framework to model and empirical networks demonstrates that sources in homogeneous and denser networks are more readily to be located. A surprising finding is that, for a connected undirected network with random link weights and weak noise, a single messenger node is sufficient for locating any number of sources. The framework deepens our understanding of the network source localization problem and offers efficient tools with broad applications.

Keywords: complex networks; compressive sensing; diffusion sources; locatability; optimal localization

Conflict of interest statement

We declare we have no competing interests.

References

  1. JAMA. 2002 Mar 6;287(9):1132-41 - PubMed
  2. Science. 2013 Apr 26;340(6131):414-5 - PubMed
  3. Science. 2010 Sep 3;329(5996):1194-7 - PubMed
  4. Phys Rev Lett. 2013 Jan 11;110(2):028701 - PubMed
  5. Science. 1999 Oct 15;286(5439):509-12 - PubMed
  6. Phys Rev Lett. 2015 Jan 16;114(2):028701 - PubMed
  7. Science. 2009 May 22;324(5930):1071-6 - PubMed
  8. Proc Natl Acad Sci U S A. 2013 Feb 12;110(7):2460-5 - PubMed
  9. Phys Rev Lett. 2012 Aug 10;109(6):068702 - PubMed
  10. Radiology. 1982 Apr;143(1):29-36 - PubMed
  11. Phys Rev E. 2016 Mar;93(3):032301 - PubMed
  12. Nature. 2009 Jun 18;459(7249):931-9 - PubMed
  13. Phys Rev Lett. 2011 Apr 15;106(15):154101 - PubMed
  14. Sci Rep. 2015 Feb 12;5:8422 - PubMed
  15. Science. 2013 Dec 13;342(6164):1337-42 - PubMed
  16. Science. 2001 May 18;292(5520):1316-7 - PubMed
  17. Sci Rep. 2014 Jul 03;4:5547 - PubMed
  18. Nat Commun. 2013;4:2447 - PubMed
  19. Nature. 2011 May 12;473(7346):167-73 - PubMed
  20. Nature. 2001 Mar 8;410(6825):268-76 - PubMed
  21. Nature. 2015 Aug 6;524(7563):65-8 - PubMed
  22. Phys Rev Lett. 2014 Mar 21;112(11):118701 - PubMed
  23. Science. 2014 Sep 12;345(6202):1369-72 - PubMed

Publication Types