融合屬性熵權(quán)和拓?fù)涞木植可鐓^(qū)發(fā)現(xiàn)算法

曹 旭，殷 銘，漆翔宇

(1.西南民族大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，四川 成都 610041；2.東華大學(xué)信息科學(xué)與技術(shù)學(xué)院，上海 200051)

復(fù)雜網(wǎng)絡(luò)研究一直是圖領(lǐng)域中的熱點(diǎn)研究問(wèn)題，通過(guò)對(duì)復(fù)雜網(wǎng)絡(luò)的研究可以有效揭示事物間隱含的固有深層關(guān)系.例如通過(guò)對(duì)社交網(wǎng)絡(luò)的研究可以幫助人們理解社會(huì)現(xiàn)象，對(duì)社交網(wǎng)絡(luò)用戶(hù)的關(guān)系和所發(fā)表的言論進(jìn)行分析，從而獲取不同群體的關(guān)系和觀點(diǎn)立場(chǎng)，進(jìn)而對(duì)網(wǎng)絡(luò)輿論予以管控[1].

社區(qū)結(jié)構(gòu)是社交網(wǎng)絡(luò)的一個(gè)重要特征，通常定義為具有緊密聯(lián)系的一組節(jié)點(diǎn).社區(qū)內(nèi)的節(jié)點(diǎn)連接緊密，即內(nèi)聚性強(qiáng)；社區(qū)之間連接較為松散，即耦合度弱[2].社區(qū)發(fā)現(xiàn)在現(xiàn)實(shí)生活中具備廣闊的應(yīng)用前景.如，可以對(duì)形成的社區(qū)進(jìn)行針對(duì)性的定向營(yíng)銷(xiāo)、疾病傳播建模預(yù)測(cè)、社交平臺(tái)的輿情監(jiān)測(cè)分析等[3].

1 研究現(xiàn)狀和存在問(wèn)題分析

傳統(tǒng)的社區(qū)發(fā)現(xiàn)算法通常側(cè)重于全局角度檢測(cè)社區(qū)，但是隨著網(wǎng)絡(luò)規(guī)模的快速擴(kuò)張，網(wǎng)絡(luò)的全局信息獲取難度不斷加大，導(dǎo)致算法效率不斷下降甚至算法無(wú)法使用.2005年，Clauset[4]提出只考慮目標(biāo)節(jié)點(diǎn)以及周?chē)?jié)點(diǎn)信息的局部社區(qū)發(fā)現(xiàn)算法.該算法定義了“局部社區(qū)模塊度”這一局部社區(qū)質(zhì)量指標(biāo).此為局部社區(qū)發(fā)現(xiàn)算法被首次提出.近年來(lái)，Wu[5]等人考慮到節(jié)點(diǎn)和社區(qū)相似度這一因素，通過(guò)賦予更高權(quán)重優(yōu)先級(jí)給高相似度的節(jié)點(diǎn)，以利于構(gòu)建局部社區(qū).Bouyer[6]提出了一種基于局部相似性的多級(jí)標(biāo)簽擴(kuò)散算法.該方法的優(yōu)勢(shì)在于從低度節(jié)點(diǎn)由外向內(nèi)的傳播標(biāo)簽，具有極低的時(shí)間復(fù)雜度.考慮到節(jié)點(diǎn)的屬性可以幫助發(fā)現(xiàn)社區(qū)，同時(shí)可使所形成的社區(qū)具有更好的可解釋性[7].Naderipour[8]等人基于可能性C-means模型，通過(guò)在大規(guī)模社交網(wǎng)絡(luò)中使用結(jié)構(gòu)相似性和屬性相似性來(lái)發(fā)現(xiàn)局部社區(qū).Lu[9]等人提出了一種基于領(lǐng)袖節(jié)點(diǎn)的局部社區(qū)發(fā)現(xiàn)算法.該算法利用網(wǎng)絡(luò)中節(jié)點(diǎn)之間的屬性信息構(gòu)造屬性相似度矩陣，然后將其與網(wǎng)絡(luò)拓?fù)湫畔⑾嘟Y(jié)合來(lái)建立節(jié)點(diǎn)之間的依賴(lài)關(guān)系.進(jìn)而，借助形成的依賴(lài)樹(shù)，可以得到社區(qū)劃分的最終結(jié)果.此外，研究人員還提出諸如模糊相似度[10]、節(jié)點(diǎn)熵[11]、圖嵌入[12]等方法來(lái)完成局部社區(qū)的發(fā)現(xiàn).

