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