Language:
English
繁體中文
Help
回圖書館首頁
手機版館藏查詢
Login
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
based on 0 review(s)
Location:
ALL
電子資源
Year:
Volume Number:
Items
1 records • Pages 1 •
1
Inventory Number
Location Name
Item Class
Material type
Call number
Usage Class
Loan Status
No. of reservations
Opac note
Attachments
W9502262
電子資源
11.線上閱覽_V
電子書
EB
一般使用(Normal)
On shelf
0
1 records • Pages 1 •
1
Multimedia
Reviews
Add a review
and share your thoughts with other readers
Export
pickup library
Processing
...
Change password
Login