Community-based diffusion scheme using Markov chain and spectral clustering for mobile social networks

Jegwang Ryu, Jiho Park, Junyeop Lee, Sung Bong Yang

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)


With the increase in the number of mobile devices such as tablets and smart watches, mobile social networks (MSNs) provide great opportunities for people to exchange information. As a result, information diffusion has become a critical issue in the emerging MSNs. In this paper, we address the problem of finding the top-k influential users who can effectively spread information in a network, which is referred to as the diffusion minimization problem. In order to minimize the spreading period, we can utilize the k-center problem, but which has a time complexity of NP-hard. We propose a community-based diffusion scheme using Markov chain and spectral clustering (CDMS) to minimize the spreading time by adopting a community concept based on the geographic regularity of human mobility in the MSNs. We exploit the Markov chain to predict a node’s mobility patterns and cluster the predicted patterns using the spectral graph theory. Finally, we select the top-k influential nodes in each community. Simulations are performed using the NS-2, based on the home-cell community-based mobility model, to show that the proposed scheme results in MSNs. In addition, we demonstrate that CDMS outperforms the noncommunity-based algorithms in terms of the number of nodes and ratio of k influential nodes.

Original languageEnglish
Pages (from-to)875-887
Number of pages13
JournalWireless Networks
Issue number2
Publication statusPublished - 2019 Feb 15

Bibliographical note

Funding Information:
Acknowledgements This research was supported by the Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education, Science, and Technology (2016R1A2B4010142).

Publisher Copyright:
© 2017, Springer Science+Business Media, LLC.

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Computer Networks and Communications
  • Electrical and Electronic Engineering


Dive into the research topics of 'Community-based diffusion scheme using Markov chain and spectral clustering for mobile social networks'. Together they form a unique fingerprint.

Cite this