綜上所述，當(dāng)前研究都僅從相似性出發(fā)考慮節(jié)點(diǎn)屬性信息，著重于屬性值自身意義，忽略了屬性值在概率上的含義.地發(fā)現(xiàn)社區(qū).此外，設(shè)計(jì)一種兩階段的屬性加權(quán)策略來(lái)區(qū)分不同屬性的權(quán)重，以滿(mǎn)足社區(qū)擴(kuò)張過(guò)程的動(dòng)態(tài)變化.綜合以上二者再加之文獻(xiàn)[13]提出的社區(qū)密度，從而形成了“融合加權(quán)屬性熵和拓?fù)浣Y(jié)構(gòu)的局部社區(qū)發(fā)現(xiàn)算法(WAET)”.

2.1 問(wèn)題定義

給定圖G＝{VG，EG，A}，其中VG＝{vi｜i＝1...n}為圖G的節(jié)點(diǎn)集，共n個(gè)節(jié)點(diǎn)；EG＝{eij｜(i，j)∈VG}為圖G的邊集，共m條邊；A＝{at｜t＝1...d}為圖G的屬性集，共d條屬性.ai＝{avit｜vi∈VG，t∈A}是節(jié)點(diǎn)vi的屬性向量，avit表示節(jié)點(diǎn)vi在屬性at上的取值.Q是目標(biāo)節(jié)點(diǎn).要求在圖G上尋找一個(gè)包含目標(biāo)節(jié)點(diǎn)集的子圖C(即社區(qū))，社區(qū)節(jié)點(diǎn)集為VC＝{vi｜i＝1...c}，共c個(gè)節(jié)點(diǎn)；EC＝{eij｜(i，j)∈VC}為圖的邊集.

2.2 算法描述

2 WAET局部社區(qū)發(fā)現(xiàn)算法

本文將信息熵理論引入社區(qū)發(fā)現(xiàn)中，提出利用“社區(qū)加權(quán)屬性熵”衡量社區(qū)的屬性同質(zhì)性，從而更好

首先，創(chuàng)建初始社區(qū):結(jié)合“節(jié)點(diǎn)屬性”和“拓?fù)浣Y(jié)構(gòu)”挖掘目標(biāo)節(jié)點(diǎn)的核心節(jié)點(diǎn)集.其次，根據(jù)核心節(jié)點(diǎn)集學(xué)習(xí)社區(qū)初始屬性權(quán)重.之后，遍歷當(dāng)前社區(qū)的鄰居節(jié)點(diǎn)，并計(jì)算不同鄰居節(jié)點(diǎn)加入社區(qū)所能帶來(lái)的社區(qū)質(zhì)量增益.若添加該鄰居節(jié)點(diǎn)可以給社區(qū)帶來(lái)超越歷史加入節(jié)點(diǎn)的平均質(zhì)量增益，則將該節(jié)點(diǎn)加入社區(qū)并更新社區(qū)屬性權(quán)重；反之則跳過(guò)該節(jié)點(diǎn).循環(huán)遍歷直到?jīng)]有鄰居節(jié)點(diǎn)可以加入則終止循環(huán).最終，將當(dāng)前社區(qū)作為局部社區(qū)結(jié)果返回.算法流程詳見(jiàn)圖1.

圖1 WAET算法流程圖Fig.1 Algorithm flow chart of WAET

2.3 核心檢測(cè)

