Research On Influence Maximization Algorithm Based On Community Detection

As the Internet enters the era of Web 2.0,thanks to the convenience of social networks,people actively share their daily activities on social platforms,which in turn generates a lot of data.Because virtual networks are the mapping of real world,analyzing the influence of social networks on real societies has long-term and practical significance.At present,a common social phenomenon is usually ignored in influence maximization algorithms: the nodes with important influences in the community may be suddenly lost,which leads to the influences of seed node set greatly reducing.Moreover,existing influence maximization solution processes have a large number of repeated iterative operations,resulting in inefficiency and long running time,which cannot meet the existing data environment.In addition,the existing alternative seed node finding algorithms have some obvious disadvantages,such as the randomization of nodes and the sparse data.The main research contents of this thesis are as follows:(1)Aiming at the problem of the inefficiency of community influence maximization in social networks,this thesis proposes an IMBCP algorithm based on community partition.In IMBCP algorithm,the proposed IPS algorithm is used to solve the community organization of social network,and then to maximize the influence in the community structure.The IPS algorithm can accurately measure the influence probability of a node on non-adjacent nodes,and then fill in the influence probability matrix between users,reduce the impact of data sparseness,and improve the data quality from the source of community detection.When calculating the influence of the community on the nodes,the influence transmitted from the non-adjacent nodes is also counted.Through multiple experiments,the influence weights of adjacent nodes and non-adjacent nodes are confirmed to ensure that the real environment is met.Many experiments have shown that the proposed community detection results are better than the existing methods,and the community detection structure is more reasonable and accurate.Based on the IPS algorithm,the IMBCP algorithm is proposed to replace the global influence by the topology of the social network and the local influence of the node,which improves the efficiency of the algorithm as well as improving the accuracy of the algorithm.(2)For the problem of sudden loss of nodes when solving community influences,this thesis introduces the substitutability concept based on the existing search methods of substitute nodes,and proposes a pre-selected search algorithm(Full pre-selected search,FPSS).For the seed node n that cannot be activated,the k nodes with highest substitutability with n are first obtained,and the descending order is sorted according to the substitutability to form a substitute node queue.Once the node n cannot be activated,the first node in the alternate node queue can be extracted from the replaceable list according to the alternative node search algorithm.If the node has been joined the seed node set,it traverses the alternate queue in sequence until finding the first activatable node which was not in the seed node set.Through comparing with other existing algorithms,the experiment demonstrates that the proposed algorithm reduces the update operations of the late seed node and improves the efficiency of the existing substitute node search algorithm.(3)The advertising marketing system integrating IMBCP algorithm and FPSS algorithm is designed and implemented.For the application of the influence maximization algorithm and the substitute seed node search algorithm in the real situation,this thesis analyzes the requirements and analyzes the business needs and functional requirements in the field of advertising marketing,thus designing and implementing the advertising marketing system.In this system,not only the proposed IMBCP algorithm and FPSS are integrated,but also the modules of data acquisition and data import are designed from the perspective of the enterprise.Through this system,on one hand,the most influential set of seed nodes in the social network can be quickly obtained,and the product marketing revenue can be maximized.At the same time,when the seed node is lost,the substitute seed node can be quickly found to reduce the loss of marketing revenue.Certain practical value and application significance.