張振宇，朱培棟，王 可，胡慧俐

(國(guó)防科學(xué)技術(shù)大學(xué) 計(jì)算機(jī)學(xué)院，湖南 長(zhǎng)沙 410073)

0 引 言

20世紀(jì)90年代以來，國(guó)際互聯(lián)網(wǎng)、社交網(wǎng)絡(luò)、新陳代謝網(wǎng)絡(luò)、電力網(wǎng)絡(luò)、交通網(wǎng)絡(luò)、腦細(xì)胞網(wǎng)絡(luò)等使得人們生活的世界處于各種不同類型的復(fù)雜網(wǎng)絡(luò)之中，對(duì)各類復(fù)雜網(wǎng)絡(luò)性質(zhì)的研究隨之成為必要。社交網(wǎng)絡(luò)中社區(qū)結(jié)構(gòu)的發(fā)現(xiàn)，不僅有助于網(wǎng)絡(luò)功能的發(fā)掘、網(wǎng)絡(luò)內(nèi)部連接層次的識(shí)別、社交網(wǎng)絡(luò)上復(fù)雜用戶行為及群體行為的理解[1]，同時(shí)其分析理論也廣泛應(yīng)用于其他學(xué)科。

現(xiàn)有的一些經(jīng)典社區(qū)發(fā)現(xiàn)算法，如GN算法、FastNewman算法、遺傳算法、系派過濾法、紐帶社區(qū)等，均只是基于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)[2]進(jìn)行社區(qū)發(fā)現(xiàn)。但是，社交網(wǎng)絡(luò)節(jié)點(diǎn)往往蘊(yùn)含豐富的屬性信息，這些信息對(duì)社區(qū)結(jié)構(gòu)的形成具有重要影響，目前帶有節(jié)點(diǎn)屬性的社區(qū)發(fā)現(xiàn)，如基于隨機(jī)游走的邊權(quán)值節(jié)點(diǎn)屬性相似度NAS算法[3]，衡量拓?fù)浣Y(jié)構(gòu)和節(jié)點(diǎn)屬性的距離概念[4]，邊穩(wěn)定稀疏模型[5]，聯(lián)合拓?fù)浜蛯傩缘姆治鯷6]，這些均將節(jié)點(diǎn)屬性作為影響因素進(jìn)行了考慮，但都沒有很好地解決兩者之間的相關(guān)關(guān)系，使其聯(lián)合分析無可避免地產(chǎn)生相關(guān)性誤差。目前聯(lián)合拓?fù)浣Y(jié)構(gòu)和節(jié)點(diǎn)屬性的社區(qū)發(fā)現(xiàn)技術(shù)有待進(jìn)一步深入分析。

文中綜合考慮社交網(wǎng)絡(luò)中的拓?fù)浣Y(jié)構(gòu)和節(jié)點(diǎn)屬性，通過對(duì)兩因素進(jìn)行去相關(guān)性操作和賦權(quán)處理，從而建立社交網(wǎng)絡(luò)的社區(qū)距離關(guān)系矩陣，最后針對(duì)得到的關(guān)系矩陣，設(shè)計(jì)一種依據(jù)模糊關(guān)系相關(guān)原理的社區(qū)發(fā)現(xiàn)算法。該算法具有較高的社區(qū)發(fā)現(xiàn)準(zhǔn)確率，并通過不同閾值的選定能得到多層次社區(qū)結(jié)構(gòu)[7]，解決社區(qū)層次性問題。

1 問題描述

對(duì)社交網(wǎng)絡(luò)進(jìn)行精準(zhǔn)的描述是社區(qū)發(fā)現(xiàn)的基礎(chǔ)?？捎脠D結(jié)構(gòu)對(duì)社交網(wǎng)絡(luò)進(jìn)行描述，用WG=(V,E,W,S)表示社交網(wǎng)絡(luò)[8]，其中V為圖節(jié)點(diǎn)集合，表示人；E為圖邊集合，表示人與人之間的社交關(guān)系；W為圖邊權(quán)值，表示關(guān)系的強(qiáng)弱；S為圖節(jié)點(diǎn)信息，表示人對(duì)應(yīng)的屬性信息。

