Pandurangan, Gopal2019-12-17December 22019-12December 2https://hdl.handle.net/10657/5571Network-related problems span over many areas in computer science. In this dissertation, we investigate two problems, one is in the domain of distributed computing, and the other is in the domain of graph mining. We approach these problems by probabilistic tools, to model, analyze, and design algorithms. In the first problem, we aim to improve upon the known bounds of some fundamental distributed algorithms, Minimum Spanning Tree (MST) in particular. We propose the Smoothed Analysis, where the key is to randomly and slightly alter the input, and show new asymptotic bounds. For the MST problem, we also design an algorithm that almost matches the lower bound. In the second problem, we study influence spreading in networks, which is a stochastic process. We propose a new optimization problem: minimizing the seed set with probabilistic guarantees on the influence. This problem relates to non-submodular target functions, and is hard even for an approximation solution. We design an efficient algorithm using relaxed multi-criterial approximation and Monte Carlo sampling. We provide theoretically proven properties and supportive empirical results.application/pdfengThe author of this work is the copyright owner. UH Libraries and the Texas Digital Library have their permission to store and provide access to this work. Further transmission, reproduction, or presentation of this work is prohibited except with permission of the author(s).Distributed computingSmoothed analysisInfluence maximizationOptimization2019-12-17Thesisborn digital