[發(fā)明專利]一種基于大規(guī)模網絡進行高效聚類方法

在審

• 申請?zhí)枺?/td>: 201810767101.X
• 申請日: 2018-07-13
• 公開（公告）號: CN108960335A
• 公開（公告）日: 2018-12-07
• 發(fā)明（設計）人: 寧兆龍;馮玉凡;于碩;夏鋒
• 申請（專利權）人: 大連理工大學
• 主分類號: G06K9/62
• 分類號: G06K9/62
• 代理公司: 大連理工大學專利中心 21200
• 代理人: 溫福雪;侯明遠

1.一種基于大規(guī)模網絡進行高效聚類方法，其特征在于，步驟如下：

步驟1)：聚類結果要求的不同，確定網絡劃分的條件

給出四個條件包括節(jié)點和子圖兩個方面的連接屬性，并根據選擇的條件對大規(guī)模網絡進行初始切割，得到網絡切割之后的子圖集合；

對于無向無權網絡G＝(V,E)，定義網絡鄰接矩陣為H＝{h_i,j}_n×n，定義為G的一個劃分G_i,i∈[1,k]，表示網絡中的一個子圖；四個條件定義如下：

條件一：

條件二：

條件三：

條件四：

條件一和條件二從節(jié)點方面保證某子圖內部節(jié)點具有高度的內聚性，條件三和條件四從子圖的整體角度對子圖分割進行限制；條件一把網絡切割成許多規(guī)模較小的子圖，而條件四則最終生成少量規(guī)模較大的子圖；條件二和條件三則的切割結果則介于以上二者之間；根據具體聚類結果的要求不同，對條件進行選擇；

針對選定的切割條件，采用啟發(fā)式策略，選取網絡中度最大的節(jié)點作為根節(jié)點，并對其鄰居節(jié)點根據切割條件進行迭代歸屬劃分，最終得到給定輸入網絡子圖集；

當某一次迭代結束，分為兩種情況：第一種無候選節(jié)點，即上一次劃分的節(jié)點沒有未劃分的鄰居節(jié)點，此時則在原網絡中選擇一個新的根節(jié)點，該節(jié)點需滿足，節(jié)點與新子圖連接的邊數占其總邊數的1/2，且節(jié)點度最大；此時，則繼續(xù)迭代；另一種情況，沒有新的子圖產生，則整個迭代過程結束；

步驟2)：根據步驟1)中得到的網絡子圖集，利用模塊度對子圖劃分結果進行優(yōu)化處理；

模塊度是社區(qū)發(fā)現問題中，衡量網絡社區(qū)劃分的指標，定義如下：

其中，i和j代表網絡中的兩個節(jié)點，h_i,j為G的鄰接矩陣中的值；當節(jié)點i和節(jié)點j被劃分到同一個子圖s_is_j＝1，否則，該值為-1；

優(yōu)化過程是通過將步驟1)中的任意兩個子圖進行循環(huán)合并求解模塊度，若模塊度增長，則將兩子圖進行合并，否則繼續(xù)循環(huán)；最終得到模塊度最大的網絡劃分；

步驟3)：步驟2)中的得到的子圖集是基于網絡節(jié)點的連接特性進行初始劃分

網絡子圖集包含若干規(guī)模較大的子圖，并不能滿足聚類的細粒度要求；本步驟分為三個子步驟：

3.1)本步驟中根據傳導率的概念基于三角形圖元對網絡建模降維，首先定義三角形圖元M，方法中運用二元組M(B,A)表示圖元，其中A是網絡節(jié)點集合，x_A是一個選擇函數，set(·)表示將有序元組表示為無序集合的一種運算符；表示為set((v₁,v₂,…,v_k))＝{v₁,v₂,…,v_k}，表示將節(jié)點組(v₁,v₂,…,v_k)無序化為{v₁,v₂,…,v_k}的過程；因此對于一個圖元定義表征如下：

M(B,A)＝{set(v),set(x_A(v))|v∈V^k,v₁,v₂,…,v_kdistinct,A_v＝B}

根據M(B,A)對網絡圖元的表征，構建網絡基于圖元的網絡鄰接矩陣W_M，對角矩陣D_M，拉普拉斯矩陣L_M以及歸一化的拉普拉斯矩陣l_M，定義如下：

L_M＝D_M-W_M

3.2)首先計算輸入網絡對應的歸一化的拉普拉斯矩陣l_M向量對應的特征值，排序得到第二小的特征值，并獲得其對應的特征向量z；通過計算對網絡節(jié)點進行排序，獲得有序的節(jié)點序列；

3.3)對步驟2)中的網絡子圖集進行并行化聚類，按照步驟3.2)中的節(jié)點順序，該過程將序列化的網絡節(jié)點依次添加到新的子圖中，并計算傳導率，從最小的傳導率節(jié)點處將輸入子圖進行切割；

對于給定網絡G和三角形圖元M，基于圖元的傳導率定義如下：

其中，表示兩個簇S和之間的圖元數目，等于S中的圖元數目；

對每一個子圖進行基于圖元聚類，得到最終的網絡聚類集合；該網絡聚類集合中的聚類簇充分考慮了網絡全局性連接關系，并且運用圖元代替節(jié)點作為網絡分析的最小單元對網絡進行聚類分析，對于網絡聚類提出了結構上的連接要求。