社區(qū)結(jié)構(gòu)是一種網(wǎng)絡(luò)拓?fù)涮匦?，刻畫了連邊關(guān)系的局部聚類特性。為了發(fā)現(xiàn)或識(shí)別社區(qū)結(jié)構(gòu)，如果能夠判定任意兩個(gè)節(jié)點(diǎn)是否處于同一社區(qū)，那么該社區(qū)結(jié)構(gòu)也就唯一確定。用矩陣描述為P=[pij]n×n，其中pij∈{0,1}，0表示對(duì)應(yīng)兩人處于不同社區(qū)，1表示對(duì)應(yīng)兩人處于相同社區(qū)。需要指出的是：每個(gè)人和自己必定處于相同社區(qū)；如果A與B處于相同社區(qū)，那么B與A也處于相同社區(qū)，反之亦然；如果A與C處于相同社區(qū)，B與C也處于相同社區(qū)，那么B與C亦處于相同社區(qū)。

將上述三個(gè)條件符號(hào)化：矩陣P中，若pii=1，即滿足自反性；若pij=pji，即滿足對(duì)稱性；若pij=1，pjk=1，則有pik=1，即滿足傳遞性。故反映社區(qū)結(jié)構(gòu)的矩陣P是普通等價(jià)矩陣。

由此，可將問題進(jìn)行如下描述：

f(W,S)=P

(1)

其中，W表示網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)；S表示網(wǎng)絡(luò)節(jié)點(diǎn)屬性；P表示社區(qū)結(jié)構(gòu)，為普通等價(jià)矩陣；函數(shù)f表示網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和節(jié)點(diǎn)屬性到社區(qū)結(jié)構(gòu)的映射關(guān)系，即為所求。

2 網(wǎng)絡(luò)社區(qū)距離

從社交網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)和節(jié)點(diǎn)屬性出發(fā)得到社交網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)。為避免社區(qū)發(fā)現(xiàn)結(jié)果受影響因子間相關(guān)性的影響，本節(jié)對(duì)影響因子進(jìn)行去相關(guān)性分析；同時(shí)，基于設(shè)計(jì)的穩(wěn)定性賦權(quán)方法綜合拓?fù)浣Y(jié)構(gòu)和節(jié)點(diǎn)屬性。

2.1 拓?fù)浣Y(jié)構(gòu)與節(jié)點(diǎn)屬性的相關(guān)性分析

對(duì)于節(jié)點(diǎn)屬性，同社區(qū)的屬性相似度相對(duì)較高，不同社區(qū)的屬性相似度相對(duì)較低，因此，相較于屬性值，屬性相似性更能體現(xiàn)網(wǎng)絡(luò)的社區(qū)情況。文中用歐氏距離描述屬性相似性。

綜合拓?fù)浣Y(jié)構(gòu)和節(jié)點(diǎn)屬性進(jìn)行社區(qū)結(jié)構(gòu)發(fā)現(xiàn)時(shí)，兩者之間的相關(guān)性容易為后面的綜合討論帶來疊加效應(yīng)[3]。目前社交網(wǎng)絡(luò)中關(guān)系的量化并沒有形成統(tǒng)一的標(biāo)準(zhǔn)，量化誤差會(huì)使得關(guān)系數(shù)據(jù)偏離理論上的正態(tài)分布；節(jié)點(diǎn)屬性的量化賦值方法具有極大的主觀性，使得屬性總體分布類型未知。因此，采用Spearman相關(guān)系數(shù)對(duì)兩者之間的相關(guān)性進(jìn)行度量。Spearman相關(guān)系數(shù)用于對(duì)不服從正態(tài)分布的數(shù)據(jù)、總體分布類型未知的數(shù)據(jù)的關(guān)聯(lián)性進(jìn)行描述。

