《中国人工智能学会通讯》——8.24 基于演化优化的网络影响最大化

影响最大化问题是社交网络分析中一个重要的研究问题。影响最大化是为了找到一个在网络中有最大影响力的节点集合。影响最大化在现实生活中有着广泛的应用，如社交媒体中广告的投放。

影响最大化被 Kempe、Kleinberg 和 Tardos建模为一个离散的优化问题。在独立级联模型中，影响最大化问题被证明是一个 NP-hard 问题。文献[34] 提出了一种基于集合编码的演化算法 (SGA) 来优化独立级联模型中的期望影响值 。在该算法中，染色体使用节点集合表示，其中每一个基因表示一个目标节点。在该算法中，采用的遗传算子非常简单。交叉操作中，首先从父代染色体中随机选择两个相同大小的子集；然后，交换这两个子集得到两个子代染色体。该算法采用了随机变异操作。在目标函数的计算中，使用了蒙特卡洛模拟，但是蒙特卡罗模拟并不高效。

在文献 [35] 中，一个概率模型被用于评价独立级联模型的影响力。为了优化该模型，作者提出了一种基于演化优化的影响最大化算法（MAGA）。MAGA 采用了与 SGA 一样的个体表示方法。Tsaiet al [36] 通过结合演化算法和贪婪算法提出了一种改进的 MAGA 算法。在该算法的交叉操作中，首先对父代染色体取并集，然后去除并集中影响力小的节点，从而得到子代染色体。同时该算法采用了一种基于贪婪算法的局部搜索来提高算法的质量。

为了减小贪婪算法的计算代价，社区检测被用于影响最大化问题。文献 [37] 中，作者结合社区检测和演化算法来求解影响最大化问题。首先，使用社区检测算法将网络划分为多个社区；然后，在每一个社区中选择种子节点；最后，使用演化算法在候选种子中选择最终的种子集。在该算法中，目标函数使用了 2-hop 影响函数。该算法使用了单点交叉和基于单点相似度的变异操作。同样的，该算法采用了一种基于贪婪的局部搜索策略。