Structural Results and Applications for Perturbed Markov Chains

Abstract:

Each day, we interact with a myriad of networks: we search for information on the web, connect with friends over social media, and power our homes from the electrical grid. Many of these interactions have improved our lives — the web facilitating access to information, for example — but some have caused new issues — the rise of fake news on social media, for example. The goal of this thesis is to advance our understanding of these systems, in hopes improving beneficial interactions with networks while reducing the harm of detrimental ones.

Our primary contributions are threefold. First, we devise algorithms for estimating Personalized PageRank (PPR), a measure of node similarity used in applications like web search and recommendation systems. Second, we apply ideas from the PPR literature to devise policy evaluation algorithms in reinforcement learning, and to characterize the robustness of Markov models. Third, we analyze a model of fake news and obtain new insights regarding its spread over networks.

While these topics are diverse, a unifying mathematical theme is that of perturbed Markov chains. This includes perturbations that yield useful interpretations in applications, provide algorithmic and analytical advantages, or disrupt some well-functioning system.

Chair: Professor Vijay Subramanian