Research On Influence Maximization And Optimization Based On Network Structure

Influence maximization problem aims to find the Top-k users who can make the information spread the most widely from social networks as information sources.The diversity of social network structure has continuously injected vitality into the influence maximization problem,which has been a hot issue in academic circles for nearly two decades.In this paper,the following work is carried out from two aspects: cut-vertex-based influence maximization algorithm in social network and influence maximization by optimizing the network structure:(1)Cut-vertex-based influence maximization algorithm in social network: The existing algorithms mainly focused on the characteristics of the node,and rarely considered the influence maximization problem from the perspective of social networks connectivity.As a bridge between connected components,the cut-vertex is the core of connectivity.To this end,this paper comprehensively considers the characteristics of node and connectivity of social networks,and proposes a heuristic algorithm based on cut-vertex to solve the influence maximization problem.The algorithm uses degree and connected components to evaluate the influence of nodes,which solves the problem of overlapping influences to a certain extent.Based on the susceptible-infected-recovered model,this paper conducts related experiments on four open source datasets.In the algorithm comparison experiment,the influence maximization algorithm based on the cut-vertex performed well in terms of the running time,influence spread range and seed enrichment,which verified the practicality and effectiveness of the algorithm.(2)Influence maximization by optimizing the network structure: For most researchers only focus on the beginning of information dissemination(i.e.mining information sources)and ignore the timeliness of dissemination,resulting in dissemination effects that fall short of expectations.In order to solve this problem,this paper studies the problem of maximum impact from the perspective of dynamic network topology.And designed a dynamic and static network hybrid edging(DSNHE)framework.This framework can not only solve the problem of edge addition in dynamic networks,but also solve the problem of edge addition in static networks.The main idea of the framework: First,this paper proposes the IMM++ algorithm for seed mining based on the Influence Maximization via Martingales(IMM)algorithm;then,in order to capture the dynamic changes of the network as soon as possible,this paper adopts the method of establishing an influence set to reduce the update time;Finally,because the edge addition problem is #P-hard,this paper proposes a new edge addition strategy,and finishes the edge addition work in nearly linear time.This paper conducts experiments on multiple real data sets to verify the effectiveness of the strategies and algorithms proposed in this paper.