[發明專利]一種基于社區度和結構洞的影響力最大化方法

在審

• 申請號: 202110890795.8
• 申請日: 2021-08-04
• 公開（公告）號: CN113592663A
• 公開（公告）日: 2021-11-02
• 發明（設計）人: 許國艷;莊天益;黃靜;張琦睿
• 申請（專利權）人: 河海大學
• 主分類號: G06Q50/00
• 分類號: G06Q50/00;G06Q10/04
• 代理公司: 南京蘇高專利商標事務所(普通合伙) 32204
• 代理人: 張華蒙

1.一種基于社區度和結構洞的影響力最大化方法，其特征在于：包括如下步驟：

(1)社區劃分：將初始社交網絡定義為G(V,E)，定義社區個數為S作為初始的種子節點集；根據社區聚集系數劃分社區，識別并選取社區間的邊界連接節點；

(2)社區內種子節點篩選：在社區內部：通過算法篩選部分種子節點，以網絡效率反映的聯通效率和節點自身度中心性以及受關注節點提升的影響力，共同衡量節點的最終影響力，以此來篩選種子節點；

(3)社區邊界種子節點篩選：從邊界點中篩選剩余部分的種子節點，算法在篩選社區邊界節點中的種子節點時，在基于社區度的評價標準中加入了改進的結構洞評價指標，用以提高篩選節點的準確性，并將兩次篩選的種子節點合并加入到最終的種子節點集合；

(4)選取種子節點；若在網絡中選取k個節點，在社區中選取的種子節點數為(k×α)，選取k′個影響力最高的社區邊界種子節點，則k′＝k-k×α，社區中選取的種子節點和社區邊界選取的種子節點共同構成種子節點集。

2.根據權利要求1所述的一種基于社區度和結構洞的影響力最大化方法，其特征在于：所述的步驟(1)，包括如下步驟：

步驟1.1：社區的劃分以社區的聚集系數作為參考標準，社區的聚集系數取決于該社區內所有節點的聚集系數的和除以社區節點數的比值；社區的聚集系數：

g(i)為節點的聚集系數，公式為：

其中i表示網絡中節點的編號，n表示網絡中節點的最大編號，g(i)表示為節點的聚集系數；E(i)表示節點i的鄰居節點之間存在的連接邊數；ME(i)表示為節點i的鄰居節點之間可能形成的最大的連接邊數；因此推斷出g(i)的取值范圍是0到1；

步驟1.2：合理地分配社區內種子節點和社區邊界種子節點的占比，提出比例系數α，α∈(0,1)；設在網絡中選取k個節點，令在社區中選取的種子節點數為(k×α)；α的取值與社區的個數相關，表示為

其中S表示劃分的社區個數。

3.根據權利要求2所述的一種基于社區度和結構洞的影響力最大化方法，其特征在于：所述的步驟(2)，包括如下步驟：

步驟2.1：計算各社區規模占比，并構建貢獻矩陣，在矩陣M中節點i與節點j的連接關系為m_ij，關聯關系為C_ij，節點j對節點i貢獻比例為m_ij*C_ij，則網絡中各節點的關注節點的貢獻比例用矩陣表示為H，表達式為：

矩陣H中的每一行為節點i的所有下屬節點的貢獻比例描述，節點i與每列節點的關聯關系用鄰接矩陣元素m_ij表示；

步驟2.2：構建中心性矩陣I；在有向網絡中，以節點i的入度為分子，節點i的出入度之和作為分母，兩者相除的結果作為有向網絡中的度中心性衡量標準；節點i在有向網絡中的度中心性衡量標準計算公式為：

degⁱⁿ(i)表示節點i的入度，deg^out(i)表示節點i的出度，則構建中心性矩陣的表達式如下：

步驟2.3：利用中心性矩陣I，構建HC矩陣，矩陣HC用于修飾節點i的下屬節點給予影響力的提升部分，HC矩陣節點自身的度中心性矩陣相加則能夠給出網絡中每個節點的局部影響力表示，記為H_RC，其中H_RC＝HC+I；HC矩陣和H_RC矩陣表達式為：

h為各節點的關注節點的貢獻比例，m_ij為節點i與節點j的連接關系，節點i與節點j的關聯關系為C_ij，i表示網絡中節點的編號，n表示網絡中節點的最大編號；

步驟2.4：計算節點影響力。

4.根據權利要求3所述的一種基于社區度和結構洞的影響力最大化方法，其特征在于：所述的步驟2.4，以節點i計算，節點的影響力K(i)＝αh_rc(i)+(1-α)E(i)，E(i)為節點i的網絡效率；比例因子α用來分配網絡效率值和關聯關系值的比重；并從節點中選取(k×α)個影響力最高的節點，將節點加入到篩選的種子節點中。

5.根據權利要求3所述的一種基于社區度和結構洞的影響力最大化方法，其特征在于：所述的步驟(3)，包括如下步驟：

步驟3.1：計算p_iq表達式；p_iq代表相對于總精力而言節點i為維護和節點q連接關系投進精力所占的比例，節點i的鄰居節點為維護其二階鄰居節點節點j的關系而投入的精力與節點i為維護其所有二階鄰居節點而投入的精力的比值為a_iq為i到q的連通度；若i到q有鏈接，則a_iq為1，否則為0；

步驟3.2：計算m_jq，代表節點j為維護和節點q的連接關系投進的精力和節點j為維護其他節點的連接關系投進最大精力的比值m_jq＝p_jq/maxp_jw，w∈N(j)，N(j)表示與節點i有直接連接關系的鄰居節點集合；

步驟3.3：獲取結構洞評價指標，網絡中節點i的結構洞效率指標計算方式如公式所示：

其中N(i)表示與節點i有直接連接關系的鄰居節點集合，j為節點i的直接鄰居節點，q為節點i和j的共同鄰居，n_i表示節點i所處網絡的規模，m_jq代表節點j為維護和節點q的連接關系投進的精力和節點j為維護其他節點的連接關系投進最大精力的比值；

步驟3.4：設節點i的鄰居節點數為l(i)，則節點i為維護其二階鄰居節點j的關系而投入的精力為：R(i)＝∑_j∈N(i)l(j)；根據經典算法，結合一階鄰居與二階鄰居，計算結構洞對鄰居節點投入精力比例公式為：

其中v為節點i的鄰居節點，N(i)表示與節點i有直接連接關系的鄰居節點集合；∑_v∈N(i)R(v)為節點i為維護所有二階鄰居節點而投入的精力；

步驟3.5：將T_ij代入到得到最終i節點的結構洞的評價指標表達式為下列公式所示：

其中j，v為節點i的鄰居節點，N(i)表示與節點i有直接連接關系的鄰居節點集合，q為節點i和j的共同鄰居，n_i表示節點i所處網絡的規模，m_jq代表節點j為維護和節點q的連接關系投進的精力和節點j為維護其他節點的連接關系投進最大精力的比值；

步驟3.6：考慮主要從社區的邊界節點處選取候選節點，將邊界節點的度、邊界節點連接的社區數以及這些社區的規模均值三者疊加，結合結構洞評價指標，共同構成社區度值表達式：

其中EF(i)代表節點i的結構洞效率指標值，ODeg(i)為節點i所連接的社區數，n_i表示節點i所連接的社區個數，SC(u)表示節點u所在社區的規模(所包含的節點數)，N(i)是指節點i所連接的社區。