高 娟,張曉濱

(西安工程大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院,陜西 西安 710048)

0 引 言

網(wǎng)絡(luò)社區(qū)檢測(cè)作為復(fù)雜網(wǎng)絡(luò)研究的一個(gè)重要方向，越來(lái)越引起研究者的關(guān)注[1-2]。大量的實(shí)際應(yīng)用案例可以看作是復(fù)雜網(wǎng)絡(luò)在社會(huì)生產(chǎn)與生活場(chǎng)景中的應(yīng)用,如生物網(wǎng)絡(luò)[3]、電力網(wǎng)絡(luò)[4]、社交網(wǎng)絡(luò)[5]等；在社會(huì)化電商平臺(tái)[6]上的應(yīng)用也越來(lái)越多,如微博平臺(tái)、淘寶平臺(tái)等。在這些應(yīng)用中，網(wǎng)絡(luò)社區(qū)劃分普遍存在一定的規(guī)律,表現(xiàn)為社區(qū)內(nèi)部結(jié)點(diǎn)間聯(lián)系緊密,社區(qū)之間結(jié)點(diǎn)聯(lián)系稀疏。社區(qū)檢測(cè)與發(fā)現(xiàn)算法就是利用這種特征準(zhǔn)確識(shí)別復(fù)雜網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)。

目前，復(fù)雜網(wǎng)絡(luò)中的社區(qū)檢測(cè)算法主要有ZHANG等提出的LPANI算法。該算法利用標(biāo)簽的重要性與標(biāo)簽的影響力解決標(biāo)簽傳播算法在傳播過(guò)程中標(biāo)簽選取的不確定性和隨機(jī)性的問(wèn)題,提高了社區(qū)檢測(cè)算法的準(zhǔn)確性[7]。但是，這個(gè)算法適合用在相對(duì)較小的網(wǎng)絡(luò)中。LIANG等提出的SLP方法,在標(biāo)簽傳播方法中引入了隨機(jī)梯度下降進(jìn)行算法推導(dǎo),實(shí)現(xiàn)了利用輕量級(jí)的迭代完成標(biāo)簽傳播過(guò)程的求解,為處理大規(guī)模數(shù)據(jù)提供了一種新的求解思路[8]。但是，標(biāo)簽傳播算法由于其過(guò)程存在隨機(jī)性,產(chǎn)生標(biāo)簽震蕩使得算法存在一定的不穩(wěn)定性。DAOOD等對(duì)摩洛哥的電子商務(wù)網(wǎng)站進(jìn)行用戶評(píng)估與聚類：首先采用自組織映射法確定最佳聚類數(shù)和初始質(zhì)心,再用K-means方法根據(jù)顧客的屬性值將顧客進(jìn)行社區(qū)劃分,從而制定有效的營(yíng)銷策略[9]。王佳琦等提出一種基于改進(jìn)的K-means算法的社區(qū)檢測(cè)算法，但該算法在劃分社區(qū)時(shí)只考慮結(jié)點(diǎn)屬于一個(gè)社區(qū),存在一定的不準(zhǔn)確性[10]。文獻(xiàn)[11]提出一種通用的屬性化社交網(wǎng)絡(luò)嵌入框架,利用用戶間的朋友關(guān)系屬性和行為屬性提升網(wǎng)絡(luò)結(jié)構(gòu)的嵌入,從而更準(zhǔn)確地獲得用戶的劃分。同樣,文獻(xiàn)[12-13]也利用了社區(qū)結(jié)構(gòu)嵌入的方法,基于對(duì)社區(qū)中密集連接結(jié)構(gòu)的觀察,并通過(guò)底層社區(qū)成員關(guān)系對(duì)固有的社區(qū)結(jié)構(gòu)進(jìn)行編碼,利用網(wǎng)絡(luò)嵌入的方法研究社區(qū)結(jié)構(gòu)及社區(qū)的屬性,獲得了更好的社區(qū)結(jié)構(gòu)檢測(cè)效果。但是，嵌入結(jié)構(gòu)帶來(lái)解釋性差的問(wèn)題。RODRIGUEZ等提出密度峰值聚類(DPC)算法,該方法可以自動(dòng)發(fā)現(xiàn)聚類中心,實(shí)現(xiàn)任意形狀的高效聚類,且相較于以上方法簡(jiǎn)單易懂且高效[14]。DENG等在DPC算法基礎(chǔ)上做了改進(jìn),提出了IDPM算法[15]。DU等改進(jìn)了屬性計(jì)算方法,從單一類別的屬性擴(kuò)展為2類數(shù)據(jù)類別的屬性計(jì)算,從而擴(kuò)展了屬性類別的計(jì)算,更充分地利用了用戶的屬性信息[16]。金志剛等提出一種基于核密度估計(jì)的社區(qū)發(fā)現(xiàn)算法,實(shí)現(xiàn)自適應(yīng)地劃分各個(gè)數(shù)據(jù)規(guī)模的社區(qū)[17]。文獻(xiàn)[18]認(rèn)為傳統(tǒng)的KNN方法在選擇相鄰對(duì)象集時(shí)存在一定的局限性,因此引入了鄰居因子和時(shí)間函數(shù),利用動(dòng)態(tài)選擇模型選擇相鄰的對(duì)象集。結(jié)合RNN和注意機(jī)制進(jìn)行相似用戶聚類,從而完成電子商務(wù)產(chǎn)品推薦。文獻(xiàn)[19]利用網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)與結(jié)點(diǎn)屬性計(jì)算結(jié)點(diǎn)間的相似性,通過(guò)對(duì)結(jié)點(diǎn)相似性的計(jì)算衡量結(jié)點(diǎn)間的距離。雖然這些方法都能很好地完成社區(qū)發(fā)現(xiàn),但仍然存在社區(qū)劃分中邊界結(jié)點(diǎn)不明確的問(wèn)題,出現(xiàn)數(shù)據(jù)結(jié)點(diǎn)被誤分的現(xiàn)象。

