Influence diffusion: A consolidated survey, a unifying transformation, and the greedy algorithm's demonstration of force

Date created: 
2020-08-10
Identifier: 
etd21076
Keywords: 
Influence Diffusion
Networks
Graphs
Submodularity
Greedy Algorithms
Theoretical Computer Science
Abstract: 

Influence diffusion concerns the propagation of an entity throughout a network. The naming alludes to the application that motivated the study of this process: the influence that social network users have on each other's opinions. Influence diffusion has a plethora of applications in the real world, ranging from marketing campaigns, to the spread of fake news, to reinforcement learning. In this work, we provide a broad survey of the models proposed for this process in the relevant literature. We consolidate this survey of models by providing missing pieces, i.e. proofs and new models. We show intuitive connections between the introduced models, a unifying transformation between two fundamentally different models, and finally, we show the remarkable performance of the greedy algorithm in a subfield of influence diffusion that has been receiving increasing attention recently, adaptive influence diffusion.

Document type: 
Thesis
Rights: 
This thesis may be printed or downloaded for non-commercial research and scholarly purposes. Copyright remains with the author.
File(s): 
Supervisor(s): 
Joseph Peters
Department: 
Applied Sciences: School of Computing Science
Thesis type: 
(Thesis) M.Sc.
Statistics: