Study Of Influence Maximization In Social Networks Based On Swarm Intelligence Optimization

The past few years have witnessed the flourishing development of various online social platforms which are now becoming the most popular media for information sharing and spreading. These online social media often cost little and bring tremendous benefits to the enterprises and shops, thus causing a new wave of using social media to promote products and services.Influence maximization(IM) is a concept used to select influential groups which will be used as information sources to maximize the information spread in social networks. It is the core problem concerning information spread in the social networks. Its applications in various scenarios, such as advertising, marketing, water quality monitoring and public voice control, demonstrate great research value and social significance.Influence maximization is mostly subject to the accuracy and efficiency in selecting node sets. The priority of solving the influence maximization problem is to efficiently dig out the target node sets from the social networks.Among the algorithms currently used, the greedy algorithm features high accuracy yet fails to solve the influence maximization in large-scale social networks for its unsatisfactory efficiency. Some algorithms for heuristic purposes, by contrast, may bring adequate efficiency but themselves are usually of regrettable inaccuracy and poor stability.To solve the problem mentioned above, the thesis studies influence maximization problem in this paper in the following aspects:It is a sharp-P hard problem to compute the influence spreading range which is conventionally obtained by Monte Carlo simulations that entails high computational complexity.The sharp-P hard problem is no less complex than the NP-hard problem. A very different solution comes from this thesis. In this thesis, a local influence estimation function is put forward to compute the approximate influence spreading range in the independent cascade model and weighted cascade model based on the analysis of influence spread in the social networks. Besides, influence maximization problem is modeled as optimization problem based on target function. And a new algorithm based on discrete particle swarm optimization(DPSO) is put forward to solve this problem. For the suggested algorithm, a degree based initialization method and a neighbor based local search operator are designed, thereby accelerating the algorithm convergence and enhancing the algorithm efficiency.Conventionally, the cost of node selection is neglected in solving the influence maximization problem. By introducing the concept of selected cost into IM, this paper comes up with a new influence maximization model: budgeted influence maximization(BIM). To maximize the influence in the social networks with relatively little cost, the BIM problem is seen as a multi-objective optimization problem and solved by a novel evolutionary multi-objective optimization algorithm(MOEA). As shown from the experiments, the seed sets selected by the MOEA algorithm preserves the maximum influence range and costs little.