基于結(jié)構(gòu)熵約束的圖聚類(lèi)方法

張志穎，田有亮,3

（1. 貴州大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，貴州 貴陽(yáng) 550025；2. 貴州省公共大數(shù)據(jù)重點(diǎn)實(shí)驗(yàn)室，貴州 貴陽(yáng) 550025；3. 貴州大學(xué)密碼學(xué)與數(shù)據(jù)安全研究所，貴州 貴陽(yáng) 550025）

1 引言

在大數(shù)據(jù)和5G時(shí)代的環(huán)境下，云計(jì)算、大數(shù)據(jù)和物聯(lián)網(wǎng)等為代表的信息技術(shù)得到了前所未有的飛速發(fā)展[1-2]。新技術(shù)的不斷涌現(xiàn)和發(fā)展，讓人們意識(shí)到數(shù)據(jù)的價(jià)值和開(kāi)放共享[3]的重要性。例如，在物聯(lián)網(wǎng)的大數(shù)據(jù)社交電子商務(wù)中，智能設(shè)備通過(guò)感知用戶(hù)的偏好和瀏覽足跡，為用戶(hù)提供精準(zhǔn)的商品和便捷的服務(wù)[4]。因此，在大型網(wǎng)絡(luò)圖中，迫切需要利用一種方法來(lái)發(fā)現(xiàn)網(wǎng)絡(luò)圖中的真實(shí)結(jié)構(gòu)和相關(guān)程度。

圖聚類(lèi)是一種針對(duì)圖中節(jié)點(diǎn)間的某種相近或相似性的劃分方式[5]，發(fā)現(xiàn)圖中各節(jié)點(diǎn)數(shù)據(jù)間的相關(guān)關(guān)系，并通過(guò)聚類(lèi)效果為智能設(shè)備提供有效的服務(wù)。近年來(lái)，圖聚類(lèi)在社交網(wǎng)絡(luò)[6]、醫(yī)學(xué)圖像[7]和生物數(shù)據(jù)網(wǎng)絡(luò)[8]等應(yīng)用領(lǐng)域得到了廣泛的發(fā)展。因此，根據(jù)網(wǎng)絡(luò)圖生成一個(gè)無(wú)向無(wú)權(quán)圖，可以通過(guò)結(jié)構(gòu)熵[9]來(lái)檢測(cè)圖結(jié)構(gòu)中的真實(shí)結(jié)構(gòu)，進(jìn)而更有效地挖掘出圖中節(jié)點(diǎn)的關(guān)聯(lián)程度。

目前，研究者對(duì)共享和挖掘圖結(jié)構(gòu)中數(shù)據(jù)的興趣不斷增長(zhǎng)，對(duì)社交網(wǎng)絡(luò)中隱私數(shù)據(jù)的保護(hù)力度也在逐漸加大。Keyvanpour等[10]在隱私保護(hù)數(shù)據(jù)挖掘中提出了一種新的自定義隱私模型。進(jìn)一步擴(kuò)展了有向無(wú)環(huán)圖的隱私模型和討論了發(fā)布社交網(wǎng)絡(luò)時(shí)的隱私風(fēng)險(xiǎn)[11]，當(dāng)數(shù)據(jù)挖掘算法應(yīng)用于真實(shí)數(shù)據(jù)集時(shí)，可被惡意數(shù)據(jù)挖掘者用來(lái)威脅社交網(wǎng)絡(luò)用戶(hù)的隱私。Al-Saggaf等[12]在社交網(wǎng)絡(luò)上下文中使用決策森林?jǐn)?shù)據(jù)挖掘算法，該算法不僅構(gòu)建了決策樹(shù)，而且還建立了一個(gè)森林，允許從數(shù)據(jù)集中探索更多的邏輯規(guī)則。數(shù)據(jù)集的龐大，導(dǎo)致數(shù)據(jù)集中存在敏感信息。并且這項(xiàng)技術(shù)在信息提取、數(shù)據(jù)縮減和隱私方面也面臨著巨大的技術(shù)挑戰(zhàn)。G?rnerup等[13]提出了一種從大量蜂窩網(wǎng)絡(luò)數(shù)據(jù)中挖掘路線(xiàn)信息的復(fù)合方法，該方法可通過(guò)分布式集群有效減少序列數(shù)據(jù)來(lái)解決可伸縮性問(wèn)題，以及通過(guò)將原始數(shù)據(jù)分組到聚合中之后，在需要時(shí)對(duì)有關(guān)聚合的統(tǒng)計(jì)進(jìn)行擾動(dòng)以實(shí)現(xiàn)進(jìn)一步的隱私保護(hù)。

為了平衡網(wǎng)絡(luò)的效用和隱私，周藝華等[14]針對(duì)如何在保證隱私安全的前提下，挖掘出有效知識(shí)的問(wèn)題，提出了一種基于聚類(lèi)的社交網(wǎng)絡(luò)隱私保護(hù)方法，該方法有效地減少了信息損失，提高了數(shù)據(jù)有效性。Yan等[15]提出了一種細(xì)粒度的差分隱私機(jī)制，用于在線(xiàn)社交網(wǎng)絡(luò)中的數(shù)據(jù)挖掘。還考慮了針對(duì)差分隱私的共謀攻擊，提出了保護(hù)隱私數(shù)據(jù)挖掘的對(duì)策。Tian等[16]介紹了一種用于將不確定性注入社區(qū)以生成不確定性圖的隱私保護(hù)方法。關(guān)鍵思想是混淆原始圖形的一部分，以實(shí)現(xiàn)隱私保護(hù)和有效地提高數(shù)據(jù)的實(shí)用性，并使用公開(kāi)的真實(shí)數(shù)據(jù)集評(píng)估生成的不確定圖的實(shí)用性。

針對(duì)網(wǎng)絡(luò)數(shù)據(jù)挖掘研究成果中存在高冗余和不安全的問(wèn)題。Jiang等[17]提出了一種基于Apriori算法的網(wǎng)絡(luò)隱私數(shù)據(jù)挖掘方法，基于結(jié)合數(shù)據(jù)冗余分析、過(guò)濾和偽裝，采用優(yōu)化的TS Apriori算法對(duì)偽裝后的數(shù)據(jù)集進(jìn)行挖掘。實(shí)驗(yàn)結(jié)果表明，該方法存在冗余度低、安全性強(qiáng)和挖掘精度高等優(yōu)點(diǎn)。Reza等[18]提出了一種3LP+（three layers of protection）隱私保護(hù)技術(shù)，以保護(hù)用戶(hù)的敏感信息泄露，將3LP +應(yīng)用于合成生成的在線(xiàn)社交網(wǎng)絡(luò)數(shù)據(jù)集，并證明3LP +優(yōu)于現(xiàn)有的隱私保護(hù)技術(shù)。為了分析和查看人們對(duì)在線(xiàn)商人、社交網(wǎng)絡(luò)和其他數(shù)字媒體的隱私和安全。Alshaikh等[19]使用最廣泛的社交網(wǎng)絡(luò)之一Twitter，以分析Twitter用戶(hù)之間的交互，為了提取有意義的數(shù)據(jù)以幫助確定用戶(hù)對(duì)數(shù)字世界的隱私和安全的感知。然而以上研究方法并不能檢測(cè)出圖結(jié)構(gòu)中數(shù)據(jù)結(jié)構(gòu)的真實(shí)信息，從而在挖掘圖結(jié)構(gòu)中關(guān)聯(lián)信息時(shí)可能會(huì)存在一定的誤差。

