Multiple propagation paths enhance locating the source of diffusion in complex networks

Łukasz Gajewski , Krzysztof Suchecki , Janusz Hołyst


We investigate the problem of locating the source of diffusion in complex networks without complete knowledge of nodes’ states. Some currently known methods assume the information travels via a single, shortest path, which by assumption is the fastest way. We show that such a method leads to the overestimation of propagation time for synthetic and real networks, where multiple shortest paths as well as longer paths between vertices exist. We propose a new method of source estimation based on maximum likelihood principle, that takes into account existence multiple shortest paths. It shows up to 1.6 times higher accuracy in synthetic and real networks.
Publication typeOriginal work published as abstract
Author Łukasz Gajewski (FP / LPESS)
Łukasz Gajewski,,
- Center of Physics in Economics and Social Sciences
, Krzysztof Suchecki (FP / LPESS)
Krzysztof Suchecki,,
- Center of Physics in Economics and Social Sciences
, Janusz Hołyst (FP / LPESS)
Janusz Hołyst,,
- Center of Physics in Economics and Social Sciences
Corporate authorThe Faculty of Physics, WUT (WF)
Journal seriesPhysica A-Statistical Mechanics and Its Applications, ISSN 0378-4371, (0 pkt)
Issue year2019
Publication size in sheets0.5
Keywords in EnglishMultiple propagation, Complex Systems
ASJC Classification3104 Condensed Matter Physics; 2613 Statistics and Probability
ProjectReverse EngiNeering of sOcial Information pRocessing. Project leader: Hołyst Janusz, , Phone: 22 234 7133, application date 28-04-2015, start date 01-01-2016, end date 31-12-2019, 691152, Implemented
WF Horizon 2020 [Horyzont 2020]
Languageen angielski
Score (nominal)0
Score sourcejournalList
Publication indicators WoS Citations = 0; Scopus Citations = 0; Scopus SNIP (Source Normalised Impact per Paper): 2016 = 1.324; WoS Impact Factor: 2018 = 2.5 (2) - 2018=2.464 (5)
Citation count*
Share Share

Get link to the record

* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.
Are you sure?