The Research On Algebraic Connectivity-based Influence Maximization Problem In Social Networks

With the emergence of many online social networks, the way of information propogation and communication has a new pattern.The viral marketing and word of mouth(WOM) have become the focus of marketing industry research. As it shown in the McKinsey report on social networks, social network has changed the "consumer journey",so that online social network can supervise and guide consumers’behavior. Domingos and Richardson first classified such phenomenon into the influence spread maximization problem, and introduced it into the field of social network.In the research of social network influence spread maximization, there are two main directions:one is to find the most influential points, usually used for mining opinion leaders and experts,etc;the other is to explore the realization of influence spread maximization, which is to discuss how to correctly choose the initial communication object to reach the maximization of social network influence spread. This paper is mainly about the latter research.The transmission mechanism and the structure characteristic of the social network should be integrated into the analysis of diffusion process. But the existing research is mostly about exploring the specific application scenarios(such as micro-blog) of the transmission mechanism. The influence of the structure of network topologies has not been given enough consideration This paper presents the influence of algebraic connectivity that based on maximization model, and the core of the model is to compute edge centrality by the algebraic connectivity parameters,so as to realize the quick network division of the community;Mining the local influential nodes, degree central nodes, and finding bridge nodes between communities (also called community connection point), then the Top-K global influential nodes can be selected from the three collection in the initial point set.The main innovation of this paper:i. It is based on the features of the community structure of social network to generate seed nodes set,and selects global influential nodes from seed nodes set. ii. Finding the bridge nodes by the second small feature vector (algebraic connectivity),which is an effective supplement to existing algorithm. ⅲ.Combing the community and whole network method, in this way,it can improve the algorithm effect.The result of experiment shows that this model has achieved good effect in the final impact area and running time.