針對(duì)網(wǎng)絡(luò)社區(qū)檢測(cè)研究中存在的社區(qū)劃分不夠準(zhǔn)確的問(wèn)題,本文基于密度峰值聚類思想以及電商網(wǎng)絡(luò)平臺(tái)上的海量用戶評(píng)論信息進(jìn)行電商平臺(tái)網(wǎng)絡(luò)的社區(qū)檢測(cè)與發(fā)現(xiàn),利用用戶評(píng)論信息的主題屬性作為用戶結(jié)點(diǎn)的屬性信息,提出融合結(jié)點(diǎn)屬性和網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的密度峰值社區(qū)檢測(cè)算法(combined node attributes and network topology of density peak clustering community detect algorithm，ANDPC)。

1 ANDPC算法

1.1 密度峰值聚類(DPC)

電商平臺(tái)網(wǎng)絡(luò)可表示為無(wú)向無(wú)權(quán)圖G=(V,E)。其中V={v1,v2,…vn},n為網(wǎng)絡(luò)中結(jié)點(diǎn)的個(gè)數(shù),網(wǎng)絡(luò)社區(qū)中的用戶在圖中用結(jié)點(diǎn)表示；E={(vi,vj)},是結(jié)點(diǎn)間邊的集合,其中1≤i,j≤n。網(wǎng)絡(luò)社區(qū)中的用戶社區(qū)關(guān)聯(lián)在圖G中用邊表示。鄰接矩陣A=(aij)n×n,當(dāng)結(jié)點(diǎn)vi和結(jié)點(diǎn)vj之間有連邊時(shí),aij=1,否則為0，且給定aii=1。

電商平臺(tái)的用戶網(wǎng)絡(luò)社區(qū)檢測(cè)與發(fā)現(xiàn)問(wèn)題可以看作是網(wǎng)絡(luò)的聚類問(wèn)題,而密度峰值聚類算法(DPC)是一種簡(jiǎn)單高效,且不需要迭代的聚類算法。DPC具有2個(gè)重要的特征:①聚類中心的局部密度較大;②不同簇之間的聚類中心相對(duì)距離較大。局部密度表示為分布在中心結(jié)點(diǎn)周?chē)慕Y(jié)點(diǎn)的個(gè)數(shù),用結(jié)點(diǎn)的度表示，而結(jié)點(diǎn)的相對(duì)距離表示為結(jié)點(diǎn)到密度更大的點(diǎn)的距離。根據(jù)這2個(gè)特征,算法主要涉及結(jié)點(diǎn)的局部密度ρi和結(jié)點(diǎn)的相對(duì)距離δi。其計(jì)算方法為

