ORIGINAL ARTICLE Positive influence dominating sets in power-law graphs

Dominating Set (PIDS) is a problem arisen from the social network applications. The problem has been studied on general random graphs. However, the social networks is presented more precisely by power-law graphs. One of the most important properties of social networks is the power-law degree distribution. In this paper, we focus on the PIDS problem in power-law graphs and prove that the greedy algorithm has a constant approximation ratio. Simulation results also demonstrate that greedy algorithm can effec-tively select a small scale PIDS set