Paper Info
Title
Information diffusion in mobile social networks: The speed perspective
Abstract
The emerging of mobile social networks opens opportunities for viral marketing. However, before fully utilizing mobile social networks as a platform for viral marketing, many challenges have to be addressed. In this paper, we address the problem of identifying a small number of individuals through whom the information can be diffused to the network as soon as possible, referred to as the diffusion minimization problem. Diffusion minimization under the probabilistic diffusion model can be formulated as an asymmetric k-center problem which is NP-hard, and the best known approximation algorithm for the asymmetric k-center problem has approximation ratio of log* n and time complexity O(n5). Clearly, the performance and the time complexity of the approximation algorithm are not satisfiable in large-scale mobile social networks. To deal with this problem, we propose a community based algorithm and a distributed set-cover algorithm. The performance of the proposed algorithms is evaluated by extensive experiments on both synthetic networks and a real trace. The results show that the community based algorithm has the best performance in both synthetic networks and the real trace, and the distributed setcover algorithm outperforms the approximation algorithm in the real trace in terms of diffusion time.
Year
DOI
Venue
2014
10.1109/INFOCOM.2014.6848133
INFOCOM
Keywords
DocType
ISSN
time complexity,approximation theory,NP-hard problem,mobile social networks,approximation algorithm,computational complexity,asymmetric k-center problem,marketing,information diffusion,viral marketing,social networking (online),mobile computing,probabilistic diffusion model
Conference
0743-166X
Citations 
PageRank 
References 
24
0.86
20
Authors
3
Name
Order
Citations
PageRank
Zongqing Lu120926.18
Yonggang Wen22512156.47
Guohong Cao36690326.81