Probabilistic Models and Algorithmic Analysis of Network Problems

Network-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.Computer Science, Department o