因此，本文需要解碼出網(wǎng)絡(luò)結(jié)構(gòu)的真實(shí)結(jié)構(gòu)，進(jìn)一步地挖掘出圖結(jié)構(gòu)的關(guān)聯(lián)信息。Li等[20]定義了圖的結(jié)構(gòu)熵的概念，以度量圖中嵌入的信息，并確定和解碼圖的基本結(jié)構(gòu)。Li等[21-23]首先提出了一種通過(guò)網(wǎng)絡(luò)結(jié)構(gòu)熵的度量方法來(lái)尋找社區(qū)的算法。他們發(fā)現(xiàn)，社區(qū)檢測(cè)算法可以準(zhǔn)確識(shí)別幾乎所有自然選擇產(chǎn)生的網(wǎng)絡(luò)社區(qū)。隨后提出了圖的抵抗力的概念，使用一個(gè)伴隨結(jié)構(gòu)熵的概念來(lái)度量圖抵抗策略性病毒攻擊的級(jí)聯(lián)失敗的能力。進(jìn)一步提出了一種利用結(jié)構(gòu)信息理論的快速且無(wú)歸一化的算法來(lái)解碼染色體域。Liu等[24]提出了一種基于社區(qū)的結(jié)構(gòu)熵來(lái)表達(dá)由社區(qū)結(jié)構(gòu)揭示的信息量。通過(guò)利用用戶(hù)賬戶(hù)的社區(qū)隸屬關(guān)系，攻擊者可以推斷出敏感的用戶(hù)屬性。這就提出了社區(qū)結(jié)構(gòu)欺騙的問(wèn)題，并著重于在在線(xiàn)社交網(wǎng)絡(luò)中披露社區(qū)結(jié)構(gòu)的隱私風(fēng)險(xiǎn)。

基于以上研究，本文針對(duì)大規(guī)模動(dòng)態(tài)數(shù)據(jù)之間的關(guān)聯(lián)程度，提出了一種基于結(jié)構(gòu)熵約束的圖聚類(lèi)方法。相比已有工作，該方法通過(guò)引入結(jié)構(gòu)熵來(lái)度量動(dòng)態(tài)復(fù)雜網(wǎng)絡(luò)，解碼出網(wǎng)絡(luò)的真實(shí)結(jié)構(gòu)信息，解決了現(xiàn)有文獻(xiàn)對(duì)動(dòng)態(tài)復(fù)雜網(wǎng)絡(luò)中信息關(guān)聯(lián)刻畫(huà)不足的問(wèn)題。具體而言，本文的貢獻(xiàn)如下。

1) 提出了利用二維結(jié)構(gòu)信息的求解算法和熵減原則的聚類(lèi)算法。通過(guò)算法將圖結(jié)構(gòu)中節(jié)點(diǎn)進(jìn)行劃分，關(guān)聯(lián)程度強(qiáng)的劃分為一個(gè)模塊，從而挖掘出圖結(jié)構(gòu)中關(guān)聯(lián)程度強(qiáng)弱的模塊隱私信息。

2) 提出了K維結(jié)構(gòu)信息的求解算法。通過(guò)算法將已劃分的模塊做進(jìn)一步的劃分，得到圖中所有節(jié)點(diǎn)的關(guān)聯(lián)程度。同時(shí)結(jié)構(gòu)熵可以解碼出在大規(guī)模噪聲結(jié)構(gòu)中圖結(jié)構(gòu)的信息，這個(gè)信息能區(qū)分圖結(jié)構(gòu)中的規(guī)律和噪聲，從而挖掘出圖結(jié)構(gòu)中節(jié)點(diǎn)的實(shí)質(zhì)結(jié)構(gòu)。

3) 通過(guò)實(shí)例分析和實(shí)驗(yàn)評(píng)估表明，所提出的圖聚類(lèi)方法不僅能夠有效地反映圖結(jié)構(gòu)的真實(shí)結(jié)構(gòu)，而且還能有效地挖掘出圖結(jié)構(gòu)中節(jié)點(diǎn)之間的關(guān)聯(lián)程度。與其他3種聚類(lèi)方法相比，該方法在執(zhí)行時(shí)間上具有更高的效率，并且保證了聚類(lèi)結(jié)果的可靠性。

2 相關(guān)概念定義

定義1（圖的編碼樹(shù)[20-25]）設(shè)圖G=(V,E)，圖的編碼樹(shù)T，使得圖中的每個(gè)節(jié)點(diǎn)都在編碼樹(shù)中，存在頂點(diǎn)集V的子集Tα，并且以下屬性成立。

對(duì)于根節(jié)點(diǎn)λ，定義一個(gè)集合Tλ=V。

對(duì)于每個(gè)節(jié)點(diǎn)α?T，α?〈j〉表示α的子節(jié)點(diǎn)，j是1到自然數(shù)N從左到右遞增。每個(gè)內(nèi)部節(jié)點(diǎn)至少有兩個(gè)直接后繼節(jié)點(diǎn)，因此當(dāng)i＜j時(shí)，α?〈i〉在α?〈j〉左邊。

對(duì)于α?T，都有一個(gè)與α相關(guān)的子集Tα?V，對(duì)于α，β。α表示β的父節(jié)點(diǎn)，如果α≠λ，α-表示α的父節(jié)點(diǎn)。

對(duì)于每一個(gè)i，{Tα|h(α)=i}是V的一個(gè)分區(qū)，其中h(α)是α的高度，根節(jié)點(diǎn)的高度為0，當(dāng)α≠λ時(shí)，h(α) =h(α-)+1。

對(duì)于每個(gè)節(jié)點(diǎn)α，Tα是Tβ對(duì)所有β的聯(lián)合，β-=α，因此Tα=∪β-=αTβ。