(1)

式中：dij是結(jié)點(diǎn)vi與結(jié)點(diǎn)vj之間的距離；dc為截?cái)嗑嚯x,需要人為干預(yù)進(jìn)行設(shè)定,一般取網(wǎng)絡(luò)中結(jié)點(diǎn)個(gè)數(shù)的2%；χ(·)為指示函數(shù),表示為

(2)

結(jié)點(diǎn)的相對(duì)距離δi的計(jì)算公式為

(3)

以ρi為橫坐標(biāo),δi為縱坐標(biāo)生成結(jié)點(diǎn)分布圖,形成聚類結(jié)果決策圖。根據(jù)密度峰值算法的特征可知，ρi和δi值都較大的結(jié)點(diǎn)為聚類中心(關(guān)鍵點(diǎn)),故而位于決策圖右上角的點(diǎn)被選為關(guān)鍵點(diǎn),剩余結(jié)點(diǎn)為非關(guān)鍵點(diǎn)。在獲得關(guān)鍵結(jié)點(diǎn)后,DPC算法對(duì)非關(guān)鍵點(diǎn)根據(jù)相對(duì)距離的大小，將其分配到距離關(guān)鍵點(diǎn)最近的點(diǎn)簇中完成聚類過(guò)程。

然而，DPC算法對(duì)電商平臺(tái)進(jìn)行社區(qū)檢測(cè)，會(huì)遺漏重要的用戶屬性信息,導(dǎo)致聚類結(jié)果與實(shí)際聚類偏差較大。因此，本文利用用戶的商品評(píng)論信息作為用戶的屬性,并根據(jù)不同用戶間的網(wǎng)絡(luò)結(jié)構(gòu)計(jì)算用戶結(jié)點(diǎn)相似度,得到用戶間相對(duì)距離改進(jìn)的DPC算法,從而更好地進(jìn)行電商平臺(tái)的社區(qū)檢測(cè)與發(fā)現(xiàn)。

在無(wú)向無(wú)權(quán)圖G=(V,E)中,定義屬性矩陣B=(bit)n×k,其中k為結(jié)點(diǎn)相關(guān)評(píng)論信息涉及的所有用戶關(guān)注的主題個(gè)數(shù),作為結(jié)點(diǎn)的屬性,且t∈[1,k]。

1.2 局部密度計(jì)算

在DPC算法中,局部密度的計(jì)算方法是通過(guò)位于其附近，距離≤dc的結(jié)點(diǎn)的個(gè)數(shù)確定。dc值的選取需要人工干預(yù),會(huì)影響社區(qū)的劃分,但不能準(zhǔn)確獲得結(jié)點(diǎn)的社區(qū)劃分。而在電商平臺(tái)上,用戶會(huì)受其他用戶評(píng)論信息的影響,特別是大V用戶的評(píng)論信息。所以，在電商用戶社區(qū)中,作為社區(qū)的關(guān)鍵結(jié)點(diǎn),與社區(qū)中的大部分結(jié)點(diǎn)都存有聯(lián)系。關(guān)鍵結(jié)點(diǎn)可以對(duì)其直接鄰居做出影響,也可以通過(guò)鄰居結(jié)點(diǎn)間接對(duì)其他結(jié)點(diǎn)產(chǎn)生影響。根據(jù)這個(gè)特點(diǎn),本文提出利用結(jié)點(diǎn)的直接鄰居和間接鄰居的度計(jì)算結(jié)點(diǎn)的局部密度,即

(4)

式中：di為結(jié)點(diǎn)vi的度。dj-1是在計(jì)算結(jié)點(diǎn)vi的鄰居結(jié)點(diǎn)vj的度時(shí),去除重復(fù)計(jì)算的結(jié)點(diǎn)vi和vj之間度的計(jì)算次數(shù),以更精確計(jì)算結(jié)點(diǎn)的度,從而得到更精確的結(jié)點(diǎn)局部密度。di的計(jì)算式為

