Research On Influence Maximization Based On Community Discovery

With the popularity of Internet,a large number of social applications have been appeared in recent years.Thanks to its convenience,more and more people take it as one of the main media to understand the world’s hot spots.Using social networks,people can quickly establish social relations,to communicate and share their views on a social hot event of common concern.Social networks seem to have become an indispensable part of people’s life.It is the mapping of people’s real life in the virtual world and reflects people’s living conditions in real life.Research on social network can explore the hidden information that is not easy to detect in real life,so it has strong research value and has attracted the attention of many scholars in recent years.Influence maximization(IM)is an important field of social network.Its main research problem is to find several nodes in the network,spread them through the communication model,and affect more nodes.It can play an important role in network marketing,public opinion control,epidemic prevention and control and other fields.At present,IM algorithms are mainly divided into two categories: greedy algorithms and heuristic algorithms.Greedy algorithm can find the optimal result,but the time complexity is too high to be used in large-scale networks.Because the time complexity of heuristic algorithm is low,it is an indirect measure of influence through other indicators,and the propagation effect can’t be guaranteed.Through the analysis of the existing IMs,this paper mainly includes the following aspects.On the one hand,because most heuristic algorithms currently use degree as a measure,which have poor performance in measuring network characteristics and can’t get potential information.By using original Page Rank combined with threshold filtering as a measure,this paper achieves a heuristic IM algorithm based on Page Rank,which can effectively solve the aggregation problem in the general IM algorithm based on Page Rank alone.On the other hand,in order to solve the problem that greedy algorithm takes a long time and heuristic algorithm has poor performance,this paper combines the community discovery algorithm with the former to propose a new IM algorithm based on community partitioning.The specific work of this paper is as follows:Firstly,it improves the original Page Rank algorithm,and the redundant edges are removed by setting a threshold filter method.A new heuristic maximization of influence algorithm PRTH(Page Rank Centrality and Propagation Probability Threshold Algorithm)is proposed,which can improve the propagation performance.Secondly,because of the unstable performance of PRTH algorithm,a new algorithm PRDD(Combining Page Rank with Degree Discount)is proposed by combining PRTH algorithm with discount degree,which solves the unstable result of PRTH algorithm and improves the node diffusion range.Finally,the network characteristics of community structure are introduced into the study,which combines community discovery with the previous two strategies to form a community-based and PRTH for IM algorithm Co PRDD(community-based and PRDD for IM).These two algorithms will combine heuristic and greedy algorithms,and take into account the location and size of the community and the importance of the community edge nodes in the original network,to ensure that the algorithm has an acceptable propagation time while expanding its propagation range.At the same time,relevant experimental validation is carried out for the above content.The PRTH algorithm and PRRDD algorithm are experimented on four datasets and compared with five baseline algorithms.Both algorithms have good results in propagation effect and propagation time.The Co PRTH and Co PRDD algorithms are experimented on four experimental datasets and compared with five baseline algorithms respectively.Experimental results show that both algorithms have good propagation performance.