Diffusion Minimization on Specific Targets in Social Networks

  • 呂 鴻

Student thesis: Master's Thesis


In recent years people have begun utilizing social networks as a platform for receiving or propagating information because it’s flourishing Numerous shops want to promote their products or activities through social networks via viral marketing Therefore in previous studies lots of research of Influence Maximization is to focus on how to find effective salesmen in social networks and try to sell products or activities for marketing through these men However we find those problems of selecting effective salesmen will ignore that people have preferences on the information and also have time-sensitive issues Therefore in this paper we address the problem of identifying a small number of individuals through whom the information can be diffused to the specific targets as soon as possible referred to as the diffusion minimization on specific targets problem (DM-ST) We formally define the DM-ST problem and show that it is NP-hard In order to solve this problem we proposed diffusion cascade model and label-based propagation probabilistic model to simulate real world diffusion behavior and information propagation probability And proposed two algorithms: Baseline algorithm and LDT algorithm The former use greedy-based way to find the approximate solution by spending less time The latter is more efficient algorithm; by creating LDT and two pruning mechanisms such that reducing the search space and accelerating the execution time Finally extensive experiments are proposed to evaluate the efficiency of each algorithm and the result show that our algorithms have better performance
Date of Award2016 Aug 11
Original languageEnglish
SupervisorChiang Lee (Supervisor)

Cite this