Skip navigation
Please use this identifier to cite or link to this item:
Title: Inference of Cascades and Correlated Networks
Authors: Sridhar, Anirudh
Advisors: PoorRácz, VincentMiklós Z
Contributors: Electrical and Computer Engineering Department
Keywords: community recovery
graph matching
hypothesis testing
Network cascades
stochastic block model
susceptible-infected process
Subjects: Statistics
Applied mathematics
Issue Date: 2023
Publisher: Princeton, NJ : Princeton University
Abstract: 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 multi-hypothesis 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.
Type of Material: Academic dissertations (Ph.D.)
Language: en
Appears in Collections:Electrical Engineering

Files in This Item:
File Description SizeFormat 
Sridhar_princeton_0181D_14629.pdf3.25 MBAdobe PDFView/Download

Items in Dataspace are protected by copyright, with all rights reserved, unless otherwise indicated.