本階段是算法的第一步，旨在檢測(cè)合適的節(jié)點(diǎn)集作為局部社區(qū)的核心成員，對(duì)應(yīng)圖1的“a”部分.研究表明，社區(qū)的形成和穩(wěn)定取決于其核心成員[14]，因此合適的核心檢測(cè)是十分重要的.首先，挖掘圖G中包含目標(biāo)節(jié)點(diǎn)的極大團(tuán)[15].由于包含目標(biāo)節(jié)點(diǎn)的極大團(tuán)之間可能相互重疊，所以需要進(jìn)行篩選.若兩個(gè)規(guī)模為N的極大團(tuán)之間存在N-1個(gè)重疊節(jié)點(diǎn)，且兩個(gè)非重疊節(jié)點(diǎn)的屬性相似度同時(shí)大于兩個(gè)極大團(tuán)的平均屬性相似度，則將兩個(gè)極大團(tuán)合并成一個(gè)新節(jié)點(diǎn)集.當(dāng)所有節(jié)點(diǎn)集均無(wú)法合并時(shí)，選擇平均屬性相似度最大的節(jié)點(diǎn)集作為核心節(jié)點(diǎn)集.離散屬性相似度采用余弦相似度計(jì)算，連續(xù)屬性相似度采用歐幾里得相似度計(jì)算.

2.4 初始屬性權(quán)重

由于不同屬性在發(fā)現(xiàn)社區(qū)時(shí)的貢獻(xiàn)并非相同，也并非恒定的，因此本文設(shè)計(jì)了一種兩階段的屬性加權(quán)策略來(lái)確定屬性的權(quán)重.首先考慮到社區(qū)的核心節(jié)點(diǎn)集可以在一定程度上代表最終的局部社區(qū)，因此可以根據(jù)社區(qū)的核心節(jié)點(diǎn)集學(xué)習(xí)屬性初始權(quán)重.本階段對(duì)應(yīng)圖1中的“b”部分.

給定核心節(jié)點(diǎn)集Z，可通過(guò)最小化核心節(jié)點(diǎn)集的加權(quán)屬性距離之和，求解各屬性初始權(quán)重向量，目標(biāo)函數(shù)定義如式(1).

其中，c是核心節(jié)點(diǎn)集的節(jié)點(diǎn)數(shù)，d是屬性集的大小，wt代表屬性at的權(quán)重，β是權(quán)重wt的參數(shù)，avit是節(jié)點(diǎn)vi在屬性at上的值，vt＝K∈Vcore，‖avit-avjt‖2是節(jié)點(diǎn)vi和節(jié)點(diǎn)vj在屬性at上值的差值二范數(shù).該目標(biāo)函數(shù)描述了初始社區(qū)中節(jié)點(diǎn)之間基于屬性的加權(quán)距離之和，屬性權(quán)重遵循約束條件:其中wt∈[0，1].

對(duì)于有約束的函數(shù)極值求解，可通過(guò)Lagrange乘子法解決，最終求解出的初始權(quán)重wt見(jiàn)式(2).

2.5 局部社區(qū)質(zhì)量函數(shù)

求解出屬性的初始權(quán)重之后，便可擴(kuò)張核心節(jié)點(diǎn)集以獲得最終的局部社區(qū)，即圖1中的“c”部分.在本階段，算法會(huì)根據(jù)不同鄰居節(jié)點(diǎn)加入社區(qū)所能帶來(lái)的社區(qū)質(zhì)量增益判斷是否將其加入當(dāng)前社區(qū).社區(qū)質(zhì)量由本文提出的局部社區(qū)質(zhì)量函數(shù)計(jì)算，該函數(shù)從社區(qū)密度和社區(qū)加權(quán)屬性熵兩個(gè)角度對(duì)社區(qū)質(zhì)量進(jìn)行了衡量.函數(shù)公式見(jiàn)式(3).

其中，α為平衡結(jié)構(gòu)信息和屬性信息的參數(shù)；Dens(C)為社區(qū)密度；Ent(C)為社區(qū)加權(quán)屬性熵.

2.5.1 社區(qū)密度

文獻(xiàn)[13]提出的社區(qū)密度可以衡量社區(qū)的結(jié)構(gòu)內(nèi)聚性，雖其原是針對(duì)二部圖所設(shè)計(jì)，但其思想可沿用于本文所用圖中.社區(qū)密度Dens(C)定義為社區(qū)中節(jié)點(diǎn)對(duì)密度均值.節(jié)點(diǎn)對(duì)密度Dens(C)_node定義見(jiàn)式(4).

