关键词: 社交网络,影响力最大化,贪心算法,传播模型

Abstract: Influence maximization is a problem of finding a small group of seed nodes in a social network,so that the influence scope of spread in the network is maximized.Kempe and Kleinberg proposed a greedy algorithm which has a wide influence,but its high complexity makes it unsuitable for large social network.Chen and Yuan proposed a heuristic algorithm called local directed acyclic graphs based on linear threshold (LT) model.But LT model only considers the direct influence of neighbors nodes,and ignores the indirect influence between the settled nodes.Therefore,combining with the indirect influence between nodes in the network,we proposed LT⁺ influence model based on LT model.We also used the local directed acyclic graphs (DAGs) heuristic algorithm to solve the problem of influence maximization,known as LT⁺DAG algorithm.Extensive experiments were done on real-world dataset to compare the proposed method with other influence maximization algorithms.The result shows that the proposed method can achieve better influence scope and extensibility.

Key words: Social network,Influence maximization,Greedy algorithms,Propagation model