融合結點屬性與結構的電商網絡社區檢測算法

高 娟,張曉濱

(西安工程大學 計算機科學學院,陜西 西安 710048)

0 引 言

網絡社區檢測作為復雜網絡研究的一個重要方向，越來越引起研究者的關注[1-2]。大量的實際應用案例可以看作是復雜網絡在社會生產與生活場景中的應用,如生物網絡[3]、電力網絡[4]、社交網絡[5]等；在社會化電商平臺[6]上的應用也越來越多,如微博平臺、淘寶平臺等。在這些應用中，網絡社區劃分普遍存在一定的規律,表現為社區內部結點間聯系緊密,社區之間結點聯系稀疏。社區檢測與發現算法就是利用這種特征準確識別復雜網絡中的社區結構。

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

針對網絡社區檢測研究中存在的社區劃分不夠準確的問題,本文基于密度峰值聚類思想以及電商網絡平臺上的海量用戶評論信息進行電商平臺網絡的社區檢測與發現,利用用戶評論信息的主題屬性作為用戶結點的屬性信息,提出融合結點屬性和網絡拓撲結構的密度峰值社區檢測算法(combined node attributes and network topology of density peak clustering community detect algorithm，ANDPC)。

1 ANDPC算法

1.1 密度峰值聚類(DPC)

電商平臺網絡可表示為無向無權圖G=(V,E)。其中V={v1,v2,…vn},n為網絡中結點的個數,網絡社區中的用戶在圖中用結點表示；E={(vi,vj)},是結點間邊的集合,其中1≤i,j≤n。網絡社區中的用戶社區關聯在圖G中用邊表示。鄰接矩陣A=(aij)n×n,當結點vi和結點vj之間有連邊時,aij=1,否則為0，且給定aii=1。

電商平臺的用戶網絡社區檢測與發現問題可以看作是網絡的聚類問題,而密度峰值聚類算法(DPC)是一種簡單高效,且不需要迭代的聚類算法。DPC具有2個重要的特征:①聚類中心的局部密度較大;②不同簇之間的聚類中心相對距離較大。局部密度表示為分布在中心結點周圍的結點的個數,用結點的度表示，而結點的相對距離表示為結點到密度更大的點的距離。根據這2個特征,算法主要涉及結點的局部密度ρi和結點的相對距離δi。其計算方法為

(1)

式中：dij是結點vi與結點vj之間的距離；dc為截斷距離,需要人為干預進行設定,一般取網絡中結點個數的2%；χ(·)為指示函數,表示為

(2)

結點的相對距離δi的計算公式為

(3)

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

然而，DPC算法對電商平臺進行社區檢測，會遺漏重要的用戶屬性信息,導致聚類結果與實際聚類偏差較大。因此，本文利用用戶的商品評論信息作為用戶的屬性,并根據不同用戶間的網絡結構計算用戶結點相似度,得到用戶間相對距離改進的DPC算法,從而更好地進行電商平臺的社區檢測與發現。

在無向無權圖G=(V,E)中,定義屬性矩陣B=(bit)n×k,其中k為結點相關評論信息涉及的所有用戶關注的主題個數,作為結點的屬性,且t∈[1,k]。

1.2 局部密度計算

在DPC算法中,局部密度的計算方法是通過位于其附近，距離≤dc的結點的個數確定。dc值的選取需要人工干預,會影響社區的劃分,但不能準確獲得結點的社區劃分。而在電商平臺上,用戶會受其他用戶評論信息的影響,特別是大V用戶的評論信息。所以，在電商用戶社區中,作為社區的關鍵結點,與社區中的大部分結點都存有聯系。關鍵結點可以對其直接鄰居做出影響,也可以通過鄰居結點間接對其他結點產生影響。根據這個特點,本文提出利用結點的直接鄰居和間接鄰居的度計算結點的局部密度,即

(4)

式中：di為結點vi的度。dj-1是在計算結點vi的鄰居結點vj的度時,去除重復計算的結點vi和vj之間度的計算次數,以更精確計算結點的度,從而得到更精確的結點局部密度。di的計算式為

(5)

1.3 相似度計算

通過對結點間的相似度計算進一步得到結點的距離度量表示。獲得用戶的相關評論信息以及評論信息的數量,得到每條評論所屬的主題；將主題的類別作為用戶的屬性信息，根據每一個用戶的每一個主題評論數量確定用戶的屬性值。具體方法是：獲取用戶結點vi的所有評論ni,并確定用戶的每條評論所屬的主題t,統計該用戶的每個主題所對應的評論數nt。根據這些數據計算用戶結點的每一個屬性的值(bit),即

(6)

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

