This thesis can be viewed as a scientific investigation of the ''network centralities as statistical inference'' approach to inferential statistical analysis. The idea is that network centralities induce a metric on each graph node, and an appropriate design of a network centrality has a statistical basis. Therefore, it can accurately capture the optimality of stochastic problems studied in this thesis and bring graph algorithm machinery to bear on solving the stochastic program. Moreover, this approach demonstrates a novel way to prove optimality guarantees to stochastic optimization problems in inferential statistics by transforming them into graph-theoretic problems, which can be efficiently solved by graph algorithms.

In particular, we consider two statistical inference problems: minimizing the outage when a cascading failure from a single source occurs and finding the rumor source in a social network. These two research topics find timely applications in modern networks like smart grid and online social networks.

For the first research topic, we formulate the problem of minimizing the outage when a cascading failure from a single source occurs as a stochastic optimization problem. We leverage the idea of a classic network centrality called centroid to develop a new network centrality called vaccine centrality to solve this stochastic optimization problem. We give a linear-time algorithm for calculating vaccine centrality, showing its feasibility for large networks. Vaccine centrality is proven to be a feasible solution with a performance guarantee for tree graphs.

For the second research topic, we investigate the problem of finding the rumor source in a social network. We extend the analysis to bounded graphs and graphs with cycles. We show that the graph boundary and cycles have a similar effect on the vertex likelihood of being the rumor source. For the particular case of regular graphs with a single cycle or a single vertex on the graph boundary, we characterize the optimal rumor source estimator. For general bounded regular graphs, we propose a new distance-based network centrality called statistical distance centrality to solve the rumor source finding problem. Simulation results show that the statistical distance center outperforms the source estimator in the literature.