張志穎，田有亮,3

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

1 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

對于每個節(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)是一個n個頂點(diǎn)m條邊的無向連通圖，對于每個頂點(diǎn)i? { 1,2,…,n}。用di表示G中頂點(diǎn)i的度，m為圖邊的數(shù)量，設(shè)Qi=di/2m。然后用概率向量Q=(Q1,Q2,…,Qn)來描述圖G中頂點(diǎn)的平穩(wěn)分布。由此可定義圖G的一維結(jié)構(gòu)信息：

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

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

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

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

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

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

3 問題描述

3.1 方案模型

結(jié)構(gòu)熵被用來度量嵌入圖結(jié)構(gòu)中的不確定性，結(jié)構(gòu)熵的最小化是解碼圖結(jié)構(gòu)中真實(shí)結(jié)構(gòu)的一種直觀的方法。通過圖結(jié)構(gòu)的結(jié)構(gòu)熵最小化，將圖結(jié)構(gòu)的隨機(jī)變化和噪聲引起的擾動減小到最小，并且在比較圖結(jié)構(gòu)的節(jié)點(diǎn)模塊合并前后結(jié)構(gòu)熵的差異程度過程中，可反映出圖結(jié)構(gòu)中節(jié)點(diǎn)之間的關(guān)聯(lián)程度。如圖1所示，在圖結(jié)構(gòu)交互過程中如何有效地挖掘出它們之間的關(guān)聯(lián)程度是本文所要考慮的新問題。針對這一問題，可以用圖的二維結(jié)構(gòu)熵度量圖中的結(jié)構(gòu)信息。對于圖中的每一個節(jié)點(diǎn)模塊，在模塊的生成過程中，任意兩個節(jié)點(diǎn)模塊的合并必須滿足熵減原則，也就是說兩個節(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)聚類模型Figure 1 Graph structure node clustering model

3.2 算法設(shè)計

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

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

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

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

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

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

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

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

該算法的節(jié)點(diǎn)模塊劃分方法的主要過程如下：假設(shè)v1,v2,…,vn是節(jié)點(diǎn)集合V中所有按順序排列出的節(jié)點(diǎn)。將Xi設(shè)置為所有i的單例{vi}，構(gòu)成了所有節(jié)點(diǎn)集V的初始劃分模塊。如果不存在滿足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)程度，既不需要改變原始數(shù)據(jù)也不需要選擇參數(shù)。這就排除了在歸一化或在參數(shù)選擇中可能產(chǎn)生噪聲的影響。

本節(jié)使用了一種基于結(jié)構(gòu)信息理論的圖節(jié)點(diǎn)分區(qū)算法。通過節(jié)點(diǎn)的劃分模塊和整體的劃分分區(qū)，用結(jié)構(gòu)熵的最小值來獲取圖中節(jié)點(diǎn)隨機(jī)游動發(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ū)算法不僅挖掘出了使整個網(wǎng)絡(luò)的不確定性最小化的基本結(jié)構(gòu)，而且從模塊分區(qū)結(jié)果中反映出網(wǎng)絡(luò)中連接緊密程度最高的節(jié)點(diǎn)模塊。

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

網(wǎng)絡(luò)表現(xiàn)為特定群體中多個個體及它們之間相互聯(lián)系組成的集合，最適合用圖來表示。其中，節(jié)點(diǎn)表示個體，邊表示個體間的聯(lián)系。常見的網(wǎng)絡(luò)圖結(jié)構(gòu)模型為簡單的圖模型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ò)中個體之間聯(lián)系的緊密程度不同，結(jié)構(gòu)邊的權(quán)值不同。本文假設(shè)給定的是一個無向無權(quán)的連通圖，結(jié)構(gòu)邊具有相等的權(quán)值，均為1。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

首先通過算法1和算法2對圖進(jìn)行模塊劃分，計算出圖的二維結(jié)構(gòu)信息H2(G)3.23= 。由此可見，通過二維結(jié)構(gòu)信息和熵減原則算法，將圖劃分為大小不同的模塊，并計算不同模塊的結(jié)構(gòu)熵H P(G)，最終得出圖的二維結(jié)構(gòu)信息H2(G) =min{H P(G)}，此時模塊P的劃分結(jié)果便是圖中節(jié)點(diǎn)屬性相關(guān)程度大的為一個模塊。因此，如圖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ū)樹，引入根節(jié)點(diǎn)λ，模塊P中每一個子模塊X i(i= 1,2,3,4)為樹節(jié)點(diǎn)，每個子模塊中的節(jié)點(diǎn)為該樹節(jié)點(diǎn)下的葉子節(jié)點(diǎn)。二維分區(qū)樹如圖4所示。

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

最后將以模塊P的最優(yōu)劃分結(jié)果通過算法3做進(jìn)一步的節(jié)點(diǎn)聚類，并計算出圖的K維結(jié)構(gòu)信息H K(G)= 3.07。因此，通過K維結(jié)構(gòu)信息聚類算法，將所有的模塊P生成的二維分區(qū)樹轉(zhuǎn)化成高度為K的分區(qū)樹，并計算出不同的K維分區(qū)樹的結(jié)構(gòu)熵H T(G)，最終得出圖的K維結(jié)構(gòu)信息H K(G) =min{H T(G)}，此時所得到的分區(qū)樹便是將圖中每個節(jié)點(diǎn)屬性關(guān)聯(lián)程度最大的聚類在一起。如圖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)程度沒有變化。

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

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

5.2 有效性比較與分析

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

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

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

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

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

表2 聚類功能對比Table 2 clustering function comparison

5.3 仿真分析

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

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

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

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

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

為了實(shí)現(xiàn)一個高效的動態(tài)聚類方法，本文利用結(jié)構(gòu)熵的最小值來反映圖結(jié)構(gòu)節(jié)點(diǎn)的最優(yōu)聚類效果。圖8為模擬網(wǎng)絡(luò)節(jié)點(diǎn)的數(shù)目在100~500變化的情況下進(jìn)行的節(jié)點(diǎn)聚類所得到二維結(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)熵。因此更好地說明K維結(jié)構(gòu)信息能夠有效地反映圖結(jié)構(gòu)的真實(shí)信息，從而有利于針對圖結(jié)構(gòu)中節(jié)點(diǎn)得出最優(yōu)的聚類結(jié)果。同時結(jié)構(gòu)熵可以用來度量嵌入在一個圖中的高維信息或深度信息，并且在度量結(jié)構(gòu)信息的同時解碼出原始圖結(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)之間的聚類效果。

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

6 結(jié)束語

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