其中，(a，b)是社區(qū)C中的節(jié)點(diǎn)對(duì)；N(a)是節(jié)點(diǎn)a的鄰居集；為節(jié)點(diǎn)a的鄰居數(shù)量；vi是節(jié)點(diǎn)a的鄰居；vi是節(jié)點(diǎn)b的鄰居；φ為示性函數(shù)，見(jiàn)式(5).

進(jìn)一步的，局部社區(qū)密度計(jì)算方式見(jiàn)式(6).

當(dāng)使用社區(qū)密度Dens(C)作為社區(qū)檢測(cè)的評(píng)價(jià)標(biāo)準(zhǔn)時(shí)，社區(qū)密度越高，社區(qū)內(nèi)部的節(jié)點(diǎn)對(duì)越緊密.這一趨勢(shì)與社區(qū)發(fā)現(xiàn)所要求的社區(qū)結(jié)構(gòu)非常一致.因此，社區(qū)密度可以用來(lái)判斷社區(qū)發(fā)現(xiàn)結(jié)果的好壞.

2.5.2 社區(qū)加權(quán)屬性熵

信息熵[16]可以衡量一個(gè)系統(tǒng)的混亂程度，信息熵越大則系統(tǒng)越混亂，反之則系統(tǒng)越有序.

基于信息熵可以衡量系統(tǒng)混亂程度的思想，本文提出社區(qū)加權(quán)屬性熵.假設(shè)社區(qū)內(nèi)各屬性之間相互獨(dú)立的情況下，首先計(jì)算社區(qū)內(nèi)各屬性的信息熵值，之后將各屬性熵加權(quán)加總后即為社區(qū)的加權(quán)屬性熵.計(jì)算方法如下.

設(shè)社區(qū)中任一節(jié)點(diǎn)vi∈VC在屬性at∈A上的屬性概率為

即節(jié)點(diǎn)vi在屬性at上能取到值avit的概率.顯然，pi天然具有歸一性，則社區(qū)C在屬性at上的屬性熵定義為:

當(dāng)各屬性相互獨(dú)立時(shí)，社區(qū)的加權(quán)屬性熵計(jì)算見(jiàn)式(10).

由于前文中社區(qū)密度的值域?yàn)閇0，1]，而屬性熵的值域在[0，log2c]之間，在值域不同的情況下無(wú)法將兩者線性結(jié)合.故本文采用反正切歸一法將社區(qū)屬性熵映射到[0，1]中，最終和社區(qū)密度構(gòu)成局部社區(qū)質(zhì)量指標(biāo).反正切歸一法計(jì)算見(jiàn)式(10).

2.6 動(dòng)態(tài)權(quán)重調(diào)整

雖然社區(qū)加權(quán)屬性熵從屬性取值概率出發(fā)，提供了考慮節(jié)點(diǎn)屬性的新角度，但也忽略了屬性值的自身信息.因此在社區(qū)擴(kuò)張過(guò)程中，采用屬性相似度作為基本指標(biāo)來(lái)彌補(bǔ)社區(qū)屬性熵的不足，并據(jù)此完成第二階段的屬性權(quán)重調(diào)整.本階段同樣屬于圖1中“c”部分的內(nèi)容.

若社區(qū)內(nèi)多數(shù)節(jié)點(diǎn)在屬性at上都取值相似，則屬性at有利于社區(qū)發(fā)現(xiàn)；反之，若取值分布十分隨機(jī)，則at不是很好的社區(qū)屬性.社區(qū)屬性權(quán)重的計(jì)算見(jiàn)式(11).

其中，sim(avit，avjt)是節(jié)點(diǎn)vi，vj關(guān)于屬性vi，vj的相似度.

3 實(shí)驗(yàn)及分析

