UC Santa Barbara

Networks (or graphs) are a powerful tool to model complex systems such as social networks, transportation networks, and the Web. Network design problems, including planning, implementing and augmenting networks for desirable properties, arise naturally in many applications: How to improve commute time in traffic network? How to contain fake news in social networks? How to preserve a species by conserving important properties of an ecosystem? How to promote healthier behaviour among individuals via their social interactions? However, characterizing the combinatorial effect of these network modifications leads to challenging optimization problems. From a theoretical standpoint, different from their search counterparts (e.g. computing shortest path), the design problems (e.g. optimizing shortest paths) are computationally hard.

My thesis focuses on the development of algorithms for solving large-scale real-world problems using network design. In this thesis, I will discuss a few network design problems and their solutions. In the first part, I will describe design problems to optimize structural properties of a network. More specifically, I will focus on shortest path distance optimization and improvement of node centrality. In the second part, I will show how network design can be used in security related applications via leader hiding problem. Lastly, network modification will be used to improve or control network processes. In particular I will describe influence minimization and resilience maximization in networks via making optimal changes. I will present fast algorithms for these problems using continuous optimization, randomized algorithms and game theoretic techniques.