Hwai-Liang Tung - DIMACS REU 2021

Name:	Hwai-Liang Tung
Email:	hwai-liang_tung@brown.edu
Mentor:	Min Xu
Home Institution:	Brown University
Project:	Statistical inference on infection processes over graphs

---

Project Description

Epidemics, cyber attacks, dissemination of fake news, and a variety of other processes can be modeled as an infection process on a graph. For this project, we seek to improve an MCMC Metropolis-within-Gibbs algorithm which probability a node is the true patient zero given a set of infected nodes and the background graph. We seek to make this algorithm faster and also more generalizable. We also wish to derive theoretical results about how well we may estimate the patient zero on various kinds of graphs.

Research Log

Week 1: 5/24-5/30

During the first week, I spent time familiarizing myself with code implementing a Metropolis-within-Gibbs algorithm for finding a patient zero. After I understood the code and algorithm, my mentor and I also spent time discussing methods to improve the algorithm. I also spent time preparing for the presentation introducing my project on 6/1.

Week 2: 5:31-6/6

On Tuesday I delivered a short 4 minute presentation describing my project. Afterwards, I spent time testing the algorithm on different types of networks and started reading literature about the mixing time of Markov chains. My mentor and I also discussed methods for extending our algorithm to the case where we have noisy observations of our infected nodes.

Week 3: 6/7-6/13

This week my mentor and I formulated the algorithm for the case where we have noisy observations of our infected nodes. After we had decided all the details, I implemented the algorithm in python. Throughout the week, I was also reading the papers two papers assigned to me by my professor on first passage percolation theory and convergence of MCMC algorithms.

Week 4: 6/14-6/21

During this week, I was continued reading the first passage percolation theory, and my mentor and I discussed results from the paper. I also tested the algorithm on noisy cases to ensure that it converged to the correct result and displayed expected behavior. To do so, I calculated the posterior probabilities we would expect on a simple graph and verified that the probabilities matched the results of the algorithm. I also constructed a confidence set based on the results of the algorithm and tested that the true patient zero lay in the set with the proportion we expected.

Week 5: 6/22-6/28

This week I learned about Sequential Monte Carlo and particle filtering methods. I also wrote up a proof that given n infected nodes on a lattice graph, we can bound the size of a confidence set for the patient zero so it is less than O(n). My mentor and I also discussed possibilities to apply the proof techniques used to other types of graphs.

Week 6: 6/29-7/4

This week, I kept reading the Kesten paper on first passage percolation theory. My mentor and I discovered an error in the proof written last week and we worked to fix the error; at the end of the week, I almost completed writing up the new proof. We also attempted to write up an algorithm using particle filtering methods but found that using this approach will likely be intractable. For now, we have set aside thsi approach and will be looking for other methods to make our algorithm more scalable.

Week 7: 7/5-7/11

This week, my mentor and I formulated a new proposal to use in our algorithm to make it more scalable; we spent the week discussing and refining our ideas for the new potential proposal. On next monday we expect to decide the specifics of our method and start implementing the approach. While deciding this approach, I was given two papers to read in order to learn how it would work. Throughout the week, I also spent time reading the Kesten paper on first passage percolation theory.

Week 8: 7/12-7/18

On Monday, as planned, my mentor and I finalized the specifics of our new algorithm. On Thursday, I finished implementing the algorithm and started testing the code. At the end of the week, the code was running without bugs.

Week 9: 7/19-7/23

This week, I spent most of my time working on the final report and presentation. For the report and presentation, I wrote code to create a visualization of the results of the algorithm. I delivered my presentation and finished my report on Friday.