(5)

1.3 相似度計(jì)算

通過(guò)對(duì)結(jié)點(diǎn)間的相似度計(jì)算進(jìn)一步得到結(jié)點(diǎn)的距離度量表示。獲得用戶的相關(guān)評(píng)論信息以及評(píng)論信息的數(shù)量,得到每條評(píng)論所屬的主題；將主題的類別作為用戶的屬性信息，根據(jù)每一個(gè)用戶的每一個(gè)主題評(píng)論數(shù)量確定用戶的屬性值。具體方法是：獲取用戶結(jié)點(diǎn)vi的所有評(píng)論ni,并確定用戶的每條評(píng)論所屬的主題t,統(tǒng)計(jì)該用戶的每個(gè)主題所對(duì)應(yīng)的評(píng)論數(shù)nt。根據(jù)這些數(shù)據(jù)計(jì)算用戶結(jié)點(diǎn)的每一個(gè)屬性的值(bit),即

(6)

由上述計(jì)算可以得到用戶的屬性矩陣B,它的每一行向量代表用戶涉及的所有主題屬性,表示為bi。

根據(jù)屬性信息與結(jié)點(diǎn)的網(wǎng)絡(luò)結(jié)構(gòu)計(jì)算結(jié)點(diǎn)間的相似性,分為直接鄰居結(jié)點(diǎn)間的相似性計(jì)算,間接鄰居結(jié)點(diǎn)間的相似性計(jì)算及剩余結(jié)點(diǎn)的相似性計(jì)算。

直接鄰居采用余弦相似度計(jì)算,即

(7)

式中：bi為結(jié)點(diǎn)vi的屬性向量；sij為結(jié)點(diǎn)vi與結(jié)點(diǎn)vj的相似性。

間接鄰居由于結(jié)點(diǎn)間沒(méi)有直接連邊,采用式(8)計(jì)算結(jié)點(diǎn)間的相似性，即

siz=sij·sjz

(8)

根據(jù)小世界效應(yīng)的定義:若網(wǎng)絡(luò)中任意兩點(diǎn)間的平均距離L(網(wǎng)絡(luò)中兩點(diǎn)之間的邊數(shù))隨著網(wǎng)絡(luò)結(jié)點(diǎn)數(shù)n的增長(zhǎng)呈對(duì)數(shù)增長(zhǎng),即L～lnn。結(jié)合小世界效應(yīng)與阻尼問(wèn)題,計(jì)算剩余結(jié)點(diǎn)的相似度,即有

(9)

式中:α是相似度距離權(quán)重參數(shù),其計(jì)算公式為

(10)

為了滿足DPC算法的距離越小,2個(gè)結(jié)點(diǎn)越相似的要求,將計(jì)算的相似度轉(zhuǎn)換回距離值。其計(jì)算式為

dij=-log(sij)

(11)

應(yīng)用式 (3) 計(jì)算結(jié)點(diǎn)的相對(duì)距離δi。

由于局部密度ρi與相對(duì)距離δi的計(jì)算值是不同的數(shù)量級(jí),故對(duì)局部密度和相對(duì)距離進(jìn)行歸一化處理,避免在進(jìn)行中心結(jié)點(diǎn)選取時(shí),出現(xiàn)將較大的局部密度與較小的相對(duì)距離的點(diǎn)選為中心結(jié)點(diǎn),造成選取不準(zhǔn)確的問(wèn)題。用式(12)進(jìn)行歸一化計(jì)算：

(12)

根據(jù)歸一化處理后的局部密度ρi和相對(duì)距離δi，通過(guò)式(13)可以選出關(guān)鍵點(diǎn),即

γi=ρiδi

(13)

對(duì)γi進(jìn)行降序排列,選取關(guān)鍵結(jié)點(diǎn)；對(duì)剩余結(jié)點(diǎn)進(jìn)行社區(qū)分配,將剩余的每個(gè)點(diǎn)分配給與其距離最近的、密度更高的集群。算法過(guò)程如下：

輸入:圖G、鄰接矩陣A及屬性矩陣B。

輸出:clustersC。

步驟1:根據(jù)式(7)、(8)、(9)計(jì)算結(jié)點(diǎn)間的相似度。

