Estimating the number of infection sources in a tree

Feng Ji, Wee Peng Tay, Lav R Varshney

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Most algorithms for identifying multiple rumor or infection sources require prior knowledge of the number of sources, or at least an upper bound on the number of sources. In this paper, we consider a deterministic Susceptible-Infected (SI) spreading model in which infection at different source nodes may start at different times. We introduce the concept of a minimal and linear cover of the infection graph, and propose the use of graph signals on the infection graph to estimate the number of sources. Under certain mild conditions, we demonstrate that our method gives a good estimate of the number of infection sources for tree graphs.

Original languageEnglish (US)
Title of host publication2016 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2016 - Proceedings
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages380-384
Number of pages5
ISBN (Electronic)9781509045457
DOIs
StatePublished - Apr 19 2017
Event2016 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2016 - Washington, United States
Duration: Dec 7 2016Dec 9 2016

Publication series

Name2016 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2016 - Proceedings

Other

Other2016 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2016
CountryUnited States
CityWashington
Period12/7/1612/9/16

Keywords

  • Graph signal
  • Infection spreading
  • Rumor spreading
  • SI model
  • Source number estimation

ASJC Scopus subject areas

  • Signal Processing
  • Computer Networks and Communications

Cite this

Ji, F., Tay, W. P., & Varshney, L. R. (2017). Estimating the number of infection sources in a tree. In 2016 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2016 - Proceedings (pp. 380-384). [7905868] (2016 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2016 - Proceedings). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/GlobalSIP.2016.7905868

Estimating the number of infection sources in a tree. / Ji, Feng; Tay, Wee Peng; Varshney, Lav R.

2016 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2016 - Proceedings. Institute of Electrical and Electronics Engineers Inc., 2017. p. 380-384 7905868 (2016 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2016 - Proceedings).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Ji, F, Tay, WP & Varshney, LR 2017, Estimating the number of infection sources in a tree. in 2016 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2016 - Proceedings., 7905868, 2016 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2016 - Proceedings, Institute of Electrical and Electronics Engineers Inc., pp. 380-384, 2016 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2016, Washington, United States, 12/7/16. https://doi.org/10.1109/GlobalSIP.2016.7905868
Ji F, Tay WP, Varshney LR. Estimating the number of infection sources in a tree. In 2016 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2016 - Proceedings. Institute of Electrical and Electronics Engineers Inc. 2017. p. 380-384. 7905868. (2016 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2016 - Proceedings). https://doi.org/10.1109/GlobalSIP.2016.7905868
Ji, Feng ; Tay, Wee Peng ; Varshney, Lav R. / Estimating the number of infection sources in a tree. 2016 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2016 - Proceedings. Institute of Electrical and Electronics Engineers Inc., 2017. pp. 380-384 (2016 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2016 - Proceedings).
@inproceedings{e52b517aa5d04abab8d05ced74b105b3,
title = "Estimating the number of infection sources in a tree",
abstract = "Most algorithms for identifying multiple rumor or infection sources require prior knowledge of the number of sources, or at least an upper bound on the number of sources. In this paper, we consider a deterministic Susceptible-Infected (SI) spreading model in which infection at different source nodes may start at different times. We introduce the concept of a minimal and linear cover of the infection graph, and propose the use of graph signals on the infection graph to estimate the number of sources. Under certain mild conditions, we demonstrate that our method gives a good estimate of the number of infection sources for tree graphs.",
keywords = "Graph signal, Infection spreading, Rumor spreading, SI model, Source number estimation",
author = "Feng Ji and Tay, {Wee Peng} and Varshney, {Lav R}",
year = "2017",
month = "4",
day = "19",
doi = "10.1109/GlobalSIP.2016.7905868",
language = "English (US)",
series = "2016 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2016 - Proceedings",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "380--384",
booktitle = "2016 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2016 - Proceedings",
address = "United States",

}

TY - GEN

T1 - Estimating the number of infection sources in a tree

AU - Ji, Feng

AU - Tay, Wee Peng

AU - Varshney, Lav R

PY - 2017/4/19

Y1 - 2017/4/19

N2 - Most algorithms for identifying multiple rumor or infection sources require prior knowledge of the number of sources, or at least an upper bound on the number of sources. In this paper, we consider a deterministic Susceptible-Infected (SI) spreading model in which infection at different source nodes may start at different times. We introduce the concept of a minimal and linear cover of the infection graph, and propose the use of graph signals on the infection graph to estimate the number of sources. Under certain mild conditions, we demonstrate that our method gives a good estimate of the number of infection sources for tree graphs.

AB - Most algorithms for identifying multiple rumor or infection sources require prior knowledge of the number of sources, or at least an upper bound on the number of sources. In this paper, we consider a deterministic Susceptible-Infected (SI) spreading model in which infection at different source nodes may start at different times. We introduce the concept of a minimal and linear cover of the infection graph, and propose the use of graph signals on the infection graph to estimate the number of sources. Under certain mild conditions, we demonstrate that our method gives a good estimate of the number of infection sources for tree graphs.

KW - Graph signal

KW - Infection spreading

KW - Rumor spreading

KW - SI model

KW - Source number estimation

UR - http://www.scopus.com/inward/record.url?scp=85017664301&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85017664301&partnerID=8YFLogxK

U2 - 10.1109/GlobalSIP.2016.7905868

DO - 10.1109/GlobalSIP.2016.7905868

M3 - Conference contribution

AN - SCOPUS:85017664301

T3 - 2016 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2016 - Proceedings

SP - 380

EP - 384

BT - 2016 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2016 - Proceedings

PB - Institute of Electrical and Electronics Engineers Inc.

ER -