计算机科学 ›› 2024, Vol. 51 ›› Issue (6): 161-171.doi: 10.11896/jsjkx.230400006
邓紫维, 陈崚, 刘维
DENG Ziwei, CHEN Ling, LIU Wei
摘要： 影响力最大化是在社交网络中寻求一组最具有影响力的用户作为种子节点,通过种子节点向网络中传播信息,使得传播的范围最大化。现有的对影响力最大化的研究大多是针对每个节点,考虑是否将其作为种子节点。而在实际应用中,需要根据用户的影响力来赋予他成为种子的概率,使得根据这个概率分布得到的种子集合的影响力传播范围的期望值最大化,这就是连续影响力最大化问题。文中提出了一种独立级联传播模型下连续影响力最大化算法。该算法首先将上述问题抽象成一个约束优化问题,然后抽样若干个可能的种子集,并对每个可能的种子集估计影响的传播范围;使用梯度下降法,在每轮迭代中根据估计的传播范围计算各个方向的增量值,取最大增量的方向作为梯度进行目标函数值的迭代更新,从而得到目标函数值的最优解。在真实和虚拟网络上进行实验,结果表明,该算法在影响范围的期望值上优于Random,Degree,UD和CD等算法。
中图分类号:
| [1]SHAO J H,ZHANG E,XIANG Y,et al.Efficient combinations of dual incentives on social networks to achieve viral spread[J/OL].https://link.springer.com/article/10.1007/s10660-022-09668-z. [2]HE Q,ZHANG D,WANG X,et al.Graph Convolutional Net-work-Based Rumor Blocking on Social Networks[J].IEEE Transactions on Computational Social Systems,2022,10(5):2244-2253. [3]REN J,LIU M,LIU Y,et al.Optimal resource allocation with spatiotemporal transmission discovery for effective disease control[J].Infectious Diseases of Poverty,2022,11(1):34. [4]FERRARA L,MOGLIANI M,SAHUC J G.High-frequencymonitoring of growth at risk[J].International Journal of Forecasting,2022,38(2):582-595. [5]DOMINGOS P,RICHARDSON M.Mining the network value of customers[C]//Proceedings of the seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mi-ning.2001:57-66. [6]RICHARDSON M,DOMINGOS P.Mining knowledge-sharingsites for viral marketing[C]//Proceedings of the eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.2002:61-70. [7]KEMPE D,KLEINBERG J,TARDOS É.Maximizing the spread of influence through a social network[C]//Proceedings of the ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.2003:137-146. [8]LI Y,FAN J,WANG Y,et al.Influence maximization on social graphs:A survey[J].IEEE Transactions on Knowledge and Data Engineering,2018,30(10):1852-1872. [9]LESKOVEC J,KRAUSE A,GUESTRIN C,et al.Cost-effective outbreak detection in networks[C]//Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Disco-very and Data Mining.2007:420-429. [10]LI W M,LI Z,LUVEMBE A M,et al.Influence maximizationalgorithm based on Gaussian propagation model[J].Information Sciences,2021,568:386-402. [11]KUMAR S,GUPTA A,KHATRI I.CSR:A community based spreaders ranking algorithm for influence maximization in social networks[J].World Wide Web,2022,25(6):2303-2322. [12]ZHANG J X,CHEN D B,DONG Q,et al.Identifying a set of influential spreaders in complex networks[J].Scientific reports,2016,6(1):27823. [13]LIU P,LI L,FANG S,et al.Identifying influential nodes in social networks:A voting approach[J].Chaos,Solitons & Fractals,2021,152:111309. [14]SUN G,CHEN C C.Influence maximization algorithm based on reverse reachable set[J].Mathematical Problems in Enginee-ring,2021,2021:1-12. [15]ZHU W,HUANG Y,YANG S,et al.A Positive Influence Maximization Algorithm in Signed Social Networks[J].Computers,Materials & Continua,2023,76(2):1977-1994. [16]ALI J,BABAEI M,CHAKRABORTY A,et al.On the fairness of time-critical influence maximization in social networks[C]//2022 IEEE 38th International Conference on Data Engineering(ICDE).IEEE,2022:1541-1542. [17]GONG H,GUO C.Influence maximization considering fairness:A multi-objective optimization approach with prior knowledge[J].Expert Systems with Applications,2023,214:119138. [18]QIN X,ZHONG C,YANG Q.An Influence Maximization Algorithm Based on Community-Topic Features for Dynamic Social Networks[J].IEEE Transactions on Network Science and Engineering,2021,9(2):608-621. [19]ZHANG X,XU L,XU Z.Influence maximization based on network motifs in mobile social networks[J].IEEE Transactions on Network Science and Engineering,2022,9(4):2353-2363. [20]GHOSHAL A K,DAS N,DAS S.Influence of community structure on misinformation containment in online social networks[J].Knowledge-Based Systems,2021,213:106693. [21]LI Y,ZHU J,JIAO J,et al.Competitive Influence Minimization in Multi-Group Social Networks:An Opinion-Based Solution[J].IEEE Transactions on Network Science and Engineering,2022,9(4):2617-2630. [22]KEMPE D,KLEINBERG J,TARDOS É.Maximizing the Spreadof Influence through a Social Network[J].Theory of Computing,2015,11(1):105-147. [23]YANG Y,MAO X,PEI J,et al.Continuous influence maximization:What discounts should we offer to social network users?[C]//Proceedings of the 2016 International Conference on Ma-nagement Df data.2016:727-741. [24]YANG Y,MAO X,PEI J,et al.Continuous influence maximization[J].ACM Transactions on Knowledge Discovery from Data(TKDD),2020,14(3):1-38. [25]CHEN W,WU R,YU Z.Scalable lattice influence maximization[J].IEEE Transactions on Computational Social Systems,2020,7(4):956-970. [26]CHEN W,ZHANG W,ZHAO H.Gradient method for continuous influence maximization with budget-saving considerations[C]//Proceedings of the AAAI Conference on Artificial Intelligence.2020,34(1):43-50. [27]CHEN W,WANG Y,YANG S.Efficient influence maximization in social networks[C]//Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.2009:199-208. [28]TANG Y,XIAO X,SHI Y.Influence maximization:Near-optimal time complexity meets practical efficiency[C]//Proceedings of the 2014 ACM SIGMOD International Conference on Ma-nagement of Data.2014:75-86. |
|
||
首页