張 玲，吳發(fā)輝

(武夷學(xué)院 信息技術(shù)與實驗室管理中心，福建 武夷 354300)

互聯(lián)網(wǎng)技術(shù)的發(fā)展，使得人際交流越來越方便，人們之間的聯(lián)系隨之越來越密切。在此背景下，各類社交平臺隨之出現(xiàn)，如微博、微信、抖音、釘釘?shù)?。通過社交平臺，將分布各地的人們聯(lián)系在一起，形成了一個龐大的社交網(wǎng)絡(luò)。在社交網(wǎng)絡(luò)上人們可以就一個問題發(fā)表自己的觀點和見解。由于個人在偏好和興趣方面存在的差異，又分成了各個不同的社區(qū)[1]。例如，就微博而言，一個明星擁有了眾多粉絲，這些粉絲都關(guān)注了該明星，以該明星為核心節(jié)點，就形成了一個社區(qū)。然而現(xiàn)實情況是一個人通常不會有一個興趣點，這就造成了一個人可能屬于多個社區(qū)的情況，即發(fā)生社區(qū)重疊現(xiàn)象。

社區(qū)重疊研究有著非常廣闊的應(yīng)用場景，比如，在社會消費方面，可以通過分析同一社區(qū)內(nèi)消費者行為特征，在該社區(qū)內(nèi)進(jìn)行商品推薦，提高商品的銷售量；在教育教學(xué)方面，可以根據(jù)同一社區(qū)內(nèi)學(xué)生的學(xué)習(xí)特征，分析該社區(qū)內(nèi)學(xué)生學(xué)習(xí)難點，并有針對性地推薦學(xué)習(xí)資源?；诖耍P(guān)于社區(qū)重疊問題的研究有很多[2]，面向?qū)傩跃W(wǎng)絡(luò)，提出一種基于密度峰值聚類的思想的發(fā)現(xiàn)算法，實現(xiàn)了重疊社區(qū)的劃分[3]。通過計算社區(qū)節(jié)點間H指數(shù)和局部影響力來判斷節(jié)點重要性，以此進(jìn)行重疊社區(qū)的識別[4]。提出了一個群體上兩端之間的協(xié)同進(jìn)化方案來解決網(wǎng)絡(luò)的重疊劃分問題。為表示網(wǎng)絡(luò)的重疊劃分，開發(fā)了一種由兩段組成的編碼方案，第一段表示不相交的劃分，第二段表示允許多成員身份的劃分的擴展，然后給出節(jié)點信息性的兩個度量，以此來判斷群體上兩段是否發(fā)生重疊。

本文在前人研究的基礎(chǔ)上，提出一種基于多模態(tài)融合的加權(quán)網(wǎng)絡(luò)重疊社區(qū)劃分算法。該算法主要提取網(wǎng)絡(luò)社區(qū)間的不同特征，然后進(jìn)行多模態(tài)融合，將融合后的特征輸入到分類器中，進(jìn)行重疊社區(qū)劃分。最后將所研究算法應(yīng)用到不同的社區(qū)網(wǎng)絡(luò)當(dāng)中，進(jìn)行重疊社區(qū)劃分，驗證算法應(yīng)用效果。

1 多模態(tài)融合的加權(quán)網(wǎng)絡(luò)重疊社區(qū)劃分算法研究

基于多模態(tài)融合的加權(quán)網(wǎng)絡(luò)重疊社區(qū)之間就會存在重疊部分，其結(jié)構(gòu)示意圖如圖1所示。

圖1 重疊社區(qū)網(wǎng)絡(luò)結(jié)構(gòu)示意圖

在重疊社區(qū)網(wǎng)絡(luò)結(jié)構(gòu)中可以看出，一個節(jié)點可以屬于多個社區(qū)，而重疊社區(qū)主要是圍繞這些節(jié)點建立的，重疊社區(qū)中節(jié)點就被稱為重疊節(jié)點。本文研究的加權(quán)網(wǎng)絡(luò)重疊社區(qū)劃分算法就是以加權(quán)網(wǎng)絡(luò)為基礎(chǔ)，找出其中重疊節(jié)點，完成不同社區(qū)之間重疊部分的識別。

1.1 加權(quán)網(wǎng)絡(luò)模型