步驟2:根據(jù)式(4)計(jì)算結(jié)點(diǎn)vi的局部密度,并利用式(12)進(jìn)行歸一化。

步驟3:根據(jù)式(3)計(jì)算結(jié)點(diǎn)vi的相對(duì)距離,并利用式(12)進(jìn)行歸一化。

步驟4:根據(jù)式(13)計(jì)算γi,選擇關(guān)鍵結(jié)點(diǎn)。

步驟5:對(duì)剩余非關(guān)鍵結(jié)點(diǎn)進(jìn)行社區(qū)分配。

2 實(shí) 驗(yàn)

2.1 實(shí)驗(yàn)數(shù)據(jù)

實(shí)驗(yàn)數(shù)據(jù)集來(lái)源于淘寶電商平臺(tái)和拼多多平臺(tái),自動(dòng)采集了2019年4月至7月淘寶的3 272個(gè)用戶和用戶發(fā)布的234 930條商品評(píng)論信息,及拼多多的1 586個(gè)用戶和用戶發(fā)布的85 649條評(píng)論信息。對(duì)數(shù)據(jù)集進(jìn)行預(yù)處理：利用外部語(yǔ)料庫(kù)進(jìn)行詞嵌入訓(xùn)練,獲得詞的語(yǔ)義及語(yǔ)義間的關(guān)系;結(jié)合概率生成模型對(duì)評(píng)論信息進(jìn)行短文本主題獲取,獲其類別k。將評(píng)論信息的主題做為用戶的屬性。將ANDPC算法與改進(jìn)的K-means算法[10]、KDED算法[17]進(jìn)行社區(qū)檢測(cè)實(shí)驗(yàn)對(duì)比。

2.2 評(píng)估方法

實(shí)驗(yàn)采用的評(píng)價(jià)指標(biāo)為模塊度Q、歸一化互信息INM及準(zhǔn)確度Acc等。

1) 模塊度Q是用于社區(qū)檢測(cè)與發(fā)現(xiàn)算法中檢測(cè)社區(qū)結(jié)構(gòu)穩(wěn)定性的一個(gè)衡量指標(biāo),表示網(wǎng)絡(luò)社區(qū)劃分質(zhì)量[20],定義為

(14)

式中：m為網(wǎng)絡(luò)總邊數(shù)；A=(avw)n×n為網(wǎng)絡(luò)的鄰接矩陣；dv表示結(jié)點(diǎn)v的度；cv為結(jié)點(diǎn)v所屬的社區(qū)。cv取值越大表示社區(qū)劃分的質(zhì)量越好,社區(qū)越穩(wěn)定。

2) 歸一化信息度量通過(guò)計(jì)算社區(qū)檢測(cè)結(jié)果與社區(qū)的真實(shí)類別之間的互信息評(píng)價(jià)類別標(biāo)志的一致性,表示為

(15)

式中：I(c,c′)表示為社區(qū)檢測(cè)結(jié)果c與真實(shí)社區(qū)類別c′之間的互信息;H(c)表示單個(gè)類別向量的信息熵。INM的計(jì)算結(jié)果值位于[0,1]之間,INM值越大表示社區(qū)檢測(cè)結(jié)果就越好,反之則越差。

3) 準(zhǔn)確度用來(lái)衡量聚類結(jié)果的質(zhì)量,取值范圍為[0,1],值越大聚類效果就越好。計(jì)算方法為

(16)

2.3 結(jié)果與分析

圖1、2表示聚類結(jié)果圖。圖1(a)～(c)為3個(gè)算法在淘寶數(shù)據(jù)集上的聚類結(jié)果；圖2(a)～(c)為3個(gè)算法在拼多多數(shù)據(jù)集上的聚類結(jié)果。從圖1、2可知,ANDPC算法在2個(gè)數(shù)據(jù)集上都取得了最好的效果。相比于KDED算法與改進(jìn)的K-means算法，此算法都能將數(shù)據(jù)結(jié)點(diǎn)進(jìn)行明確的劃分,邊緣結(jié)點(diǎn)也能得到很好的歸屬劃分,且很少出現(xiàn)數(shù)據(jù)結(jié)點(diǎn)被誤分的現(xiàn)象。算法KDED與改進(jìn)的K-means算法不能對(duì)邊緣結(jié)點(diǎn)進(jìn)行很好的劃分,在每個(gè)社區(qū)的邊緣處,結(jié)點(diǎn)出現(xiàn)了高度的數(shù)據(jù)交叉,即不能準(zhǔn)確劃分結(jié)點(diǎn)。但是，KDED算法聚類效果比改進(jìn)的K-means算法聚類效果要好一些。

