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

An universal algorithm for source location in complex networks

Author

Listed:
  • Wang, Hongjue

Abstract

We study locating propagation source in complex networks. We proposed an universal algorithm, which can accurately locate source of different propagation dynamics by using sparse observations. Without knowing the propagation dynamics and any parameters, we calculate Spearman centrality based on the character that positive correlation between inform time of nodes and geodesic distance between nodes and source. The algorithm have high location accuracy with low time complexity and can accurately infer initial time of source. All simulations on both model and real-world networks proved the feasibility and validity of this algorithm.

Suggested Citation

  • Wang, Hongjue, 2019. "An universal algorithm for source location in complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 514(C), pages 620-630.
    • Handle: RePEc:eee:phsmap:v:514:y:2019:i:c:p:620-630
    DOI: 10.1016/j.physa.2018.09.114
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0378437118312470
    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.2018.09.114?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. Zhesi Shen & Wen-Xu Wang & Ying Fan & Zengru Di & Ying-Cheng Lai, 2014. "Reconstructing propagation networks with natural diversity and identifying hidden sources," Nature Communications, Nature, vol. 5(1), pages 1-10, September.
    2. Hauke Jan & Kossowski Tomasz, 2011. "Comparison of Values of Pearson's and Spearman's Correlation Coefficients on the Same Sets of Data," Quaestiones Geographicae, Sciendo, vol. 30(2), pages 87-93, June.
    3. Jinlong Ma & Weizhan Han & Qing Guo & Zhenyong Wang & Shuai Zhang, 2016. "A link-adding strategy for transport efficiency of complex networks," International Journal of Modern Physics C (IJMPC), World Scientific Publishing Co. Pte. Ltd., vol. 27(05), pages 1-12, May.
    4. Ma, Ying-Hong & Li, Hui-Jia & Zhang, Xiao-Dong, 2009. "Strength distribution of novel local-world networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 388(21), pages 4669-4677.
    5. Cui, Yaozu & Wang, Xingyuan & Li, Junqiu, 2014. "Detecting overlapping communities in networks using the maximal sub-graph and the clustering coefficient," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 405(C), pages 85-91.
    6. Tao Zhou & Linyuan Lü & Yi-Cheng Zhang, 2009. "Predicting missing links via local information," The European Physical Journal B: Condensed Matter and Complex Systems, Springer;EDP Sciences, vol. 71(4), pages 623-630, October.
    7. Wang, Xingyuan & Li, Junqiu, 2013. "Detecting communities by the core-vertex and intimate degree in complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 392(10), pages 2555-2563.
    8. Shuai Zhang & Man-Gui Liang & Zhong-Yuan Jiang & Hui-Jia Li, 2015. "Improved efficient static weighted routing strategy on two-layer complex networks," International Journal of Modern Physics C (IJMPC), World Scientific Publishing Co. Pte. Ltd., vol. 26(01), pages 1-13.
    9. Ma, Jinlong & Han, Weizhan & Guo, Qing & Wang, Zhenyong, 2016. "Traffic dynamics on two-layer complex networks with limited delivering capacity," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 456(C), pages 281-287.
    10. Tao Wang & Hongjue Wang & Xiaoxia Wang, 2016. "CD-Based Indices for Link Prediction in Complex Network," PLOS ONE, Public Library of Science, vol. 11(1), pages 1-13, January.
    11. Li, Junqiu & Wang, Xingyuan & Eustace, Justine, 2013. "Detecting overlapping communities by seed community in weighted complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 392(23), pages 6125-6134.
    12. Wang, Xingyuan & Zhao, Tianfang & Qin, Xiaomeng, 2016. "Model of epidemic control based on quarantine and message delivery," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 458(C), pages 168-178.
    13. Jinlong Ma & Weizhan Han & Qing Guo & Shuai Zhang, 2016. "Enhancing traffic capacity of scale-free networks by link-directed strategy," International Journal of Modern Physics C (IJMPC), World Scientific Publishing Co. Pte. Ltd., vol. 27(03), pages 1-12, March.
    14. Li, Dongyan & Wang, Xingyuan & Huang, Penghe, 2017. "A fractal growth model: Exploring the connection pattern of hubs in complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 471(C), pages 200-211.
    Full references (including those not matched with items on IDEAS)

    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. Nan, Dong-Yang & Yu, Wei & Liu, Xiao & Zhang, Yun-Peng & Dai, Wei-Di, 2018. "A framework of community detection based on individual labels in attribute networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 512(C), pages 523-536.
    2. Wen, Xiangxi & Tu, Congliang & Wu, Minggong & Jiang, Xurui, 2018. "Fast ranking nodes importance in complex networks based on LS-SVM method," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 506(C), pages 11-23.
    3. Zhang, Hong, 2015. "Moderate tolerance promotes tag-mediated cooperation in spatial Prisoner’s dilemma game," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 424(C), pages 52-61.
    4. Wang, Tao & Wang, Hongjue & Wang, Xiaoxia, 2015. "A novel cosine distance for detecting communities in complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 437(C), pages 21-35.
    5. Shang, Ronghua & Luo, Shuang & Li, Yangyang & Jiao, Licheng & Stolkin, Rustam, 2015. "Large-scale community detection based on node membership grade and sub-communities integration," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 428(C), pages 279-294.
    6. Zhang, Xiaolei & Ren, Yibin & Huang, Baoxiang & Han, Yong, 2018. "Analysis of time-varying characteristics of bus weighted complex network in Qingdao based on boarding passenger volume," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 506(C), pages 376-394.
    7. Li, Jiawei & Wen, Xiangxi & Wu, Minggong & Liu, Fei & Li, Shuangfeng, 2020. "Identification of key nodes and vital edges in aviation network based on minimum connected dominating set," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 541(C).
    8. Yang, Guizhen & Qi, Xiaogang & Liu, Lifang, 2020. "Research on network robustness based on different deliberate attack methods," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 545(C).
    9. Jiang, Xurui & Wen, Xiangxi & Wu, Minggong & Song, Min & Tu, Congliang, 2019. "A complex network analysis approach for identifying air traffic congestion based on independent component analysis," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 523(C), pages 364-381.
    10. Guo, Wei-Feng & Zhang, Shao-Wu, 2016. "A general method of community detection by identifying community centers with affinity propagation," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 447(C), pages 508-519.
    11. Ding, Rui & Ujang, Norsidah & Hamid, Hussain bin & Manan, Mohd Shahrudin Abd & He, Yuou & Li, Rong & Wu, Jianjun, 2018. "Detecting the urban traffic network structure dynamics through the growth and analysis of multi-layer networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 503(C), pages 800-817.
    12. Jiang, Zhongyuan & Tang, Xiaoke & Zeng, Yong & Li, Jinku & Ma, Jianfeng, 2021. "Adversarial link deception against the link prediction in complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 577(C).
    13. Agumas Alamirew Mebratu, 2024. "Theoretical foundations of voluntary tax compliance: evidence from a developing country," Palgrave Communications, Palgrave Macmillan, vol. 11(1), pages 1-8, December.
    14. Huan Wang & Chuang Ma & Han-Shuang Chen & Ying-Cheng Lai & Hai-Feng Zhang, 2022. "Full reconstruction of simplicial complexes from binary contagion and Ising data," Nature Communications, Nature, vol. 13(1), pages 1-10, December.
    15. Xu, Hai-Chuan & Wang, Zhi-Yuan & Jawadi, Fredj & Zhou, Wei-Xing, 2023. "Reconstruction of international energy trade networks with given marginal data: A comparative analysis," Chaos, Solitons & Fractals, Elsevier, vol. 167(C).
    16. Ke Hu & Ju Xiang & Yun-Xia Yu & Liang Tang & Qin Xiang & Jian-Ming Li & Yong-Hong Tang & Yong-Jun Chen & Yan Zhang, 2020. "Significance-based multi-scale method for network community detection and its application in disease-gene prediction," PLOS ONE, Public Library of Science, vol. 15(3), pages 1-24, March.
    17. Wu, Qingchu, 2024. "A hybrid one-vertex model for susceptible–infected–susceptible diseases on networks with partial connection information," Chaos, Solitons & Fractals, Elsevier, vol. 178(C).
    18. Karimi, Fatemeh & Lotfi, Shahriar & Izadkhah, Habib, 2021. "Community-guided link prediction in multiplex networks," Journal of Informetrics, Elsevier, vol. 15(4).
    19. Park, Jinhee & Ahn, Hyeongjin & Kim, Dongjae & Park, Eunil, 2024. "GNN-IR: Examining graph neural networks for influencer recommendations in social media marketing," Journal of Retailing and Consumer Services, Elsevier, vol. 78(C).
    20. Alex Bara & Pierre LeRoux, 2018. "Technology, Financial Innovations and Bank Behavior in a Low Income Country," Journal of Economics and Behavioral Studies, AMH International, vol. 10(4), pages 221-234.

    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:514:y:2019:i:c:p:620-630. 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.