Information diffusion in mobile social networks: The speed perspective

Zongqing Lu, Yonggang Wen, Guohong Cao

Research output: Chapter in Book/Report/Conference proceedingConference contribution

52 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 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.

Original languageEnglish (US)
Title of host publicationIEEE INFOCOM 2014 - IEEE Conference on Computer Communications
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages9
ISBN (Print)9781479933600
StatePublished - 2014
Event33rd IEEE Conference on Computer Communications, IEEE INFOCOM 2014 - Toronto, ON, Canada
Duration: Apr 27 2014May 2 2014

Publication series

NameProceedings - IEEE INFOCOM
ISSN (Print)0743-166X


Other33rd IEEE Conference on Computer Communications, IEEE INFOCOM 2014
CityToronto, ON

All Science Journal Classification (ASJC) codes

  • General Computer Science
  • Electrical and Electronic Engineering


Dive into the research topics of 'Information diffusion in mobile social networks: The speed perspective'. Together they form a unique fingerprint.

Cite this