東華大學圖書館 |

Language: English

Help

回圖書館首頁

手機版館藏查詢

Back

Switch To: Labeled | MARC Mode | ISBD

Inference of Cascades and Correlated...

Sridhar, Anirudh.

Linked to FindBook

Google Book

Amazon

博客來

Inference of Cascades and Correlated Networks.

Record Type:	Electronic resources : Monograph/item
Title/Author:	Inference of Cascades and Correlated Networks./
Author:	Sridhar, Anirudh.
Published:	Ann Arbor : ProQuest Dissertations & Theses, : 2023,
Description:	239 p.
Notes:	Source: Dissertations Abstracts International, Volume: 84-12, Section: B.
Contained By:	Dissertations Abstracts International84-12B.
Subject:	Statistics. -
Online resource:	https://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.{A0}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:

517247
Statistics.
Subjects--Index Terms:

Community recovery

Inference of Cascades and Correlated Networks.
LDR:03384nmm a2200409 4500 001 2393942
005 20240414211928.5
006 m o d
007 cr#unu||||||||
008 251215s2023 ||||||||||||||||| ||eng d
020 $a 9798379719210
035 $a (MiAaPQ)AAI30492319
035 $a AAI30492319
040 $a MiAaPQ $c MiAaPQ
100 1 $a Sridhar, Anirudh. $3 3496057
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.{A0}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 517247
650 4 $a Applied mathematics. $3 2122814
650 4 $a Electrical engineering. $3 649834
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 3689367
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 https://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=30492319