Algorithms for Emerging Networked Applications

Graph data structures represent one of the most widely adopted solution to model and process datasets arising in real-world networked information systems, such as, e.g., social networks, web search engines, software for biological analytics, distributed systems and transportation infrastructures. In the last two decades, the traditional notion of efficiency for computational methods for graphs has been challenged by the advent of so-called Big Data, i.e. datasets of massive size. In fact, while several efficient, polynomial-time algorithms have been developed in the last decades for most computational problems defined on graphs, such known graph algorithms have been often shown to perform poorly when applied to massive graphs, i.e. graphs with millions of vertices and edges, which have become more and more frequent in practical application domains. For this reason, a great deal of research has been done recently with the goal of designing and analyzing both theoretically and experimentally new algorithms that show superior scalability compared to state-of-the-art methodologies for a wide range of computational problems with significant practical impact. The content of this thesis lies in the aforementioned research field and consists of two major contributions. First, we design approximation and heuristic algorithms for the digraph k-coloring game problem and provide extensive experimental evaluations of such methods over synthetic and real-world inputs, to establish which is the most suited framework to address the problem in practice; interestingly, we show that algorithms with theoretical guarantees perform poorly in practice, while our newly introduced heuristic, based on classical best-response dynamics, converges to best solutions in most of the tested instances. Second, we study the k-shortest paths problem in massive, time-evolving graphs, i.e. in those scenarios where the graph topology can change over time. We design and analyze two dynamic algorithms to maintain, in such scenarios, the k-2-hop-cover data structure, the state-of-the-art data structure for supporting fast retrieval of k-shortest paths at scale. We present the results of a thorough experimental analysis to assess the practical effectiveness of our framework.