為了驗(yàn)證本文所提出算法的有效性，本文選擇與兩種局部社區(qū)發(fā)現(xiàn)方法:FocusCO[17]和TSCM[18]及一種全局社區(qū)發(fā)現(xiàn)方法:CODICIL[19]在真實(shí)數(shù)據(jù)集上進(jìn)行了大量實(shí)驗(yàn)以作對(duì)比.實(shí)驗(yàn)選擇三個(gè)指標(biāo):準(zhǔn)確率(Accuracy)、標(biāo)準(zhǔn)化互信息(NMI)[20]和局部模塊度(Local Modularity)來(lái)衡量算法性能.實(shí)驗(yàn)數(shù)據(jù)集使用了四個(gè)真實(shí)數(shù)據(jù)集:Political Books(Polbooks)、SinaNet、Facebook100以及Cora數(shù)據(jù)集.由于SinaNet數(shù)據(jù)集中存在無(wú)邊節(jié)點(diǎn)，故予以清除.真實(shí)數(shù)據(jù)集信息詳見(jiàn)表1.

表1 真實(shí)數(shù)據(jù)集Table 1 Realworld datasets

3.1 WAET參數(shù)設(shè)定

3.1.1 參數(shù)α的取值

參數(shù)α是平衡局部社區(qū)質(zhì)量函數(shù)的拓?fù)浣Y(jié)構(gòu)和節(jié)點(diǎn)屬性的參數(shù).圖2為當(dāng)α取值區(qū)間為[0，1]時(shí)對(duì)Accuracy和局部模塊度的影響.

圖2 α取值對(duì)于算法性能的影響Fig.2 Influence of different α values on algorithm performance

由于Polbooks數(shù)據(jù)集只有“政治傾向”一個(gè)屬性且并非稀疏圖，其在屬性和結(jié)構(gòu)相對(duì)平衡時(shí)表現(xiàn)較好；Cora數(shù)據(jù)集由于是二進(jìn)制屬性同時(shí)屬性維度較高，當(dāng)屬性占比過(guò)大時(shí)會(huì)影響實(shí)際社區(qū)發(fā)現(xiàn)的精確性；SinaNet數(shù)據(jù)集和Facebook100數(shù)據(jù)集均為較為密集的圖，且屬性維度均在10以?xún)?nèi)，但Facebook100數(shù)據(jù)集中屬性缺省值較多，即便進(jìn)行填充，屬性占比過(guò)大也會(huì)降低算法性能；而SinaNet數(shù)據(jù)集的真實(shí)社區(qū)分類(lèi)就是依據(jù)屬性偏好進(jìn)行分類(lèi)，所以屬性占比相較拓?fù)浣Y(jié)構(gòu)多時(shí)反而會(huì)取得較好的結(jié)果.

3.1.2 參數(shù)β的取值

在計(jì)算屬性權(quán)重時(shí)，除了屬性?xún)?nèi)部的相似度會(huì)影響到權(quán)重值外，參數(shù)β同樣會(huì)對(duì)權(quán)重產(chǎn)生影響.

當(dāng)β＜0時(shí)，Dt越大，wt越大，但wβt越小.而且由于β是負(fù)數(shù)的原因，在計(jì)算Dt時(shí)，權(quán)重wβt對(duì)于計(jì)算結(jié)果的影響也越小了，顯然該情況不考慮.

當(dāng)β＝0時(shí)，所有的權(quán)重值恒為1，相當(dāng)于忽略了權(quán)重因素，不符本文初衷，故不予考慮；當(dāng)β∈(0，1)時(shí)，Dt越大，權(quán)重wt越大，wβ t越大，這并不符合實(shí)際情況中社區(qū)的屬性同質(zhì)性，所以不考慮.

當(dāng)β＝1時(shí)，對(duì)于可以讓Dt中的最小值的屬性at來(lái)說(shuō)，可以讓其權(quán)重為1，其余的屬性的權(quán)重為0.雖然目標(biāo)函數(shù)此時(shí)已經(jīng)最小化，但是相當(dāng)于只用了一個(gè)屬性進(jìn)行社區(qū)發(fā)現(xiàn)，拋棄了其余屬性的影響.對(duì)于高維屬性社區(qū)發(fā)現(xiàn)問(wèn)題來(lái)說(shuō)，故該方法不可取.

