Study Of Algorithms For Cost-based Influence Maximization Problems

In recent years,the rapid rise of online social networks has not only become an important way for people to spread information,but also has become a popular platform for the implementation of many applications.The most typical application is word-of-mouth influence(or viral marketing),which achieves marketing information dissemination through teaching orally among Internet users.A key issue in the implementation of this application is the issue of maximizing influence: Given a network and parameter k,find k users in the network;initiate information propagation from these users to maximize the number of final affected users.Most traditional influence maximization algorithms ignore the cost of user node selection and have low operating efficiency.This paper considers the cost factors of selecting nodes and studies the problem of maximizing influence based on cost.The main work contents are as follows:(1)To study how to finding k users with maximum influence and minimum cost in the network.In this paper,an independent cascade model based on hop is used to propose the lazy forward(HCLF for short)algorithm for the least cost IM problem.The algorithm used the sub-mode characteristic of maximizing influence to quickly calculate the upper limit of the "profit ratio" gain of the non-seed node of the current round.If it was greater than or equal to the upper limit of the gain of the previous round,this node was the seed set.The experimental results showed that the running time of HCLF is more than a thousand times faster than the traditional influence maximization algorithm CELF at different data sets and different costs.In terms of benefits,HCLF is also 5 to 8 times more profitable than CELF,which verifies the effectiveness of the proposed algorithm.(2)To study how to quickly identify a seed user group with high profits on a given budget.On the basis of independent cascade model of hops,a lazy forward algorithm(BHLF)based on the IM problem on different budgets is designed to solve the above problem.In this method,candidate sets under the corresponding budget were found based on hop,and then BHLF algorithm was used to quickly select seed sets under the corresponding budget from candidate sets.Experiments were carried out on real data sets Nethept and GR-QC.The running time and effect of the algorithm were compared;The results showed that the running time of the BHLF algorithm had been reduced by more than 1000 times,while the "cost performance" had been increased by 20%.(3)To research how to find the target set with the lowest activation cost under the given influence coverage.For linear threshold model,an algorithm with approximate guarantee based on hop is proposed.The algorithm evaluates the influence and cost of nodes in the local scope of finite hops and measures the influence of nodes on the whole network.Experiments were carried out on the data set Net HEPT and Email.The results show that the proposed algorithm can save 15%-80% cost compared with discount algorithm and random algorithm under given influence coverage.