Scalable sub-graph centric distributed influence maximization

Abstract

A group of socially connected persons with specific interaction or contact patterns connected through one or more online relationships can be referred to as an online social network. People can share information and communicate with their family and friends on online social networks. A lot of focus has been placed on information diffusion as a result of the popularity of online social networks, as a piece of information could spread widely through word-of-mouth among friends in the network. This diffusion phenomenon has demonstrated use in a variety of applications. The subset of influential users in the network is determined by the influence maximization (IM) problem to offer solutions for practical issues such as outbreak detection and viral marketing. Real-world graphs have become significantly more complicated and larger in recent years. Particularly, global social networks can have up to a billion connections and hundreds of millions of users. Thus, for problems like influence maximization on social networks, even algorithms with reasonable time or space complexity encounter difficulties when working with large-scale networks. In this thesis, we look at the scalability of influence maximization algorithms on large-scale networks. To address the scalability issue with influence maximization (IM) algorithms we implemented two distributed IM algorithms. The first distributed IM method we provide is based on the Update Approximation (UA) algorithm. The distributed version of UA provides an influence spread almost near to the influence spread provided with the original UA algorithm in most of the cases along with a reduction in memory usage between 13-30% for different datasets. The other distributed algorithm we implemented is based on reverse influence sampling. We implemented a distributed version of the IMM algorithm using the existing Influence Maximization with Martingale(IMM) algorithms and parameter settings. The influence spread achieved in the case of distributed IMM is less compared to centralized IMM, but the reduction in memory usage is almost 22–25% for different datasets.