[發明專利]一種復雜網絡社區數量的估計方法

在審

• 申請號: 201810794522.1
• 申請日: 2018-07-19
• 公開（公告）號: CN109039716A
• 公開（公告）日: 2018-12-18
• 發明（設計）人: 杜航原
• 申請（專利權）人: 山西大學
• 主分類號: H04L12/24
• 分類號: H04L12/24
• 代理公司: 太原市科瑞達專利代理有限公司 14101
• 代理人: 李富元

1.一種復雜網絡社區數量估計方法，其特征在于：該復雜網絡表示為圖的形式，記作網絡G(V,E)，網絡G(V,E)中包含m個網絡節點，記作V＝(v₁,v₂,…,v_m)，其中第i個網絡節點(1≤i≤m)記作v_i；網絡節點之間共形成了n個連接，表現為n條連邊，記作E＝(e₁,e₂,…,e_n)，其中第l條邊(1≤l≤n)記作e_l；確定網絡G(V,E)中所含社區數量及各社區中心節點的過程，包括以下步驟：

S10、計算網絡G(V,E)中的任一網絡節點v_i的內聚度，用于表達該網絡節點對其所屬社區中其它網絡節點的最大聚合性，即網絡社區內部連接的稠密性；

S20、計算網絡G(V,E)中的任一網絡節點v_i的分離度，用于表達該網絡節點與其所屬社區之外網絡節點間的相關性，即社區外部連接的稀疏性：

S30、對于網絡G(V,E)中的任一網絡節點v_i，依據其內聚度和分離度計算網絡節點的中心度，用于描述每個網絡節點對其所屬社區的影響力，中心度越高，則該網絡節點越可能成為社區中心；

S40、計算各網絡節點中心度的Z分數：

S50、利用3σ法則對網絡節點中心度的Z分數進行篩選，生成候選社區中心節點集合；

S60、從候選社區中心節點集合中選擇內聚度和分離度都較大的網絡節點，作為社區中心節點，進行結果輸出。

2.根據權利要求1所述一種復雜網絡社區數量估計方法，其特征在于：所述步驟S10中對于網絡G(V,E)中的任一網絡節點v_i，令NG_i＝{v_j|<v_i,v_j>∈E}表示v_i的鄰居網絡節點構成的集合，將網絡節點v_i的連接度表示為d_i＝|NG_i|，所述網絡G(V,E)任一網絡節點v_i的內聚度的計算包含以下步驟：

S11、計算網絡節點v_i與其各鄰居網絡節點間的相似度，兩網絡節點間的相似度為這兩個網絡節點的公共鄰居網絡節點數，網絡節點v_i與其某一鄰居網絡節點v_j的相似度sim_i,j計算方法如式(1)：

sim_i,j＝|NG_i∩NG_j| (1)

S12、利用式(2)計算網絡節點v_i的內聚度：

其中I_i為網絡節點v_i的內聚度，表示該網絡節點的度及其與鄰居網絡節點的最大相似度。

3.根據權利要求1所述一種復雜網絡社區數量估計方法，其特征在于：所述步驟S20中網絡G(V,E)任一網絡節點v_i的分離度計算方法如式(3)所示：

其中，P_i表示網絡節點v_i的分離度，表示網絡G(V,E)中內聚度比v_i高的網絡節點與v_i間的最大相似度。

4.根據權利要求1所述一種復雜網絡社區數量估計方法，其特征在于：所述步驟S30中網絡G(V,E)中任一網絡節點v_i的中心度定義為其內聚度與分離度的乘積，計算方法如式(4)所示：

R_i＝I_i·P_i (4)。