國立虎尾科技大學 |

Inference of Cascades and Correlated Networks.

紀錄類型:	書目-語言資料,手稿 : Monograph/item
正題名/作者:	Inference of Cascades and Correlated Networks./
作者:	Sridhar, Anirudh.
面頁冊數:	1 online resource (239 pages)
附註:	Source: Dissertations Abstracts International, Volume: 84-12, Section: B.
Contained By:	Dissertations Abstracts International84-12B.
標題:	Statistics. -
電子資源:	click for full text (PQDT)
ISBN:	9798379719210

Inference of Cascades and Correlated Networks.
Sridhar, Anirudh.

Inference of Cascades and Correlated Networks. - 1 online resource (239 pages)

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

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

Includes bibliographical references

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.

Electronic reproduction.
Ann Arbor, Mich. :
ProQuest,
2024

Mode of access: World Wide Web

ISBN: 9798379719210Subjects--Topical Terms:

556824
Statistics.
Subjects--Index Terms:

Community recoveryIndex Terms--Genre/Form:

554714
Electronic books.

Inference of Cascades and Correlated Networks.
LDR:03535ntm a22004097 4500 001 1142038
005 20240414211928.5
006 m o d
007 cr mn ---uuuuu
008 250605s2023 xx obm 000 0 eng d
020 $a 9798379719210
035 $a (MiAaPQ)AAI30492319
035 $a AAI30492319
040 $a MiAaPQ $b eng $c MiAaPQ $d NTU
100 1 $a Sridhar, Anirudh. $e editor. $3 1359306
245 1 0 $a Inference of Cascades and Correlated Networks.
264 0 $c 2023
300 $a 1 online resource (239 pages)
336 $a text $b txt $2 rdacontent
337 $a computer $b c $2 rdamedia
338 $a online resource $b cr $2 rdacarrier
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.
504 $a Includes bibliographical references
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.
533 $a Electronic reproduction. $b Ann Arbor, Mich. : $c ProQuest, $d 2024
538 $a Mode of access: World Wide Web
650 4 $a Statistics. $3 556824
650 4 $a Applied mathematics. $3 1069907
650 4 $a Electrical engineering. $3 596380
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
655 7 $a Electronic books. $2 local $3 554714
690 $a 0463
690 $a 0364
690 $a 0544
710 2 $a ProQuest Information and Learning Co. $3 1178819
710 2 $a Princeton University. $b Electrical and Computer Engineering. $3 1413580
773 0 $t Dissertations Abstracts International $g 84-12B.
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=30492319 $z click for full text (PQDT)