Network Infusion to Infer Information Sources in Networks
IEEE Several significant models have been developed that enable the study of diffusion of signals across biological, social and engineered networks. Within these established frameworks, the inverse problem of identifying the source of the propagated signal is challenging, owing to the numerous alter...
| Main Authors: | , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Institute of Electrical and Electronics Engineers (IEEE)
2021
|
| Online Access: | https://hdl.handle.net/1721.1/134667 |
| _version_ | 1826213406005264384 |
|---|---|
| author | Feizi, Soheil Medard, Muriel Quon, Gerald Kellis, Manolis Duffy, Ken |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Feizi, Soheil Medard, Muriel Quon, Gerald Kellis, Manolis Duffy, Ken |
| author_sort | Feizi, Soheil |
| collection | MIT |
| description | IEEE Several significant models have been developed that enable the study of diffusion of signals across biological, social and engineered networks. Within these established frameworks, the inverse problem of identifying the source of the propagated signal is challenging, owing to the numerous alternative possibilities for signal progression through the network. In real world networks, the challenge of determining sources is compounded as the true propagation dynamics are typically unknown, and when they have been directly measured, they rarely conform to the assumptions of any of the well-studied models. In this paper we introduce a method called Network Infusion (NI) that has been designed to circumvent these issues, making source inference practical for large, complex real world networks. The key idea is that to infer the source node in the network, full characterization of diffusion dynamics, in many cases, may not be necessary. This objective is achieved by creating a diffusion kernel that well-approximates standard diffusion models such as the susceptible-infected diffusion model, but lends itself to inversion, by design, via likelihood maximization or error minimization. We apply NI for both single-source and multi-source diffusion, for both single-snapshot and multi-snapshot observations, and for both homogeneous and heterogeneous diffusion setups. We prove the mean-field optimality of NI for different scenarios, and demonstrate its effectiveness over several synthetic networks. Moreover, we apply NI to a real-data application, identifying news sources in the Digg social network, and demonstrate the effectiveness of NI compared to existing methods. Finally, we propose an integrative source inference framework that combines NI with a distance centrality-based method, which leads to a robust performance in cases where the underlying dynamics are unknown. |
| first_indexed | 2024-09-23T15:48:34Z |
| format | Article |
| id | mit-1721.1/134667 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T15:48:34Z |
| publishDate | 2021 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/1346672023-01-11T17:47:24Z Network Infusion to Infer Information Sources in Networks Feizi, Soheil Medard, Muriel Quon, Gerald Kellis, Manolis Duffy, Ken Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science IEEE Several significant models have been developed that enable the study of diffusion of signals across biological, social and engineered networks. Within these established frameworks, the inverse problem of identifying the source of the propagated signal is challenging, owing to the numerous alternative possibilities for signal progression through the network. In real world networks, the challenge of determining sources is compounded as the true propagation dynamics are typically unknown, and when they have been directly measured, they rarely conform to the assumptions of any of the well-studied models. In this paper we introduce a method called Network Infusion (NI) that has been designed to circumvent these issues, making source inference practical for large, complex real world networks. The key idea is that to infer the source node in the network, full characterization of diffusion dynamics, in many cases, may not be necessary. This objective is achieved by creating a diffusion kernel that well-approximates standard diffusion models such as the susceptible-infected diffusion model, but lends itself to inversion, by design, via likelihood maximization or error minimization. We apply NI for both single-source and multi-source diffusion, for both single-snapshot and multi-snapshot observations, and for both homogeneous and heterogeneous diffusion setups. We prove the mean-field optimality of NI for different scenarios, and demonstrate its effectiveness over several synthetic networks. Moreover, we apply NI to a real-data application, identifying news sources in the Digg social network, and demonstrate the effectiveness of NI compared to existing methods. Finally, we propose an integrative source inference framework that combines NI with a distance centrality-based method, which leads to a robust performance in cases where the underlying dynamics are unknown. 2021-10-27T20:06:06Z 2021-10-27T20:06:06Z 2019 2019-06-07T14:53:17Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/134667 Feizi, S., et al. "Network Infusion to Infer Information Sources in Networks [Arxiv]." arXiv (2016): 21 pp. en 10.1109/TNSE.2018.2854218 IEEE Transactions on Network Science and Engineering Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Institute of Electrical and Electronics Engineers (IEEE) arXiv |
| spellingShingle | Feizi, Soheil Medard, Muriel Quon, Gerald Kellis, Manolis Duffy, Ken Network Infusion to Infer Information Sources in Networks |
| title | Network Infusion to Infer Information Sources in Networks |
| title_full | Network Infusion to Infer Information Sources in Networks |
| title_fullStr | Network Infusion to Infer Information Sources in Networks |
| title_full_unstemmed | Network Infusion to Infer Information Sources in Networks |
| title_short | Network Infusion to Infer Information Sources in Networks |
| title_sort | network infusion to infer information sources in networks |
| url | https://hdl.handle.net/1721.1/134667 |
| work_keys_str_mv | AT feizisoheil networkinfusiontoinferinformationsourcesinnetworks AT medardmuriel networkinfusiontoinferinformationsourcesinnetworks AT quongerald networkinfusiontoinferinformationsourcesinnetworks AT kellismanolis networkinfusiontoinferinformationsourcesinnetworks AT duffyken networkinfusiontoinferinformationsourcesinnetworks |