EPA

exoneration and prominence based age for infection source identification

Syed Shafat Ali, Tarique Anwar, Ajay Rastogi, Syed Afzal Murtaza Rizvi

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

1 Citation (Scopus)

Abstract

Infection source identification is a well-established problem, having gained a substantial scale of research attention over the years. In this paper, we study the problem by exploiting the idea of the source being the oldest node. For the same, we propose a novel algorithm called Exoneration and Prominence based Age (EPA), which calculates the age of an infected node by considering its prominence in terms of its both infected and non-infected neighbors. These non-infected neighbors hold the key in exonerating an infected node from being the infection source. We also propose a computationally inexpensive variant of EPA, called EPA-LW. Extensive experiments are performed on seven datasets, including 5 real-world and 2 synthetic, of different topologies and varying sizes to demonstrate the effectiveness of the proposed algorithms. We consistently outperform the state-of-the-art single source identification methods in terms of average error distance. To the best of our knowledge, this is the largest scale performance evaluation of the considered problem till date. We also extend EPA to identify multiple sources by developing two new algorithms - one based on K-Means, called EPA_K-Means, and another based on successive identification of sources, called EPA_SSI. Our results show that both EPA_K-Means and EPA_SSI outperform the other multi-source heuristic approaches.

Original languageEnglish
Title of host publicationCIKM 2019 - Proceedings of the 28th ACM International Conference on Information and Knowledge Management
Place of PublicationNew York
PublisherAssociation for Computing Machinery (ACM)
Pages891-900
Number of pages10
ISBN (Electronic)9781450369763
DOIs
Publication statusPublished - 2019
Event28th ACM International Conference on Information and Knowledge Management, CIKM 2019 - Beijing, China
Duration: 3 Nov 20197 Nov 2019

Publication series

NameInternational Conference on Information and Knowledge Management, Proceedings

Conference

Conference28th ACM International Conference on Information and Knowledge Management, CIKM 2019
CountryChina
CityBeijing
Period3/11/197/11/19

Keywords

  • Complex networks
  • Exoneration and Prominence
  • Infection source identification
  • Information diffusion
  • Rumor detection

Fingerprint Dive into the research topics of 'EPA: exoneration and prominence based age for infection source identification'. Together they form a unique fingerprint.

Cite this