[發明專利]基于社交網絡層級結構的影響最大化種子集建立方法

有效

• 申請號: 201811037119.0
• 申請日: 2018-09-06
• 公開（公告）號: CN109508415B
• 公開（公告）日: 2021-01-05
• 發明（設計）人: 李侃;李玲玲
• 申請（專利權）人: 北京理工大學
• 主分類號: G06F16/9535
• 分類號: G06F16/9535;G06Q50/00
• 代理公司: 北京正陽理工知識產權代理事務所(普通合伙) 11639
• 代理人: 鮑文娟

1.基于社交網絡層級結構的影響力最大化種子集建立方法，其特征在于：包括以下步驟：

步驟1、輸入社交網絡的節點和邊、目標種子節點數以及傳播概率；其中，信源節點包含在節點內；

其中，信源節點，記為v_s；種子節點數最大值，記為K；傳播概率，記為pp；網絡記為G(V，E)，其中，V表示節點的集合，E表示邊的集合，節點的個數記為n＝|V|；

步驟2、遍歷所有節點，求兩個節點之間的一階鄰近度和二階鄰近度，然后計算其他節點相對于信源節點的緊密程度，最后將計算好的節點緊密程度按照降序排列，具體為以下三個子步驟：

步驟2.1、遍歷所有節點，求一階鄰近度和二階鄰近度，具體地，分別根據公式(1)和(2)求一階鄰近度和二階鄰近度：

其中，S1_ij表示節點v_i和節點v_j之間的一階鄰近度，S2_ij表示節點v_i和節點v_j之間的二階鄰近度；A_ij表示節點v_i和節點v_j之間是否存在邊，如果存在，則A_ij＝1，否則，A_ij＝0；d_i表示節點v_i的度數；N(i)和N(j)分別表示節點v_i和v_j的鄰居節點集合；

步驟2.2、計算其他節點相對于信源節點的緊密程度，具體根據公式(3)計算：

其中，其他節點是指除信源節點v_s以外的網絡節點；緊密程度，記為表示在t步之內從節點v_i游走到節點v_s的概率，初始化當v_i＝v_s時，否則，其中t的取值范圍為從1到T的整數，T表示從節點v_i游走到信源節點v_s的最長步數；當v_i＝v_s時，Q_ij＝0，否則，Q_ij＝p_ij；

其中，p_ij表示節點v_i和v_j之間的轉移概率，具體根據公式(4)計算：

p_ij＝αS1_ij+(1-α)S2_ij (4)

其中，α(α∈[0，1])表示一階鄰近度和二階鄰近度的調參因子；

p_ij相對應的矩陣P就叫做轉移矩陣；Q等同于除Q_si＝0之外的轉移矩陣P；

步驟2.3、將計算好的節點緊密程度按照降序排列，將排序后的節點序列記為L；

步驟3、初始化層級數為1，另各層級的斷點為-1，層級結構的穩定性為0，然后計算所有層級之內，前x個節點的緊密程度的不一致性的最小值，具體為：

層級數記為M，各層級的斷點記為g_Mx，層級結構的穩定性記為FL_M，x的取值范圍為從1到n的整數；根據公式(5)，計算前M個層級之內，前x個節點的緊密程度的不一致性的最小值f_1x：

f_1x＝min{f_{0，x′}+cost(x′+1，x)}，x′＝0，…，x-1 (5)

其中f_0，x′＝0，cost(x′，x)表示擬合從第x′個節點到第x個節點這部分順序的最小殘差，它由公式(6)計算得到：

其中，z＝x，...，x，y(z)表示第z個節點的擬合函數，L_z表示第z個節點的緊密程度，y(z)由公式(7)計算得到：

y(z)＝ωz+b (7)

其中，ω和b分別表示擬合函數的一階系數和常數項，分別由公式(8)(9)計算得到：

其中h表示擬合函數采樣的節點數，h＝x-x′+1；