取X和Y兩個(gè)集合對(duì)應(yīng)表示矩陣W和N中的數(shù)值，Xi、Yi為對(duì)應(yīng)集合中的第i(0

(2)

基于上述分析，通過如下操作進(jìn)行相似性和去相關(guān)性處理：

(3)

(4)

此時(shí)，對(duì)于問題的求解，得到如下過程：

f1(W,S)=(W,N)

(5)

其中，W為關(guān)系強(qiáng)度矩陣；S為網(wǎng)絡(luò)節(jié)點(diǎn)屬性矩陣；N為強(qiáng)度無關(guān)屬性矩陣；函數(shù)f1為相關(guān)性剔除函數(shù)，是函數(shù)f的分函數(shù)。

2.2 網(wǎng)絡(luò)社區(qū)距離指數(shù)

所研究問題的難點(diǎn)在于如何確定兩影響因素對(duì)社區(qū)結(jié)構(gòu)的影響程度。針對(duì)不相關(guān)變量的綜合處理，目前有多種解決方法，但是，大部分方法中的權(quán)重需要主觀賦予，而社交網(wǎng)絡(luò)很難從機(jī)理的角度得到二者對(duì)社區(qū)結(jié)構(gòu)之間的影響權(quán)重，故該類方法對(duì)于本問題具有較大主觀性。

(6)

前文只分析了兩節(jié)點(diǎn)間的直接關(guān)系對(duì)社區(qū)結(jié)構(gòu)形成的影響，而社區(qū)結(jié)構(gòu)其內(nèi)部節(jié)點(diǎn)的聚類系數(shù)很高，社區(qū)聚類系數(shù)由節(jié)點(diǎn)間的間接關(guān)系反映。因此，把節(jié)點(diǎn)間的間接關(guān)系作為社區(qū)結(jié)構(gòu)形成的另一影響因素，同時(shí)，由于社交網(wǎng)絡(luò)的小世界性，認(rèn)為三度(及以上)鄰居關(guān)系的影響較小。用該對(duì)節(jié)點(diǎn)與其他節(jié)點(diǎn)的距離的差方和來衡量?jī)啥揉従拥挠绊懸蜃樱?/p>

(7)

(8)

文中提出“社區(qū)距離”的概念[9]。根據(jù)以上分析，綜合穩(wěn)定性賦權(quán)和聚類系數(shù)操作，根據(jù)式(6)～(8)提出反映兩節(jié)點(diǎn)的社區(qū)情況的社區(qū)距離，定義如下：

(9)

其中，σN為矩陣N元素的方差；σW為矩陣W元素的方差；lij為節(jié)點(diǎn)i與節(jié)點(diǎn)j之間的社區(qū)距離。得到社區(qū)距離矩陣L=[lij]n×n。

此時(shí)，對(duì)于問題的求解，得到如下過程：

f3(W,N)=L

(10)

其中，W為關(guān)系強(qiáng)度矩陣；N為強(qiáng)度無關(guān)屬性矩陣；L為網(wǎng)絡(luò)社區(qū)距離矩陣；函數(shù)f3為社區(qū)距離函數(shù)，是函數(shù)f的分函數(shù)。

3 基于模糊關(guān)系的社區(qū)發(fā)現(xiàn)

文中最終要得到的社區(qū)結(jié)構(gòu)是一種普通等價(jià)關(guān)系，而社區(qū)距離矩陣L也是一種關(guān)系的表現(xiàn)，因此，文中社區(qū)發(fā)現(xiàn)的過程實(shí)質(zhì)是關(guān)系變換的過程，即從普通關(guān)系變換為等價(jià)關(guān)系。本節(jié)基于模糊關(guān)系相關(guān)理論對(duì)網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行分析，從而進(jìn)行社區(qū)發(fā)現(xiàn)。

3.1 社區(qū)距離的模糊等價(jià)化

將社區(qū)距離矩陣Ln×n表示為節(jié)點(diǎn)集V×V中的模糊關(guān)系。在該模糊關(guān)系中[10]，lij∈[0,1]，lii=0，lij=lji，此模糊關(guān)系只滿足對(duì)稱性。