對(duì)于T的每個(gè)葉子節(jié)點(diǎn)α，Tα是一個(gè)單例。因此Tα包含V中的單個(gè)節(jié)點(diǎn)。

對(duì)于每個(gè)節(jié)點(diǎn)α?T，如果Tα=X為一組頂點(diǎn)X，則α是X的碼字，記c(X)=α，X是α的標(biāo)記，記M(α)=X。

定義2（結(jié)構(gòu)熵[20]）設(shè)圖G=(V,E)，根據(jù)圖G的不同維度得到一維結(jié)構(gòu)熵、二維結(jié)構(gòu)熵和K維結(jié)構(gòu)熵。將不同維度的結(jié)構(gòu)熵的最小值定義為圖在不同維度下的結(jié)構(gòu)信息。

定義3（一維結(jié)構(gòu)信息[20]）假設(shè)G=(V,E)是一個(gè)n個(gè)頂點(diǎn)m條邊的無(wú)向連通圖，對(duì)于每個(gè)頂點(diǎn)i? { 1,2,…,n}。用di表示G中頂點(diǎn)i的度，m為圖邊的數(shù)量，設(shè)Qi=di/2m。然后用概率向量Q=(Q1,Q2,…,Qn)來(lái)描述圖G中頂點(diǎn)的平穩(wěn)分布。由此可定義圖G的一維結(jié)構(gòu)信息：

定義4（二維結(jié)構(gòu)信息[20]）給定一個(gè)無(wú)向連通圖G=(V,E)，假設(shè)P= (X1,X2,…,XL)是V的一個(gè)分區(qū)，稱(chēng)Xj為一個(gè)模塊或者社區(qū)。通過(guò)P定義圖G的結(jié)構(gòu)信息如下：

其中，L是分區(qū)P中的模塊數(shù)，n j是模塊Xj中的節(jié)點(diǎn)數(shù)，是Xi中第i個(gè)節(jié)點(diǎn)的度，V j是模塊Xj的體積，也就是模塊Xj中所有節(jié)點(diǎn)的度之和。gj是模塊中Xj只有一個(gè)端點(diǎn)的邊的數(shù)量。

因此可以定義圖G的二維結(jié)構(gòu)信息，也稱(chēng)之為模塊熵：

其中，P是圖G中所有可能劃分出的分區(qū)模塊。

定義5（圖聚類(lèi)[26]）根據(jù)節(jié)點(diǎn)間的某種相近或相似性，利用聚類(lèi)方法將圖中所有節(jié)點(diǎn)劃分成一些聚類(lèi)，這個(gè)過(guò)程被稱(chēng)為圖聚類(lèi)。

為了更好地理解圖聚類(lèi)，本文將圖聚類(lèi)表示為社交網(wǎng)絡(luò)圖G上的一種映射關(guān)系φ:(v1,v2,…,vn)→(X1,X2,…,Xm)，φ滿(mǎn)足以下兩個(gè)條件。

3 問(wèn)題描述

3.1 方案模型

結(jié)構(gòu)熵被用來(lái)度量嵌入圖結(jié)構(gòu)中的不確定性，結(jié)構(gòu)熵的最小化是解碼圖結(jié)構(gòu)中真實(shí)結(jié)構(gòu)的一種直觀的方法。通過(guò)圖結(jié)構(gòu)的結(jié)構(gòu)熵最小化，將圖結(jié)構(gòu)的隨機(jī)變化和噪聲引起的擾動(dòng)減小到最小，并且在比較圖結(jié)構(gòu)的節(jié)點(diǎn)模塊合并前后結(jié)構(gòu)熵的差異程度過(guò)程中，可反映出圖結(jié)構(gòu)中節(jié)點(diǎn)之間的關(guān)聯(lián)程度。如圖1所示，在圖結(jié)構(gòu)交互過(guò)程中如何有效地挖掘出它們之間的關(guān)聯(lián)程度是本文所要考慮的新問(wèn)題。針對(duì)這一問(wèn)題，可以用圖的二維結(jié)構(gòu)熵度量圖中的結(jié)構(gòu)信息。對(duì)于圖中的每一個(gè)節(jié)點(diǎn)模塊，在模塊的生成過(guò)程中，任意兩個(gè)節(jié)點(diǎn)模塊的合并必須滿(mǎn)足熵減原則，也就是說(shuō)兩個(gè)節(jié)點(diǎn)合并后的模塊熵較合并之前減少的越多，表示模塊合并后的不確定性越低，其圖結(jié)構(gòu)的二維結(jié)構(gòu)熵也越小。這就反映了網(wǎng)絡(luò)結(jié)構(gòu)中本質(zhì)的真實(shí)結(jié)構(gòu)信息，即網(wǎng)絡(luò)結(jié)構(gòu)的結(jié)構(gòu)熵越小，模塊中的節(jié)點(diǎn)關(guān)聯(lián)程度越強(qiáng)。

圖1 圖結(jié)構(gòu)節(jié)點(diǎn)聚類(lèi)模型Figure 1 Graph structure node clustering model

3.2 算法設(shè)計(jì)

為了能從大規(guī)模噪聲結(jié)構(gòu)中挖掘出圖結(jié)構(gòu)的隱私信息，必須利用結(jié)構(gòu)熵的最小值來(lái)解碼圖結(jié)構(gòu)的真實(shí)結(jié)構(gòu)，從而更好地反映出圖結(jié)構(gòu)中任意兩個(gè)節(jié)點(diǎn)的關(guān)聯(lián)程度。在此，本文提出利用二維結(jié)構(gòu)熵最小值的計(jì)算算法和熵減原則的模塊分區(qū)算法來(lái)得出圖結(jié)構(gòu)中節(jié)點(diǎn)的關(guān)聯(lián)性。

為了解決網(wǎng)絡(luò)結(jié)構(gòu)中數(shù)據(jù)的高精度問(wèn)題需要一個(gè)新的信息度量，能度量嵌入在復(fù)雜系統(tǒng)中的信息，這個(gè)信息能區(qū)分網(wǎng)絡(luò)結(jié)構(gòu)中數(shù)據(jù)的規(guī)律和噪聲，從而解碼出嵌入在大規(guī)模噪音結(jié)構(gòu)中的規(guī)律。因此需要設(shè)計(jì)算法1。

算法1二維結(jié)構(gòu)信息最小值求解算法

輸入一個(gè)n個(gè)頂點(diǎn)m條邊的無(wú)向連通圖G=(V,E)

