On the approximability of positive influence dominating set in social networks

In social networks, there is a tendency for connected users to match each other's behaviors. Moreover, a user likely adopts a behavior, if a certain fraction of his family and friends follows that behavior. Identifying people who have the most influential effect to the others is of great advantages, especially in politics, marketing, behavior correction, and so on. Under a graph-theoretical framework, we study the positive influence dominating set (PIDS) problem that seeks for a minimal set of nodes such that all other nodes in the network have at least a fraction rho > 0 of their neighbors in . We also study a different formulation, called total positive influence dominating set (TPIDS), in which even nodes in are required to have a fraction rho of neighbors inside . We show that neither of these problems can be approximated within a factor of (1-I mu)lnmax{Delta,|V|(1/2)}, where Delta is the maximum degree. Moreover, we provide a simple proof that both problems can be approximated within a factor ln Delta+O(1). In power-law networks, where the degree sequence follows a power-law distribution, both problems admit constant factor approximation algorithms. Finally, we present a linear-time exact algorithms for trees.