《中國人工智能學會通訊》——8.24 基于演化優化的網絡影響最大化

影響最大化問題是社交網絡分析中一個重要的研究問題。影響最大化是為了找到一個在網絡中有最大影響力的節點集合。影響最大化在現實生活中有着廣泛的應用，如社交媒體中廣告的投放。

影響最大化被 Kempe、Kleinberg 和 Tardos模組化為一個離散的優化問題。在獨立級聯模型中，影響最大化問題被證明是一個 NP-hard 問題。文獻[34] 提出了一種基于集合編碼的演化算法 (SGA) 來優化獨立級聯模型中的期望影響值 。在該算法中，染色體使用節點集合表示，其中每一個基因表示一個目标節點。在該算法中，采用的遺傳算子非常簡單。交叉操作中，首先從父代染色體中随機選擇兩個相同大小的子集；然後，交換這兩個子集得到兩個子代染色體。該算法采用了随機變異操作。在目标函數的計算中，使用了蒙特卡洛模拟，但是蒙特卡羅模拟并不高效。

在文獻 [35] 中，一個機率模型被用于評價獨立級聯模型的影響力。為了優化該模型，作者提出了一種基于演化優化的影響最大化算法（MAGA）。MAGA 采用了與 SGA 一樣的個體表示方法。Tsaiet al [36] 通過結合演化算法和貪婪算法提出了一種改進的 MAGA 算法。在該算法的交叉操作中，首先對父代染色體取并集，然後去除并集中影響力小的節點，進而得到子代染色體。同時該算法采用了一種基于貪婪算法的局部搜尋來提高算法的品質。

為了減小貪婪算法的計算代價，社群檢測被用于影響最大化問題。文獻 [37] 中，作者結合社群檢測和演化算法來求解影響最大化問題。首先，使用社群檢測算法将網絡劃分為多個社群；然後，在每一個社群中選擇種子節點；最後，使用演化算法在候選種子中選擇最終的種子集。在該算法中，目标函數使用了 2-hop 影響函數。該算法使用了單點交叉和基于單點相似度的變異操作。同樣的，該算法采用了一種基于貪婪的局部搜尋政策。