Locating the Source of Diffusion in Complex Networks via Gaussian-Based Localization and Deduction
Locating the source that undergoes a diffusion-like process is a fundamental and challenging problem in complex network, which can help inhibit the outbreak of epidemics among humans, suppress the spread of rumors on the Internet, prevent cascading failures of power grids, etc. However, our ability...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2019-09-01
|
| Series: | Applied Sciences |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2076-3417/9/18/3758 |
| _version_ | 1818922893222871040 |
|---|---|
| author | Xiang Li Xiaojie Wang Chengli Zhao Xue Zhang Dongyun Yi |
| author_facet | Xiang Li Xiaojie Wang Chengli Zhao Xue Zhang Dongyun Yi |
| author_sort | Xiang Li |
| collection | DOAJ |
| description | Locating the source that undergoes a diffusion-like process is a fundamental and challenging problem in complex network, which can help inhibit the outbreak of epidemics among humans, suppress the spread of rumors on the Internet, prevent cascading failures of power grids, etc. However, our ability to accurately locate the diffusion source is strictly limited by incomplete information of nodes and inevitable randomness of diffusion process. In this paper, we propose an efficient optimization approach via maximum likelihood estimation to locate the diffusion source in complex networks with limited observations. By modeling the informed times of the observers, we derive an optimal source localization solution for arbitrary trees and then extend it to general graphs via proper approximations. The numerical analyses on synthetic networks and real networks all indicate that our method is superior to several benchmark methods in terms of the average localization accuracy, high-precision localization and approximate area localization. In addition, low computational cost enables our method to be widely applied for the source localization problem in large-scale networks. We believe that our work can provide valuable insights on the interplay between information diffusion and source localization in complex networks. |
| first_indexed | 2024-12-20T02:00:46Z |
| format | Article |
| id | doaj.art-e5bbd96c4b99459fb9f8a7c5d750ea52 |
| institution | Directory Open Access Journal |
| issn | 2076-3417 |
| language | English |
| last_indexed | 2024-12-20T02:00:46Z |
| publishDate | 2019-09-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Applied Sciences |
| spelling | doaj.art-e5bbd96c4b99459fb9f8a7c5d750ea522022-12-21T19:57:20ZengMDPI AGApplied Sciences2076-34172019-09-01918375810.3390/app9183758app9183758Locating the Source of Diffusion in Complex Networks via Gaussian-Based Localization and DeductionXiang Li0Xiaojie Wang1Chengli Zhao2Xue Zhang3Dongyun Yi4College of Liberal Arts and Sciences, National University of Defense Technology, Changsha 410073, ChinaCollege of Liberal Arts and Sciences, National University of Defense Technology, Changsha 410073, ChinaCollege of Liberal Arts and Sciences, National University of Defense Technology, Changsha 410073, ChinaCollege of Liberal Arts and Sciences, National University of Defense Technology, Changsha 410073, ChinaCollege of Liberal Arts and Sciences, National University of Defense Technology, Changsha 410073, ChinaLocating the source that undergoes a diffusion-like process is a fundamental and challenging problem in complex network, which can help inhibit the outbreak of epidemics among humans, suppress the spread of rumors on the Internet, prevent cascading failures of power grids, etc. However, our ability to accurately locate the diffusion source is strictly limited by incomplete information of nodes and inevitable randomness of diffusion process. In this paper, we propose an efficient optimization approach via maximum likelihood estimation to locate the diffusion source in complex networks with limited observations. By modeling the informed times of the observers, we derive an optimal source localization solution for arbitrary trees and then extend it to general graphs via proper approximations. The numerical analyses on synthetic networks and real networks all indicate that our method is superior to several benchmark methods in terms of the average localization accuracy, high-precision localization and approximate area localization. In addition, low computational cost enables our method to be widely applied for the source localization problem in large-scale networks. We believe that our work can provide valuable insights on the interplay between information diffusion and source localization in complex networks.https://www.mdpi.com/2076-3417/9/18/3758source localizationoptimization algorithmdata miningcomplex networks |
| spellingShingle | Xiang Li Xiaojie Wang Chengli Zhao Xue Zhang Dongyun Yi Locating the Source of Diffusion in Complex Networks via Gaussian-Based Localization and Deduction Applied Sciences source localization optimization algorithm data mining complex networks |
| title | Locating the Source of Diffusion in Complex Networks via Gaussian-Based Localization and Deduction |
| title_full | Locating the Source of Diffusion in Complex Networks via Gaussian-Based Localization and Deduction |
| title_fullStr | Locating the Source of Diffusion in Complex Networks via Gaussian-Based Localization and Deduction |
| title_full_unstemmed | Locating the Source of Diffusion in Complex Networks via Gaussian-Based Localization and Deduction |
| title_short | Locating the Source of Diffusion in Complex Networks via Gaussian-Based Localization and Deduction |
| title_sort | locating the source of diffusion in complex networks via gaussian based localization and deduction |
| topic | source localization optimization algorithm data mining complex networks |
| url | https://www.mdpi.com/2076-3417/9/18/3758 |
| work_keys_str_mv | AT xiangli locatingthesourceofdiffusionincomplexnetworksviagaussianbasedlocalizationanddeduction AT xiaojiewang locatingthesourceofdiffusionincomplexnetworksviagaussianbasedlocalizationanddeduction AT chenglizhao locatingthesourceofdiffusionincomplexnetworksviagaussianbasedlocalizationanddeduction AT xuezhang locatingthesourceofdiffusionincomplexnetworksviagaussianbasedlocalizationanddeduction AT dongyunyi locatingthesourceofdiffusionincomplexnetworksviagaussianbasedlocalizationanddeduction |