서브메뉴
검색
Inference of Cascades and Correlated Networks- [electronic resource]
![Inference of Cascades and Correlated Networks - [electronic resource]](/Users/Baul/Images/book.png)
Inference of Cascades and Correlated Networks- [electronic resource]
상세정보
- 자료유형
- 학위논문파일 국외
- 최종처리일시
- 20240214100455
- ISBN
- 9798379719210
- DDC
- 310
- 서명/저자
- Inference of Cascades and Correlated Networks - [electronic resource]
- 발행사항
- [S.l.]: : Princeton University., 2023
- 발행사항
- Ann Arbor : : ProQuest Dissertations & Theses,, 2023
- 형태사항
- 1 online resource(239 p.)
- 주기사항
- Source: Dissertations Abstracts International, Volume: 84-12, Section: B.
- 주기사항
- Advisor: Poor, H. Vincent;Racz, Miklos Z.
- 학위논문주기
- 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.
- 일반주제명
- Statistics.
- 일반주제명
- Applied mathematics.
- 일반주제명
- Electrical engineering.
- 키워드
- Graph matching
- 키워드
- Network cascades
- 기타저자
- Princeton University Electrical and Computer Engineering
- 기본자료저록
- Dissertations Abstracts International. 84-12B.
- 기본자료저록
- Dissertation Abstract International
- 전자적 위치 및 접속
- 로그인 후 원문을 볼 수 있습니다.
MARC
008240612s2023 us |||||||||||||||c||eng d■001000016932414
■00520240214100455
■006m o d
■007cr#unu||||||||
■020 ▼a9798379719210
■035 ▼a(MiAaPQ)AAI30492319
■040 ▼aMiAaPQ▼cMiAaPQ
■0820 ▼a310
■1001 ▼aSridhar, Anirudh.
■24510▼aInference of Cascades and Correlated Networks▼h[electronic resource]
■260 ▼a[S.l.]:▼bPrinceton University. ▼c2023
■260 1▼aAnn Arbor :▼bProQuest Dissertations & Theses, ▼c2023
■300 ▼a1 online resource(239 p.)
■500 ▼aSource: Dissertations Abstracts International, Volume: 84-12, Section: B.
■500 ▼aAdvisor: Poor, H. Vincent;Racz, Miklos Z.
■5021 ▼aThesis (Ph.D.)--Princeton University, 2023.
■506 ▼aThis item must not be sold to any third party vendors.
■520 ▼aThis 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 ▼aSchool code: 0181.
■650 4▼aStatistics.
■650 4▼aApplied mathematics.
■650 4▼aElectrical engineering.
■653 ▼aCommunity recovery
■653 ▼aGraph matching
■653 ▼aHypothesis testing
■653 ▼aNetwork cascades
■653 ▼aStochastic block model
■653 ▼aSusceptible-infected process
■690 ▼a0463
■690 ▼a0364
■690 ▼a0544
■71020▼aPrinceton University▼bElectrical and Computer Engineering.
■7730 ▼tDissertations Abstracts International▼g84-12B.
■773 ▼tDissertation Abstract International
■790 ▼a0181
■791 ▼aPh.D.
■792 ▼a2023
■793 ▼aEnglish
■85640▼uhttp://www.riss.kr/pdu/ddodLink.do?id=T16932414▼nKERIS▼z이 자료의 원문은 한국교육학술정보원에서 제공합니다.
■980 ▼a202402▼f2024
