Greedy Strategy Influence Maximization Algorithm Based on Seed Candidates
LI Meiling1,2, QIAN Fulan1,2, XU Tao1,2, ZHAO Shu1,2, ZHANG Yanping1,2
1. School of Computer Science and Technology,Anhui University,Hefei 230601; 2. Key Laboratory of Intelligent Computing and Signal Processing,Ministry of Education,Anhui University,Hefei 230601
Abstract：The hill-climbing greedy algorithm is not easily extended to large-scale social networks due to its high time complexity.In this paper,it is theoretically analyzed that the node set influence evaluation can be transformed into local probability solution,and thus the algorithm efficiency is significantly improved.The local probability solution function is extend to the greedy algorithm.Based on seed candidates,the greedy influence maximization algorithm and the lazy forward influence maximization algorithm are proposed,respectively. Experiments on four real datasets show that the performance of the proposed algorithms is as high as that of cost-effective lazy forward selection,and the proposed algorithms are superior in running time.
[1] WU J,CHEN Z G,ZHAO M.Information Cache Management and Data Transmission Algorithm in Opportunistic Social Networks.Wireless Networks,2019,25(6):2977-2988. [2] 曹玖新,闵绘宇,王浩然,等.竞争环境中基于主题偏好的利己信息影响力最大化算法.计算机学报,2019,42(7):1495-1510. (CAO J X,MIN H Y,WANG H R,et al.Self-interest Influence Maximization Algorithm Based on Subject Preference in Competitive Environment.Chinese Journal of Computers,2019,42(7):1495-1510.) [3] WU J,CHEN Z G,ZHAO M.Weight Distribution and Community Reconstitution Based on Communities Communications in Social Opportunistic Networks.Peer-to-Peer Networking and Applications,2019,12(1):158-166. [4] 胡庆成,张 勇,邢春晓.基于有重叠社区划分的社会网络影响最大化方法研究.计算机科学,2018,45(6):32-35. (HU Q C,ZHANG Y,XING C X.K-clique Heuristic Algorithm for Influence Maximization in Social Network.Computer Science,2018,45(6):32-35.) [5] DOMINGOS P,RICHARDSON M.Mining the Network Value of Customers//Proc of the 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York,USA:ACM,2001:57-66. [6] KEMPE D,KLEINBERG J M,TARDOS É.Maximizing the Spread of Influence through a Social Network//Proc of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mi-ning.New York,USA:ACM,2003:137-146. [7] LESKOVEC J,KRAUSE A,GUESTRIN C,et al. Cost-Effective Outbreak Detection in Networks//Proc of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York,USA:ACM,2007:420-429. [8] CHEN W,WANG Y J,YANG S Y.Efficient Influence Maximization in Social Networks//Proc of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York,USA:ACM,2009:199-208. [9] WANG Y,CONG G,SONG G J,et al.Community-Based Greedy Algorithm for Mining Top-k Influential Nodes in Mobile Social Networks//Proc of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York,USA:ACM,2010:1039-1048. [10] KUNDU S,PAL S K.Deprecation Based Greedy Strategy for Target Set Selection in Large Scale Social Networks.Information Sciences,2015,316:107-122. [11] COHEN R,EREZ K,BEN-AVRAHAM D,et al.Breakdown of the Internet under Intentional Attack.Physical Review Letters,2001,86(16):3682-3685. [12] NEWMAN M E J.A Measure of Betweenness Centrality Based on Random Walks.Social Networks,2005,27(1):39-54. [13] ZHANG J X,CHEN D B,DONG Q,et al.Identifying a Set of Influential Spreaders in Complex Networks.Scientific Reports,2016,6(1).DOI:10.1038/srep31254. [14] KUNDU S,MURTHY C A,PAL S K.A New Centrality Measure for Influence Maximization in Social Networks//Proc of the International Conference on Pattern Recognition and Machine Intelligence.Berlin,Germany:Springer,2011:242-247. [15] JIANG Q Y,SONG G J,GAO C,et al. Simulated Annealing Based Influence Maximization in Social Networks//Proc of the 25th AAAI Conference on Artificial Intelligence.Palo Alto,USA:AAAI Press,2011:127-132. [16] GONG M G,YAN J N,SHEN B,et al. Influence Maximization in Social Networks Based on Discrete Particle Swarm Optimization.Information Sciences,2016,367/368:600-614. [17] SINGH S S,KUMAR A,SINGH K,et al. LAPSO-IM:A Lear-ning-Based Influence Maximization Approach for Social Networks.Applied Soft Computing,2019,82.DOI:10.1016/j.asoc.2019.105554. [18] CUI L Z,HU H X,YU S,et al.DDSE:A Novel Evolutionary Algorithm Based on Degree-Descending Search Strategy for Influence Maximization in Social Networks.Journal of Network and Computer Applications,2018,103:119-130. [19] TANG J X,ZHANG R S,WANG P,et al. A Discrete Shuffled Frog-Leaping Algorithm to Identify Influential Nodes for Influence Maximization in Social Networks.Knowledge-Based Systems,2020,187:104833.1-104833.12. [20] LI Y C,FAN J,WANG Y H,et al.Influence Maximization on Social Graphs:A Survey.IEEE Transactions on Knowledge and Data Engineering,2018,30(10):1852-1872. [21] LINFOOT E H.On the Law of Large Numbers.Philosophical Tran-sactions of the Royal Society of London,1928,227:417-451. [22] ZHANG M,DAI C N,DING C,et al.Probabilistic Solutions of Influence Propagation on Social Networks//Proc of the 22nd ACM International Conference on Information and Knowledge Management.New York,USA:ACM,2013:429-438. [23] CHRISTAKIS N A,FOWLER J H.Connected:The Surprising Power of Our Social Networks and How They Shape Our Lives.New York,USA:Little,Brown Spark,2009. [24] NEWMAN M E J.Finding Community Structure in Networks Using the Eigenvectors of Matrices.Physical Review E,2006,74(3).DOI:10.1103/PhysRevE.74.036104. [25] LESKOVEC J,KLEINBERG J,FALOUTSOS C.Graph Evolution:Densification and Shrinking Diameters.ACM Transactions on Knowledge Discovery from Data,2007,1(1).DOI:10.1145/1217299.1217301.
2020, Vol. 33 
