[發明專利]基于文化基因算法的社交網絡影響最大化方法

有效

• 申請號: 201410674364.8
• 申請日: 2014-11-21
• 公開（公告）號: CN104361462B
• 公開（公告）日: 2017-09-05
• 發明（設計）人: 公茂果;馬晶晶;沈波;馬文萍;羅恩湖;馬里佳;曾久琳;蔡清;王爽
• 申請（專利權）人: 西安電子科技大學
• 主分類號: G06Q10/06
• 分類號: G06Q10/06;G06N3/12
• 代理公司: 陜西電子工業專利中心61205
• 代理人: 王品華,朱紅星

1.一種基于文化基因算法的社交網絡影響最大化方法，其特征在于包括下列步驟：

(1)輸入目標網絡G＝(V,E)，其中，V表示網絡中的節點集合，E為網絡中邊的集合；

(2)設定傳播概率p和初始激活節點數目K，對于初始激活節點集合A，根據獨立級聯信息傳播形式構建期望傳播值函數EDV，作為待優化的目標函數：

其中，表示初始激活節點集合A的鄰居節點集合，μ為初始激活節點集合A的某一鄰居節點，σ_μ＝|{ω|ω∈A,ωμ∈E}|表示鄰居節點μ連接初始激活節點集合A中的節點個數；

(3)種群初始化：

(3a)設定種群大小為N，對于指定的初始激活節點數目K，根據最大度啟發式方法選出前K個具有最大度的節點，并將其賦給前N/2個個體X₁......X_N/2，每一個體表示為X_i＝{x_i1,x_i2,...x_ij,...,x_iK}，其中x_ij代表第i個個體的第j個元素所選定節點的編號，i∈[1,N/2]，j∈[1,K]；

(3b)從個體X₂到個體X_N/2，對個體中的每一位生成一個隨機概率p_d∈[0,1]，如果p_d＞0.5，則將個體中的該位變換為在這個個體內不重復的節點編號；否則，不進行變換；

(3c)利用隨機方法對后N/2個個體X_N/2+1......X_N進行初始化；

(3d)利用上述步驟(2)中的待優化的目標函數EDV，計算每個個體的期望傳播值，并將擁有最大期望傳播值的個體作為種群的最優個體；

(4)通過進化獲得具有最大優化目標函數值的初始激活節點集合：

(4a)設定種群進化迭代次數T，個體交叉變換概率p_c和變異概率p_m，并令當前迭代次數t＝0；

(4b)選擇父代個體：采用錦標賽競爭機制進行父代個體的選擇，每一次從種群中隨機選擇兩個個體，比較兩個個體的期望傳播值EDV，選擇EDV值較大的個體作為一個父代 個體，重復N次上述的選擇過程，選出N個父代個體；

(4c)交叉變換操作：隨機從父代個體中選擇兩個個體，對其進行單點交叉變換操作，從父代個體1中隨機選擇一個節點，對于該節點以及之后的節點均產生一個介于[0,1]之間的隨機概率，如果隨機概率小于交叉變換概率p_c且父代個體1中不包含父代個體2中的對應節點，則進行對位交叉交換，產生兩個子代個體；否則，不進行交叉變換；

重復N/2次上述交叉變換過程，產生N個子代個體；

(4d)對于上述子代種群中的每一個個體，對其每一位生成一個介于[0,1]之間隨機概率，如果隨機概率小于p_m，則將個體中的該位變換作為這個個體內不重復的節點編號；如果隨機概率大于、等于p_m，則該位不進行變換；

(4e)從經過上述(4c)和(4d)操作后的子代種群中選擇出具有最大EDV值的個體作為最優的子代個體，對其進行局部搜索，產生新的最優子代個體；

(4f)從父代種群和子代種群中選擇前N個最大EDV值的個體作為下一代的種群，用來進行下一次的迭代；比較種群最優個體與上述(4e)過程中產生的新的最優子代個體的EDV值，選擇具有較大EDV值的個體作為當前種群最優個體，令t＝t+1；

(4g)判斷是否終止：如果迭代次數t滿足預先設定的次數T，即獲得了具有最大優化目標函數值的初始激活節點集合，并執行步驟(5)；否則，重復步驟(4b)至步驟(4f)；

(5)輸出步驟(4f)中的種群最優個體所包含的K個節點。