當(dāng)β＞1時(shí)，Dt越大，wt越小，wβt也越小.具有較大Dt的屬性at對(duì)于社區(qū)發(fā)現(xiàn)的影響也就越小.

綜上所述，最終權(quán)重參數(shù)β的取值應(yīng)當(dāng)大于1.

由于Polbooks數(shù)據(jù)集只有一個(gè)屬性，因此對(duì)該數(shù)據(jù)集β取1即可，對(duì)于其他數(shù)據(jù)集，本文進(jìn)行了大量的實(shí)驗(yàn).實(shí)驗(yàn)證明，β取值在8、10、12時(shí)表現(xiàn)較好.圖3展示了不同的β值對(duì)算法Accuracy和局部模塊度的影響.

圖3 β取值對(duì)于算法性能的影響Fig.3 Influence of different β values on algorithm performance

3.2 結(jié)果分析

由于所用真實(shí)數(shù)據(jù)集中只有SinaNet數(shù)據(jù)集和Cora數(shù)據(jù)集具有真實(shí)社區(qū)分類(lèi)結(jié)果，因此選擇用NMI和Accracy兩個(gè)指標(biāo)與TSCM、FocusCO這兩個(gè)局部社區(qū)發(fā)現(xiàn)算法和全局社區(qū)發(fā)現(xiàn)方法CODICIL對(duì)比；而沒(méi)有真實(shí)社區(qū)結(jié)果的Polbooks數(shù)據(jù)集和Facebook數(shù)據(jù)集選擇使用局部模塊度(Local Modularity)指標(biāo)進(jìn)行衡量.

圖4和圖5展示了本文算法與對(duì)比算法在具有真實(shí)社區(qū)情況數(shù)據(jù)集上的準(zhǔn)確率和NMI值表現(xiàn)，圖6展示了本文算法在沒(méi)有真實(shí)社區(qū)分類(lèi)的數(shù)據(jù)集上的局部模塊度表現(xiàn).

圖4 Cora數(shù)據(jù)集上的Accuracy和NMI結(jié)果對(duì)比Fig.4 Comparison of Accuracy and NMI results on Cora dataset

由圖4和圖5可知，本文算法無(wú)論是在Accuracy還是NMI指標(biāo)上的表現(xiàn)均優(yōu)于對(duì)比算法，而全局社區(qū)發(fā)現(xiàn)算法CODICIL的表現(xiàn)較差.

圖5 SinaNet數(shù)據(jù)集上的Accuracy和NMI結(jié)果對(duì)比Fig.5 Comparison of Accuracy and NMI results on SinaNet dataset

由圖6可知，本文算法在無(wú)真實(shí)社區(qū)分類(lèi)的數(shù)據(jù)集上的表現(xiàn)也保持穩(wěn)定，CODICIL因其為全局算法，因此在局部模塊度上的表現(xiàn)較差，與其他局部社區(qū)發(fā)現(xiàn)算法差距較大.

圖6 Polbooks和Facebook100數(shù)據(jù)集上局部模塊度結(jié)果對(duì)比Fig.6 Comparison of local modularity results on Polbooks and Facebook100 datasets

4 總結(jié)

針對(duì)現(xiàn)有局部社區(qū)發(fā)現(xiàn)算法中利用節(jié)點(diǎn)屬性時(shí)僅從相似度出發(fā)，存在過(guò)于針對(duì)屬性值而未考慮其概率值的問(wèn)題.本文提出了一種從信息熵理論出發(fā)的社區(qū)加權(quán)屬性熵指標(biāo)，并在此基礎(chǔ)上設(shè)計(jì)了新的局部社區(qū)發(fā)現(xiàn)算法——WAET算法.該算法不僅為衡量社區(qū)屬性同質(zhì)性提供了新的思考角度，還較好解決了局部社區(qū)發(fā)現(xiàn)所存在的問(wèn)題.

事實(shí)上，實(shí)際情況中的社區(qū)結(jié)構(gòu)大多是重疊的，但本文算法無(wú)法識(shí)別重疊社區(qū)結(jié)構(gòu)，因此對(duì)于重疊社區(qū)的發(fā)現(xiàn)將在下一步的研究工作中進(jìn)行.