关键词: 社交网络, 影响最大化, k-核过滤, 独立级联模型, 传播树结构

Abstract: Concerning the limited influence scope and high time complexity of existing influence maximization algorithms in social networks, a k-core filtered algorithm was proposed. Firstly, an existing influence maximization algorithm should be provided, where the rank of nodes did not depend on the whole network. Secondly, previous training was done to find the k which optimized the existing algorithm best and was independent with the number of selected seeds. Finally, the k-core subgraph was computed to apply the existing influence maximization algorithm, and because nodes and edges out of k-core were filtered, the time complexity was reduced. The k-core filtered algorithm worked differently for different existing algorithms, and experiments on datasets of different scale were conducted. For the PMIA algorithm, k-core filtered algorithm achieved 13.89% bigger influence scope and reduced running time by 8.34%; for the CCA algorithm, the influence scope remained the same but running time decreased by 28.5%;for the Degree algorithm, it was 21.81% bigger influence scope and 26.96% less running time;for the Random algorithm, it was 71.99% bigger influence scope and 24.21% less running time. Furthermore, the GIMS algorithm was proposed and remained running time in seconds but achieved bigger influence scope than the outstanding existing algorithms PMIA and IRIE, and also its k-core filtered algorithm optimized almost nothing. The experimient results show that k-core filtered algorithm can effectively increase the influence scope of existing algorithms and reduce their running time, and the GIMS algorithm can achieve bigger influence scope and better efficiency robustly.

Key words: Social Network, Influence Maximization (IM), k-core filtered, Independent Cascade Model, Diffusion Tree