Online social network has developed significantly in recent years. Most of current research has utilized the property of online social network to spread information and ideas. Motivated by applications in social networks (such as alcohol intervention strategies), a variation of the dominating set called a positive influence dominating set (PIDS) has been studied in the literature. However, the existing work all focused on greedy algorithms for the PIDS problem with different approximation ratios, which are limited to find approximate solutions to PIDS in large networks. In order to select a minimal PIDS (MPIDS) in large social networks, we first present a self-stabilizing algorithm for the MPIDS problem in this paper, which can find a MPIDS in an arbitrary network graph without any isolated node. It is assumed that the nodes in the proposed algorithm have globally unique identifiers, and the algorithm works under a central daemon. We further prove that the worst case convergence time of the algorithm from any arbitrary initial state is O(n2) steps where n is the number of nodes in the network.
|Cite as: Wang, G., Wang, H., Tao, X. and Zhang, J. (2013). A Self-Stabilizing Algorithm for Finding a Minimal Positive Influence Dominating Set in Social Networks. In Proc. Database Technologies 2013 (ADC 2013) Adelaide, Australia. CRPIT, 137. Wang, H. and Zhang, R. Eds., ACS. 93-100 |
(local if available)