算法1可計(jì)算出一個(gè)n個(gè)頂點(diǎn)和m條邊的無(wú)向連通圖G的二維結(jié)構(gòu)信息，圖G的二維結(jié)構(gòu)信息就是圖所能劃分的所有模塊熵的最小值。設(shè)圖的二維結(jié)構(gòu)熵在最小值時(shí)所對(duì)應(yīng)節(jié)點(diǎn)的劃分為分區(qū)P，P= {X1,X2,…,XL}。其中，分區(qū)P是對(duì)所有節(jié)點(diǎn)的一個(gè)劃分，X i(i= 1,2,…,L)是劃分P下的一個(gè)模塊或者說(shuō)是一個(gè)社區(qū)，模塊是由部分節(jié)點(diǎn)組成的集合。然而針對(duì)不同的劃分結(jié)果，計(jì)算出圖的二維結(jié)構(gòu)信息也不同。只有當(dāng)圖的二維結(jié)構(gòu)信息取值為模塊熵的最小值的時(shí)候，對(duì)應(yīng)的圖中節(jié)點(diǎn)分區(qū)P才能體現(xiàn)出該圖的節(jié)點(diǎn)關(guān)聯(lián)程度的最優(yōu)結(jié)果。也就是當(dāng)圖的二維結(jié)構(gòu)信息最小時(shí)，模塊中節(jié)點(diǎn)的不確定性最小，節(jié)點(diǎn)的關(guān)聯(lián)程度最強(qiáng)。

然而在計(jì)算二維結(jié)構(gòu)信息時(shí)，為了得到模塊熵的最小值，只能通過(guò)不同的分區(qū)和計(jì)算進(jìn)行比較。然而無(wú)法快速地通過(guò)計(jì)算對(duì)比來(lái)減少計(jì)算成本，從而無(wú)法更有效地確定圖中的頂點(diǎn)的劃分結(jié)果是否完善。因此，進(jìn)一步地利用二維結(jié)構(gòu)信息和熵減原則來(lái)有效提高本文獲取模塊分區(qū)的結(jié)果。為了能夠?qū)D中節(jié)點(diǎn)有效分區(qū)，得到節(jié)點(diǎn)模塊之間的關(guān)聯(lián)程度設(shè)計(jì)了算法2。

算法2網(wǎng)絡(luò)節(jié)點(diǎn)模塊分區(qū)算法

輸入一個(gè)n個(gè)頂點(diǎn)m條邊的無(wú)向連通圖G=(V,E)

該算法的節(jié)點(diǎn)模塊劃分方法的主要過(guò)程如下：假設(shè)v1,v2,…,vn是節(jié)點(diǎn)集合V中所有按順序排列出的節(jié)點(diǎn)。將Xi設(shè)置為所有i的單例{vi}，構(gòu)成了所有節(jié)點(diǎn)集V的初始劃分模塊。如果不存在滿(mǎn)足i＜j這樣的，則返回分區(qū)P。否則，有i0,j0使得是所有i,j在上的最大值，得到其中，表達(dá)式如下：

根據(jù)二維結(jié)構(gòu)信息最小值求解算法和網(wǎng)絡(luò)節(jié)點(diǎn)模塊分區(qū)算法可以有效地處理圖的結(jié)構(gòu)信息數(shù)據(jù)，從大規(guī)模噪聲結(jié)構(gòu)中解碼出圖節(jié)點(diǎn)之間的關(guān)聯(lián)程度，既不需要改變?cè)紨?shù)據(jù)也不需要選擇參數(shù)。這就排除了在歸一化或在參數(shù)選擇中可能產(chǎn)生噪聲的影響。

本節(jié)使用了一種基于結(jié)構(gòu)信息理論的圖節(jié)點(diǎn)分區(qū)算法。通過(guò)節(jié)點(diǎn)的劃分模塊和整體的劃分分區(qū)，用結(jié)構(gòu)熵的最小值來(lái)獲取圖中節(jié)點(diǎn)隨機(jī)游動(dòng)發(fā)生的不確定性，從而更好地反映出圖節(jié)點(diǎn)之間的關(guān)聯(lián)程度。因此，網(wǎng)絡(luò)節(jié)點(diǎn)分區(qū)算法的本質(zhì)是固定結(jié)構(gòu)不確定性最大的網(wǎng)絡(luò)節(jié)點(diǎn)，合并網(wǎng)絡(luò)中連接緊密程度高的節(jié)點(diǎn)模塊。節(jié)點(diǎn)的分區(qū)算法不僅挖掘出了使整個(gè)網(wǎng)絡(luò)的不確定性最小化的基本結(jié)構(gòu)，而且從模塊分區(qū)結(jié)果中反映出網(wǎng)絡(luò)中連接緊密程度最高的節(jié)點(diǎn)模塊。

4 K維結(jié)構(gòu)信息的聚類(lèi)算法

網(wǎng)絡(luò)表現(xiàn)為特定群體中多個(gè)個(gè)體及它們之間相互聯(lián)系組成的集合，最適合用圖來(lái)表示。其中，節(jié)點(diǎn)表示個(gè)體，邊表示個(gè)體間的聯(lián)系。常見(jiàn)的網(wǎng)絡(luò)圖結(jié)構(gòu)模型為簡(jiǎn)單的圖模型G=(V,E)，在圖G中，V= {v1,v2,…,vn}為圖中節(jié)點(diǎn)集，E= {(vi,vj)| 1≤i,j≤n,i≠j}為邊集。圖中任何邊(vi,vj)表示節(jié)點(diǎn)之間的聯(lián)系，為結(jié)構(gòu)邊。根據(jù)實(shí)際網(wǎng)絡(luò)中個(gè)體之間聯(lián)系的緊密程度不同，結(jié)構(gòu)邊的權(quán)值不同。本文假設(shè)給定的是一個(gè)無(wú)向無(wú)權(quán)的連通圖，結(jié)構(gòu)邊具有相等的權(quán)值，均為1。

為了發(fā)現(xiàn)圖中的簇，把圖分割成若干塊。每一塊是一個(gè)簇，使得簇內(nèi)的節(jié)點(diǎn)能夠以利益最大化的方式有效地連接，而不同簇內(nèi)的節(jié)點(diǎn)之間以較弱的方式連接。因此，本文通過(guò)利用結(jié)構(gòu)熵能檢測(cè)圖結(jié)構(gòu)的真實(shí)結(jié)構(gòu)來(lái)更有效地對(duì)圖中節(jié)點(diǎn)進(jìn)行劃分。其主要特點(diǎn)都是聚類(lèi)，將圖中所有節(jié)點(diǎn)劃分為模塊子集的過(guò)程，使得圖中相似度最高的節(jié)點(diǎn)形成一個(gè)簇，簇內(nèi)的節(jié)點(diǎn)與其他簇內(nèi)的節(jié)點(diǎn)相似度最低。

