Optimization Problems in Social Networks




Journal Title

Journal ISSN

Volume Title




Social networks have become the dominant platform for daily communication, social activities and viral marketing. The past years have witnessed a drastic increase in the population of social network users. One one hand, we aim at fully taking the advantage of social networks such that, for example, the effect of the online advertising can be maximized or the expectation of the users can be satisfied. On the other hand, negative impact resulted by social networks should be constrained. For example, to limit the spread of misinformation or to protect the privacy of online users. In this dissertation, we study the problems emerging from modern online social systems, from the view of information diffusion. Based on different information diffusion models, we study several problems regarding viral marketing, online friending, rumor blocking, etc. We formulate the considered problems as optimization problems and design solutions with performance guarantees. As the considered problems are all NP-hard, we focus on the analysis of approximation result. Another challenge comes from the high scale of real social network and the #P-hard nature of computing information influence. In order to provide efficient algorithms with respect to running time, we adopt effective sampling techniques to improve the efficiency of the solutions.



Online social networks, Mathematical optimization, Online algorithms, Information networks