根據屬性信息與結點的網絡結構計算結點間的相似性,分為直接鄰居結點間的相似性計算,間接鄰居結點間的相似性計算及剩余結點的相似性計算。

直接鄰居采用余弦相似度計算,即

(7)

式中：bi為結點vi的屬性向量；sij為結點vi與結點vj的相似性。

間接鄰居由于結點間沒有直接連邊,采用式(8)計算結點間的相似性，即

siz=sij·sjz

(8)

根據小世界效應的定義:若網絡中任意兩點間的平均距離L(網絡中兩點之間的邊數)隨著網絡結點數n的增長呈對數增長,即L～lnn。結合小世界效應與阻尼問題,計算剩余結點的相似度,即有

(9)

式中:α是相似度距離權重參數,其計算公式為

(10)

為了滿足DPC算法的距離越小,2個結點越相似的要求,將計算的相似度轉換回距離值。其計算式為

dij=-log(sij)

(11)

應用式 (3) 計算結點的相對距離δi。

由于局部密度ρi與相對距離δi的計算值是不同的數量級,故對局部密度和相對距離進行歸一化處理,避免在進行中心結點選取時,出現將較大的局部密度與較小的相對距離的點選為中心結點,造成選取不準確的問題。用式(12)進行歸一化計算：

(12)

根據歸一化處理后的局部密度ρi和相對距離δi，通過式(13)可以選出關鍵點,即

γi=ρiδi

(13)

對γi進行降序排列,選取關鍵結點；對剩余結點進行社區分配,將剩余的每個點分配給與其距離最近的、密度更高的集群。算法過程如下：

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

輸出:clustersC。

步驟1:根據式(7)、(8)、(9)計算結點間的相似度。

步驟2:根據式(4)計算結點vi的局部密度,并利用式(12)進行歸一化。

步驟3:根據式(3)計算結點vi的相對距離,并利用式(12)進行歸一化。

步驟4:根據式(13)計算γi,選擇關鍵結點。

步驟5:對剩余非關鍵結點進行社區分配。

2 實 驗

2.1 實驗數據

實驗數據集來源于淘寶電商平臺和拼多多平臺,自動采集了2019年4月至7月淘寶的3 272個用戶和用戶發布的234 930條商品評論信息,及拼多多的1 586個用戶和用戶發布的85 649條評論信息。對數據集進行預處理：利用外部語料庫進行詞嵌入訓練,獲得詞的語義及語義間的關系;結合概率生成模型對評論信息進行短文本主題獲取,獲其類別k。將評論信息的主題做為用戶的屬性。將ANDPC算法與改進的K-means算法[10]、KDED算法[17]進行社區檢測實驗對比。

2.2 評估方法

實驗采用的評價指標為模塊度Q、歸一化互信息INM及準確度Acc等。

1) 模塊度Q是用于社區檢測與發現算法中檢測社區結構穩定性的一個衡量指標,表示網絡社區劃分質量[20],定義為

(14)

式中：m為網絡總邊數；A=(avw)n×n為網絡的鄰接矩陣；dv表示結點v的度；cv為結點v所屬的社區。cv取值越大表示社區劃分的質量越好,社區越穩定。

2) 歸一化信息度量通過計算社區檢測結果與社區的真實類別之間的互信息評價類別標志的一致性,表示為

(15)

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

3) 準確度用來衡量聚類結果的質量,取值范圍為[0,1],值越大聚類效果就越好。計算方法為

(16)

2.3 結果與分析

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

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

圖3、4分別為歸一化信息及準確度的評估值。

圖 4 準確度評估結果Fig.4 Accuracy results

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

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

從表1可以看出，在2個數據集上ANDPC算法的模塊度值都要高于KDED算法和改進的K-means算法的值。原因是ANDPC算法能很好地識別聚類中心以及跟隨聚類中心的結點。此外，對邊緣結點也能很好地將其歸入到所屬的聚類類別,強化了結點間的關系,這是其他2個基線模型無法做到的。

3 結 語

針對基于密度峰值社區檢測算法中截斷距離大小需要人為干預,且相似度計算只考慮了網絡拓撲結構而影響社區檢測結果準確性的問題,利用結點屬性與網絡結構相結合的方法計算結點的局部密度與結點之間的相對距離，進行電商平臺的社區發現。實驗結果表明,ANDPC算法的歸一化信息和準確度實驗值比KDED算法與改進的K-means算法的實驗值好,聚類結果準確明晰,能夠很好地將社區的邊緣結點進行準確劃分,很少出現數據交叉以及被誤分的數據結點。模塊度實驗表明，ANDPC算法獲得的社區間結構強度高,能夠描述社區內結點間的關系。該算法可以實現高效的社區檢測,具有較高的應用價值。