A study of social networks: an Lp norm relaxation approach

Abstract

In this thesis, an Influence Maximization problem in Social Network under the Deterministic Linear Threshold model and Discovering Efficient Sets of Key Players in Directed Weighted Social Networks are considered. In the first problem, the objective is to minimize the number of eventually negatively opinionated nodes in the network in a dynamic setting. The main ingredient of the new approach is the application of the sparse optimization technique. In the presence of inequality constraints and nonlinear relationships, the standard convex relaxation method of the L1 relaxation does not perform well in this context. Therefore we propose to apply the Lp relaxation where 0<p<1. The resulting optimization model is therefore non-convex. By means of an interior point method, the model can be solved efficiently and stably, typically yielding robust and sparse solutions in our numerical experiments with the simulated data. In the latter problem, the objective is to find the seed sets to maximize the influence subject to the constraint of budget only in the first stage. There has been a lot of different approaches to this problem. However, those approaches are all mostly specifically based on graph theory. In the era of big data, much information may be known such as the initial state and the threshold of the individuals in the social network by data mining and statistics. Algorithm design taking into account such factors considered is a new challenge. This thesis shows that the Lp norm relaxation is a promising approach to tackle this problem.