Influence maximization in social networks: an integer programming approach

Abstract

The use of social networks has been spreading rapidly in recent years. There is a growing interest in influencemaximization in social networks, especially after observing that the effects of social events of the Arab Spring, Gezi eventsof Turkey, uprising in Ukraine, etc. have been built by the help of social networks. Consequently, many institutionslike political parties or commercial firms are willing to spread their messages throughout social networks. There aremany studies that concentrate on finding the most influential initial nodes, called seeds, which maximize the spreadof an intended message over the social network. However, most of these works provide numeric algorithmic methodswithout including an integer program that seeks for a theoretical optimal point. Integer programs, on the other hand,are provided in very few studies, and they mostly assume an independent cascade model, which is a diffusion modeldepending on probabilistic affection rates, to formulate the diffusion in the network. In this study, we first provide abasic integer program that works under a linear threshold model, which is a diffusion model assuming threshold affectionlevels, and extend it for the situation in which there is a competing opinion (like black propaganda for a product, anevent, or an opinion). Finally, we provide heuristic solution procedures and efficiency analysis with extensive numericalinstances