根據(jù)是否加權(quán)，社交網(wǎng)絡(luò)大致分為兩種類型，即無權(quán)網(wǎng)絡(luò)和加權(quán)網(wǎng)絡(luò)，如圖2所示。

(a)無權(quán)網(wǎng)絡(luò)

(b)加權(quán)網(wǎng)絡(luò)圖2 社交網(wǎng)絡(luò)類型

在圖2中，wij是節(jié)點i和節(jié)點j之間的權(quán)重，代表了兩個節(jié)點之間的聯(lián)系緊密度。

在進(jìn)行網(wǎng)絡(luò)重疊社區(qū)劃分之前，為更好地刻畫現(xiàn)實網(wǎng)絡(luò)特征，需要對社交網(wǎng)絡(luò)進(jìn)行建模。由于本文研究的是加權(quán)網(wǎng)絡(luò)中重疊社區(qū)的劃分，因此針對圖2(b)進(jìn)行建模。在這里就用到了圖論(是利用圖為研究對象，是數(shù)學(xué)的一個分支)的知識，即將網(wǎng)絡(luò)中的所有事物用圖模型中的節(jié)點進(jìn)行表示，而事物之間存在的相互聯(lián)系就用圖模型中的邊表示[5]。由此可見，一個具體的社交網(wǎng)絡(luò)就是一個抽象的圖。

通過G(V,E,W)來描述加權(quán)網(wǎng)絡(luò)，其中，V為加權(quán)網(wǎng)絡(luò)中的節(jié)點集；E為加權(quán)網(wǎng)絡(luò)中兩兩節(jié)點連接邊的集合，W為兩兩節(jié)點連接邊的權(quán)重集合，W={wij}，wij值越大，兩兩節(jié)點聯(lián)系越密切。加權(quán)網(wǎng)絡(luò)通過鄰接矩陣表示如下。

(1)

1.2 加權(quán)網(wǎng)絡(luò)節(jié)點特征選擇

基于建立的加權(quán)網(wǎng)絡(luò)模型，對網(wǎng)絡(luò)中節(jié)點特征進(jìn)行選擇。重疊社區(qū)中各個節(jié)點的特征具有相似部分，因此只要明確節(jié)點特征，就能夠在后期很輕易地將其劃分為重疊部分[6]。

以往研究的大部分重疊劃分算法都以一種或者兩種算法作為基礎(chǔ)，因此導(dǎo)致后續(xù)識別精度不足，因此在本文當(dāng)中選擇多個特征，然后在下一步進(jìn)行多模態(tài)融合，將其作為分類器分類的依據(jù)。加權(quán)網(wǎng)絡(luò)節(jié)點特征主要包括以下平均路徑長度、節(jié)點度分布、節(jié)點從屬度、聚類系數(shù)、共鄰節(jié)點相似度等五種[7]。下面進(jìn)行具體分析。

1.2.1 平均路徑長度

平均路徑長度求取過程如下。

Step 1：明確加權(quán)網(wǎng)絡(luò)中節(jié)點間最短的路徑。

Step 2：計算最短路徑上邊的長度。

Step 3：對最短路徑上所有邊的長度進(jìn)行求和。

Step 4：求取求和結(jié)果的平均值，即平均路徑長度[8]。

平均路徑長度計算公式如式(2)所示。

(2)

1.2.2 節(jié)點度分布

節(jié)點度是指隨機選取一個節(jié)點，圍繞該節(jié)點周圍的相鄰節(jié)點的數(shù)量[9]。在加權(quán)網(wǎng)絡(luò)當(dāng)中，節(jié)點度是指鄰接矩陣中行或列相加之和，計算公式如式(3)所示。

(3)

式中，ki為節(jié)點i的節(jié)點度；aij為鄰接矩陣中行或列。

1.2.3 節(jié)點從屬度

節(jié)點從屬度是指節(jié)點對于核心社區(qū)Qk的從屬程度[10]。計算公式如式(4)所示。

(4)

式中，F(xiàn)(Ok,i)為節(jié)點i相對于核心社區(qū)Ok的從屬程度；Si,j為節(jié)點i與核心節(jié)點j之間邊的距離；wi為節(jié)點的權(quán)重。

1.2.4 聚類系數(shù)

聚類系數(shù)是指節(jié)點與之相鄰節(jié)點之間的連接緊密度，聚類系數(shù)越大，越有可能是重疊節(jié)點[11-12]。計算公式如式(5)所示。

