[發(fā)明專利]一種k-核心覆蓋的社團發(fā)現(xiàn)方法

在審

• 申請?zhí)枺?/td>: 201810547801.8
• 申請日: 2018-05-31
• 公開（公告）號: CN108830307A
• 公開（公告）日: 2018-11-16
• 發(fā)明（設(shè)計）人: 王林;李陽
• 申請（專利權(quán)）人: 西安理工大學
• 主分類號: G06K9/62
• 分類號: G06K9/62;G06Q50/00
• 代理公司: 西安弘理專利事務(wù)所 61214
• 代理人: 寧文濤

1.一種k-核心覆蓋的社團發(fā)現(xiàn)方法，其特征在于，通過找到網(wǎng)絡(luò)中節(jié)點重要度最大的前k個節(jié)點形成對網(wǎng)絡(luò)的覆蓋，對節(jié)點相似度較高的覆蓋進行合并，對未覆蓋到的節(jié)點基于模塊度最大進行劃分。

2.根據(jù)權(quán)利要求1所述的一種k-核心覆蓋的社團發(fā)現(xiàn)方法，其特征在于，具體步驟如下：

步驟1、計算網(wǎng)絡(luò)數(shù)據(jù)集中每個節(jié)點的節(jié)點重要度，按節(jié)點重要度的降序?qū)λ泄?jié)點進行排序；

步驟2、根據(jù)網(wǎng)絡(luò)的規(guī)模確定該網(wǎng)絡(luò)的核心節(jié)點個數(shù)k；

步驟3、定義一個閾值β，計算網(wǎng)絡(luò)中每個節(jié)點與各個核心節(jié)點之間的節(jié)點相似度，并與閾值β進行比較，若某一節(jié)點與一核心節(jié)點的節(jié)點相似度大于閾值β，則將該節(jié)點與該核心節(jié)點合并，直至得到k個核心節(jié)點對大部分網(wǎng)絡(luò)的覆蓋集；

步驟4、定義閾值ε，計算各個覆蓋集之間的相似性，即統(tǒng)計任意兩個覆蓋集之間共同節(jié)點，并計算共同節(jié)點數(shù)目占兩個覆蓋集節(jié)點數(shù)目總和的比值，若這個比值大于閾值ε，則對這兩個覆蓋集進行合并，得到一個新的覆蓋集；

步驟5、繼續(xù)重復步驟4中的過程，對覆蓋集進行合并，直至覆蓋集數(shù)目達到最少，將每一個覆蓋集定義為一個社團；

步驟6、對于步驟3中未覆蓋到的節(jié)點，基于模塊度最大進行劃分，最后用模塊度對劃分的結(jié)果進行評估。

3.根據(jù)權(quán)利要求2所述的k-核心覆蓋的社團發(fā)現(xiàn)方法，其特征在于，所述步驟1中節(jié)點重要度的計算方法如下：

其中，H是節(jié)點重要度矩陣，節(jié)點i的度為D_i，節(jié)點的平均度值為w_ij取值為0或1，w_ij取1時表示網(wǎng)絡(luò)中的節(jié)點i和j有邊相連；矩陣中對角線上的元素全部為1表示網(wǎng)絡(luò)中每個節(jié)點對自身的重要度貢獻比值為1。

4.根據(jù)權(quán)利要求2所述的k-核心覆蓋的社團發(fā)現(xiàn)方法，其特征在于，所述步驟2中k值計算方法如下：

其中，n代表網(wǎng)絡(luò)的節(jié)點數(shù)目，k₁和k₂代表兩種方法計算得到的核心節(jié)點數(shù)目，k代表根據(jù)不同的網(wǎng)絡(luò)選用不同的方法確定網(wǎng)絡(luò)的核心節(jié)點數(shù)目，d(v)代表節(jié)點v的節(jié)點重要度值。

5.根據(jù)權(quán)利要求2所述的k-核心覆蓋的社團發(fā)現(xiàn)方法，其特征在于，所述步驟3中節(jié)點相似度的計算方法如下：

其中，i,j分別代表節(jié)點i和節(jié)點j，φ(i)∩φ(j)表示節(jié)點i和節(jié)點j的共同鄰居節(jié)點集合，k(a)表示兩個節(jié)點共同鄰居的節(jié)點的度。

6.根據(jù)權(quán)利要求2所述的k-核心覆蓋的社團發(fā)現(xiàn)方法，其特征在于，所述步驟6中基于模塊度最大的原理劃分節(jié)點的方法為：將未覆蓋到的節(jié)點劃分到步驟5中的各個社團中，并計算加入節(jié)點后的社團的模塊度，將使得某社團模塊度增大最大的節(jié)點加入到該社團中；

其中，模塊度計算方法如下：

其中，A代表網(wǎng)絡(luò)的鄰接矩陣，若節(jié)點i和節(jié)點j有邊相連，A_ij為1，否則為0，k_i和k_j分別表示節(jié)點v_i的入度和節(jié)點v_j的出度，δ為沖擊函數(shù)，取值為0或1，m是網(wǎng)絡(luò)中邊的個數(shù)。

7.根據(jù)權(quán)利要求2～7任一項所述的k-核心覆蓋的社團發(fā)現(xiàn)方法，其特征在于：所述閾值β取值范圍為0.18～0.3。

8.根據(jù)權(quán)利要求8所述的k-核心覆蓋的社團發(fā)現(xiàn)方法，其特征在于：所述閾值ε取值范圍為0.3～0.4。