A graph whose edges are associated with a probability that indicates the likelihood of their existence is called uncertain. Such structures are prevalent in various applications, e.g., biology, social networks, and security. Due to their probabilistic nature, there are exponentially many potential worlds associated with it. The processing of a query mandates the materialization of all potential worlds, which is expensive even for moderately sized graphs. In this thesis, we tackle the following problems: (i) uncertain graph sparsification and (ii) collective influence maximization with multiple competing products. For the sparsification, we design a refining algorithm, inspired by game theory. This algorithm takes as input a user-tailored graph and refines it by minimizing the sp...[ Read more ]

A graph whose edges are associated with a probability that indicates the likelihood of their existence is called uncertain. Such structures are prevalent in various applications, e.g., biology, social networks, and security. Due to their probabilistic nature, there are exponentially many potential worlds associated with it. The processing of a query mandates the materialization of all potential worlds, which is expensive even for moderately sized graphs. In this thesis, we tackle the following problems: (i) uncertain graph sparsification and (ii) collective influence maximization with multiple competing products. For the sparsification, we design a refining algorithm, inspired by game theory. This algorithm takes as input a user-tailored graph and refines it by minimizing the sparsification-induced error. For the influence maximization problem we introduce an Awareness-to-Influence (ATI) model and show that it exhibits monotonicity and submodularity; Additionally, we propose GCW, a game-theoretic framework that computes the seed sets for each competitor, which is a monotone utility game. This allows us to develop an efficient best-response algorithm, with quality guarantees on the collective utility. Our experiments suggest that our methods are effective, efficient, and scale well to large graphs.