[發明專利]一種基于庫侖力模型求解社會網絡影響力問題的方法

有效

• 申請號: 202010164598.3
• 申請日: 2020-03-11
• 公開（公告）號: CN111339444B
• 公開（公告）日: 2022-10-04
• 發明（設計）人: 樂光學;陳光魯
• 申請（專利權）人: 嘉興學院
• 主分類號: G06F16/9536
• 分類號: G06F16/9536;G06Q50/00
• 代理公司: 桂林市華杰專利商標事務所有限責任公司 45112
• 代理人: 楊雪梅

1.一種基于庫侖力模型求解社會網絡影響力問題的方法，其特征在于，包括如下步驟：

1)構建社交網絡圖：G＝(V，E)，其中V為節點的集合，E為邊的集合；

2)獲取傳播概率：在面向社會網絡時，充分考慮真實社會網絡中傳播概率P_ij生變化因素，通過使用庫侖定律，加入信任因素與節點數量動態變化因素求解動態影響力的初始傳播概率由于后期傳播過程中存在激活節點疊加現象，故將動態影響力的傳播概率構建為

3)建立影響力傳播模型：基于IC模型進行改進，構建DSC-TR模型，該模型依據社會網絡拓撲結構構建節點自身影響力，結合社會網絡動態變化因素與信任因素，同時利用庫侖定律與社會網絡的相似關聯性構造節點間影響力函數，根據節點自身影響力與節點間影響力計算出傳播概率P_ij；

4)定義動態積極影響力最大化(DPIM)問題：根據步驟3)構建的DSC-TR模型，進一步優化社會網絡影響力最大化問題，即提出DPIM問題；

5)執行RG-DPIM算法：利用隨機性運行時間短的特性與貪心算法近似性高的特點相結合，根據DSC-TR模型得傳播機制求解DPIM問題；

經過上述步驟，完成了社會網絡影響力最大化問題優化求解；

步驟2)中，所述的獲取傳播概率，具體包括如下步驟：

2-1)節點自身影響力計算：構建節點i自身影響力α_i模型為：

上述公式(1)中，m代表傳播跳數，代表節點i中h層的鄰居節點數目，代表對應的出度，表示社會網絡中節點h層的鄰居節點數目；

2-2)節點間影響力計算：將社會網絡節點類比為電荷，則電荷量代表節點自身影響力，電荷之間存在的庫侖力代表節點間影響力，將其定義為節點間社會庫侖力，其庫侖力方向代表影響傳播擴散或抑制，則兩個節點i、j之間的社會庫侖力計算公式如下：

上述公式(2)中，a_i代表節點i的自身影響力，a_j代表節點j的自身影響力，F_ij代表兩個節點i、j的社會庫侖力，r表示兩節點之間的最短路徑，k表示社會庫侖系數；

2-3)動態影響力傳播概率計算：結合社會庫侖力的疊加計算方法，提出疊加社會庫侖力，疊加社會庫侖力充分考慮前驅節點的影響力，當前驅節點數量增加或者減少時，疊加社會庫侖力會發生相應的動態變化，故節點i的疊加社會庫侖力β_i表示為：

上述公式(3)中，l為i的前驅節點；

設節點i的傳播影響力表示為γ_i，具體形式如下所示：

γ_i＝α_i+β_i (4)

根據γ_i大小可以將傳播影響力劃分為積極傳播影響力、堵塞傳播影響力兩種類型，其中積極傳播影響力滿足γ_i＞0，堵塞傳播影響力滿足γ_i＜0；則動態影響力初始傳播概率如下所示：

其中，γ_v表示社會網絡中節點自身影響力；

社會網絡影響力傳播過程中，存在激活節點重復疊加現象，針對該現象將初始時刻后動態影響力的傳播概率改為：

上述公式(6)中，I代表i的鄰居節點集，N_I分別表示I內處于激活狀態的節點數目與I的總節點數目；

步驟3)中，所述的DSC-TR模型，其傳播機制如下：

3-1)假設社會網絡中節點包括激活狀態、未激活狀態和堵塞狀態；其中，激活狀態表示用戶接收到該信息且會轉發，未激活狀態表示用戶未接收到該信息且不會轉發，堵塞狀態表示用戶接收到該信息且不會轉發；

3-2)網絡初始化時，除信源節點外，所有節點均處于未激活狀態，信源節點以初始傳播概率激活或堵塞未激活狀態鄰居節點；

3-3)若當前節點被信源節點激活時，當前節點由未激活狀態變為激活狀態或堵塞狀態，激活狀態的當前節點將會以傳播概率進行之后的傳播過程；

3-4)每次更新激活或堵塞節點，重復步驟3-3)，直至社會網絡中所有節點不再進行激活或堵塞行為；

步驟5)中，所述的RG-DPIM算法，包括如下步驟：

5-1)初始化：任意選擇k個初始種子節點集合S′；

5-2)計算初始種子節點集合S′影響力：對Influ_positive(S′)進行計算；

5-3)計算更換種子節點后種子節點集合S″影響力：隨機選取除種子節點外的節點更換種子節點，對Influ_positive(S″)進行計算；

5-4)計算更換后影響力增益：對比Influ_positive(S′)與Influ_positive(S″)，影響力增益的計算公式為：

Δ(S)＝Influ_positive(S″)-Influ_positive(S′)

5-5)選擇種子節點：根據增益的正負來判斷是否保留當前種子節點，當增益為正值時，即Δ(S)＞0時，保留當前種子節點；反之，當Δ(S)＜0時，丟棄當前種子節點；

5-6)對步驟5-2)-步驟5-5)重復迭代N次，以增加所得結果的準確性。

2.根據權利要求1所述的一種基于庫侖力模型求解社會網絡影響力問題的方法，其特征在于，步驟4)中，所述的DPIM問題，定義如下：

根據DSC-TR模型傳播機制以及節點的信任關系，在社會網絡圖G＝(V，E)內獲取節點數目為k的種子節點集合S，并保證達到積極影響力下激活種子節點數目的最大值，具體公式表示為：

Influ_positive(S)＝argmax_{s∈V,|S|＝k}σ(S) (7)

上述公式(7)中，σ(·)表示影響擴散函數，σ(S)表示在DSC-TR模型下被積極影響力激活的節點數量。