(5)

式中，Z為聚類系數(shù)；Ei為節(jié)點i與之相鄰節(jié)點之間的連接邊的數(shù)量。

1.2.5 共鄰節(jié)點相似度

共鄰節(jié)點相似度計算過程：隨機選擇兩個節(jié)點，然后尋找與之相鄰的節(jié)點，然后判斷兩個節(jié)點是否存在共同的鄰居節(jié)點[13]。二者之間擁有的共同鄰居數(shù)目越多，相似度越高，越有可能是重疊節(jié)點。計算過程如下：

Step 1：隨機選擇兩個節(jié)點，記為x和y；

Step 2：以x和y為核心，建立兩個鄰域網(wǎng)絡(luò)，即X和Y；

Step 3：計算X中每一個節(jié)點與Y中每一個節(jié)點的匹配程度；

Step 4：將匹配成功的X和Y中的節(jié)點分別組成鄰域網(wǎng)絡(luò)I和J。

Step 5：計算鄰域網(wǎng)絡(luò)I和J中匹配的所有節(jié)點的和，得到節(jié)點度量值，記為H(X)。

Step 6：重復(fù)上述步驟，得到網(wǎng)絡(luò)Y的度量，記為H(Y)；

Step 7：計算X和Y之間的相似度，即為x和y之間的相似度。計算公式如式(6)所示。

(6)

式中，Qx,y為節(jié)點x和y的相似度；K(I,J)為鄰域網(wǎng)絡(luò)I和J中成功匹配的節(jié)點數(shù)量。

1.3 節(jié)點特征多模態(tài)融合

為方便后期分類器識別重疊節(jié)點，劃分重疊社區(qū)，需要將上一章節(jié)提取出來的節(jié)點特征進(jìn)行融合。在這里需要用到多模態(tài)特征融合的方法[14]。多模態(tài)特征融合是指利用特征之間的關(guān)聯(lián)性將不同特征融合成一個總的特征向量。根據(jù)融合位置的不同，多模態(tài)融合策略分為三類，即特征層融合，決策層融合以及模型層融合[15-16]，如表1所示。

在這里采用特征層融合策略進(jìn)行融合，即采用基于多數(shù)投票的算法給每個特征賦予不同的權(quán)重，以代表對于重疊社區(qū)劃分的重要程度[17]。融合公式如式(7)所示。

(7)

式中，Y為總的特征向量；wi為權(quán)值。

1.4 基于分類器的重疊社區(qū)劃分

基于上述融合的總的特征向量，通過構(gòu)建分類器的方法來識別不同社區(qū)中發(fā)生重疊現(xiàn)象的節(jié)點，完成重疊社區(qū)劃分[18]。由多個決策樹組成隨機森林，森林中每個決策樹就是一個分類器，如圖3所示。

圖3 隨機森林結(jié)構(gòu)示意圖

隨機森林建立基本流程如下：

Step 1：利用bootstrap算法在n個樣本的集合中有放回地抽取n個樣本形成一個數(shù)據(jù)集。

Step 2：利用隨機森林建立n個決策樹分類器。

Step 3：當(dāng)每個樣本有M個屬性時，在決策樹的每個節(jié)點需要分裂時，隨機從這M個屬性中選

取出m個屬性，滿足條件m

Step 4：從這m個屬性中采用某種策略(比如說信息增益)來選擇1個屬性作為該節(jié)點的分裂屬性。

Step 5：重復(fù)上述過程，一直到不能夠再分裂為止。注意整個決策樹形成過程中沒有進(jìn)行剪枝。

Step 6：按照上述建立大量的決策樹，由此構(gòu)成了隨機森林。

在隨機森林建立完成后，最后采用多數(shù)投票的方法，識別社區(qū)重疊節(jié)點，完成重疊社區(qū)的劃分。

2 仿真實驗分析

2.1 數(shù)據(jù)集介紹

本次仿真實驗中總共用到了四種數(shù)據(jù)集，其中一種為人工合成的加權(quán)網(wǎng)絡(luò)，其余三種為真實加權(quán)網(wǎng)絡(luò)，并以文獻(xiàn)[2]和文獻(xiàn)[3]劃分算法作為對比。

2.1.1 人工合成加權(quán)網(wǎng)絡(luò)

