Research On Influence Maximization Problem In Social Networks

With the popularity of the Internet and the rapid development of Web2.0technology,the scale of social network is expanding.Social network has become the main platform for people to communicate with each other,disseminate information and share knowledge.The information dissemination in the network brings great convenience to the promotion of new technology and new ideas,and also has potential threats.In the process of interaction,the individuals in the network will affect the surrounding individuals,and then change the behavior and cognition of other individuals,so as to change the network topology.Therefore,influence analysis plays an important role in understanding the behavior characteristics of nodes in the network,revealing the propagation dynamics in the network and analyzing the evolution of network topology.As one of the main research contents of influence analysis,influence maximization is to select a group of influential nodes of specified size to form a seed node set in a given network with certain strategies.Under a given propagation model,the influence spread of the selected seed node set can be maximized.It is of great theoretical significance and practical application value to carry out the research on influence maximization in product promotion,advertising,rumor control,epidemic monitoring,water quality monitoring and other aspects.Traditional influence maximization algorithms are mainly based on greedy strategy and heuristic algorithm based on centrality strategy.The algorithm based on greedy strategy has high time complexity,and it is difficult to be extended to large-scale social networks.However,the heuristic algorithm based on centrality strategy has poor solution because of its own limitations.Aiming at the shortcomings of existing algorithms,based on community structure and meta-heuristic optimization algorithm,different algorithms are proposed in this study to solve the influence maximization problem in social networks by generating candidate node set.Details are as follows:(1)Aiming at the problems of high time complexity of traditional greedy algorithm and poor solution of heuristic algorithm,a hybrid influence maximization algorithm based on clique community division is proposed.Firstly,the importance of community structure in influence propagation is analyzed.After obtaining the community structure based on the clique community division method,the significant community and the method of extracting candidate nodes are defined.On this basis,the strategy of evaluating node influence based on node's neighborhood set is defined.Finally,based on the characteristics of efficient heuristic algorithm and accurate greedy algorithm,the most influential nodes are obtained from the candidate node set by combining the two methods.The experimental results on real social networks show that the hybrid influence maximization algorithm based on clique community partition has better accuracy and lower time complexity than CELF algorithm.(2)Aiming at the time-consuming problem of using a greedy strategy to select some seed nodes in the above work.The community and node propagation overlap in the structural characteristics of the network are analyzed,and an influence maximization algorithm based on the clique and influence discount of node is proposed.Firstly,the characteristics of the easier spread of node influence in cliques are analyzed.After obtaining the cliques in the network,in order to avoid overlapping influence spread,the method of clique pruning is used to obtain the candidate node set.And the method of estimating node influence by multi-hop neighborhood set and propagation probability is defined.Finally,seed nodes are selected from the candidates based on node influence estimation.At the same time,a degree discount strategy is adopted to solve the problem of poor solution caused by the aggregation of selected nodes in the network.The experimental results on the social networks show that the proposed algorithm has comparable influence spread to the CELF algorithm,and it is efficient.(3)On the basis of the previous two chapters,the feasibility and effectiveness of the meta-heuristic optimization algorithm to solve the influence maximization problem are studied,and the crow search algorithm is applied to the influence maximization problem,and the discrete crow search algorithm is proposed.Firstly,based on the discrete characteristics of the network solution space,the discrete coding mechanism and evolution mechanism of the crow individual are proposed.In addition,in order to avoid blindness in the crow search process,a node contribution index of influence is constructed based on k-shell decomposition and structural hole constraint.According to this index,a certain number of candidate nodes are selected from the network for the crows' random walk strategy,which improves the convergence speed of the algorithm.Finally,a local search strategy based on greedy mechanism is used to optimize the current optimal candidate nodes.The search strategy is to fully search the first-order neighbors of the candidate nodes to replace the current candidate seed node to improve the quality of the optimal candidate seed.The comparisons with classic algorithms show that the discrete crow search algorithm has better solution and stability in solving the problem of influence maximization.(4)In order to further improve the efficiency of meta-heuristic optimization algorithm in solving the influence maximization problem,a strategy of selecting seed nodes based on community division and discrete differential evolution algorithm is proposed by taking advantage of the community structures in the network.Firstly,some less influential nodes are eliminated to form a candidate node set based on the network community structures.In order to ensure the diversity of the population,an initialization method based on the combination of the global network and the candidate node set is proposed.Based on the discrete structure of the network,the discrete coding mechanism and evolution rules of the differential evolution population are defined in the actual social networks.Compared with the typical influence maximization algorithms,the experimental results show that the accuracy of node influence estimation based on the two-hop neighborhood is higher than that based on the one-hop neighborhood.In addition,the experimental results also reveal that the proposed algorithm based on community division and discrete differential evolution has high efficiency and good performance.In conclusion,this paper puts forward a series of effective solutions to the influence maximization problem in social network,and verifies and compares the algorithm on the real-world social network.It has strong theoretical and practical significance for further promoting the research of the influence maximization problem in social network.