圖聚類(lèi)問(wèn)題的實(shí)質(zhì)就是圖劃分問(wèn)題，聚類(lèi)的過(guò)程其實(shí)就是對(duì)圖劃分過(guò)程的優(yōu)化。優(yōu)化的目的是使劃分的模塊間的相似度變小，模塊內(nèi)的節(jié)點(diǎn)相似度變大。然而對(duì)于如何度量嵌入大規(guī)模噪聲結(jié)構(gòu)中的整體圖結(jié)構(gòu)的信息，僅是二維結(jié)構(gòu)信息是遠(yuǎn)遠(yuǎn)不夠的。因此，利用K維結(jié)構(gòu)信息來(lái)作為圖聚類(lèi)的一種方法，也就是在二維結(jié)構(gòu)信息和熵減原則的基礎(chǔ)上，進(jìn)一步地計(jì)算出圖結(jié)構(gòu)的最小結(jié)構(gòu)熵，從而更有效地反映圖結(jié)構(gòu)的真實(shí)結(jié)構(gòu)。為了更加針對(duì)性地對(duì)圖中節(jié)點(diǎn)間的關(guān)聯(lián)程度做出有效的挖掘，設(shè)計(jì)了算法3。

算法3K維結(jié)構(gòu)信息求解算法

定義6（K維結(jié)構(gòu)信息[20]）對(duì)于一個(gè)無(wú)向連通圖G=(V,E)，假設(shè)T是圖G的分區(qū)樹(shù)。通過(guò)T定義圖G的結(jié)構(gòu)信息如下：

對(duì)于任意頂點(diǎn)α?T，如果α≠λ，λ為樹(shù)T的根節(jié)點(diǎn)，那么定義頂點(diǎn)α的結(jié)構(gòu)信息為其中，gα是從Tα中的節(jié)點(diǎn)到Tα之外節(jié)點(diǎn)的邊數(shù)，Vα是集合Tα的體積。

通過(guò)分區(qū)樹(shù)T定義圖G的結(jié)構(gòu)信息如下：

圖G的K維結(jié)構(gòu)信息定義如下：

其中，T覆蓋圖G的所有分區(qū)樹(shù)，K表示T的高度。算法3計(jì)算出圖結(jié)構(gòu)的整體K維結(jié)構(gòu)信息，K維結(jié)構(gòu)信息能挖掘嵌入在圖結(jié)構(gòu)中的信息，這個(gè)信息能區(qū)分圖結(jié)構(gòu)的規(guī)律和噪聲，從而解碼出嵌入在大規(guī)模噪聲結(jié)構(gòu)中的規(guī)律，進(jìn)一步?jīng)Q定并解碼出該圖結(jié)構(gòu)的真實(shí)結(jié)構(gòu)。通過(guò)在二維結(jié)構(gòu)信息的基礎(chǔ)上加入merge和combine兩個(gè)算法，將圖結(jié)構(gòu)由高度為2的分區(qū)樹(shù)轉(zhuǎn)化為高度為K的分區(qū)樹(shù)，從而進(jìn)一步地劃分圖結(jié)構(gòu)中節(jié)點(diǎn)的關(guān)聯(lián)程度。因此，當(dāng)K維結(jié)構(gòu)熵越小時(shí)，越能反映出圖結(jié)構(gòu)中單個(gè)節(jié)點(diǎn)間的關(guān)聯(lián)程度。

聚類(lèi)分析可以對(duì)網(wǎng)絡(luò)中節(jié)點(diǎn)實(shí)行分組管理，使得組內(nèi)的節(jié)點(diǎn)具有非常相似的特性或者需求，這有利于應(yīng)用在智能設(shè)備中更好地服務(wù)用戶(hù)和加強(qiáng)對(duì)用戶(hù)信息的保護(hù)。利用結(jié)構(gòu)信息的最小化將復(fù)雜的網(wǎng)絡(luò)抽象成一個(gè)圖，不僅對(duì)分析整體網(wǎng)絡(luò)的結(jié)構(gòu)信息有著重要的幫助，而且還能對(duì)網(wǎng)絡(luò)中用戶(hù)的隱私信息進(jìn)行挖掘和保護(hù)有著重要的意義。具體來(lái)說(shuō)，根據(jù)模塊熵和熵減原則，對(duì)圖中節(jié)點(diǎn)進(jìn)行合并得到不同的模塊，進(jìn)一步根據(jù)圖的K維結(jié)構(gòu)熵的最小值K維結(jié)構(gòu)信息，最終得到對(duì)所有圖節(jié)點(diǎn)的關(guān)聯(lián)聚類(lèi)。此時(shí)，結(jié)構(gòu)熵能度量出圖在大規(guī)模噪聲結(jié)構(gòu)中的信息，所得到的信息也反映了圖的真實(shí)結(jié)構(gòu)。其中節(jié)點(diǎn)的模塊分區(qū)就表示圖結(jié)構(gòu)在挖掘圖中關(guān)聯(lián)信息條件下的聚類(lèi)結(jié)果，便可將圖中隱私信息關(guān)聯(lián)程度緊密的節(jié)點(diǎn)劃分為一個(gè)模塊，而模塊間節(jié)點(diǎn)隱私信息的關(guān)聯(lián)程度遠(yuǎn)遠(yuǎn)小于模塊內(nèi)節(jié)點(diǎn)的關(guān)聯(lián)程度。

5 實(shí)驗(yàn)評(píng)估與分析

本節(jié)通過(guò)實(shí)驗(yàn)來(lái)評(píng)估本文所提出的方法，并給出詳細(xì)的實(shí)驗(yàn)結(jié)果和討論與其他方法的優(yōu)缺點(diǎn)。

5.1 實(shí)驗(yàn)評(píng)估

本文隨機(jī)生成一個(gè)15個(gè)頂點(diǎn)60條邊的無(wú)向無(wú)權(quán)的網(wǎng)絡(luò)模型圖。如圖2所示。

圖2 隨機(jī)生成圖Figure 2 Randomly generated graph

首先通過(guò)算法1和算法2對(duì)圖進(jìn)行模塊劃分，計(jì)算出圖的二維結(jié)構(gòu)信息H2(G)3.23= 。由此可見(jiàn)，通過(guò)二維結(jié)構(gòu)信息和熵減原則算法，將圖劃分為大小不同的模塊，并計(jì)算不同模塊的結(jié)構(gòu)熵H P(G)，最終得出圖的二維結(jié)構(gòu)信息H2(G) =min{H P(G)}，此時(shí)模塊P的劃分結(jié)果便是圖中節(jié)點(diǎn)屬性相關(guān)程度大的為一個(gè)模塊。因此，如圖3所示，利用算法1和算法2將圖劃分為模塊P={X1,X2,X3,X4}，且X1={A,E,H}，X2={B,F,G,I,L}，X3={C,D,K,M,O}，X4={J,N}。

