[發明專利]一種考慮非活躍節點和社區邊界的競爭影響力最大化方法

在審

• 申請號: 202010891298.5
• 申請日: 2020-08-30
• 公開（公告）號: CN112035545A
• 公開（公告）日: 2020-12-04
• 發明（設計）人: 謝曉芹;李家輝;王巍;楊武
• 申請（專利權）人: 哈爾濱工程大學
• 主分類號: G06F16/2458
• 分類號: G06F16/2458;G06Q50/00;G06N20/00
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種考慮非活躍節點和社區邊界的競爭影響力最大化方法，其特征在于，包括以下步驟：

步驟1：輸入社會網絡圖G＝(V,E)，V為社會網絡圖中所有節點的集合，E為社會網絡中所有邊的集合；確定第一競爭者和第二競爭者；

步驟2：利用社區發現算法將社會網絡劃分成n個社區C＝{C₁,C₂,...,C_n}；

步驟3：計算社會網絡圖中每個節點的BI值和每條邊的權重；

對于任意節點v∈V，節點v的BI值BI(v)為：

BI(v)＝outDegree(v)+(1-e^-inf(v))+cimp(v)

其中，outDegree(v)為節點v的出度；inf(v)為節點v施加于所有未激活鄰居節點的影響力之和；cimp(v)為節點v與其他社區之間的連通能力；num(v)為節點v在其所在的社區之外的鄰居節點數量；和分別為社會網絡G中num(v_i)取最小值和最大值時對應節點v_i在其所在的社區之外的鄰居節點數量；

任意兩個節點v_a∈V和v_b∈V之間的邊的權重為：

其中，nb(v_a)和nb(v_b)分別為節點v_a和節點v_b的所有鄰居節點集合；

步驟4：利用種子節點選擇算法從集合V中篩選出第一競爭者的初始種子集合S₁，S₁之外的其余節點都為未激活狀態的節點，構成節點集合S₃，S₃∩S₁＝φ；

步驟5：計算第二競爭者的種子集合S₂；

步驟5.1：從節點集合S₃中選擇BI值最大的節點v_j加入到種子集合S₂中；

步驟5.2：基于種子集合S₂在社會網絡圖G中進行影響力傳播，更新集合S₃中節點的狀態；更新狀態的方法具體為：

步驟5.2.1：若未激活節點v_s的入邊鄰居節點對節點v_s的影響力達到節點v_s的激活閾值即則節點v_s由未激活狀態變為思考狀態；其中，aci(v_s)為節點v_s的入邊鄰居節點中所有激活節點的影響力之和；ini(v_s)為節點v_s的入邊鄰居節點中所有未激活節點的影響力之和；

步驟5.2.2：經過d個時間步數之后，處于思考狀態中的節點v_s進入激活狀態，并選擇是否成為第二競爭者的追隨者；

若則節點v_s成為第二競爭者的追隨者；否則，節點v_s成為第一競爭者的追隨者；

其中，為第一競爭者的追隨者在時刻t+d對節點v_s的影響力之和；為第二競爭者的追隨者在時刻t+d對節點v_s的影響力之和；

其中，為t+d時刻節點v_s的入邊鄰居節點中第一競爭者的追隨者的節點集合；為t+d時刻節點v_s的入邊鄰居節點中第二競爭者的追隨者的節點集合；A_t+d(v_s)為t+d時刻節點v_s的入邊鄰居節點中處于未激活狀態的節點的集合；

步驟5.3：更新集合S₃中所有未激活節點的BI值；

步驟5.4：重復執行k次步驟5.1至步驟5.3，c為設定的啟發參數；

步驟5.5：若f(S₂)f(S₁)，則輸出第二競爭者的種子集合S₂，結束計算；否則，執行步驟5.6；f(·)為邊緣影響力的度量函數，f(S₁)和f(S₂)分別表示集合S₁和S₂在社會網絡圖G上的影響范圍；

步驟5.6：計算每個未激活節點加入集合S₂后的邊緣影響力，取對應邊緣影響力最大的節點加入到集合S₂中；

步驟5.7：更新社會網絡圖G中所有節點的狀態，返回步驟5.5；

步驟6：輸出第二競爭者的種子集合S₂，即目標的廣告推廣用戶。