Diffusion Processes in Uncertain Graphs

MPhil Thesis Defence


Title: "Diffusion Processes in Uncertain Graphs"

By

Mr. Dimitrios TSARAS


Abstract

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 ex- ponentially 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 spar- sification, 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 er- ror. For the 
influence maximization problem we introduce an Awareness-to-Influence (ATI) 
model and show that it exhibits monotonicity and submodularity; Additionally, 
we pro- pose 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 algo- rithm, with quality guarantees on the collective 
utility. Our experiments suggest that our methods are effective, efficient, and 
scale well to large graphs.


Date:  			Monday, 24 August 2020

Time:			11:00am - 1:00pm

Zoom meeting:		https://hkust.zoom.us/j/93971890840

Committee Members:	Prof. Dimitris Papadias (Supervisor)
 			Prof. Ke Yi (Chairperson)
 			Prof. Dik-Lun Lee


**** ALL are Welcome ****