A New Algorithm for Positive Influence Dominating Set in Social Networks

摘要

Positive Influence Dominating Set (PIDS) has applications in Online Social Networks (OSN) such as Viral Marketing and College Drinking Problem. To many reasons finding Minimum PIDS (MPIDS) is very desirable. Beside, one of the most important features that distinguish the graph of OSN from other networks is Power-Law degree distribution. Unfortunately computing MPIDS in Power-Law graph is a NP-Complete problem. Recently, one greedy algorithm has been proposed in the literature for the PIDS problem with time complexity of O(n^3). In this paper, we propose a new greedy algorithm for PIDS which has outstanding time complexity of O(n^2). Theoretical analysis and simulation results are also presented to verify our approach's efficiency. The simulation results reveal that compared to other algorithm, our algorithm efficiently reduces the PIDS size.