圖3 模塊熵的關(guān)聯(lián)節(jié)點(diǎn)Figure 3 Associated node of module entropy

然后將圖劃分的模塊P轉(zhuǎn)化為高度2的分區(qū)樹(shù)，引入根節(jié)點(diǎn)λ，模塊P中每一個(gè)子模塊X i(i= 1,2,3,4)為樹(shù)節(jié)點(diǎn)，每個(gè)子模塊中的節(jié)點(diǎn)為該樹(shù)節(jié)點(diǎn)下的葉子節(jié)點(diǎn)。二維分區(qū)樹(shù)如圖4所示。

圖4 二維分區(qū)樹(shù)Figure 4 Two-dimensional partition tree

最后將以模塊P的最優(yōu)劃分結(jié)果通過(guò)算法3做進(jìn)一步的節(jié)點(diǎn)聚類(lèi)，并計(jì)算出圖的K維結(jié)構(gòu)信息H K(G)= 3.07。因此，通過(guò)K維結(jié)構(gòu)信息聚類(lèi)算法，將所有的模塊P生成的二維分區(qū)樹(shù)轉(zhuǎn)化成高度為K的分區(qū)樹(shù)，并計(jì)算出不同的K維分區(qū)樹(shù)的結(jié)構(gòu)熵H T(G)，最終得出圖的K維結(jié)構(gòu)信息H K(G) =min{H T(G)}，此時(shí)所得到的分區(qū)樹(shù)便是將圖中每個(gè)節(jié)點(diǎn)屬性關(guān)聯(lián)程度最大的聚類(lèi)在一起。如圖5所示，從圖3中可以看出，利用算法3將模塊中的節(jié)點(diǎn)再一次進(jìn)行劃分，得到劃分結(jié)果更為詳細(xì)。因此，可以得到在模塊X1中節(jié)點(diǎn)A、E關(guān)聯(lián)程度更大，模塊X2和X3中節(jié)點(diǎn)進(jìn)一步得出兩兩關(guān)聯(lián)程度：X2:((G,(B,L)),(F,I))，X3:((K,(C,M)),(D,O))，模塊X4中的關(guān)聯(lián)程度沒(méi)有變化。

圖5 K維分區(qū)樹(shù)Figure 5 K-dimensional partition tree

當(dāng)圖中頂點(diǎn)和邊的數(shù)量在不斷變化時(shí)，圖結(jié)構(gòu)的本質(zhì)信息也會(huì)改變，從而導(dǎo)致圖的劃分結(jié)果也會(huì)隨之變化，如表1所示。隨機(jī)生成4個(gè)不同大小的網(wǎng)絡(luò)圖，通過(guò)二維結(jié)構(gòu)信息的劃分方法將圖中相似度高的節(jié)點(diǎn)分成一個(gè)模塊，再通過(guò)K維結(jié)構(gòu)熵最小值的原理將模塊中的節(jié)點(diǎn)進(jìn)一步劃分，最終得到圖中所有節(jié)點(diǎn)間的關(guān)聯(lián)程度。所以，本文通過(guò)結(jié)構(gòu)熵挖掘出圖中節(jié)點(diǎn)關(guān)聯(lián)程度大的節(jié)點(diǎn)都屬于一個(gè)模塊，而節(jié)點(diǎn)之間關(guān)聯(lián)程度小的則被劃分在不同的模塊中。因此可以利用結(jié)構(gòu)熵的最小值來(lái)體現(xiàn)網(wǎng)絡(luò)節(jié)點(diǎn)的關(guān)聯(lián)程度，從而挖掘出網(wǎng)絡(luò)結(jié)構(gòu)中節(jié)點(diǎn)之間的交互信息以及其他相關(guān)信息。

表1 不同網(wǎng)絡(luò)圖的聚類(lèi)效果Table 1 Clustering result of different network graphs

5.2 有效性比較與分析

對(duì)數(shù)據(jù)挖掘的研究領(lǐng)域中，聚類(lèi)往往可以直接或者間接地描述數(shù)據(jù)的關(guān)聯(lián)程度，從而能夠有效地分析數(shù)據(jù)的相關(guān)特性。因此聚類(lèi)分析算法是探索數(shù)據(jù)分析的關(guān)鍵要素，其中K均值算法因其易于實(shí)現(xiàn)、可并行性強(qiáng)和計(jì)算成本相對(duì)較低而成為最受歡迎的方法。然而正如文獻(xiàn)[27]提出的K均值對(duì)初始條件的高度依賴(lài)，以及在大規(guī)模數(shù)據(jù)集中可能無(wú)法很好地?cái)U(kuò)展。文獻(xiàn)[27]提出了一個(gè)遞歸并行逼近K均值算法，該算法在不影響逼近質(zhì)量的情況下，能很好地根據(jù)問(wèn)題實(shí)例的數(shù)量進(jìn)行縮放。但是該算法在遞歸次數(shù)和計(jì)算開(kāi)銷(xiāo)方面都消耗較大，無(wú)法有效地分析社交網(wǎng)絡(luò)或圖等結(jié)構(gòu)化網(wǎng)絡(luò)圖中所嵌入的信息。

劃分和層次方法旨在發(fā)現(xiàn)球狀簇，對(duì)于給定的數(shù)據(jù)很難發(fā)現(xiàn)任意形狀的簇。然而為了發(fā)現(xiàn)任意形狀的簇，可以把簇看作數(shù)據(jù)空間中被稀疏區(qū)域分開(kāi)的稠密，從而可以發(fā)現(xiàn)任意非球狀的簇?；诿芏鹊脑肼晳?yīng)用空間聚類(lèi)（DBSCAN，

