A revisit to the infection source identification problem under classical graph centrality measures

Syed Shafat Ali, Tarique Anwar*, Syed Afzal Murtaza Rizvi

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

4 Citations (Scopus)

Abstract

The high connectivity of the modern day world has lead to the easy diffusion of harmful information content like rumors, computer viruses, and contagions like diseases. This is detrimental to human societies in terms of compromised security, monetary loss and life threats. Therefore, to mitigate such damages, identifying and timely quarantining the sources of such diffusion processes is highly critical. Despite the difficulty and challenges of the problem, researchers have extensively studied source identification in complex networks over the past decade. Several approaches have been proposed, but limited attention has been given to the classical graph centrality measures. Moreover, researchers have generally advised against employing these measures for identifying infection sources. Motivated by the same, in this paper, we revisit these measures in context to source identification and raise the question: “Are classical graph centrality measures really not good enough?”, and perform an extensive experimental journey. We pick five such measures, viz., betweenness, closeness, degree, eigenvector and eccentricity, and conduct an in-depth analysis of their effectiveness in source detection. Our extensive results show that, contrary to the popular belief, a combination of eccentricity and closeness (EC+CC) generally performs better than several state-of-the-art source identification techniques, with higher accuracy and lower average hop error. We also analyze the impact of infection size on source identification and observe that EC+CC is generally highly scalable and stable as well. We also understand that as the infection size increases, the detection accuracy decreases, irrespective of the technique used. However, when we examine the effect of graph density, we observe that as the graph density increases, the detection accuracy increases as well, with EC+CC again outperforming state-of-the-art.
Original languageEnglish
Article number100061
Pages (from-to)1-12
Number of pages12
JournalOnline Social Networks and Media
Volume17
DOIs
Publication statusPublished - May 2020

Bibliographical note

Version archived for private and non-commercial use with the permission of the author/s and according to publisher conditions. For further rights please contact the publisher.

Keywords

  • Infection source identification
  • Graph centrality
  • Complex graphs
  • Susceptible-infected model
  • Online social networks
  • Information diffusion

Fingerprint

Dive into the research topics of 'A revisit to the infection source identification problem under classical graph centrality measures'. Together they form a unique fingerprint.

Cite this