Optimization on Content Spread in Social Network Studies

Li, Yi; Yan, Ruidong; Wu, Weili

With the rapid growth of online social networks, people change the way of generating, sharing, and spreading various social contents. The contagiousness of social content is highly depending on the size of of seed nodes and connectivity of the network. In this study, we propose the optimization problems of information content diffusion over social networks. The content here can be either useful information such as news, innovation ideas, and marketing purpose content or negative content such as misinformation and malicious rumors. We show that the optimization problem on information diffusion has been discussed in previous researches from different aspects using different approaches. In our study, we formulate two optimization problems—content spread maximization and misinformation minimization—which are both NP-hard and non-submodular. To tackle the difficulty of these problems we sandwich approximation which has data-dependent guarantees.