density-based spatial clustering of applications with noise）是基于密度的聚類(lèi)算法，也是主要的聚類(lèi)范式之一。盡管DBSCAN算法已被廣泛應(yīng)用，但算法本身依然存在一定的缺點(diǎn)。DBSCAN算法的輸入?yún)?shù)包括掃描半徑ε和閾值MinPts，在聚類(lèi)的過(guò)程中需要計(jì)算每個(gè)數(shù)據(jù)點(diǎn)的密度。數(shù)據(jù)點(diǎn)的密度與從該點(diǎn)到其他所有點(diǎn)的距離有關(guān)，使得聚類(lèi)過(guò)程中存在很多冗余的距離計(jì)算，復(fù)雜度高，效率低。因此，該算法同樣不適用于大規(guī)模數(shù)據(jù)和高維數(shù)據(jù)。Li等[28]對(duì)DBSCAN的聚類(lèi)原理進(jìn)行了深入的分析和研究，發(fā)現(xiàn)DBSCAN的核心問(wèn)題是尋找每個(gè)點(diǎn)的最近鄰，然后通過(guò)三角不等式提出了一種基于最近鄰相似的快速密度算法，并且利用覆蓋樹(shù)對(duì)每個(gè)并行點(diǎn)的領(lǐng)域進(jìn)行檢索，可以有效減少聚類(lèi)過(guò)程中距離計(jì)算的次數(shù)，提高聚類(lèi)效率。但是，該算法的不足在于只基于最近距離來(lái)分析每個(gè)節(jié)點(diǎn)的相似度，忽略了網(wǎng)絡(luò)的自組織原理與網(wǎng)絡(luò)節(jié)點(diǎn)所嵌入的結(jié)構(gòu)信息對(duì)圖聚類(lèi)的影響。

圖聚類(lèi)主要是針對(duì)圖的一種聚類(lèi)方法，用來(lái)搜索圖找出節(jié)點(diǎn)間某種相似的特性形成一個(gè)簇。網(wǎng)絡(luò)結(jié)構(gòu)聚類(lèi)算法（SCAN，structural clustering algorithm for networks）在處理大型網(wǎng)絡(luò)圖時(shí)，其時(shí)間復(fù)雜性關(guān)于邊數(shù)是線(xiàn)性的，具有良好的可伸縮性。SCAN是一種快速高效的集群技術(shù)，用于查找隱藏的社區(qū)并隔離網(wǎng)絡(luò)中的集線(xiàn)器或異常值。然而，對(duì)于大型網(wǎng)絡(luò)仍然需要相當(dāng)多的時(shí)間。Stovall等[29]提出了一種基于計(jì)算統(tǒng)一設(shè)備架構(gòu)（CUDA，computer unified device architecture）的SCAN并行實(shí)現(xiàn)（GPUSCAN，graphic processing unit structural clustering algorithm for networks）。SCAN的計(jì)算步驟經(jīng)過(guò)仔細(xì)的重新設(shè)計(jì)，通過(guò)將SCAN轉(zhuǎn)化為一系列高度規(guī)則和獨(dú)立的并發(fā)操作，使其在圖形處理單元（GPU，graphic processing unit）上高效運(yùn)行。通過(guò)GPUSCAN，可以將大型網(wǎng)絡(luò)或一批不相交的網(wǎng)絡(luò)卸載到GPU，以進(jìn)行非常快速且高效的結(jié)構(gòu)聚類(lèi)。GPUSCAN是在考慮CUDA的情況下開(kāi)發(fā)的，啟用CUDA的GPU充當(dāng)了并行分布式系統(tǒng)的縮影。由于GPUSCAN專(zhuān)注于合并和本地資源訪(fǎng)問(wèn)方法，因此具有可伸縮性，并且可以輕松地適應(yīng)并發(fā)或分布式環(huán)境。相比之下，SCAN基于廣度優(yōu)先搜索，盡管計(jì)算效率高，但往往需要高頻率的隨機(jī)資源訪(fǎng)問(wèn)，并迅速成為超大型網(wǎng)絡(luò)的I / O綁定。GPUSCAN當(dāng)前受GPU上可用的設(shè)備內(nèi)存量的限制。雖然可以通過(guò)將復(fù)雜的計(jì)算分布在多個(gè)連接的GPU上，從而可以輕松地?cái)U(kuò)大規(guī)模，但其開(kāi)銷(xiāo)仍是一個(gè)難以解決的問(wèn)題。

因此，表2對(duì)以上3種聚類(lèi)方法與本文所提出的基于結(jié)構(gòu)熵的圖聚類(lèi)方法進(jìn)行了比較。從表2可以看出，文獻(xiàn)[27]所提方法的時(shí)間復(fù)雜度為O(nkt)，因此，該方法在計(jì)算大規(guī)模數(shù)據(jù)集時(shí)，將消耗大量的計(jì)算時(shí)間和計(jì)算開(kāi)銷(xiāo)。文獻(xiàn)[28]所提方法的時(shí)間復(fù)雜度為logn+ MinPts2])，該算法在聚類(lèi)過(guò)程中具有許多冗余計(jì)算，導(dǎo)致效率低和復(fù)雜度較高的問(wèn)題。文獻(xiàn)[29]所提方法的時(shí)間復(fù)雜度為O(n2)，該方法的計(jì)算效率與本文方法存在很小的差距，但該方法受GPU上可用的設(shè)備內(nèi)存限制，將會(huì)增加聚類(lèi)過(guò)程中的開(kāi)銷(xiāo)問(wèn)題。由于圖的結(jié)構(gòu)信息能夠度量出圖結(jié)構(gòu)中所嵌入的信息，這個(gè)信息量可以更好地反映出圖結(jié)構(gòu)的真實(shí)結(jié)構(gòu)。因此，可以在大規(guī)模噪聲結(jié)構(gòu)中解碼出網(wǎng)絡(luò)結(jié)構(gòu)的真實(shí)結(jié)構(gòu)信息的情況下，利用結(jié)構(gòu)熵更有利于對(duì)圖結(jié)構(gòu)中節(jié)點(diǎn)的關(guān)聯(lián)信息的挖掘，從而將達(dá)到節(jié)點(diǎn)屬性有效地聚類(lèi)。因此，無(wú)論是在處理大規(guī)模數(shù)據(jù)集時(shí)，還是在動(dòng)態(tài)復(fù)雜的網(wǎng)絡(luò)結(jié)構(gòu)中，本文方法在計(jì)算規(guī)模、計(jì)算開(kāi)銷(xiāo)以及計(jì)算效率等方面都優(yōu)于其他方法。

表2 聚類(lèi)功能對(duì)比Table 2 clustering function comparison

5.3 仿真分析

本文實(shí)驗(yàn)環(huán)境是一臺(tái)CPU為Intel (R)Core(TM) i5-7500，內(nèi)存為8 GB，操作系統(tǒng)為64位Windows 10的計(jì)算機(jī)。選用Python作為編程語(yǔ)言，模擬運(yùn)行熵減原則圖劃分算法和圖節(jié)點(diǎn)的聚類(lèi)算法。如圖6所示，本文使用0~10 000的不同節(jié)點(diǎn)數(shù)量運(yùn)行6個(gè)實(shí)驗(yàn)，比較了本文所提出的二維結(jié)構(gòu)信息和熵減原則下的圖劃分算法與K維結(jié)構(gòu)信息對(duì)圖節(jié)點(diǎn)的相似聚類(lèi)算法的執(zhí)行時(shí)間。

