國立高雄大學圖資館 |

登入

回首頁

Inference of Cascades and Correlated Networks.

紀錄類型:	書目-電子資源 : Monograph/item
正題名/作者:	Inference of Cascades and Correlated Networks.
作者:	Sridhar, Anirudh.
出版者:	Ann Arbor : ProQuest Dissertations & Theses, 2023
面頁冊數:	239 p.
附註:	Source: Dissertations Abstracts International, Volume: 84-12, Section: B.
附註:	Advisor: Poor, H. Vincent;Racz, Miklos Z.
Contained By:	Dissertations Abstracts International84-12B.
標題:	Statistics.
電子資源:	http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=30492319
ISBN:	9798379719210

Inference of Cascades and Correlated Networks.
Sridhar, Anirudh.

Inference of Cascades and Correlated Networks. - Ann Arbor : ProQuest Dissertations & Theses, 2023 - 239 p.

Source: Dissertations Abstracts International, Volume: 84-12, Section: B.

Thesis (Ph.D.)--Princeton University, 2023.

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

This thesis makes fundamental contributions to a few statistical inference tasks on networks, with a focus on information-theoretic characterizations. In the first part of this thesis, we study the problem of localizing a network cascade from noisy, real-time measurements of its spread (i.e., through error-prone diagnostic tests). Our objective is to design algorithms that can estimate the cascade source as fast as possible, so that the impact of the cascade on the network can be mitigated. We design estimation procedures from Bayesian and minimax perspectives. In the Bayesian setting, we propose an estimator which observes samples until the error of the Bayes-optimal estimator falls below a threshold. In the minimax setting, we devise a novel multihypothesis sequential probability ratio test (MSPRT) for source estimation. When estimating simple cascades in trees and lattices, we show that both methods are optimal, in the sense that no other algorithm can accurately estimate the source with a substantially smaller number of samples. Finally, we discuss how our methods may be extended to estimate realistic cascades in generic networks.In the second part of this thesis, we study graph matching and community recovery in networks with correlated structure. First, we derive the precise information-theoretic threshold for fully recovering the latent vertex correspondence between two edge-correlated stochastic block models – a task known as exact graph matching. We then characterize the information-theoretic landscape of community recovery in correlated stochastic block models, which requires a delicate interplay between graph matching and community recovery algorithms. In particular, we uncover and characterize a region of the parameter space where exact community recovery is possible using multiple correlated graphs, even though (1) this is information-theoretically impossible using a single graph and (2) exact graph matching is also information-theoretically impossible. In this regime, we develop a novel algorithm that carefully synthesizes community recovery and graph matching algorithms.

ISBN: 9798379719210Subjects--Topical Terms:

182057
Statistics.
Subjects--Index Terms:

Community recovery

Inference of Cascades and Correlated Networks.
LDR:03387nmm a2200409 4500 001 655779
005 20240414211928.5
006 m o d
007 cr#unu||||||||
008 240620s2023 ||||||||||||||||| ||eng d
020 $a 9798379719210
035 $a (MiAaPQ)AAI30492319
035 $a AAI30492319
040 $a MiAaPQ $c MiAaPQ
100 1 $a Sridhar, Anirudh. $3 892583
245 1 0 $a Inference of Cascades and Correlated Networks.
260 1 $a Ann Arbor : $b ProQuest Dissertations & Theses, $c 2023
300 $a 239 p.
500 $a Source: Dissertations Abstracts International, Volume: 84-12, Section: B.
500 $a Advisor: Poor, H. Vincent;Racz, Miklos Z.
502 $a Thesis (Ph.D.)--Princeton University, 2023.
506 $a This item must not be sold to any third party vendors.
520 $a This thesis makes fundamental contributions to a few statistical inference tasks on networks, with a focus on information-theoretic characterizations. In the first part of this thesis, we study the problem of localizing a network cascade from noisy, real-time measurements of its spread (i.e., through error-prone diagnostic tests). Our objective is to design algorithms that can estimate the cascade source as fast as possible, so that the impact of the cascade on the network can be mitigated. We design estimation procedures from Bayesian and minimax perspectives. In the Bayesian setting, we propose an estimator which observes samples until the error of the Bayes-optimal estimator falls below a threshold. In the minimax setting, we devise a novel multihypothesis sequential probability ratio test (MSPRT) for source estimation. When estimating simple cascades in trees and lattices, we show that both methods are optimal, in the sense that no other algorithm can accurately estimate the source with a substantially smaller number of samples. Finally, we discuss how our methods may be extended to estimate realistic cascades in generic networks.In the second part of this thesis, we study graph matching and community recovery in networks with correlated structure. First, we derive the precise information-theoretic threshold for fully recovering the latent vertex correspondence between two edge-correlated stochastic block models – a task known as exact graph matching. We then characterize the information-theoretic landscape of community recovery in correlated stochastic block models, which requires a delicate interplay between graph matching and community recovery algorithms. In particular, we uncover and characterize a region of the parameter space where exact community recovery is possible using multiple correlated graphs, even though (1) this is information-theoretically impossible using a single graph and (2) exact graph matching is also information-theoretically impossible. In this regime, we develop a novel algorithm that carefully synthesizes community recovery and graph matching algorithms.
590 $a School code: 0181.
650 4 $a Statistics. $3 182057
650 4 $a Applied mathematics. $3 377601
650 4 $a Electrical engineering. $3 454503
653 $a Community recovery
653 $a Graph matching
653 $a Hypothesis testing
653 $a Network cascades
653 $a Stochastic block model
653 $a Susceptible-infected process
690 $a 0463
690 $a 0364
690 $a 0544
710 2 $a Princeton University. $b Electrical and Computer Engineering. $3 966858
773 0 $t Dissertations Abstracts International $g 84-12B.
790 $a 0181
791 $a Ph.D.
792 $a 2023
793 $a English
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=30492319