Influence Maximization Research Based On Linear Threshold Model In Social Networks

Recently,with the improvement of Internet and technology,many online social networks flourish.With the information spread rapidly,influence maximization has been a hot topic in social networks.Influence maximization apply for many areas,such as viral marketing,advertising promotion and public opinion control.Kempe proved that influence maximization is a NP-hard problem and proposed a greedy algorithm.The algorithm ensures that it is close to the optimal solution in the 1-1/e range.But there is a problem that the time complexity is too high.Besides,there are some common heuristic node selection strategies.However,these strategies based entirely on the degree of heuristic rules are not satisfactory.Hybrid potential-influence greedy algorithm can reduce the time complexity.The core of the algorithm is that it divides the process of selecting nodes into two portions.In the heuristic stage,they chose the seed nodes which has potentiality most;In the greedy stage,a lot of nodes are activated and most of the rest will be activated easily,so that it can reduce the runtime a lot.But it's still a problem that how to choose the most potential nodes and how to seek seeds fast during the greedy stage.In order to solve the problems mentioned above,we proposed an algorithm,which is hybrid algorithm based on H-floor outcoming nodes.As same as traditional hybrid algorithm,we choose seeds in two stages.In the heuristic stage,we change one-floor outcoming nodes to H-floor.And we think about the threshold of outcoming nodes.Therefore,the algorithm based on H-floor outcoming nodes can judge the potentiality of a node exactly.In the greedy stage,we seek seed nodes fast by building the directed acyclic graphs.Meanwhile,we deal with those nodes with low potentiality and wouldn't choose those nodes as seeds.The experimental results show that the algorithm we proposed can perform better than other influence algorithms.