<address id="japib"><nav id="japib"></nav></address>

<cite id="japib"></cite>

        基于自適應混沌遺傳算法的影響力最大化研究

        張萌 李維華

        引用本文:
        Citation:

        基于自適應混沌遺傳算法的影響力最大化研究

          作者簡介: 張 萌(1996?),女,云南人,彝族,碩士生,主要研究數據挖掘. E-mail:1184845664@qq.com;
          通訊作者: 李維華, lywey@163.com
        • 中圖分類號: TP301.6

        Influence maximization based on self-adapting chaos genetic algorithm

          Corresponding author: LI Wei-hua, lywey@163.com
        • CLC number: TP301.6

        • 摘要: 目前利用智能算法代替貪婪策略求解種子集影響力的方法極大地縮短了運行時間,但一些智能算法因參數設置困難而導致搜索能力不穩定,達不到預期效果,且多數實驗僅在小型網絡中進行,沒有運用到中大型網絡.針對此不足,提出一種自適應混沌遺傳算法.首先,將一階容斥激活集引入遺傳算法作為適應度函數,目的是在迭代過程中評估種子集的預期影響;然后,利用Logistic混沌序列優化交叉和變異過程中的基因選擇;最后,在自適應變異機制下搜索出最優種子集.在4個真實網絡上的實驗表明,該算法運行效率較高,找到的種子集影響范圍較廣.
        • 圖 1  一個小型網絡

          Figure 1.  A simple network

          圖 2  順序交叉過程

          Figure 2.  The process of sequential crossover

          圖 3  關鍵節點集 $Q$ 取值與影響范圍的變化

          Figure 3.  The variations of influence spread with differet values of Q

          圖 4  算法在不同數據集上的影響范圍

          Figure 4.  Influence spread with different data sets

          圖 5  不同數據集上的算法運行時間對比

          Figure 5.  Comparison of algorithms’ running time on different data sets

          表 1  社交網絡數據集

          Table 1.  The data sets of social network

          數據集節點平均度類型
          FaceBook 4039 88234 43.692 無向
          AstroPh 18772 198110 21.107 無向
          Slashdot 77360 905468 23.409 有向
          E-mail 265214 420045 3.168 有向
          下載: 導出CSV

          表 2  SACGA算法參數設置

          Table 2.  The parameter setting of SACGA

          參數描述
          $N$種群大小4
          $\gamma $交叉概率0.4
          $\lambda $變異概率自適應
          $Q$關鍵節點集$K$
          ${I_{{\rm{max}} } }$最大迭代次數180
          下載: 導出CSV

          表 3  FIEA和IEA的影響范圍對比

          Table 3.  Comparison of influence spread about FIEA and IEA

          數據集FIEAIEA
          FaceBook395.467396.837
          AstroPh1849.5131844.995
          Slashdot1774.0561772.826
          E-mail395.714367.112
          下載: 導出CSV

          表 4  FIEA和IEA的運行時間對比(單位:秒)

          Table 4.  Comparison of running time about FIEA and IEA (Unit:s)

          數據集FIEAIEA
          FaceBook0.1360.728
          AstroPh0.42333.084
          Slashdot0.617103.671
          E-mail0.3625.213
          下載: 導出CSV
          幸运快三
        • [1] 郭靜, 張鵬, 方濱興, 等. 基于LT模型的個性化關鍵傳播用戶挖掘[J]. 計算機學報, 2014, 4: 809-818. DOI:  10.3724/SP.J.1016.2014.00809. Guo J, Zhang P, Fang B X, et al. Personalized key propagation user mining based on LT model[J]. Chinese Journal of Computers, 2014, 4: 809-818.
          [2] Richardson M, Domingos P. Mining knowledge-sharing sites for viral marketing[C]//Proceedings of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Edmonton, Alberta, Canada. 2002: 61-70. DOI: 10.1145/775047.775057.
          [3] Kempe D, Kleinberg J M, Tardos É. Maximizing the spread of influence through a social network[C]// Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Washington, USA. 2003: 137-146. DOI: 10.1145/956750.956769.
          [4] 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 Discovery and Data Mining, San Jose, California, USA. 2007: 420-429. DOI: 10.1145/1281192.1281239.
          [5] Ding J Y, Sun W J, et al. Influnce maximization based on the realistic independent cascade model[J]. Knowledge-Based System, 2019, 191: 105265.
          [6] Jiang Q, Song G, Cong G, et al. Simulated annealing based influence maximization in social networks[C]//Proceedings of the 25th AAAI Conference on Artificial Intelligence, San Francisco, California, USA, 2011: 127-132.
          [7] Cui L, Hu H, Yu S, et al. DDSE: A novel evolutionary algorithm based on degree-descending search strategy for influence maximization in social networks[J]. Journal of Network and Computer Applications, 2018, 103: 119-130. DOI:  10.1016/j.jnca.2017.12.003.
          [8] 錢付蘭, 徐濤, 趙姝, 等. 基于局部概率解的免疫遺傳影響力最大化算法[J]. 計算機科學與探索, 2020, 14(5): 783-791. DOI:  10.3778/j.issn.1673-9418.1905010. Qian F L, Xu T, Zhao S, et al. Local Probability Solution Based Immune Genetic Influence Maximization Algorithm[J]. Journal of Frontiers of Computer Science & Technology, 2020, 14(5): 783-791.
          [9] Gong M, Yan J, Shen B, et al. Influence maximization in social networks based on discrete particle swarm optimization[J]. Information Ences, 2016, 367: 600-614. DOI:  10.1016/j.ins.2016.07.012.
          [10] Liu S J, Chen C Y, e t, a l. An effective simulated annealing for influence maximization problem of online social networks[J]. Procedia Computer Science, 2017, 113: 478-483. DOI:  10.1016/j.procs.2017.08.306.
          [11] Sankar C P, Asharaf S, Kumar K S. Learning from bees: An approach for influence maximization on viral Campaigns[J]. PLos ONE, 2016, 11(12): 168125. DOI:  10.1371/journal.pone.0168125.
          [12] Zhang M, Dai C N, Chris D, et al. Probabilistic solutions of influence propagation on social networks[C]// Proceedings of the 22nd ACM International Conference on Information & Knowledge Management, San Francisco, California, USA.2013: 429-438.DOI: 10.1145/2505515.2505718.
          [13] Pei S, Muchnik L, José S, et al. Searching for superspreaders of information in real-world social media[J]. Scientific Reports, 2014(4): 5547. DOI:  10.1038/srep05547.
          [14] 譚文安, 趙堯. 基于混沌遺傳算法的Web服務組合[J]. 計算機集成制造系統, 2018, 243(7): 238-245. DOI:  10.13196/j.cims.2018.07.024. Tan W A, Zhao Y. Web service composition based on chaos genetic algorithm[J]. Computer Integrated Manufacturing Systems, 2018, 243(7): 238-245.
          [15] Bucur D, Iacca G. Influence maximization in social networks with genetic algorithms[J]. Lecture Notes in Computer Science, 2016, 9597: 379-392. DOI:  10.1007/978-3-319-31204-0_25.
          [16] Zhang K, Du H, Feldman M W. Maximizing influence in a social network: Improved results using a genetic algorithm[J]. Physica A Statistical Mechanics & Its Applications, 2017, 478: 20-30. DOI:  10.1016/j.physa.2017.02.067.
        • [1] 唐善剛 . 容斥原理及在環形錯排計數中的應用*. 云南大學學報(自然科學版), doi: 10.7540/j.ynu.20170470
          [2] 馬曉敏王新 . 基于遺傳算法的BP神經網絡改進. 云南大學學報(自然科學版), doi: 10.7540/j.ynu.2013b4
          [3] 阮永芬黃興周李仕勝趙華 . 遺傳算法擬合變異函數的參數. 云南大學學報(自然科學版),
          [4] 馬永杰馬義德蔣兆遠 . 一種快速遺傳算法的性能分析. 云南大學學報(自然科學版),
          [5] 孫巍郭敏 . 基于自適應形狀先驗的快速圖像分割算法. 云南大學學報(自然科學版), doi: 10.7540/j.ynu.20140296
          [6] 趙云劉惟一 . 一種基于遺傳算法求集中網站的方法. 云南大學學報(自然科學版),
          [7] 李繼東張學杰 . 一種基于遺傳算法多維模糊分類器的構造方法. 云南大學學報(自然科學版),
          [8] 閔文文梅 端代婷婷胡光華 . 基于遺傳算法SVM的基因表達譜數據分析. 云南大學學報(自然科學版), doi: 10.7540/j.ynu.20120663
          [9] 舒紅宇彭來謝鑫尹亮 . 基于遺傳算法的電動代步車用輪轂電機優化設計. 云南大學學報(自然科學版),
          [10] 王雷蔡勁草 . 基于改進多種群遺傳算法的柔性作業車間調度研究. 云南大學學報(自然科學版), doi: 10.7540/j.ynu.20160130
          [11] 吳文斗曹志勇 . 利用優化的遺傳算法解決飼料配方設計問題. 云南大學學報(自然科學版),
          [12] 高思聰劉云 . 能量采集WSN中的自適應機會路由算法研究. 云南大學學報(自然科學版), doi: 10.7540/j.ynu.20150162
          [13] 郭棟鴻譚麗溫潤 . 基于MMSE的自適應灰度形態學鋼軌邊緣檢測算法. 云南大學學報(自然科學版), doi: 10.7540/j.ynu.20190285
          [14] 黃宏運朱家明李詩爭 . 基于遺傳算法優化的BP神經網絡在股指預測中的應用研究. 云南大學學報(自然科學版), doi: 10.7540/j.ynu.20160516
          [15] 陳樹剛張學杰 . 一種基于小波系數自適應加權平均的解剖和功能醫學圖像融合算法. 云南大學學報(自然科學版),
          [16] 趙婷婷梁立高云 . 基于擬拓撲的有限集上拓撲構建遞推算法. 云南大學學報(自然科學版), doi: 10.7540/j.ynu.20130347
          [17] 莊紅林段鵬何磊 . 基于能量分布的自適應整體變分去噪方法. 云南大學學報(自然科學版),
          [18] 楊躍誠鐘汝能孫瑜肖夢雄 . 基于IRT的計算機化自適應測試系統研究. 云南大學學報(自然科學版),
          [19] 張晨光史偉光畢長浩 . 結合自適應高斯濾波的單幅圖像去霧方法. 云南大學學報(自然科學版), doi: 10.7540/j.ynu.20160547
          [20] 陳威張世峰張祝威胡貴妹 . 焦爐集氣管壓力系統的復合自適應PID控制. 云南大學學報(自然科學版), doi: 10.7540/j.ynu.20160597
        • 加載中
        圖(5)表(4)
        計量
        • 文章訪問數:  244
        • HTML全文瀏覽量:  254
        • PDF下載量:  10
        • 被引次數: 0
        出版歷程
        • 收稿日期:  2020-05-09
        • 網絡出版日期:  2020-09-21

        基于自適應混沌遺傳算法的影響力最大化研究

          作者簡介:張 萌(1996?),女,云南人,彝族,碩士生,主要研究數據挖掘. E-mail:1184845664@qq.com
          通訊作者: 李維華, lywey@163.com
        • 云南大學 信息學院,云南 昆明 650500

        摘要: 目前利用智能算法代替貪婪策略求解種子集影響力的方法極大地縮短了運行時間,但一些智能算法因參數設置困難而導致搜索能力不穩定,達不到預期效果,且多數實驗僅在小型網絡中進行,沒有運用到中大型網絡.針對此不足,提出一種自適應混沌遺傳算法.首先,將一階容斥激活集引入遺傳算法作為適應度函數,目的是在迭代過程中評估種子集的預期影響;然后,利用Logistic混沌序列優化交叉和變異過程中的基因選擇;最后,在自適應變異機制下搜索出最優種子集.在4個真實網絡上的實驗表明,該算法運行效率較高,找到的種子集影響范圍較廣.

        English Abstract

        • 隨著Facebook、Instagram和微博的不斷發展,社交網絡逐漸成為信息傳播、商業宣傳的絕佳平臺,一些研究者通過用戶的行為模式進行數據分析,挖掘社交網絡作為信息擴散平臺的潛力. 影響力最大化問題作為社交數據分析下的新興領域,利用最少的資源獲得最大影響,在病毒營銷、信息擴散、輿論監測和醫療保健中發揮著重要作用.

          社交網絡影響最大化問題就是如何選取K個初始節點進行傳播,從而最大程度地影響整個網絡的問題[1]. 2002年Richardson等[2]首先提出影響力最大化問題并將其定義為一個算法問題. 隨后Kempe等[3]證明了在特定傳播模型下的影響力最大化問題是NP難問題,利用離散優化思想發現K個影響增益最大的節點使得最終的影響范圍最大,并提出貪心爬山近似算法. 針對傳統貪心算法耗時過高的缺點,Leskovec[4]利用函數的子模性,提出了CELF優化算法,大大提高時間效率的同時也達到了和傳統貪心算法一樣的影響范圍. Ding等[5]引入一個現實獨立級聯模型RIC,基于該模型提出了3種新的傳播算法R-greedy,M-greedy和D-greedy. 這些改進的貪心算法可以在簡單網絡上顯示出良好的性能,但每次迭代都需要進行上萬次的蒙特卡洛(Monte Carlo,MC)模擬才能得到近似解,在中大規模的復雜網絡中計算量很大. 為了降低影響最大化問題的時間開銷,高效的智能算法為解決影響力最大化的問題開辟了新方向. Jiang等[6]提出了一種預期擴散值度量EDV來近似估計潛在節點的影響力,結合模擬退火算法SA來識別有影響力的節點. 該算法比貪心算法在時間花費上節約了近3個數量級. Cui[7]等提出了一種節點度遞減搜索策略并基于差分進化與遺傳算法提出影響力最大化算法DDSE. 錢付蘭等[8]利用免疫選擇優化遺傳算法,然后再根據局部概率解評估影響力. 實驗表明遺傳算法在影響力最大化的求解中比模擬退火算法在性能和時間上更具有優越性. Gong等[9]等將改進的粒子群算法與二跳局部影響估計器相結合提出DPSO算法. Liu等[10]通過搜索空間劃分機制來增強搜索,提出了基于模擬退火的高效算法SASP. Sankar等[11]通過探索蜂群的搖擺舞行為,提出了一種用于最大化影響力的蜂算法,并在Twitter數據集上驗證了該算法的性能. 此外,Zhang等[12]根據信息傳播的概率性,提出精確概率解影響力估計,利用增量式搜索來解決影響力最大化問題. 以上方法雖然大大提高了算法的運行效率,但除了SASP算法,其余算法只是在簡單網絡中驗證了算法性能,沒有運用到中大型網絡中,而且一些智能算法存在參數設置困難使得節點影響估計不足導致算法性能明顯下降. 如何能在合理的時間消耗很好地平衡求解精度,使得算法在不同規模的網絡中仍然能保持穩定搜索,是影響力最大化問題面臨的一個挑戰.

          本文采用一階容斥激活集(the First-order Inclusion-Exclusion Activation set,FIEA)作為適應度函數評估節點集的預期影響,利用Logistic混沌序列的均勻搜索能力和自適應變異穩定而高效的局部尋優特點,提出一種自適應混沌遺傳算法(Self-Adapting Chaos Genetic Algorithm,SACGA)迭代出最優種子集,然后再將該種子集經過特定的模型傳播后得到最終的影響范圍.

          • 在求解影響力最大化問題時一般將網絡定義為圖 $G{\rm{ = (}}V,E{\rm{)}}$,其中 $V$ 代表節點,$E$ 代表邊即節點間的聯系,從網絡中選出 $K{\rm{(}}1 \leqslant K \leqslant |V|{\rm{)}}$ 個不重復節點組合成一個種子集 $S$,讓 $S$ 在特定的模型下進行影響傳播,得到的影響擴散范圍 $\delta {\rm{(}}S{\rm{)}}$ 要達到最大,${S^*}$ 為最佳種子集,影響力最大化問題的形式化定義為:

            $ {S^*} = arg\;max\;\delta (S),S \subseteq V,|S| = K. $

          • 在影響力最大化問題中,影響傳播模型通常使用獨立級聯(Independent Cascade,IC)模型和線性閾值(Linear Threshold,LT)模型. 這里詳細介紹本文使用的IC模型.

            IC模型是一種概率模型,當節點 $a$ 被激活后,它就能以一定概率去嘗試激活它的鄰居節點 $b$,并且 $a$$b$ 的激活過程獨立,不受任何節點影響. 該模型的傳播過程如下:

            (1)在某個時刻給定一個種子集 $S$$S$ 中的節點均為活躍狀態,$S$ 以外的節點均為非活躍狀態),在該時刻節點 $a$ 被激活后,它就獲得了一次以概率 $P$ 去激活節點 $b$ 的機會.

            (2)若節點 $b$ 有多個鄰居均處于活躍狀態,那么這些鄰居會以任意順序去嘗試激活節點 $b$. 如果節點 $b$ 被成功激活,那么在下一時刻,節點 $b$ 的狀態變為活躍,可以去激活其他未被激活的節點.

            (3)重復過程(1)和(2),直到網絡中沒有可以激活的節點. 當整個過程結束時,得到的是網絡中被激活的節點數.

          • Zhang等[12]基于IC模型,從概率角度出發提出精確概率解來評估節點影響,同時證明了該方法遵循容斥原理(Principle of Inclusion-Exclusion, IE). 利用容斥原理能夠在較少的時間成本內在網絡中找到具有影響潛力的種子集. 在復雜網絡中,給定一個節點 $v$ 所有處于活躍狀態的入度鄰居節點 ${I_v}{\rm{ = \{ }}{w_1},{w_2},...,{w_k}{\rm{\} }}$ 和邊概率 ${P_{{w_k}v}}$,利用容斥原理計算節點 $v$ 的被激活概率為:

            $ \begin{split} {R_v} \!\!= \!\!\! \!\displaystyle \sum\limits_{{w_i} \to v}\! \!\!{{R_{{w_i}}}} \!{P_{{w_i}v}}\! - \! \displaystyle \sum\limits_{\begin{split} {w_i},{w_j} \to v \\ i < j \quad \end{split}} {{\rm{(}}{R_{{w_i}}}{P_{{w_i}v}}{\rm{)}}} {\rm{(}}{R_{{w_j}}}{P_{{w_j}v}}{\rm{)}} {\rm{ + }} \\ \displaystyle \sum\limits_{\begin{split} {w_i},{w_j},{w_l} \to v \\ i < j < l \quad \\ \end{split}} {{\rm{(}}{R_{{w_i}}}{P_{{w_i}v}}{\rm{)}}} {\rm{(}}{R_{{w_j}}}{P_{{w_j}v}}{\rm{)(}}{R_{{w_l}}}{P_{{w_l}v}}{\rm{) + }}\cdots{\rm{ + }} \\ \!\!\!\!{{\rm{( - 1)}}^{k - 1}}{\rm{(}}{R_{{w_1}}}{P_{{w_1}v}}{\rm{)(}}{R_{{w_2}}}{P_{{w_2}v}}{\rm{)}}\cdots{\rm{(}}{R_{{w_k}}}{P_{{w_k}v}}{\rm{)}} . \end{split} $

            簡化后可得到:

            $ R_v^{{\rm{(}}k{\rm{)}}} = R_v^{{\rm{(}}k - 1{\rm{)}}} + {\rm{(1 - }}R_v^{{\rm{(}}k - 1{\rm{)}}}{\rm{)}}{R_{{w_k}}}{P_{{w_k}v}},k = 1,\cdots,n, $

            其中 ,$k$$v$ 的活躍入度鄰居數,${R_v}(0 \leqslant {R_v} \leqslant 1)$ 也就是 $R_v^{(k)}$$v$ 的被激活概率,表示節點 $v$ 被激活的程度.

            具體實例如圖1所示,有一個種子集 $S{\rm{ = \{ 2,3\} }}$,種子集中節點均為活躍狀態,其余節點均不活躍. 節點4有兩個活躍入度鄰居,由公式(3)可計算得到節點4的被激活概率:

            圖  1  一個小型網絡

            Figure 1.  A simple network

            ${R_4} = R_4^{(2)} = R_4^{(1)} + (1 - R_4^{(1)}){R_3}{P_{34}}$

            其中 $R_{\rm{4}}^{(1)} = {R_2}{P_{24}}$ 表示節點2的被激活概率與節點2到節點4邊概率的乘積,再以同樣的方法計算節點5、節點6和節點7的被激活概率,得到 $S$ 的預期影響評估:

            $ \delta {\rm{(}}S{\rm{)}} = {R_4} + {R_5} + {R_6} + {R_7}. $

          • 遺傳算法擅長在全局范圍內搜索,使得算法不陷入局部最優且收斂快. 但遺傳算法的局部搜索能力差,特別是進化后期搜索能力的降低容易導致早熟收斂. 針對這些不足,本文提出一種自適應混沌遺傳算法.

          • 本文選擇實數編碼方式. 任意一個種子集 $S{\rm{ = \{ }}{s_1},{s_2},\cdots,{s_K}{\rm{\} }}$ 表示由 $K$ 個不重復節點組成的集合,$S$ 中的每個元素表示網絡中的節點編號,每個編號都是唯一的.

          • 適應度函數在遺傳算法中表示個體適應環境的能力,可以用此來衡量種群中個體的優劣. 適應度高的個體有更大的幾率在種群中生存下去,而適應度低的個體則會在進化過程中被淘汰. 在本文提出的算法中,適應度用于在迭代過程中評估種子集的預期影響. 在Zhang等[12]研究工作的啟發下,給定 $G{\rm{ = (}}V,E{\rm{)}}$ 和任意種子集 $S$,$S$ 中的節點均為活躍狀態,某個節點的被激活概率為 ${R_v}$,利用容斥激活集(Inclusion-Exclusion Activation set,IEA)可計算種子集的預期影響:

            $ \left\{ {\begin{array}{*{20}{c}} {\sigma {\rm{(}}S{\rm{) = }} \displaystyle \sum\limits_{v \in M} {{R_v}} }; \\ {M = N_s^{{\rm{(}}n{\rm{)}}}/s}. \end{array}} \right. $

            其中, $M$ 表示在集合 $N_s^{{\rm{(}}n{\rm{)}}}$ 中而不在 $S$ 的節點,$N_s^{{\rm{(}}n{\rm{)}}}$ 表示 $S$ 中節點的 $n$ 階鄰域內的所有非激活鄰居節點,當 $n$ 取值為 $\infty $ 時,得到的是種子集 $S$ 的全局網絡預期影響評估,但根據影響力的傳播動力學研究顯示,由于影響衰減,最近鄰域范圍內的影響評估往往是最可靠的[13]. 因此,本文采用FIEA作為適應度函數評估種子集的預期影響:

            $ {\sigma _1}{\rm{(}}S{\rm{) = }}\sum\limits_{v \in N_S^{{\rm{(1)}}}/S} {{R_v}}, $

            其中,$v \in N_S^{{\rm{(1)}}}/S$ 表示種子集 $S$ 中節點的1階鄰域內所有非激活鄰居節點. 至此,選擇K個有影響力的節點被轉化為一個優化問題,旨在選出一個種子集使得預期影響較大.

          • 實際上在真實的網絡中存在大量影響力極低的節點,這些節點并不能作為影響候選節點. 為了提高搜索效率,首先將單個節點看作一個種子集,利用適應度函數計算圖 $G$ 中每個節點的預期影響 ${\sigma _1}{\rm{(}}{v_i}{\rm{)}}$,并將這些節點按預期影響的大小進行降序排列 ${\sigma _1}({v_1}){\rm{ }} > {\sigma _1}({v_2}) > \cdots > {\sigma _1}({v_{|V|}})$,從前 $L$ 個節點中隨機產生初始種群,同時選擇前 $K$ 個節點構造關鍵節點集 $Q$.

          • 混沌的基本思想是根據一定規則讓未知變量從原有混沌空間變換到求解空間,利用混沌本身的隨機性、遍歷性和規律性等特點對解空間進行混沌搜索,從而求得全局最優解[14]. 由一個確定性方程得到,但具有隨機性的活動狀態稱為混沌. 當前的混沌優化大多采用Logistic映射混沌序列,定義如下:

            $ {x_{m + 1}} = \mu {x_m}{\rm{(1}} - {x_m}{\rm{), 0 < }}{x_m} < 1. $

            其中, $\mu $ 為控制參數,當 $\mu \in {\rm{(3}}{\rm{.5\;699\;456,4]}}$ 時系統進入混沌狀態,當 $\mu = 4$ 時的Logistic映射為滿映射,整個系統處于完全混沌狀態,生成的混沌序列具有良好的隨機性. 因此在本文中 $\mu $ 的取值為4,初始 ${x_m}$ 為0到1之間的隨機數.

            采用混沌順序交叉,既能均勻地增加種群的多樣性,也避免了個體基因位上的沖突. 選擇種群內的個體進行配對,兩兩組成父代,然后具體交叉過程如圖2所示.

            圖  2  順序交叉過程

            Figure 2.  The process of sequential crossover

            步驟1 從種群中依次選取父代個體 ${X_1}$${X_2}$,隨機產生混沌初始值,利用公式(8)產生一個混沌值,把該混沌值作為混沌序列的初值生成另一個混沌值,再將這兩個混沌值分別與 $K - 2$ 相乘得到兩個正整數 $g$$h$${\rm{(}}0 \leqslant g \leqslant h \leqslant K - 1{\rm{)}}$ 作為父代截取基因的起始位置和終止位置,截取出的基因稱作交叉基因段.

            步驟2 生成一對個體 ${X_1}'$${X_2}'$,并保證個體中被選中的基因位置與父代 ${X_1}$${X_2}$ 的相同.

            步驟3 找出父代 ${X_1}$ 中與 ${X_2}'$ 交叉基因段中不相同的基因按順序放入 ${X_2}'$ 的空位中生成新子代 ${Y_1}$,${X_2}$${X_1}'$ 重復同樣的操作得到另一個新子代 ${Y_2}$,交叉過程結束.

          • 自適應混沌變異的思想是指當種群中個體的適應度差距逐漸縮小并趨于收斂時,需要增大變異概率來破壞當前種群的穩定性. 在變異時,同樣利用公式(8)迭代生成兩個混沌值 ${x_{m + 1}}$${x_{m + 2}}$,再與 $K - 2$ 相乘得到兩個正整數 $a$$b$${\rm{(1}} \leqslant r \leqslant K{\rm{)}}$,表示個體基因位. 從關鍵節點集 $Q$ 中隨機選取一個節點替換基因位上的基因,生成新的子代,跳出當前最優,避免算法早熟. 而當種群中個體的適應度差距較大時,應降低變異概率,使算法趨于收斂. $\{ {S_1},{S_2},\cdots,{S_N}\}$ 表示一個種群,N為種群大小,${S_j}$ 表示種群中的某一個體,個體變異概率的選擇為:

            $ \lambda = \left\{ {\begin{array}{*{20}{c}} {{\sigma _{\rm{1}}}{\rm{(}}{{\rm{S}}_j}{\rm{) > }}\dfrac{{ \displaystyle \sum\limits_{i = 1}^N {{\sigma _{\rm{1}}}{\rm{(}}{{\rm{S}}_i}{\rm{)}}} }}{N},{\rm{(0,0}}{\rm{.1)}}}&{};\\ {{\sigma _{\rm{1}}}{\rm{(}}{{\rm{S}}_j}{\rm{)}} \leqslant \frac{{ \displaystyle \sum\limits_{i = 1}^N {{\sigma _{\rm{1}}}{\rm{(}}{{\rm{S}}_i}{\rm{)}}} }}{N},{\rm{(0}}{\rm{.1,0}}{\rm{.8)}}}&{}. \end{array}} \right. $

          • 算法1 描述計算節點集的預期影響函數 ${\sigma _{\rm{1}}}{\rm{(}}S{\rm{)}}$

            輸入:$G{\rm{ = (}}V,E{\rm{)}}$,邊概率 $P$,種子集 $S$

            輸出:種子集 $S$ 的預期影響

            步驟1  種子集中節點的激活概率初始化為1,網絡中其余節點的激活概率初始化為0;

            步驟2  找出種子集S中節點的n個一階鄰居節點;

            步驟3  利用公式(3)計算得到每個鄰居節點的激活概率;

            步驟4  由公式(7)得到種子集S的預期影響.

            算法2  描述自適應混沌遺傳算法SACGA

            輸入:$G = (V,E)$,邊概率 $P$,種群大小 $N$,種子集大小 $K$,交叉概率 $\gamma $,迭代次數 ${I_{{\rm{max}}}}$

            輸出:最佳種子集 ${S_{{\rm{best}}}}$

            步驟1  利用適應度函數 ${\sigma _1}$ 計算 $G$ 中所有節點的影響分數,從前 $L$ 個節點中隨機生成 $N$ 個大小為 $K$ 的個體組成初始種群 $S = \left\{ {{S_1}} \right.,{S_2},...,\left. {{S_N}} \right\}$,同時選取前 $K$ 個節點構造關鍵節點集 $Q$;

            步驟2  從初始種群中選出初始最優解 ${S_{{\rm{best}}}}$;

            步驟3  開始進行種群迭代;

            步驟4  依次從當前種群中選取兩個個體作為父代,如果當前父代的 $\gamma $ 滿足交叉條件就隨機產生混沌初始值 ${x_m}$,由公式(8)計算得到兩個混沌隨機數 ${x_{m + 1}}$${x_{m + 2}}$,將兩個隨機數分別與(K?2)相乘得到 $g$$h$,根據 $g$,$h$ 進行基因位順序交叉. 如果不滿足交叉條件,則直接進入新種群;

            步驟5  得到交叉后的新種群 $N'$;

            步驟6  在新種群 $N'$ 中的個體j,根據公式(9)產生變異概率 $\lambda $,如果 $\lambda $ 滿足變異條件,隨機產生初始混沌值 ${x_m}$,由公式(8)迭代生成 ${x_{m + 1}}$${x_{m + 2}}$,將兩個隨機數分別與(K?2)相乘得到 $a$$b$. 從Q中隨機選擇節點與 $a$$b$ 上的基因進行交換,如果 $\lambda $ 不滿足變異條件,則進入下一階段;

            步驟7  如果 ${\sigma _1}{\rm{(}}{S_j}{\rm{) > }}{\sigma _1}{\rm{(}}{S_{{\rm{best}}}}{\rm{)}}{S_{{\rm{best}}}} = {S_j}$;

            步驟8  得到變異后的種群;

            步驟9  更新種群,如果迭代次數小于 ${I_{{\rm{max}}}}$,跳至步驟3,否則跳至下一階段;

            步驟10  迭代完成后輸出最佳種子集 ${S_{{\rm{best}}}}$.

            $D{\rm{( - )}}$ 為節點平均度,${I_{{\rm{max}}}}$ 為最大迭代次數,$K$ 為種子集大小. 算法1的時間復雜度為 $O{\rm{(}}nKD{\rm{( - ))}}$. 算法2產生初始種群的時間復雜度為 $O{\rm{(}}nKD{\rm{( - )) + }} O{\rm{(}}NnKD{\rm{( - ))}}$,迭代過程的時間復雜度為 $2O{\rm{(}}NK{I_{{\rm{max}}}}{\rm{) + }} O{\rm{(}}N{I_{{\rm{max}}}}{\rm{) + }}O{\rm{(}}NnKD{\rm{( - )}}{I_{{\rm{max}}}}{\rm{)}}$,因此最壞情況下SACGA算法的時間復雜度為 $O{\rm{(}}NnKD{\rm{( - )}}{I_{{\rm{max}}}}{\rm{)}}$.

          • 本文利用4個真實的網絡數據集(數據均來源于http://snap.stanford.edu/data)進行實驗結果的對比和分析,驗證所提一階容斥激活集FIEA和自適應混沌遺傳算法SACGA的有效性.

          • 網絡數據集如表1所示.

            數據集節點平均度類型
            FaceBook 4039 88234 43.692 無向
            AstroPh 18772 198110 21.107 無向
            Slashdot 77360 905468 23.409 有向
            E-mail 265214 420045 3.168 有向

            表 1  社交網絡數據集

            Table 1.  The data sets of social network

          • 為了驗證SACGA的有效性,本文選取4個具有代表性的算法與SACGA進行對比,邊概率 $P$ 統一設置為0.01. 其中SAEDV算法的參數為初始溫度 ${T_i} = 500\;000$,結束溫度 ${T_f} = 100\;000$,降溫系數 $\Delta T = 2\;000$ 和外循環 $q = 10$;DDSE算法參數為種群大小 $N = 10$,種群多樣性 $div = 0.6$,交叉概率 $\gamma = 0.4$,變異概率 $\lambda = 0.1$,迭代次數為200次;GA算法的參數設置為種群大小 $N = 10$,交叉概率 $\gamma = 0.4$,變異概率 $\lambda = 0.1$,迭代次數180次;SACGA-N是在SACGA下利用 $n = \infty $ 時的IEA函數尋找種子集的算法,其參數設置與SACGA相同. 上述算法的結果均由運行10次的平均結果得出. 所有代碼使用Python3編寫,實驗在Windows(Intel Corei5.2.3 GHz,8 GB內存)下進行.

            關鍵節點集 $Q$ 的設置使得算法能夠跳出當前最優,以便尋得更優秀的個體,從而加速算法收斂. 如圖3所示,在4個數據集中,當 $Q$ 取值為 $K$ 時,影響范圍達到最大,隨著 $Q$ 取值不斷增大,影響范圍呈下降趨勢,在FaceBook和E-mail數據集上尤為明顯. 因此,本文關鍵節點集 $Q$ 的取值為 $K$. 此外,為了提高時間效率,將種群大小設置為4,SACGA算法的具體參數設置如表2所示.

            參數描述
            $N$種群大小4
            $\gamma $交叉概率0.4
            $\lambda $變異概率自適應
            $Q$關鍵節點集$K$
            ${I_{{\rm{max}} } }$最大迭代次數180

            表 2  SACGA算法參數設置

            Table 2.  The parameter setting of SACGA

            圖  3  關鍵節點集 $Q$ 取值與影響范圍的變化

            Figure 3.  The variations of influence spread with differet values of Q

          • 評價影響力最大化算法的性能通常使用影響傳播范圍和運行時間這兩個常規指標. 影響傳播范圍指利用影響力最大化算法尋找到的種子集在特定傳播模型下的影響范圍大??;運行時間即算法尋找到最優種子集所花費的時間.

          • 本文利用FIEA評估種子集的預期影響以便選出最優種子集. 為了驗證該方法的有效性,選取 $K$ 為50的種子集在FIEA和IEA上進行影響范圍和運行時間的對比. 如表3所示,除了在FaceBook數據集上利用IEA進行評估選出的種子集在影響范圍上比FIEA大0.34%,在其它3個數據集上,利用FIEA評估出的種子集產生的影響范圍均比IEA大0.24%,0.069%和7.22%. 說明利用FIEA評估種子集的預期影響是一種可靠的方法. 同時本文給出了利用FIEA和IEA計算一個種子集預期影響的運行時間對比,如表4所示,在4個數據集上FIEA只需要不到1 s的時間就能計算出大小為50的種子集的預期影響,而IEA則需要幾十秒甚至103.671 s才能計算出一個種子集的預期影響,相比起IEA,FIEA節省了很多時間,是提高算法效率的一個有效途徑. 因此,利用FIEA評估種子集的預期影響是合理且高效的.

            數據集FIEAIEA
            FaceBook395.467396.837
            AstroPh1849.5131844.995
            Slashdot1774.0561772.826
            E-mail395.714367.112

            表 3  FIEA和IEA的影響范圍對比

            Table 3.  Comparison of influence spread about FIEA and IEA

            數據集FIEAIEA
            FaceBook0.1360.728
            AstroPh0.42333.084
            Slashdot0.617103.671
            E-mail0.3625.213

            表 4  FIEA和IEA的運行時間對比(單位:秒)

            Table 4.  Comparison of running time about FIEA and IEA (Unit:s)

          • 本文的影響范圍是指種子集經過IC模型傳播后得到的種子集在一個網絡中激活的節點數目,激活的節點數越多,影響范圍越大,算法性能也越好. 由于傳播過程中的隨機性,將各算法選出的最優種子集以固定傳播概率 $P = 0.01$ 在IC模型下進行10000次的蒙特卡洛模擬,并在圖4中給出了5個算法在不同種子集大小下的平均影響范圍.

            圖  4  算法在不同數據集上的影響范圍

            Figure 4.  Influence spread with different data sets

            圖4所示,整體來看,SACGA在4個數據集中的表現最好,性能也最穩定,而GA的表現最差. 在FaceBook和E-mail這兩個數據集中SACGA明顯領先其它算法,當 $K = 50$ 時,在E-mail數據集中SACGA的影響范圍比DDSE、SAEDV、GA和SACGA-N大22.76%,5.06%,280.09%和7.79%. 需要注意的是,根據全局預期影響選擇種子集的算法SACGA-N的性能并沒有想象中的好,雖然在FaceBook和Slashdot數據集中,SACGA-N的性能僅次于SACGA,但在AstroPh數據集上,當種子集大小為20和30時,SACGA-N的影響范圍比SAEVD和DDSE分別小了0.67%和0.3%,0.5%和0.26%. 此外,同樣在FaceBook和Slashdot數據集中,當 $K < 30$ 時,SAEDV的性能落后于DDSE,在FaceBook數據集中尤為明顯,但隨著 $K > 30$,SAEDV的性能逐漸優于DDSE,并且在AstroPh和E-mail數據集上,SAEDV的性能明顯優于DDSE. 在4個數據集中可以看到,DDSE后期搜索能力明顯不足,說明基于度的方法在搜索過程中還是存在一定的局限性,特別是在稀疏網絡中. GA算法性能相比其它算法性能差的原因可能是算法沒有跳出全局最優導致搜索能力不足,不能尋找到優秀的種子集. 綜上所述,相比起其它算法,SACGA在搜索時能跳出當前最優,并且表現良好,性能也較穩定.

          • 為了驗證算法的高效性,本文給出5個算法在4個數據集中尋找到50個最佳種子節點的運行時間對比,如圖5所示,GA的時間效率最高,但GA性能最差. DDSE的運行時間也較短,但算法性能也不穩定. 而SAEDV由于要進行數萬次的迭代,所以網絡規模越大,耗時也越多. 雖然SACGA的運行時間比GA和DDSE的多,但其產生的影響范圍均比這兩個算法大,可以彌補在時間上的不足. 相比起SAEDV,SACGA在4個數據集中的時間效率提高了217.87%,174.68%,197.71%和205.02%,節省了大量時間成本. 而SACGA-N要對種子集中的每一個節點進行全局預期影響估計,所以非常耗時,在規模較小的FaceBook數據集中找到 $K = 50$ 的種子集都需要1612.471453秒,高額的時間成本在數據量較大的網絡中并不能成為一個合理的解決方案. 因此,實驗結果表明,本文提出的SACGA能在影響范圍和時間成本上有較好的平衡.

            圖  5  不同數據集上的算法運行時間對比

            Figure 5.  Comparison of algorithms’ running time on different data sets

          • 本文利用一階容斥激活集作為適應度函數評估種子集的預期影響,提出一種自適應混沌遺傳算法SACGA. 通過單個節點的影響力構造關鍵節點集,利用Logistic混沌序列均勻搜索和自適應變異來增強算法的局部尋優能力,加快收斂. 在4個真實數據集上的實驗表明,SACGA在影響范圍和運行時間兩個指標上都有良好表現,驗證了該算法的穩定性和高效性. 現有智能算法求解影響力最大化問題的方法還有很大的改進空間,如何合理設置初始種群和更好地改進算法設計,使得算法更加高效,也是需要進一步探究的問題.

        參考文獻 (16)

        目錄

          /

          返回文章
          返回