자료유형  

 학위논문

Control Number  

0016932414

International Standard Book Number  

9798379719210

Dewey Decimal Classification Number  

310

Main Entry-Personal Name  

Sridhar, Anirudh.

Publication, Distribution, etc. (Imprint  

[S.l.] : Princeton University., 2023

Publication, Distribution, etc. (Imprint  

Ann Arbor : ProQuest Dissertations & Theses, 2023

Physical Description  

1 online resource(239 p.)

General Note  

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

General Note  

Advisor: Poor, H. Vincent;Racz, Miklos Z.

Dissertation Note  

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

Restrictions on Access Note  

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

Summary, Etc.  

요약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.

Subject Added Entry-Topical Term  

Statistics.

Subject Added Entry-Topical Term  

Applied mathematics.

Subject Added Entry-Topical Term  

Electrical engineering.

Index Term-Uncontrolled  

Community recovery

Index Term-Uncontrolled  

Graph matching

Index Term-Uncontrolled  

Hypothesis testing

Index Term-Uncontrolled  

Network cascades

Index Term-Uncontrolled  

Stochastic block model

Index Term-Uncontrolled  

Susceptible-infected process

Added Entry-Corporate Name  

Princeton University Electrical and Computer Engineering

Host Item Entry  

Dissertations Abstracts International. 84-12B.

Host Item Entry  

Dissertation Abstract International

Electronic Location and Access  

로그인을 한후 보실 수 있는 자료입니다.

Control Number  

joongbu:639846