Font Size: a A A

Research On Node Influence Measurement And K-nodes Influence Maximization Problem In Social Networks

Posted on:2018-02-06Degree:DoctorType:Dissertation
Country:ChinaCandidate:Q MaFull Text:PDF
GTID:1318330512981456Subject:Computer Science and Technology
Abstract/Summary:PDF Full Text Request
With the rapid development of Internet technology,social network such as MicroBlog,WeChat has served as an important platform for people to obtain and share information.Social network gives chances to all the users to participate in the process of information dissemination.Users are not only receivers of information,but also publishers and disseminators.The influence of users plays an important role in the process of information dissemination,as influential users can promote the wide spread of information and attract the attention of many users rapidly.Selecting a certain number of influential nodes(also called seeds)for word-of-mouth marketing in social networks has become an important marketing way.Except in the field of marketing,it is also of great application value to identify and utilize the influential nodes in the fields of mining opinion leaders,controlling rumor spreading,recommendation,etc.With the continuous expansion of network scale,it has become a hot spot to study the problems such as how to measure the influence of nodes in a large scale network,or how to select a certain number of nodes whose influence can maximize the dissemination of information(also called influence maximization problem).These problems are also the main research issues concerned in this dissertation.Supported by NSF,this dissertation investigates two key research issues of influence spreading in social network:user influence measurement and influence maximization problem.The main research contents and innovations of this dissertation are listed as follows:(1)We propose a dynamic measurement for influence of users with consideration of spreading probability.A node's influence can be considered as the spreading ability of this node,which means the number of covered nodes in the network when the spreading originates from this node.The spreading probability exerts a great influence on the result of spreading.The spreading ability of the same node is different under different spreading probabilities.The traditional influence measures do not consider this factor,which leads to the sensitivity of these measures to the spreading probability.For example,degree centrality performs well under small spreading probabilities and semi-local centrality is suitable for large spreading probabilities.To alleviate the sensitivity of these measures to the spreading probability,we integrate degree centrality and semi-local centrality with the spreading probability as a parameter,as their performances are just the opposite under different spreading probabilities.We name this measure as hybrid degree centrality.In order to adapt to the different spreading features under different spreading probabilities,our measure can adjust the balance between degree centrality and semi-local centrality naturally according to the varying spreading probability.The experimental results show that this measure performs stablely under different spreading probabilities,and it can achieve the best performance on the most range of spreading probabilities.(2)We propose an adjustable method to measure the influence of nodes based on limited hops of spreading.By comparing a large number of experimental results,we found that the commonly used measures of node influence are not only sensitive to the spreading probability,but also sensitive to the network structure.Faced with an unknown network,it is difficult to know which measure is effective in this network.To solve this problem,we propose a robust measure named adjustable limited hops of spreading.According to the feature of spreading in social networks,our measure computes the influence of a node to other nodes within four hops based on the spreading paths.In order to reduce the time complexity,our measure treats the nodes who are 2.3,4 hops away from the target node as a whole and estimates the influence of this node to these distant nodes roughly.By setting and adjusting the parameter,this measure can adapt to different spreading features of different networks.Experimental results show that our measure has good performance in networks with different types and different scale,which means this measure has strong robustness.Moreover,the selection of parameter has certain rules to follow,which means this measure has good practicability.(3)We propose a suitable algorithm for influence maximization problem in microblog network.We focus on and try to solve the following two problems in the application of influence maximization problem in microblog network:how to integrate the information such as contents and actions in microblog with the influence maximization problem,and how to improve the efficiency of greedy algorithms in large scale microblog network.We model the influence strength between users with the contents,actions in microblog network,and combine the influence strength with the spreading model to improve the model's practicality.To improve the efficiency of the greedy algorithms in large-scale networks,we combine the influence measurement of nodes with the influence maximization problem,and propose an influence maximization algorithm based on candidates.In this algorithm,firstly a simple evaluation of the nodes' influence is conducted and only influential nodes are reserved as candidates.Next,we select seeds from the candidates with greedy algorithm.We systematically compare and analyze the influence of different candidate sets which are selected by commonly used influence measures to the seeds selection.Experimental results show that this method can greatly shorten the selection time of seeds,and does not lose any accuracy.(4)We propose the problem of discovering substitutes for inactive seeds and propose corresponding solutions.Some seeds may not be activated when the problem of influence maximization is applied in practice.In this situation a new research issue is how to reselect substitutes to replace these inactive seeds to minimize the loss.By analyzing this problem we propose three algorithms:1.Extended static greedy algorithm is proposed based on the static greedy algorithm in influence maximization problem.It is of theoretic basis.2.In order to improve the efficiency of greedy algorithm in substitutes discovery,we propose an algorithm called full static based on the properties of snapshot in the simulations of spreading.3.We propose preselected greedy algorithm which selects some backup seeds as substitutes when selecting the seeds.Experimental results show that all the substitutes selected by these three algorithms can be used to replace the inactive seeds effectively.
Keywords/Search Tags:Social network, Information Diffusion, Influence Measurement, Influence Maximization, Spreading Probability
PDF Full Text Request
Related items