圖6 不同網(wǎng)絡(luò)節(jié)點(diǎn)圖劃分與圖聚類(lèi)的執(zhí)行時(shí)間Figure 6 The execution time of graph division and graph clustering of different network nodes

結(jié)果表明，隨著節(jié)點(diǎn)數(shù)量的增大，算法的執(zhí)行時(shí)間在不斷增加。在執(zhí)行時(shí)間上，圖結(jié)構(gòu)的節(jié)點(diǎn)聚類(lèi)算法的執(zhí)行時(shí)間總是多于圖結(jié)構(gòu)的節(jié)點(diǎn)劃分算法。然而，圖聚類(lèi)與圖劃分相比，聚類(lèi)整個(gè)圖結(jié)構(gòu)中節(jié)點(diǎn)關(guān)聯(lián)信息的成本更高，但圖聚類(lèi)算法對(duì)圖結(jié)構(gòu)中節(jié)點(diǎn)聚類(lèi)的效果更好。因此，圖節(jié)點(diǎn)的聚類(lèi)算法是在圖劃分算法的基礎(chǔ)上進(jìn)行的。也就是在得到圖中節(jié)點(diǎn)的模塊劃分之后，進(jìn)一步為了得出節(jié)點(diǎn)之間的關(guān)聯(lián)程度，利用K維結(jié)構(gòu)熵的最小值對(duì)已劃分的模塊做進(jìn)一步的聚類(lèi)，從而有效地得出整體圖結(jié)構(gòu)中節(jié)點(diǎn)之間的關(guān)聯(lián)程度。

4種節(jié)點(diǎn)聚類(lèi)方案的執(zhí)行時(shí)間如圖7所示。結(jié)果顯示，本文方法與其他3種方法在執(zhí)行小規(guī)模數(shù)據(jù)時(shí)，執(zhí)行時(shí)間和成本開(kāi)銷(xiāo)相差較小。然而在執(zhí)行大規(guī)模數(shù)據(jù)時(shí)，本文所提出的聚類(lèi)方法有較短的執(zhí)行時(shí)間。從而反映了本文方法能夠有效地執(zhí)行大規(guī)模的動(dòng)態(tài)數(shù)據(jù)，縮短聚類(lèi)時(shí)間和減小聚類(lèi)成本。對(duì)于文獻(xiàn)[27]方法而言，隨著數(shù)據(jù)集的增加，K-means算法的執(zhí)行時(shí)間大大增加，導(dǎo)致計(jì)算開(kāi)銷(xiāo)也隨之增加。文獻(xiàn)[28]方法，在數(shù)據(jù)集中選擇的參數(shù)均為eps = 0.1，minPts = 10。隨著數(shù)據(jù)集的變化，DBSCAN算法的執(zhí)行時(shí)間也有較大幅度的上升。相對(duì)于文獻(xiàn)[29]方法而言，由于本文不需要計(jì)算分布在多個(gè)GPU上來(lái)擴(kuò)大規(guī)模，因此縮短了計(jì)算時(shí)間，同時(shí)也存在相對(duì)較小的開(kāi)銷(xiāo)成本問(wèn)題，極大程度上提高了本文方法對(duì)圖結(jié)構(gòu)中節(jié)點(diǎn)關(guān)聯(lián)信息的聚類(lèi)效率。

圖7 不同網(wǎng)絡(luò)節(jié)點(diǎn)4種聚類(lèi)方案的執(zhí)行時(shí)間Figure 7 The execution time of the four clustering schemes for different network nodes

為了實(shí)現(xiàn)一個(gè)高效的動(dòng)態(tài)聚類(lèi)方法，本文利用結(jié)構(gòu)熵的最小值來(lái)反映圖結(jié)構(gòu)節(jié)點(diǎn)的最優(yōu)聚類(lèi)效果。圖8為模擬網(wǎng)絡(luò)節(jié)點(diǎn)的數(shù)目在100~500變化的情況下進(jìn)行的節(jié)點(diǎn)聚類(lèi)所得到二維結(jié)構(gòu)熵和K維結(jié)構(gòu)熵的最小值。從圖8中可以看出，隨著節(jié)點(diǎn)數(shù)目的增大，結(jié)構(gòu)熵的值也增大。然而在相同節(jié)點(diǎn)下，K維結(jié)構(gòu)熵總是小于二維結(jié)構(gòu)熵。因此更好地說(shuō)明K維結(jié)構(gòu)信息能夠有效地反映圖結(jié)構(gòu)的真實(shí)信息，從而有利于針對(duì)圖結(jié)構(gòu)中節(jié)點(diǎn)得出最優(yōu)的聚類(lèi)結(jié)果。同時(shí)結(jié)構(gòu)熵可以用來(lái)度量嵌入在一個(gè)圖中的高維信息或深度信息，并且在度量結(jié)構(gòu)信息的同時(shí)解碼出原始圖結(jié)構(gòu)的實(shí)質(zhì)結(jié)構(gòu)。因此，可以將結(jié)構(gòu)熵的最小值K維結(jié)構(gòu)信息看作是解碼圖結(jié)構(gòu)中節(jié)點(diǎn)真實(shí)信息的衡量標(biāo)準(zhǔn)，有效地反映了圖結(jié)構(gòu)中節(jié)點(diǎn)之間的聚類(lèi)效果。

圖8 不同網(wǎng)絡(luò)圖的熵值對(duì)比Figure 8 Comparison of entropy values of different network diagrams

6 結(jié)束語(yǔ)

本文基于結(jié)構(gòu)熵的聚類(lèi)方法提出了對(duì)圖結(jié)構(gòu)中節(jié)點(diǎn)的劃分。該方法主要是檢測(cè)出圖結(jié)構(gòu)中的真實(shí)結(jié)構(gòu)信息，同時(shí)挖掘出圖結(jié)構(gòu)中節(jié)點(diǎn)之間的關(guān)聯(lián)信息。具體來(lái)說(shuō)，本文方法不僅適用于大規(guī)模的網(wǎng)絡(luò)圖結(jié)構(gòu)，而且還在保證聚類(lèi)結(jié)果可靠性的同時(shí)，有效地提高了計(jì)算效率，減少了開(kāi)銷(xiāo)。在未來(lái)的工作中，將進(jìn)一步研究當(dāng)無(wú)向無(wú)權(quán)圖擴(kuò)展到有向加權(quán)圖時(shí)，如何挖掘圖結(jié)構(gòu)中的關(guān)聯(lián)信息，以及如何有效地保護(hù)挖掘出來(lái)的結(jié)構(gòu)信息和原始圖結(jié)構(gòu)中的隱私信息。