[發明專利]一種融合節點屬性和圖結構的半監督社區發現方法

有效

• 申請號: 201910659962.0
• 申請日: 2019-07-22
• 公開（公告）號: CN110442800B
• 公開（公告）日: 2022-05-20
• 發明（設計）人: 韓啟龍;李寅龍;宋洪濤;張可佳;張海濤;劉鵬;崔寰宇
• 申請（專利權）人: 哈爾濱工程大學
• 主分類號: G06F16/9536
• 分類號: G06F16/9536
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種融合節點屬性和圖結構的半監督社區發現方法，其特征在于，包括：

步驟1：計算m個屬性的信息熵；

步驟2：計算兩個節點i、j的屬性相似度S_a；

步驟2.1：把屬性信息熵標準化，得到m個屬性的權重

步驟2.2：計算兩個節點i、j的屬性相似度S_a；

其中，I_α表示兩個節點i、j之間第α個屬性是否取值相同，如果相同就為1，否則為0；α＝1,2,...,m；

步驟3：計算兩個節點i、j的結構相似度S_s；

其中，N_i為節點i的鄰域集合；

步驟4：計算兩個節點i、j的總相似度ω_ij作為兩個節點i、j之間的權值；

ω_ij＝λS_s+(1-λ)S_a

其中，λ為可調節參數；

步驟5：尋找k個初始社區；

步驟5.1：計算各個節點的度；

步驟5.2：根據節點度的排名取前k個節點作為初始社區中心c_β；β＝1,2,...,k；

步驟5.3：把與初始社區中心c_β相連的點都標記為該社區節點并統計標記節點個數記為l；

步驟5.4：判斷是否存在一個節點同時連接兩個初始社區中心；若存在，則計算該節點與兩個初始社區中心節點的權重把該節點標記為屬于中較大的社區，得到初始社區

步驟6：初始化初始社區矩陣L(0)；

步驟7：結合半監督方法計算出社區劃分矩陣；

步驟7.1：計算最佳劃分矩陣L^*；

其中，μ_∈(0,1)；E為單位矩陣；W為由ω_ij組成的矩陣；D＝diag(d₁,d₂,…,d_n)，

步驟7.2：在未標記的n-l個節點中，把節點x_i＝(x_i1,x_i2,...,x_ik)標記為對應的社區C_β；

步驟8：計算trade-off值分析參數的合理取值范圍；

trade-off＝Density-Entropy

其中，V_β表示第β個社區；|E|表示網絡總邊數；v_p和v_q表示同一個網絡中任意兩個不同節點；|V|表示整個社區網絡中節點的數量；|V_β|表示第β個社區中節點的數量；p_αβμ表示在第β個社區中，第α個屬性類型的某個取值μ占μ_α個取值的比例；

步驟9：根據trade-off和模塊度獲得最優的模塊度及社區發現結果C＝(C₁,C₂,...,C_k)。