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