针对社交网络中的影响力最大化问题，通过适应度景观状态来规划差分进化算法

《Neurocomputing》：Orchestrating the differential evolution via fitness landscape state for the influence maximization problem in social networks

　　唐建新|庞娟|耿乐乐|傅家强|徐天鹏中国甘肃省兰州市730050，兰州理工大学计算机科学与人工智能学院摘要在社交网络中最大化信息传播效果的关键在于从高维解空间中找出最优的种子节点。然而这类空间存在大量局部最优解，容易使搜索过程陷入次优区域。现有的元启发式算法虽无需梯度信息即可进行全局搜索，但由于无法利用网络空间的结构特征，缺乏有效引导。这些局限性凸显出需要新的分析视角来研究解的分布规律，从而把握种群搜索行为并优化搜索过程。为解决这些问题，本文提出了一种基于景观感知的差分进化优化算法（LADE），该算法能够动态建模适应度景观状态，量化陷阱效应并指导搜索行为。具体而言，该算法结合了按直径分层的拉丁超立方抽样与度扰动策略，以生成具有均匀覆盖度和优质个体的初始解集。通过分析演化过程中的种群分布，引入景观状态值来构建适应度景观，该状态值可识别出包括收敛、探索、利用和逃脱在内的四种演化状态，从而描述搜索行为与局部景观结构之间的关联。最终，根据检测到的状态选择相应的景观驱动操作符，引导种群远离局部最优解，朝向更有潜力的区域发展。在九个真实网络上的实验结果表明，与CELF相比，LADE在七种基准算法下的影响力传播平均相对提升率为8.11%，这些基准算法包括LIDDE、DHHO、LDD、PHEE、BiGDN、MSPSO和DSMO。这一平均值是在所有九个网络及不同种子规模下计算得出的。实验结果证明了LADE在结构多样的网络中的有效性。引言社交网络作为由各种社会关系构成的互联系统，在信息传播、舆论动态以及精准营销等方面发挥着重要作用。微博、TikTok和Twitter等平台的快速发展，进一步加剧了由用户互动和行为模式所形成的信息流动的复杂性。在此背景下，影响力最大化问题已成为社交网络分析中的核心挑战，其目标是在给定的传播模型下找到一组少数种子节点，以实现最大的预期影响力传播范围。由于该问题的理论复杂性和实际意义，它在运筹学、统计物理学和计算机科学领域都引发了持续的研究兴趣。影响力最大化问题最初由Domingos等人提出，后被正式定义为组合优化问题，Kempe等人证明在独立级联模型和线性阈值模型下该问题是NP难问题。人们还证明了影响力函数的次模性，并提出了一种针对单调次模目标的贪心算法，具有()的近似保证。然而，依赖成本高昂的蒙特卡洛模拟限制了基于贪心算法的方法的可扩展性。即便后来出现的如CELF这样的改进方法也只能部分减轻计算负担，未能彻底解决这一问题。同时，虽然基于结构的启发式方法能够显著提高效率，但它们忽视了动态的传播模式，且缺乏最优性保证，这些仍是其在实际应用中的主要局限。正是这些局限性促使人们将元启发式算法引入到影响力最大化问题的求解中。目前大多数元启发式算法都能实现无梯度的全球搜索，并在解决影响力最大化问题方面展现出良好效果。典型的方法包括离散粒子群优化和差分进化。然而，由于信息传播的非线性特性，影响力最大化问题会呈现出高度非凸的多模态适应度景观。这类复杂的景观容易使进化种群陷入局部最优解，阻碍其在不同优化区域间的转移。因此，那些仅进行无方向探索且无法感知问题底层结构的现有元启发式算法，在有效解决影响力最大化问题方面面临根本性挑战。首先，现有的自适应搜索策略通常是根据历史搜索反馈和种群统计数据来调整参数配置或选择操作符。这类反馈机制虽然能够反映之前的搜索结果，却无法准确描述种群在离散的影响力最大化空间中所面临的当前景观状态。因此，搜索行为与景观结构之间的关系尚未得到充分建模，自适应策略调整也缺乏针对种群演化的直接结构引导。其次，由于缺乏景观状态反馈机制，种群难以检测到局部最优解并从中逃脱，进而削弱了全局探索能力与收敛稳定性。从根本上说，对结构特征的感知不足是制约元启发式算法在复杂搜索景观中适应能力的关键瓶颈。正因如此，元启发式算法仍难以根据种群所面临的景观状态调整搜索行为。这一局限性凸显出需要具备分析景观结构并将其与搜索行为相联系的工具。适应度景观理论为描述优化问题中解空间内适应度值的分布以及搜索行为的动态特征提供了坚实框架，有助于深入理解种群演化机制。实证研究表明，将适应度景观分析融入元启发式算法中，可以有效降低搜索过程的随机性，提升搜索效率。为解决这一问题，本研究将适应度景观分析引入差分进化算法中，用于影响力最大化问题，从而建立景观结构与搜索行为之间的明确映射关系。这种映射将种群层面的景观状态量化与每一代中的状态驱动操作符调度相结合。具体而言，本文提出了基于景观感知的差分进化算法（LADE）。在LADE中，适应度景观分析被嵌入到进化搜索过程中，形成一种以景观状态为导向的优化机制，而不仅仅作为搜索过程的辅助分析工具。在该机制中，所提出的景观状态值作为核心状态表示。在每一代中，该值都是根据种群分布计算得出的。作为一种定量指标，它能够描述当前的景观状态，并量化种群分布情况与当前最佳个体位置之间的关联。在LADE中，景观状态值反映了搜索行为与局部适应度景观结构之间的相互作用。基于这一值，LADE可将演化过程分为四种状态：收敛、利用、探索和逃脱。随后，LADE会根据检测到的状态来安排突变操作符的选择。与那些主要依靠历史搜索反馈来调整参数或操作符的现有方法不同，LADE建立了从当前景观状态到突变操作符选择的明确映射关系。这一映射构成了LADE的核心方法贡献，它将差分进化中的操作符调度从基于历史的调整转变为基于景观状态的智能调度。通过这一机制，LADE能够在每一代中根据当前的景观状态调整搜索行为。这样的调整有助于在不同演化阶段实现策略的自适应切换，进而提升全局搜索能力和收敛稳定性。这一机制为将适应度景观分析应用于影响力最大化问题的搜索行为提供了新的思路。从更广泛的方法论层面来看，这一机制也可为那些具有复杂景观结构的离散网络优化问题提供有益参考。这类问题包括关键节点识别、网络拆分以及网络免疫等，它们通常需要在拓扑结构约束下选择节点子集。本文的主要贡献如下：•提出了一种混合初始化策略，通过结合按直径分层的拉丁超立方抽样与基于度中心性的启发式抽样，提升了早期种群样本的结构覆盖度和传播潜力，为后续的景观状态估计及状态驱动搜索奠定了可靠基础。•提出了一种景观状态建模机制，用于描述离散影响力最大化问题中种群分布与局部适应度景观结构之间的关联。该机制以景观状态值为核心表示，用于识别演化状态并量化搜索过程中陷入陷阱的风险。•设计了一种状态驱动的操作符调度机制，使差分进化算法能够明确感知景观状态。该机制建立了从检测到的景观状态到突变操作符选择的直接映射关系，从而将操作符选择从基于历史的调整转变为基于景观状态的智能调度。本文的其余部分结构如下：第2节回顾了影响力最大化问题相关的现有研究；第3节介绍了所提方法的背景与理论基础；第4节详细描述了LADE算法的实现方式；第5节汇报了实验结果及分析；第6节探讨了LADE的优势与局限性；第7节对全文进行总结，并指出未来的研究方向。片段介绍基于近似的方法影响力最大化问题的研究可以追溯到Kempe等人，他们提出了一种贪心算法，该算法通过迭代选择边际收益最大的节点，可实现()的理论近似比。然而，该算法存在严重的计算瓶颈：评估一个节点的边际收益通常需要数万次蒙特卡洛扩散模拟，而且多次迭代中的重复评估会导致大量冗余计算。Leskovec等人提出了CELF算法。适应度景观概念由Wright提出，他将优化问题的搜索空间类比为地形地貌，该方法将可行解映射到景观中的不同位置，并以高度值作为适应度度量。Stadler后来对其进行了形式化定义，即，其中表示可行解，表示其邻域，表示适应度函数。这样的模型为揭示算法与问题之间的关系提供了严谨的数学基础。所提出的算法本节详细介绍了用于解决影响力最大化问题的LADE算法。LADE算法结合了景观状态建模与状态驱动的操作符调度机制，它能利用景观状态值动态感知解的分布情况与局部最优解，从而指导操作符调度，实现全局探索与局部利用的平衡。其核心框架如图1所示。最初，混合初始化模块会将拉丁超立方抽样与……实验结果所有实验都在一台运行Windows 11的个人电脑上完成，该电脑配备了2.20 GHz频率的Intel Core i7-14650HX处理器和16 GB内存。所提出的LADE算法以及未直接使用公开实现的基准算法均用Python 3.10语言实现。BiGDN基准算法则是在配置好所需环境后，使用其公开提供的源代码进行运行。图处理和数值计算则分别使用了NetworkX 3.4.2和NumPy 1.26.4版本。其他讨论本研究推动了元启发式搜索从静态的规则驱动搜索向动态的景观引导搜索的发展。LADE算法通过利用种群分布来推断局部景观结构，并构建搜索行为的闭环反馈机制，使差分进化算法具备了景观状态感知与自适应响应能力。这一机制有效避免了传统元启发式算法在影响力最大化问题中的盲目搜索倾向。实验结果表明，LADE算法具有出色的性能。结论本文提出了一种基于适应度景观建模的差分进化算法，通过景观状态驱动的搜索操作符调度方式，来解决社交网络中的影响力最大化问题。景观状态建模使得该算法能够动态描述搜索空间中的种群分布情况，并据此调整搜索策略，从而实现全局探索与局部利用的平衡。在多个真实网络上的大量实验表明，LADE算法……致谢本项目得到了甘肃省杰出青年科学基金（项目编号23JRRA766）、国家自然科学基金（项目编号62562044和62162040）、甘肃省高校教师创新基金（项目编号2024A-024）、甘肃省技术人才科学基金（项目编号24CXGA046）以及甘肃省自然科学基金（项目编号24JRRA251）的资助。唐建新于2019年在中国兰州的兰州大学信息科学与工程学院获得博士学位，目前为中国兰州理工大学计算机科学与人工智能学院的副教授。他的研究主要集中在复杂网络中的影响力最大化问题上。他的研究兴趣包括社交计算、图上的机器学习以及社交网络分析。