Influence Maximization Problem In Social Network Based On Coalition Partition

With the rapid development of mobile Internet technology,online social network platforms emerge changes people's daily lives.People use online social network platforms to share information and communicate with each other.The powerful information dissemination function of the social network platform makes it an important channel for advertising and corporate marketing.The study of the influence maximization on social networks has a great significance for advertising,marketing and other aspects.The influence maximization problem refers to the selection of a small number of seed users from social networks,so that through the transmission of information from these seed users,as many users as possible are affected throughout the network.From the perspective of computational complexity,influence maximization problem is a NP-hard problem.Many researchers propose heuristic methods to solve influence maximization problem based on the relationship between nodes and edges.However,a network is not only a structure composed of nodes and nodes,but also a structure of different strategies adopted by individuals according to their own gains.The method first selects rational nodes to form coalition that maximizes benefits to individual members.Based on cooperative game theory a new heuristic method of coalition partitioning,and the well-known notion of Shapley value,we obtain a coalition structure of the network.A method of influence maximization based on Shapley value is proposed.The algorithm can effectively shorten the scope and reduce running time.In the process of coalition formation,Shapley value only considers the interests of the coalition participants(node),and neglects the influence of participants in the other coalitions(externality),which impacts the result of coalition division.In order to determine whether or not the new participant will join the coalition,we use Consensus value to calculate the contribution of the new participant to the coalition as well as the impact of the new participant on the other participants.The new participant is allowed to join the coalition only if the gain of the new participant is increased after the new participant joins the coalition and the gain of other participants increases.Therefore,in the Consensus-value based method the externality of the coalition is taken into account,and make up for the shortage of Shapley value in the division of coalition.In this thesis,our proposed method for the influence maximization problem consists of three stages: Firstly,the method computes a grouping of nodes in the network;this is obtained via simulating a cooperative game.The coalition formation process was computed using two solution concepts,Shapley value and Consensus value.Secondly,the method selects the most influential coalition by calculating the overall return of each coalition.Finally,the method determines the seed set by searching for the most influential participants in each coalition,and the solution to the problem of maximizing influence is obtained.The advantage of the influence maximization method based on the division of coalitions is that it builds a bridge between social networks and coalitions,which not only calculates the influential nodes,but also computes the coalitions of influence.The work of this thesis mainly includes the following three aspects:(1)A method of influence maximization based on Shapley value is proposed.In order to improve the time efficiency of influence maximization,this paper first introduces the idea of coalition in a social network,and designs an influence maximization algorithm based on Shapley value.In this method,the classical Shapley value formula is improved from the point of view of social network.The improved Shapley value formula is used to divide the social network into coalitions.Secondly,a method based on the profit ratio of each coalition is proposed to select the candidate coalition.Finally,MaxDegree algorithm is used to find the seed node set in the candidate coalition,which aims to find the seed node set in different coalitions to avoid the influence of information overlap on the spread range in the social network.(2)A method of influence maximization based on Consensus value is proposed.In the process of forming the Shapley value coalition,the influence of the participant on the other participants is ignored,which will affect the result of the coalition division.The result is that the value of influence is not accurate.Consensus value fully considers the externality of the coalition,so this paper proposes a method of influence maximization based on Consensus value.This method firstly induces Consensus value in economics and deduces the Consensus value formula which is simple and easy to understand.Then,according to the formula,we divide the coalition-select the candidate coalition-find the seed node set.(3)Experimental verificationIn this thesis,the experimental results are analyzed in terms of the influence propagation value and the running time,and the influence maximization method based on coalition partition,the method based on non-coalition partition and the traditional classical algorithm are compared.Through experiments,different complex network models such as ER stochastic model,scale-free network model,and small-world network model and real network dataset were simulated respectively,which verified the feasibility of the Shapley value and Consensus value method based on coalition partition.Tests from the effects of influence propagation value indicate: the influence propagation value of influence maximization method based on coalition partition is superior to other heuristic algorithms;the Consensus value method is better than the Shapley value method;the influence of Consensus value method is closer to the greedy algorithm.Then the paper analyzes the experiment from the aspects of the running time.The experiment shows that influence maximization method based on coalition partition is faster than the greedy algorithm.