利用LFM準(zhǔn)則生成4種不同類型社區(qū)，這4種不同類型社區(qū)構(gòu)成了一個大的加權(quán)網(wǎng)絡(luò)。構(gòu)成的人工合成加權(quán)網(wǎng)絡(luò)基本參數(shù)如表2所示。

表2 人工合成加權(quán)網(wǎng)絡(luò)基本參數(shù)表

在人工合成加權(quán)網(wǎng)絡(luò)中共包含30個節(jié)點和70條邊，權(quán)重范圍為(0，1]。

2.1.2 真實加權(quán)網(wǎng)絡(luò)

加權(quán)網(wǎng)絡(luò)分別為空手道俱樂部網(wǎng)絡(luò)、Les Miserables網(wǎng)絡(luò)以及橄欖球社團網(wǎng)絡(luò)，這些網(wǎng)絡(luò)的基本構(gòu)成參數(shù)如表3所示。

表3 三個真實加權(quán)網(wǎng)絡(luò)的基本構(gòu)成參數(shù)表

2.2 社區(qū)劃分評價指標(biāo)

評價社區(qū)劃分算法性能的指標(biāo)有兩個，一個是在這里標(biāo)準(zhǔn)化互信息指數(shù)和模塊度。這兩個指標(biāo)的計算公式如下。

2.2.1 標(biāo)準(zhǔn)化互信息指數(shù)NMI

標(biāo)準(zhǔn)化互信息指數(shù)用來判斷利用所研究的算法劃分的社區(qū)結(jié)果與真實結(jié)果之間的相似程度。該數(shù)值取值范圍[0,1]，數(shù)值越靠近1，劃分的結(jié)果越接近真實結(jié)果，算法的劃分精度越高。計算公式如式(8)所示。

(8)

式中，N表示節(jié)點的個數(shù)；Cij表示在同時屬于社區(qū)A和B；CA和CB表示社區(qū)A和B中節(jié)點的個數(shù)；Ci、Cj表示網(wǎng)絡(luò)C中元素的總和。

2.2.2 模塊度R

模塊度是最能判斷算法劃分質(zhì)量的指標(biāo)，其值一般取值范圍為[0.3,0.7]，數(shù)值越靠近0.7，劃分的質(zhì)量越高。其計算公式如式(9)所示。

(9)

式中，m表示網(wǎng)絡(luò)中邊的個數(shù)；Aij表示網(wǎng)絡(luò)的鄰接矩陣；wi、wj表示節(jié)點i和j的權(quán)重；f(CiCj)為罰函數(shù)。

3.3 結(jié)果統(tǒng)計與分析

利用本文所研究的算法以及文獻(xiàn)[2]和文獻(xiàn)[3]劃分算法對四種數(shù)據(jù)集進(jìn)行重疊社區(qū)劃分，然后統(tǒng)計標(biāo)準(zhǔn)化互信息指數(shù)NMI和模塊度R，得到的結(jié)果如表4所示。

表4 標(biāo)準(zhǔn)化互信息指數(shù)和模塊度統(tǒng)計結(jié)果

從表4中可以看出，利用本文所研究的算法對四種加權(quán)網(wǎng)絡(luò)進(jìn)行重疊社區(qū)劃分，得到的標(biāo)準(zhǔn)化互信息指數(shù)NMI和模塊度R均要大于文獻(xiàn)[2]劃分算法和文獻(xiàn)[3]劃分算法的劃分結(jié)果，說明所研究的算法劃分性能更高。

結(jié)語

隨著社交平臺出現(xiàn)和廣泛應(yīng)用，社交網(wǎng)絡(luò)體系越來越龐大，使得人們之間的聯(lián)系越來越密切。人的興趣不同，因此在社交網(wǎng)絡(luò)中會存在若干個社區(qū)，而這些不同社區(qū)又因為一個人擁有的多種偏好存在重疊的問題?；诖耍疚木椭丿B社區(qū)的劃分進(jìn)行研究。通過提取重疊節(jié)點特征并融合，利用分類器實現(xiàn)了重疊識別和劃分，最后通過四種加權(quán)網(wǎng)絡(luò)驗證了所研究算法的劃分性能。然而，本研究仍有很多的地方需要進(jìn)行改進(jìn)，即由于提取了多個特征，雖然劃分精度增加，但運行時間相對延長。