On Positive Influence Dominating Sets in Social Networks

In this paper, the authors investigate the Positive Influence Dominating Set (PIDS) which has applications in social networks. They prove that PIDS is APX-hard and propose a greedy algorithm with an approximation ratio of H(δ) where H is the harmonic function and δ is the maximum vertex degree of the graph representing a social network. Dominating set has been extensively studied and been adopted in many real-life applications. For example, it has been utilized in wireless networks to address media access, routing, power management, and topology control issues. Recently, studied the dominating set in social networks.