(a) ANDPC (b) KDED (c) 改進(jìn)的K-means圖 1 淘寶數(shù)據(jù)集上的聚類結(jié)果Fig.1 Clustering results of Taobao data

圖3、4分別為歸一化信息及準(zhǔn)確度的評(píng)估值。

圖 4 準(zhǔn)確度評(píng)估結(jié)果Fig.4 Accuracy results

從圖3和圖4可以看出，相比較KDED算法及改進(jìn)的K-means算法,ANDPC算法在2個(gè)數(shù)據(jù)集上都取得了最好的結(jié)果。相比于基線模型分別提高了0.02及0.03以上；相比KDED方法得到了較好的歸一化信息值和準(zhǔn)確度值。這是因?yàn)锳NDPC算法利用了用戶關(guān)于核心用戶的不同鄰居位置，并結(jié)合用戶主題屬性計(jì)算結(jié)點(diǎn)間的相似性,從而可以更明確用戶之間的關(guān)系且提高了邊緣結(jié)點(diǎn)與聚類中心結(jié)點(diǎn)的聯(lián)系。KDED算法由于在最后進(jìn)行結(jié)點(diǎn)分配時(shí)存在一定的模糊性,故結(jié)果較差；改進(jìn)的K-means算法則由于參數(shù)的選擇問(wèn)題，給聚類效果帶來(lái)了一定的負(fù)面影響,產(chǎn)生了較差的聚類效果。模塊度評(píng)估的實(shí)驗(yàn)如表1所示。

表 1 算法模塊度值Tab.1 Value of algorithm module degree

從表1可以看出，在2個(gè)數(shù)據(jù)集上ANDPC算法的模塊度值都要高于KDED算法和改進(jìn)的K-means算法的值。原因是ANDPC算法能很好地識(shí)別聚類中心以及跟隨聚類中心的結(jié)點(diǎn)。此外，對(duì)邊緣結(jié)點(diǎn)也能很好地將其歸入到所屬的聚類類別,強(qiáng)化了結(jié)點(diǎn)間的關(guān)系,這是其他2個(gè)基線模型無(wú)法做到的。

3 結(jié) 語(yǔ)

針對(duì)基于密度峰值社區(qū)檢測(cè)算法中截?cái)嗑嚯x大小需要人為干預(yù),且相似度計(jì)算只考慮了網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)而影響社區(qū)檢測(cè)結(jié)果準(zhǔn)確性的問(wèn)題,利用結(jié)點(diǎn)屬性與網(wǎng)絡(luò)結(jié)構(gòu)相結(jié)合的方法計(jì)算結(jié)點(diǎn)的局部密度與結(jié)點(diǎn)之間的相對(duì)距離，進(jìn)行電商平臺(tái)的社區(qū)發(fā)現(xiàn)。實(shí)驗(yàn)結(jié)果表明,ANDPC算法的歸一化信息和準(zhǔn)確度實(shí)驗(yàn)值比KDED算法與改進(jìn)的K-means算法的實(shí)驗(yàn)值好,聚類結(jié)果準(zhǔn)確明晰,能夠很好地將社區(qū)的邊緣結(jié)點(diǎn)進(jìn)行準(zhǔn)確劃分,很少出現(xiàn)數(shù)據(jù)交叉以及被誤分的數(shù)據(jù)結(jié)點(diǎn)。模塊度實(shí)驗(yàn)表明，ANDPC算法獲得的社區(qū)間結(jié)構(gòu)強(qiáng)度高,能夠描述社區(qū)內(nèi)結(jié)點(diǎn)間的關(guān)系。該算法可以實(shí)現(xiàn)高效的社區(qū)檢測(cè),具有較高的應(yīng)用價(jià)值。