Font Size: a A A

Algorithm Of Maximizing Social Network Influence Based On Threshold

Posted on:2013-08-07Degree:MasterType:Thesis
Country:ChinaCandidate:H ChenFull Text:PDF
GTID:2208330434472108Subject:Computer application technology
Abstract/Summary:PDF Full Text Request
Influence maximization is a problem of finding a subset of nodes in a social network that can maximize the spread of influence. This optimization problem of influence maximization is proved NP-hard. Kempe and Kleinberg proposed a natural climbing-hill greedy algorithm that chooses the nodes which could provide the best marginal influence (KK algorithm). KK algorithm has large spread of influence, but is too costly for large social network.We proposed a threshold-based heuristic algorithm (TBH) for social network influence maximization based on activation threshold of nodes. The algorithm computes potential influenced nodes (PIN) according to dynamically changing activation threshold of nodes in activating process. In heuristic phase, we select nodes with maximal PIN as seed nodes. Then, in greedy phase, we greedily select nodes having maximal margin gain of influence as seed nodes. Our experiments demonstrate that, even without the greedy phase, the performance of our algorithm is close to that of KK algorithm, and our algorithm has relatively very short running time. The experimental results also show that, our algorithm outperforms HPG with the same heuristic factor c.
Keywords/Search Tags:social network, influence maximization, heuristic algorithm, greedyalgorithm, TBH
PDF Full Text Request
Related items