11th EAI International Conference on Performance Evaluation Methodologies and Tools

Research Article

MCMC Approaches to Rumor Source Inference using Pairwise Information

  • @INPROCEEDINGS{10.4108/eai.5-12-2017.2274418,
        author={Anand  Kalvit and Vivek S. Borkar and Nikhil  Karamchandani},
        title={MCMC Approaches to Rumor Source Inference using Pairwise Information},
        proceedings={11th EAI International Conference on Performance Evaluation Methodologies and Tools},
        publisher={ACM},
        proceedings_a={VALUETOOLS},
        year={2018},
        month={8},
        keywords={source detection inference on networks mcmc epidemic models},
        doi={10.4108/eai.5-12-2017.2274418}
    }
    
  • Anand Kalvit
    Vivek S. Borkar
    Nikhil Karamchandani
    Year: 2018
    MCMC Approaches to Rumor Source Inference using Pairwise Information
    VALUETOOLS
    ACM
    DOI: 10.4108/eai.5-12-2017.2274418
Anand Kalvit1,*, Vivek S. Borkar1, Nikhil Karamchandani1
  • 1: Dept. of Electrical Engineering, IIT Bombay
*Contact email: anandiitb12@gmail.com

Abstract

In this work, we examine the problem of rumor source inference on a network whose topology is known, given infected nodes and pairwise information in the form of pairwise partial orders on the set of nodes of the underlying graph based on the order in which they were infected. We analyze the Maximum Likelihood Estimator (MLE) of the rumor source, assumed unique, and compare it with other estimators popular in literature, e.g., rumor center, distance center and Jordan center. We propose an approximation to the MLE and a class of estimators based on this approximation that is agnostic to the underlying rumor model. We also propose MCMC algorithms to implement them. Further, we assess the robustness of the proposed estimators to different graph topologies via extensive simulations on the Erdos-Renyi and Barabasi-Albert models.