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

在審

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

本發(fā)明公開了一種基于大規(guī)模網(wǎng)絡(luò)進行高效聚類方法，采取一系列網(wǎng)絡(luò)切割方法對大規(guī)模網(wǎng)絡(luò)進行預處理，并根據(jù)譜聚類的核心思想，首次使用三角圖元作為網(wǎng)絡(luò)聚類的最小單元對大規(guī)模網(wǎng)絡(luò)進行并行聚類。本系統(tǒng)中節(jié)點簇內(nèi)簇間節(jié)點連接特點定義了四個條件，對大規(guī)模網(wǎng)絡(luò)進行切割，并利用模塊度對網(wǎng)絡(luò)劃分優(yōu)化，得到模塊度最高的子圖集。最后將三角圖元作為網(wǎng)絡(luò)最小單元進行降維并行聚類，以提高系統(tǒng)聚類效率。此系統(tǒng)在四個劃分條件下進行實驗，實驗結(jié)果驗證了本聚類系統(tǒng)的高效性和高精度。本發(fā)明提供了大規(guī)模網(wǎng)絡(luò)聚類的一種新高效方法，為大規(guī)模網(wǎng)絡(luò)數(shù)據(jù)關(guān)系挖掘提供了一種新的解決方案。

技術(shù)領(lǐng)域

本發(fā)明涉及網(wǎng)絡(luò)科學領(lǐng)域中一種基于大規(guī)模網(wǎng)絡(luò)進行高效聚類方法，尤其涉及一種基于網(wǎng)絡(luò)高階圖元的高效大規(guī)模網(wǎng)絡(luò)聚類方法。

背景技術(shù)

人類行為和社會關(guān)系的復雜化使得數(shù)據(jù)規(guī)模不斷增大，不同的社會個體、智能設(shè)備以及其間的復雜聯(lián)系構(gòu)成了復雜的大規(guī)模網(wǎng)絡(luò)。網(wǎng)絡(luò)規(guī)模的日益增大使得網(wǎng)絡(luò)聚類關(guān)系挖掘面臨著效率低的問題，并且冗余數(shù)據(jù)對于網(wǎng)絡(luò)有效關(guān)系的挖掘造成了干擾。聚類算法K-means和gSpan難以滿足大規(guī)模網(wǎng)絡(luò)聚類問題中對于高效性和準確性的要求。因此，高效率和高精度的大規(guī)模網(wǎng)絡(luò)聚類方法有待于研究人員的進一步探索。

發(fā)明內(nèi)容

本發(fā)明的目的主要針對現(xiàn)有研究的一些不足之處，提出基于高階圖元的大規(guī)模網(wǎng)絡(luò)聚類系統(tǒng)，通過將大規(guī)模網(wǎng)絡(luò)的連接特性基于聚類網(wǎng)絡(luò)的四個條件進行初始切割處理以提高聚類效率，并且首次將三角圖元作為網(wǎng)絡(luò)聚類的最小單元對子圖網(wǎng)絡(luò)進行并行聚類，降低網(wǎng)絡(luò)維度，提高聚類效率，為大規(guī)模網(wǎng)絡(luò)聚類提供了一種新思路。

本發(fā)明的技術(shù)方案：

一種基于大規(guī)模網(wǎng)絡(luò)進行高效聚類方法，步驟如下：

(1)根據(jù)聚類結(jié)果要求的不同，確定網(wǎng)絡(luò)劃分的條件；給出四個條件，包括節(jié)點和子圖兩個方面的連接屬性，并根據(jù)選擇的條件對大規(guī)模網(wǎng)絡(luò)進行初始切割，得到網(wǎng)絡(luò)切割之后的子圖集合；

對于大規(guī)模網(wǎng)絡(luò)劃分過程中充分考慮節(jié)點和劃分得到的子圖的連接標準，即節(jié)點劃分歸屬問題考慮節(jié)點和子圖的兩方面的連接屬性；

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

條件一：

條件二：

條件三：

條件四：

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

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

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

(2)根據(jù)模塊度的概念，對步驟(1)中得到的子圖集進行合并優(yōu)化處理，使得網(wǎng)絡(luò)劃分的子圖集的模塊度最大化；

根據(jù)步驟(1)中得到的網(wǎng)絡(luò)子圖集，利用模塊度對子圖劃分結(jié)果進行優(yōu)化處理；模塊度是社區(qū)發(fā)現(xiàn)問題中，衡量網(wǎng)絡(luò)社區(qū)劃分的指標，定義如下：