欲使關(guān)系滿足自反性，令lii=1，此時(shí)，lij∈[0,1]，lij=lji，lii=1，該矩陣同時(shí)滿足對(duì)稱性、自反性，為模糊相似矩陣。

此時(shí)，對(duì)于問題的求解，得到如下過程：

f4(L)=Ln-1

(11)

其中，L為網(wǎng)絡(luò)社區(qū)距離矩陣；Ln-1為L(zhǎng)的n-1次max-min乘積[13]；函數(shù)f4為模糊傳遞閉包函數(shù)，是函數(shù)f的分函數(shù)。

3.2 模糊關(guān)系確定化

文中需要得到能反映社區(qū)結(jié)構(gòu)的普通等價(jià)矩陣,模糊數(shù)學(xué)中的截關(guān)系運(yùn)算可以完成。令L是V×V中的模糊關(guān)系，對(duì)任意α∈[0,1]，其α截關(guān)系Lα的特征函數(shù)為：

(12)

由此，在沒有改變關(guān)系的等價(jià)性的前提下，模糊關(guān)系轉(zhuǎn)化為確定關(guān)系，最終得到明確的節(jié)點(diǎn)劃分關(guān)系—社區(qū)結(jié)構(gòu)。有必要指出：基于不同的截取值，會(huì)有不同的社區(qū)結(jié)構(gòu)，即該社區(qū)發(fā)現(xiàn)具有多層次性。

此時(shí)，對(duì)于問題的求解，得到如下過程：

f5(Ln-1)=P

(13)

其中，P為社區(qū)結(jié)構(gòu)矩陣；函數(shù)f5為截運(yùn)算函數(shù)，是函數(shù)f的分函數(shù)。

4 算法描述

從拓?fù)浣Y(jié)構(gòu)和節(jié)點(diǎn)屬性出發(fā)，對(duì)該影響因素進(jìn)行相關(guān)性分析、權(quán)值賦予討論，通過模糊關(guān)系相關(guān)理論進(jìn)行社區(qū)發(fā)現(xiàn)，給出一種新的社區(qū)結(jié)構(gòu)發(fā)現(xiàn)方法，算法模型如下：

f(W,S)=f4(f3(f2(f1(W,S))))=P

(14)

其中，W表示網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)；S表示網(wǎng)絡(luò)節(jié)點(diǎn)屬性；P表示社區(qū)結(jié)構(gòu)；f1為相關(guān)性剔除函數(shù)；f2為社區(qū)距離函數(shù)；f3為模糊傳遞閉包函數(shù)；f4為截運(yùn)算函數(shù)。

文中社區(qū)發(fā)現(xiàn)模糊算法的具體描述如下：

輸入：連接矩陣W，屬性矩陣S

輸出：社區(qū)結(jié)構(gòu)P

2.defineD=排序差分(W,N')

3.defineρ=Spearman相關(guān)系數(shù)(D)

5.for(i,j雙循環(huán))

6.for(n次循環(huán))defineλij=λij+[1-(wik-wjk)]2/n

7.defineγij=γij+[1-(nik-njk)]2/n； //三度鄰居關(guān)系

8.defineσW=(W的方差)；σN=(N的方差)；

9.σW=σN/(σW+σN)；σN=σW/(σW+σN) //基于穩(wěn)定性賦權(quán)

10.for(i,j雙循環(huán))

11.definelij=σWλijwij+σNγijnij//綜合權(quán)值擬合

12.for(n-1次循環(huán))

13.for(i,j雙循環(huán))

15.define(α=input)

17.elsepij=0 //模糊截關(guān)系處理

18.if(P==預(yù)期) over //社區(qū)層次性選擇

19.else 返回(15)

20.returnP

算法流程如圖1所示。從社交網(wǎng)絡(luò)出發(fā)，得到社交網(wǎng)絡(luò)中反映拓?fù)浣Y(jié)構(gòu)的關(guān)系矩陣和反映節(jié)點(diǎn)屬性的屬性矩陣；對(duì)屬性矩陣進(jìn)行相似性變換得到屬性相似性矩陣；對(duì)關(guān)系矩陣和屬性相似性矩陣進(jìn)行相關(guān)性分析得到修正關(guān)系矩陣和修正相似性矩陣；對(duì)兩修正矩陣進(jìn)行賦權(quán)處理得到社區(qū)距離矩陣；對(duì)社區(qū)距離矩陣進(jìn)行模糊傳遞閉包處理得到模糊等價(jià)矩陣；進(jìn)而基于截關(guān)系得到能夠反映社區(qū)結(jié)構(gòu)的普通等價(jià)矩陣。

