Introduction of Influence Maximization in Mobile Social Network

            Mobile social network systems, with the wireless technologies and the proliferation of mobile devices, are increasingly available. An essential role is being played by the mobile social network in influence in the “word of mouth” form and spread of information. Finding a subset of influential individuals is a fundamental issue in the mobile social network such that initially targeting them will contribute towards maximizing the spread of influence. Influence maximization in mobile social network aims to look for the small individuals’ group having maximal influence cascades. Precisely, influence maximization is itself a problem of a small subset of nodes' finding in a social network that is able to maximize a spread of influence. Unfortunately, the problem is NP-hard of finding the most influential nodes (Song, Zhou, Wang, & Xie, 2015).

        It has been shown that good approximation can be given by a Greedy algorithm having provable approximation guarantees; however, if it is not prohibitive then it is computationally expensive to implement a greedy algorithm on the large mobile social network (Bhosale & Kulkarni, 2015). This study has adopted the divide and conquer strategy with mechanisms that are parallel computing. First, an algorithm is proposed called Community-based Greedy algorithm so that top-K influential nodes could be mined. Two components are encompassed; selecting communities to so that influential nodes could be found by a dynamic programming and taking into account information to divide large mobile social networks into various communities. For further performance improvement, influence propagation is parallelized based on communities. Moreover, a precision analysis is given in this study to show the approximation guaranteed of proposed models.