東華大學圖書館 |

Language: English

Help

回圖書館首頁

手機版館藏查詢

Back

Switch To: Labeled | MARC Mode | ISBD

Structural Results and Applications ...

Vial, Daniel.

Linked to FindBook

Google Book

Amazon

博客來

Structural Results and Applications for Perturbed Markov Chains.

Record Type:	Electronic resources : Monograph/item
Title/Author:	Structural Results and Applications for Perturbed Markov Chains./
Author:	Vial, Daniel.
Published:	Ann Arbor : ProQuest Dissertations & Theses, : 2020,
Description:	313 p.
Notes:	Source: Dissertations Abstracts International, Volume: 81-11, Section: B.
Contained By:	Dissertations Abstracts International81-11B.
Subject:	Systems science. -
Online resource:	http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=28006627
ISBN:	9798643185260

Structural Results and Applications for Perturbed Markov Chains.
Vial, Daniel.

Structural Results and Applications for Perturbed Markov Chains. - Ann Arbor : ProQuest Dissertations & Theses, 2020 - 313 p.

Source: Dissertations Abstracts International, Volume: 81-11, Section: B.

Thesis (Ph.D.)--University of Michigan, 2020.

This item must not be sold to any third party vendors.

Each day, most of us interact with a myriad of networks: we search for information on the web, connect with friends on social media platforms, and power our homes using the electrical grid. Many of these interactions have improved our lives, but some have caused new societal issues - social media facilitating the rise of fake news, 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 new algorithms for estimating Personalized PageRank (PPR), a measure of similarity between the nodes in a network used in applications like web search and recommendation systems. In contrast to most existing PPR estimators, our algorithms exploit local graph structure to reduce estimation complexity. We show the analysis of such algorithms is tractable for certain random graph models, and that the key insights obtained from these models hold empirically for real graphs.Our second contribution is to apply ideas from the PPR literature to two other problems. First, we show that PPR estimators can be adapted to the policy evaluation problem in reinforcement learning. More specifically, we devise policy evaluation algorithms inspired by existing PPR estimators that leverage certain side information to reduce the sample complexity of existing methods. Second, we use analytical ideas from the PPR literature to show that convergence behavior and robustness are intimately related for a certain class of Markov chains.Finally, we study social learning over networks as a model for the spread of fake news. For this model, we characterize the learning outcome in terms of a novel measure of the "density" of users spreading fake news. Using this characterization, we also devise optimal strategies for seeding fake news spreaders so as to disrupt learning. These strategies empirically outperform intuitive heuristics on real social networks (despite not being provably optimal for such graphs) and thus provide new insights regarding vulnerabilities in social learning.While the topics studied in this thesis are diverse, a unifying mathematical theme is that of perturbed Markov chains. This includes perturbations that yield useful interpretations in various applications, that provide algorithmic and analytical advantages, and that disrupt some underlying system or process. Throughout the thesis, the perturbed Markov chain theme guides our analysis and suggests more general methodologies.

ISBN: 9798643185260Subjects--Topical Terms:

3168411
Systems science.
Subjects--Index Terms:

Network science

Structural Results and Applications for Perturbed Markov Chains.
LDR:03855nmm a2200385 4500 001 2271462
005 20201007134730.5
008 220629s2020 ||||||||||||||||| ||eng d
020 $a 9798643185260
035 $a (MiAaPQ)AAI28006627
035 $a (MiAaPQ)umichrackham002910
035 $a AAI28006627
040 $a MiAaPQ $c MiAaPQ
100 1 $a Vial, Daniel. $3 3548870
245 1 0 $a Structural Results and Applications for Perturbed Markov Chains.
260 1 $a Ann Arbor : $b ProQuest Dissertations & Theses, $c 2020
300 $a 313 p.
500 $a Source: Dissertations Abstracts International, Volume: 81-11, Section: B.
500 $a Advisor: Subramanian, Vijay Gautam.
502 $a Thesis (Ph.D.)--University of Michigan, 2020.
506 $a This item must not be sold to any third party vendors.
506 $a This item must not be added to any third party search indexes.
520 $a Each day, most of us interact with a myriad of networks: we search for information on the web, connect with friends on social media platforms, and power our homes using the electrical grid. Many of these interactions have improved our lives, but some have caused new societal issues - social media facilitating the rise of fake news, 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 new algorithms for estimating Personalized PageRank (PPR), a measure of similarity between the nodes in a network used in applications like web search and recommendation systems. In contrast to most existing PPR estimators, our algorithms exploit local graph structure to reduce estimation complexity. We show the analysis of such algorithms is tractable for certain random graph models, and that the key insights obtained from these models hold empirically for real graphs.Our second contribution is to apply ideas from the PPR literature to two other problems. First, we show that PPR estimators can be adapted to the policy evaluation problem in reinforcement learning. More specifically, we devise policy evaluation algorithms inspired by existing PPR estimators that leverage certain side information to reduce the sample complexity of existing methods. Second, we use analytical ideas from the PPR literature to show that convergence behavior and robustness are intimately related for a certain class of Markov chains.Finally, we study social learning over networks as a model for the spread of fake news. For this model, we characterize the learning outcome in terms of a novel measure of the "density" of users spreading fake news. Using this characterization, we also devise optimal strategies for seeding fake news spreaders so as to disrupt learning. These strategies empirically outperform intuitive heuristics on real social networks (despite not being provably optimal for such graphs) and thus provide new insights regarding vulnerabilities in social learning.While the topics studied in this thesis are diverse, a unifying mathematical theme is that of perturbed Markov chains. This includes perturbations that yield useful interpretations in various applications, that provide algorithmic and analytical advantages, and that disrupt some underlying system or process. Throughout the thesis, the perturbed Markov chain theme guides our analysis and suggests more general methodologies.
590 $a School code: 0127.
650 4 $a Systems science. $3 3168411
650 4 $a Electrical engineering. $3 649834
653 $a Network science
653 $a Network centrality
653 $a Reinforcement learning
653 $a Perturbed Markov chain
653 $a Social learning
690 $a 0544
690 $a 0790
710 2 $a University of Michigan. $b Electrical Engineering: Systems. $3 3280006
773 0 $t Dissertations Abstracts International $g 81-11B.
790 $a 0127
791 $a Ph.D.
792 $a 2020
793 $a English
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=28006627