圖1 算法流程

5 算法實(shí)現(xiàn)與分析

文中算法與各經(jīng)典算法基于不同的數(shù)據(jù)集進(jìn)行比較分析?；贖OT模型[14]得到網(wǎng)絡(luò)模擬數(shù)據(jù)，社區(qū)評(píng)價(jià)指標(biāo)為模塊度與NMI[15]。模塊度是社區(qū)內(nèi)部的總邊數(shù)和網(wǎng)絡(luò)中總邊數(shù)的比例減去一個(gè)期望值，用于在不知道網(wǎng)絡(luò)真實(shí)劃分的情況下量化或評(píng)判的社區(qū)劃分水平。NMI是歸一化互信息，用于衡量算法劃分結(jié)果和真實(shí)結(jié)果的重合程度；通過模擬數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)；基于不同社區(qū)參數(shù)和網(wǎng)絡(luò)規(guī)模下[16]的社交網(wǎng)絡(luò)進(jìn)行實(shí)驗(yàn)結(jié)果以及時(shí)間復(fù)雜度比較如圖2～4及表1所示。

圖2 不同社區(qū)度網(wǎng)絡(luò)下各算法的模塊度

圖3 不同社區(qū)度網(wǎng)絡(luò)下各算法模塊度NMI

圖4 不同規(guī)模網(wǎng)絡(luò)下社區(qū)模塊度

表1 各算法時(shí)間復(fù)雜度

由圖2可以看到，不同社區(qū)參數(shù)下，文中算法得到的社區(qū)結(jié)構(gòu)的模塊度較高，且對(duì)社區(qū)參數(shù)不敏感；由圖3可以看到，不同社區(qū)參數(shù)下，文中算法得到的社區(qū)結(jié)構(gòu)的NMI較高，且對(duì)社區(qū)參數(shù)較敏感，社區(qū)參數(shù)較大時(shí)下降較快；由圖4可以看到，不同網(wǎng)絡(luò)規(guī)模下，文中算法得到的社區(qū)結(jié)構(gòu)的模塊度低于遺傳算法但均好于其他算法，且對(duì)網(wǎng)絡(luò)規(guī)模相對(duì)不敏感；由表1可以看到，文中算法時(shí)間復(fù)雜度相對(duì)較高，不太適用于大規(guī)模網(wǎng)絡(luò)分析，這也是后續(xù)工作中應(yīng)該關(guān)注和改進(jìn)的方向。

由此，相比各算法，文中算法時(shí)間復(fù)雜度相對(duì)較高，算法準(zhǔn)確率高且穩(wěn)定，對(duì)網(wǎng)絡(luò)規(guī)模和網(wǎng)絡(luò)聚類性不敏感，具有較高的準(zhǔn)確性，適用于小型網(wǎng)絡(luò)、中型網(wǎng)絡(luò)以及對(duì)時(shí)間要求不高的大型網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)。

6 結(jié)束語

從包含拓?fù)浣Y(jié)構(gòu)和節(jié)點(diǎn)屬性的完備信息集出發(fā)，通過相似性運(yùn)算、去相關(guān)性運(yùn)算、賦權(quán)運(yùn)算等操作進(jìn)行數(shù)據(jù)前期處理；基于模糊傳遞閉包思想進(jìn)行社區(qū)結(jié)構(gòu)的發(fā)現(xiàn)，通過截運(yùn)算得到社區(qū)結(jié)構(gòu)；最終實(shí)現(xiàn)了社交網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)，同時(shí)一定程度上解決了社區(qū)層次性的問題，緩解了網(wǎng)絡(luò)動(dòng)態(tài)性帶來的影響。

