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

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.