Towards Information Diffusion in Mobile Social Networks

Zongqing Lu, Yonggang Wen, Weizhan Zhang, Qinghua Zheng, Guohong Cao

Research output: Contribution to journalArticlepeer-review

40 Scopus citations


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 logn 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 compared to existing algorithms, and the distributed set-cover algorithm outperforms the approximation algorithm in the real trace in terms of diffusion time.

Original languageEnglish (US)
Article number7145444
Pages (from-to)1292-1304
Number of pages13
JournalIEEE Transactions on Mobile Computing
Issue number5
StatePublished - May 1 2016

All Science Journal Classification (ASJC) codes

  • Software
  • Computer Networks and Communications
  • Electrical and Electronic Engineering


Dive into the research topics of 'Towards Information Diffusion in Mobile Social Networks'. Together they form a unique fingerprint.

Cite this