該算法基于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和節(jié)點(diǎn)屬性信息，增強(qiáng)了信息完備度；設(shè)計(jì)的穩(wěn)定賦權(quán)法和Spearman相關(guān)系數(shù)的引入解決了信息干擾問題；社區(qū)距離概念的提出和模糊關(guān)系理論的導(dǎo)入提升了社區(qū)發(fā)現(xiàn)的精度和穩(wěn)定性。

參考文獻(xiàn):

[1] AHN Y Y,BAGROW J P,LEHMANN S.Link communities reveal multiscale complexity in networks[J].Nature,2010,466(7307):761-764.

[2] 劉大有,金 弟,何東曉,等.復(fù)雜網(wǎng)絡(luò)社區(qū)挖掘綜述[J].計(jì)算機(jī)研究與發(fā)展,2013,50(10):2140-2154.

[3] STEINHAEUSER K,CHAWLA N V.Identifying and evaluating community structure in complex networks[J].Pattern Recognition Letters,2010,31(5):413-421.

[4] ZHOU Y,CHENG H,YU J X. Graph clustering based on structural/attribute similarities[J].Proceedings of the VLDB Endowment,2009,2(1):718-729.

[5] 林友芳,王天宇,唐 銳,等.一種有效的社會(huì)網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)模型和算法[J].計(jì)算機(jī)研究與發(fā)展,2012,49(2):337-345.

[6] 郭進(jìn)時(shí),湯紅波,葛國(guó)棟.一種聯(lián)合拓?fù)渑c屬性的社區(qū)模糊劃分算法[J].計(jì)算機(jī)工程,2013,39(11):35-40.

[7] 王 莉,程學(xué)旗.在線社會(huì)網(wǎng)絡(luò)的動(dòng)態(tài)社區(qū)發(fā)現(xiàn)及演化[J].計(jì)算機(jī)學(xué)報(bào)，2015，38(2)：219-237.

[8] 于 海,趙玉麗,崔 坤,等.一種基于交叉熵的社區(qū)發(fā)現(xiàn)算法[J].計(jì)算機(jī)學(xué)報(bào)，2015，38(8):1574-1581.

[9] HU R J,LI Q,ZHANG G Y,et al.Centrality measures in directed fuzzy social networks[J].Fuzzy Information and Engineering,2015,7(1):115-128.

[10] 范艷煥,耿生玲,李永明.Pebble模糊有窮自動(dòng)機(jī)和傳遞閉包邏輯[J].模糊系統(tǒng)與數(shù)學(xué),2015,29(4):38-44.

[11] 李秀格,朱紅寧.求模糊相似矩陣的傳遞閉包的簡(jiǎn)捷算法[J].電腦知識(shí)與技術(shù)，2014,10(26):6161-6164.

[12] PARAND F A,RAHIMI H,GORZIN M.Combining fuzzy logic and eigenvector centrality measure in social network analysis[J].Physica A:Statistical Mechanics and Its Applications,2015,459:24-31.

[13] RAJ E D,BABU L D D.A fuzzy adaptive resonance theory inspired over lapping community detection method for online social networks[J].Knowledge-Based Systems,2016,113:75-87.

[14] 吳增海.社交網(wǎng)絡(luò)模型的研究[D].合肥:中國(guó)科學(xué)技術(shù)大學(xué),2012.

[15] 王 林,戴冠中,趙煥成.一種新的評(píng)價(jià)社區(qū)結(jié)構(gòu)的模塊度研究[J].計(jì)算機(jī)工程,2010,36(14):227-229.

[16] 岳 訓(xùn),遲忠先,莫宏偉,等.基于網(wǎng)絡(luò)社區(qū)模塊結(jié)構(gòu)的特征選擇性能評(píng)價(jià)[J].計(jì)算機(jī)工程,2007,33(12):16-18.