The DOI matches its Crossref record; 17 of the 17 references it cites were found in a registry or an index.
Locating the Source of Diffusion in Large-Scale Networks
Open accessAbstract
How can we localize the source of diffusion in a complex network? Because of the tremendous size of many real networks-such as the internet or the human social graph-it is usually unfeasible to observe the state of all nodes in a network. We show that it is fundamentally possible to estimate the location of the source from measurements collected by sparsely placed observers. We present a strategy that is optimal for arbitrary trees, achieving maximum probability of correct localization. We describe efficient implementations with complexity O(N(α)), where α=1 for arbitrary trees and α=3 for arbitrary graphs. In the context of several case studies, we determine how localization accuracy is affected by various system parameters, including the structure of the network, the density of observers, and the number of observed cascades.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Emergence of Scaling in Random Networks
Barabási, A.-L., & Albert, R. (1999) · Science · doi:10.1126/science.286.5439.509 · Cited by 36,135
Statistical mechanics of complex networks
Albert, R., & Barabási, A.-L. (2002) · Reviews of Modern Physics · doi:10.1103/revmodphys.74.47 · Cited by 20,471
Epidemic Spreading in Scale-Free Networks
Pastor-Satorras, R., & Vespignani, A. (2001) · Physical Review Letters · doi:10.1103/physrevlett.86.3200 · Cited by 5,731
Spread of epidemic disease on networks
Newman, M. E. J. (2002) · Physical Review E · doi:10.1103/physreve.66.016128 · Cited by 3,218
Controllability of complex networks
Liu, Y.-Y., Slotine, J.-J., & Barabási, A.-L. (2011) · Nature · doi:10.1038/nature10011 · Cited by 3,215
Berg, H. C. (2025) · Princeton University Press eBooks · doi:10.1515/9780691279886 · Cited by 2,367
Epidemics and percolation in small-world networks
Moore, C., & Newman, M. E. J. (2000) · Physical Review E · doi:10.1103/physreve.61.5678 · Cited by 948
‘Infotaxis’ as a strategy for searching without gradients
Vergassola, M., Villermaux, E., & Shraiman, B. I. (2007) · Nature · doi:10.1038/nature05464 · Cited by 890
Olfactory Imprinting and Homing in Salmon
Hasler, A. D., & Scholz, A. T. (1983) · Zoophysiology · doi:10.1007/978-3-642-82070-0 · Cited by 622
Small World Effect in an Epidemiological Model
Kuperman, M., & Abramson, G. (2001) · Physical Review Letters · doi:10.1103/physrevlett.86.2909 · Cited by 528
Mechanisms of animal navigation in odor plumes
Vickers, N. (2000) · The Biological Bulletin · doi:10.2307/1542524 · Cited by 475
Andrade, J. S., Herrmann, H. J., Andrade, R. F. S., & da Silva, L. R. (2005) · Physical Review Letters · doi:10.1103/physrevlett.94.018702 · Cited by 398
On spatially explicit models of cholera epidemics
Bertuzzo, E., Casagrandi, R., Gatto, M., Rodriguez-Iturbe, I., & Rinaldo, A. (2010) · Journal of The Royal Society Interface · doi:10.1098/rsif.2009.0204 · Cited by 199
On the space‐time evolution of a cholera epidemic
Bertuzzo, E., Azaele, S., Maritan, A., Gatto, M., Rodriguez‐Iturbe, I., & Rinaldo, A. (2008) · Water Resources Research · doi:10.1029/2007wr006211 · Cited by 182
Self-similar disk packings as model spatial scale-free networks
Doye, J. P. K., & Massen, C. P. (2005) · Physical Review E · doi:10.1103/physreve.71.016128 · Cited by 162
Spreading gossip in social networks
Lind, P. G., da Silva, L. R., Andrade, J. S., & Herrmann, H. J. (2007) · Physical Review E · doi:10.1103/physreve.76.036117 · Cited by 145
Competitive cluster growth in complex networks
Moreira, A. A., de Paula, D. R., Filho, R. N. C., & Andrade, J. S. (2006) · Physical Review E · doi:10.1103/physreve.73.065101 · Cited by 73
Cited by
Epidemic processes in complex networks
Pastor-Satorras, R., Castellano, C., Van Mieghem, P., & Vespignani, A. (2015) · Reviews of Modern Physics · doi:10.1103/revmodphys.87.925 · Cited by 3,697
The Hidden Geometry of Complex, Network-Driven Contagion Phenomena
Brockmann, D., & Helbing, D. (2013) · Science · doi:10.1126/science.1245200 · Cited by 1,253
Dynamics of information diffusion and its applications on complex networks
Zhang, Z.-K., Liu, C., Zhan, X.-X., Lu, X., Zhang, C.-X., & Zhang, Y.-C. (2016) · Physics Reports · doi:10.1016/j.physrep.2016.07.002 · Cited by 484
Inferring the origin of an epidemic with a dynamic message-passing algorithm
Lokhov, A. Y., Mézard, M., Ohta, H., & Zdeborová, L. (2014) · Physical Review E · doi:10.1103/physreve.90.012801 · Cited by 322
The Critical Node Detection Problem in networks: A survey
Lalou, M., Tahraoui, M. A., & Kheddouci, H. (2018) · Computer Science Review · doi:10.1016/j.cosrev.2018.02.002 · Cited by 311
Metadata
- Authors
- Pinto, P. C., Thiran, P., & Vetterli, M.
- Venue
- Physical Review Letters
- Publisher
- American Physical Society (APS)
- Published
- 2012-08-10
- Volume
- 109
- Issue
- 6
- Pages
- 068702-068702
- ISSN
- 0031-9007 (ISSN-L)
- 1079-7114
- OpenAlex
- W2130466555
- Cited by
- 409
- References
- 17
- FWCI
- 17.52
- Type
- journal article
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.