曹 旭，殷 銘，漆翔宇

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

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

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

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

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

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

2.1 問題定義

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

2.2 算法描述

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

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

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

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

2.3 核心檢測

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

2.4 初始屬性權重

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

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

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

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

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

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

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

2.5.1 社區(qū)密度

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

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

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

當使用社區(qū)密度Dens(C)作為社區(qū)檢測的評價標準時，社區(qū)密度越高，社區(qū)內(nèi)部的節(jié)點對越緊密.這一趨勢與社區(qū)發(fā)現(xiàn)所要求的社區(qū)結構非常一致.因此，社區(qū)密度可以用來判斷社區(qū)發(fā)現(xiàn)結果的好壞.

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

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

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

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

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

當各屬性相互獨立時，社區(qū)的加權屬性熵計算見式(10).

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

2.6 動態(tài)權重調(diào)整

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

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

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

3 實驗及分析

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

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

3.1 WAET參數(shù)設定

3.1.1 參數(shù)α的取值

參數(shù)α是平衡局部社區(qū)質(zhì)量函數(shù)的拓撲結構和節(jié)點屬性的參數(shù).圖2為當α取值區(qū)間為[0，1]時對Accuracy和局部模塊度的影響.

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

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

3.1.2 參數(shù)β的取值

在計算屬性權重時，除了屬性內(nèi)部的相似度會影響到權重值外，參數(shù)β同樣會對權重產(chǎn)生影響.

當β＜0時，Dt越大，wt越大，但wβt越小.而且由于β是負數(shù)的原因，在計算Dt時，權重wβt對于計算結果的影響也越小了，顯然該情況不考慮.

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

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

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

綜上所述，最終權重參數(shù)β的取值應當大于1.

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

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

3.2 結果分析

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

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

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

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

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

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

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

4 總結

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

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