步驟4、將層級數M自增1，計算M個層級之內，前x個節點的緊密程度不一致性的最小值f_Mx，各層級的斷點g_Mx以及層級結構穩定性FL_M，f_Mx，g_Mx和FL_M分別由公式(10)、(11)和(12)計算得到：

f_Mx＝min{f_M-1，x′+cost(x′+1，x)}，x′＝M-1，…，x-1 (10)

其中，和分別表示M層中，處于同一層級的節點之間的邊數，及處于不同層級的節點之間的邊數，argmin表示取得不一致最小值時的節點序號x′，將其作為前M個層級內，前x個節點的斷點；

步驟5、判斷層級數為M時，網絡結構穩定性是否比層級數為M-1的網絡結構穩定性高，若比前一次高，則記錄更新的層級劃分結果，重復步驟四；否則，停止迭代，層級劃分完成，此時劃分好的網絡層級為level₁，...，level_m，...，level_M，進行步驟六；

步驟6、初始化每個層級的種子節點集合以及整個網絡的種子節點集為空集初始化在前m個層級中，挖掘第k個種子節點的影響程度R[m，k]，即，當m＝0時，R[0，k]＝0，當k＝0時，R[m，0]＝0；初始化在前m個層級中，挖掘第k個種子節點所在層級的符號函數s[m，k]，即，當m＝0時，s[0，k]＝0；當k＝1時，進行步驟7；

其中，每個層級的種子節點集合以及整個網絡的種子節點集分別記為I₁，...，I_m，...，I_M和I；m的取值范圍為從0到M的整數，k的取值范圍為從0到K的整數；

步驟7、計算在前m個層級中，挖掘第k個種子節點的影響程度R[m，k]，計算在前m個層級中，挖掘第k個種子節點所在層級的符號函數s[m，k]記為at_m；在at_m層中，尋找使影響程度增加最大的那個節點v_max作為第k個種子節點，添加到種子集和I中，具體為：

步驟7.1、分別用公式(13)和公式(14)計算在前m個層級中，挖掘第k個種子節點的影響程度R[m，k]，計算在前m個層級中，挖掘第k個種子節點所在層級的符號函數s[m，k]；

R[m，k]＝max{R[m-1，k]，R[M，k-1]+ΔR_m}，R_m[m，0]＝0，R_m[0，k]＝0 (13)

其中，ΔR_m表示在m層中，影響程度的最大增量，由公式(15)計算得到：

ΔR_m＝max{R_m(I_k-1∪{j})-R_m(I_k-1)|j∈level_m} (15)

其中j表示層級level_m中的一個節點，I_k-1表示在第k-1步中，m層所對應的種子節點集合，R_m表示m層所對應的種子節點集合的影響比例，由公式(16)計算得到：

其中，I_k表示第k步，m層所對應的種子節點集合；σ(I_k)表示集合I_k所期望影響的節點個數，它由公式(17)計算得到：

其中，NB(I_k)表示集合I_k的一跳域；r(v)表示網絡中與集合I_k中的節點有邊連接，且在集合I_k中的節點個數；NB(I_k)和r(v)分別由公式(18)和(19)計算得到：

r(v)＝|{u|u∈I_k，uv∈E}| (19)

當m從0自增到M之后，即可得到第k個種子節點所在的層級s[M，k]，記為at_m＝s[M，k]；

步驟7.2、在at_m層中，尋找使影響程度增加最大的那個節點v_max作為第k個種子節點，添加到種子集和I中；

其中，v_max由公式(20)計算得到；

添加v_max到種子集和I中時，分別由公式(21)和(22)進行操作：

I＝I∪{v_max} (22)

步驟8、k自增1，判斷k是否不大于K，如果是，則重復步驟7；否則，進行步驟9；

步驟9、輸出每個層級的種子節點集合I₁，...，I_m，...，I_M以及整個網絡的種子節點集I。