任豆豆 高娟

摘要：有效地發(fā)現(xiàn)網(wǎng)絡(luò)中隱藏的社區(qū)結(jié)構(gòu)是電商平臺(tái)中進(jìn)行高效推薦的一個(gè)前提。雖然已經(jīng)提出了許多有效的社區(qū)檢測(cè)算法，但很少有算法能對(duì)電商平臺(tái)中用戶評(píng)論信息進(jìn)行充分利用，以達(dá)到解決社區(qū)發(fā)現(xiàn)算法準(zhǔn)確性的目的。在本文中，根據(jù)用戶結(jié)點(diǎn)的影響力的不同將結(jié)點(diǎn)分為領(lǐng)導(dǎo)結(jié)點(diǎn)和跟隨結(jié)點(diǎn)，結(jié)點(diǎn)的影響力稱為領(lǐng)導(dǎo)度和跟隨度，根據(jù)結(jié)點(diǎn)的領(lǐng)導(dǎo)度和跟隨度兩個(gè)度量結(jié)合用戶的評(píng)論信息的相似度提出將復(fù)雜網(wǎng)絡(luò)簡(jiǎn)單化的方法，使簡(jiǎn)化后的網(wǎng)絡(luò)與原始網(wǎng)絡(luò)相比更容易觀察到用戶群結(jié)構(gòu)，對(duì)簡(jiǎn)化后的網(wǎng)絡(luò)進(jìn)行劃分以進(jìn)行社區(qū)檢測(cè)時(shí)更簡(jiǎn)單、準(zhǔn)確。最后，在多個(gè)網(wǎng)絡(luò)數(shù)據(jù)集上進(jìn)行算法性能的測(cè)試，實(shí)驗(yàn)結(jié)果表明該算法能夠更直觀有效地揭示社區(qū)結(jié)構(gòu)。

關(guān)鍵字：社區(qū)檢測(cè)，評(píng)論信息，領(lǐng)導(dǎo)結(jié)點(diǎn)，跟隨結(jié)點(diǎn)，網(wǎng)絡(luò)簡(jiǎn)化

1引言

社區(qū)檢測(cè)成為探索和理解網(wǎng)絡(luò)如何工作的最重要任務(wù)之一，同樣成為電商平臺(tái)上高效推薦的基礎(chǔ)，所以為了更好地進(jìn)行用戶推薦，首先應(yīng)有一個(gè)好的社區(qū)檢測(cè)算法。社區(qū)結(jié)構(gòu)以網(wǎng)絡(luò)的形式普遍存在，如社會(huì)網(wǎng)絡(luò)[1]、生物網(wǎng)絡(luò)[2]、引文網(wǎng)絡(luò)[3]等，這使得社區(qū)檢測(cè)對(duì)于更好地理解網(wǎng)絡(luò)的組織結(jié)構(gòu)、提取有用信息尤為重要。

然而，現(xiàn)有的社區(qū)檢測(cè)算法在檢測(cè)網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)時(shí)很少考慮其可視化表達(dá)的理解，一個(gè)好的視覺理解可以幫助我們?nèi)菀椎刈R(shí)別出社區(qū)結(jié)構(gòu)和內(nèi)在特征。例如，一個(gè)社區(qū)通常包括兩個(gè)重要的區(qū)域：核心和邊界，這兩個(gè)區(qū)域決定了社區(qū)的形狀和組織，但是由于網(wǎng)絡(luò)中存在大量的邊緣結(jié)點(diǎn)，我們很難直接觀測(cè)出其社區(qū)的內(nèi)部結(jié)構(gòu)。為了克服這一缺陷并且更好地進(jìn)行社區(qū)劃分，本文引入領(lǐng)導(dǎo)結(jié)點(diǎn)和跟隨結(jié)點(diǎn)，并根據(jù)其影響力（領(lǐng)導(dǎo)度和跟隨度）表征其與其他結(jié)點(diǎn)的關(guān)系。領(lǐng)導(dǎo)結(jié)點(diǎn)有較高的領(lǐng)導(dǎo)度，被視為社區(qū)的代表，跟隨結(jié)點(diǎn)有較高的跟隨度，表示網(wǎng)絡(luò)中的邊緣結(jié)點(diǎn)成員。一個(gè)社區(qū)的邊界往往由幾個(gè)領(lǐng)導(dǎo)度低、跟隨度高的結(jié)點(diǎn)組成。因此本文提出了一種新的網(wǎng)絡(luò)結(jié)構(gòu)表示方法和社區(qū)檢測(cè)算法，主要思想是根據(jù)結(jié)點(diǎn)的領(lǐng)導(dǎo)度和跟隨度將復(fù)雜網(wǎng)絡(luò)轉(zhuǎn)換為簡(jiǎn)化的網(wǎng)絡(luò)，該網(wǎng)絡(luò)可以反映每個(gè)社區(qū)的核心成員以及每個(gè)結(jié)點(diǎn)的社區(qū)成員身份。 接著對(duì)化簡(jiǎn)后的網(wǎng)絡(luò)進(jìn)行最小分割完成社區(qū)檢測(cè)。最后通過(guò)實(shí)驗(yàn)驗(yàn)證本文提出的方法具有更好的網(wǎng)絡(luò)結(jié)構(gòu)理解和更準(zhǔn)確的社區(qū)劃分效果。

2社區(qū)檢測(cè)算法

給定一個(gè)原始的無(wú)向電商平臺(tái)網(wǎng)絡(luò) ，其中V是包含n個(gè)結(jié)點(diǎn)的結(jié)點(diǎn)集，E是包含m條邊的邊集， 是鄰接矩陣， 是邊 的邊權(quán)重，如果結(jié)點(diǎn) 和結(jié)點(diǎn) 之間存在邊，則 =1，否則 為0，此外給定 為1。 是結(jié)點(diǎn) 鄰居結(jié)點(diǎn)的集合， 是結(jié)點(diǎn) 的度。

對(duì)于任意兩個(gè)結(jié)點(diǎn)，使用兩個(gè)結(jié)點(diǎn)之間的公共鄰居數(shù)量來(lái)反應(yīng)他們的網(wǎng)絡(luò)結(jié)構(gòu)相似性，兩個(gè)結(jié)點(diǎn)的公共結(jié)點(diǎn)越多兩個(gè)結(jié)點(diǎn)就越相似。網(wǎng)絡(luò)結(jié)構(gòu)相似性計(jì)算公式為

根據(jù)用戶結(jié)點(diǎn)和用戶間存在的邊可以觀察到結(jié)點(diǎn)之間的連接關(guān)系，但不容易看到各個(gè)結(jié)點(diǎn)的社區(qū)結(jié)構(gòu)。因此我們將網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)中的結(jié)點(diǎn)分為領(lǐng)導(dǎo)結(jié)點(diǎn)和跟隨結(jié)點(diǎn)，領(lǐng)導(dǎo)和跟隨的程度定義為領(lǐng)導(dǎo)度和跟隨度，用這兩個(gè)度量來(lái)衡量一個(gè)結(jié)點(diǎn)的可表示性及其他結(jié)點(diǎn)與該結(jié)點(diǎn)的關(guān)系。領(lǐng)導(dǎo)結(jié)點(diǎn)作為社區(qū)的核心結(jié)點(diǎn)，領(lǐng)導(dǎo)度越高越可能是核心結(jié)點(diǎn)，一個(gè)跟隨結(jié)點(diǎn)到其他結(jié)點(diǎn)的跟隨程度較高，則這個(gè)結(jié)點(diǎn)和其核心結(jié)點(diǎn)越可能屬于同一個(gè)社區(qū)。本文給定一個(gè)結(jié)點(diǎn)只能領(lǐng)導(dǎo)比它影響力小且跟它相似度高的鄰居，如果它的一些鄰居比它有更大的影響力，那么它就不能領(lǐng)導(dǎo)這些結(jié)點(diǎn)。此外，領(lǐng)導(dǎo)結(jié)點(diǎn)對(duì)跟隨結(jié)點(diǎn)的影響力取決于結(jié)點(diǎn)間的相似性，如果相似度很高，那么領(lǐng)導(dǎo)結(jié)點(diǎn)對(duì)它們的領(lǐng)導(dǎo)力就很大。本文使用結(jié)點(diǎn)的度數(shù)相似性來(lái)反映結(jié)點(diǎn)的影響力，故而其鄰居的數(shù)量越多，其領(lǐng)導(dǎo)程度就越高，影響力也就越大。故而結(jié)點(diǎn)的領(lǐng)導(dǎo)度定義為：

同樣可以計(jì)算結(jié)點(diǎn)的跟隨度：一個(gè)結(jié)點(diǎn)只跟隨比它擁有更高領(lǐng)導(dǎo)的結(jié)點(diǎn)，它對(duì)某個(gè)結(jié)點(diǎn)的跟隨程度取決于其共同鄰居在其鄰居中的比例，具體公式如下：

根據(jù)網(wǎng)絡(luò)中結(jié)點(diǎn)的領(lǐng)導(dǎo)度和跟隨度和用戶結(jié)點(diǎn)的評(píng)論信息內(nèi)容相似性將網(wǎng)絡(luò)映射為有權(quán)有向網(wǎng)絡(luò)，將原始網(wǎng)絡(luò)結(jié)構(gòu)映射為一個(gè)簡(jiǎn)單的網(wǎng)絡(luò)。用戶結(jié)點(diǎn)的內(nèi)容相似性，通過(guò)對(duì)各個(gè)用戶的商品評(píng)論信息進(jìn)行內(nèi)容提取并獲取可以代表用戶評(píng)論主題的關(guān)鍵信息，由于用戶的評(píng)論信息多為短文本，故而本文認(rèn)為每一個(gè)短文本僅涉及一個(gè)主題內(nèi)容，將其進(jìn)行向量化，并進(jìn)行用戶結(jié)點(diǎn)間主題相似度的計(jì)算，具體公式如下所示：

其中 表示用戶結(jié)點(diǎn)i的主題向量表示，Jaccard（ ， ）表示兩個(gè)用戶結(jié)點(diǎn)間的內(nèi)容相似性。利用用戶結(jié)點(diǎn)間內(nèi)容的相似性與跟隨度結(jié)合，作為簡(jiǎn)化網(wǎng)絡(luò)的權(quán)重，對(duì)于跟隨結(jié)點(diǎn)只留取跟隨結(jié)點(diǎn)與領(lǐng)導(dǎo)結(jié)點(diǎn)間權(quán)重最大的邊的方法對(duì)復(fù)雜網(wǎng)絡(luò)進(jìn)行重新表示。將無(wú)向無(wú)權(quán)網(wǎng)絡(luò)圖重新表示為有向加權(quán)圖 。權(quán)重計(jì)算根據(jù)結(jié)點(diǎn)的跟隨度和跟隨結(jié)點(diǎn)與領(lǐng)導(dǎo)結(jié)點(diǎn)間的內(nèi)容相似性來(lái)確定，具體計(jì)算公式如下：

這里簡(jiǎn)單的認(rèn)為用戶結(jié)點(diǎn)間的跟隨度影響力和內(nèi)容相似性影響力同樣重要，故而取影響因素權(quán)重都為0.5。

重新表示后網(wǎng)絡(luò)表示如下：

重新表示之后的網(wǎng)絡(luò)是一個(gè)樹結(jié)構(gòu)，這個(gè)網(wǎng)絡(luò)有四個(gè)屬性：第一、 中的邊數(shù)不超過(guò)n?1，其中n為結(jié)點(diǎn)數(shù);第二、設(shè)T為 的子樹，對(duì)于T中任意的 ，由于 ，其根在T中的領(lǐng)導(dǎo)度L值最大;第三、對(duì)于任意兩個(gè)結(jié)點(diǎn) 和 ，如果它們之間在 中有路徑，則它們之間的路徑存在于原網(wǎng)絡(luò)G中;第四、設(shè)T為 的子樹， 是T中的所有結(jié)點(diǎn)， 是T中的所有邊，如果把T的結(jié)點(diǎn)分成兩個(gè)簇，T有如下性質(zhì)： 。由于只保留了結(jié)點(diǎn)的最大跟隨度，故而 的邊數(shù)少于n-1，實(shí)現(xiàn)了對(duì)原始網(wǎng)絡(luò)的簡(jiǎn)化。在簡(jiǎn)化后的網(wǎng)絡(luò)中可以看出具有社區(qū)最大領(lǐng)導(dǎo)度的結(jié)點(diǎn)在劃分的社區(qū)中作為核心結(jié)點(diǎn)呈現(xiàn)，故而符合了前面提到的核心結(jié)點(diǎn)是領(lǐng)導(dǎo)度大的結(jié)點(diǎn)，而邊緣結(jié)點(diǎn)則是跟隨度比較大，跟隨核心結(jié)點(diǎn)，邊的權(quán)重反則映了一個(gè)結(jié)點(diǎn)對(duì)社區(qū)的隸屬度。簡(jiǎn)化后的網(wǎng)絡(luò)是一個(gè)樹結(jié)構(gòu)類型，而每一個(gè)社區(qū)可以看作是簡(jiǎn)化了的網(wǎng)絡(luò)中的一個(gè)子樹，每個(gè)樹可以分為樹根和葉子也就是代表這網(wǎng)絡(luò)中的核心結(jié)點(diǎn)和邊緣結(jié)點(diǎn)。對(duì)于原始網(wǎng)絡(luò)邊緣結(jié)點(diǎn)與核心結(jié)點(diǎn)間可能存在多條邊，而簡(jiǎn)化后的邊結(jié)點(diǎn)與核心結(jié)點(diǎn)相只有一條邊連接，因而對(duì)于簡(jiǎn)化后的網(wǎng)絡(luò)進(jìn)行社區(qū)劃分則大大減小的劃分的復(fù)雜度。

基于簡(jiǎn)化過(guò)的網(wǎng)絡(luò) ，利用社區(qū)間聯(lián)系稀疏的性質(zhì)，即存在的公共邊最少原理進(jìn)行社區(qū)檢測(cè)，具體公式為：

min[Δ ]

其中 是對(duì)V的劃分， 是指第l個(gè)劃分社區(qū)，k是劃分社區(qū)的個(gè)數(shù)。根據(jù)屬性四可以得出：

因此最小化Δ（ ），即可得到社區(qū)劃分，從 中刪除具有第一個(gè)k-1最低權(quán)重的邊，以找出k個(gè)社區(qū)。

3實(shí)驗(yàn)分析

3.1實(shí)驗(yàn)環(huán)境與數(shù)據(jù)

本實(shí)驗(yàn)在三個(gè)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)驗(yàn)證。數(shù)據(jù)集利用爬蟲獲取微博平臺(tái)上的數(shù)據(jù)包括152個(gè)用戶，用戶的3497條評(píng)論信息以及這152個(gè)用戶間的網(wǎng)絡(luò)結(jié)構(gòu)，其中涉及4個(gè)社區(qū)結(jié)構(gòu);在淘寶平臺(tái)上獲取了276個(gè)用戶，5796條評(píng)論信息以及這些用戶間存在的網(wǎng)絡(luò)結(jié)構(gòu)信息，其中包含9個(gè)社區(qū)結(jié)構(gòu);在京東平臺(tái)上獲取214個(gè)用戶的5327條商品評(píng)論信息以及網(wǎng)絡(luò)結(jié)構(gòu)信息，其中包含6個(gè)社區(qū)結(jié)構(gòu)。實(shí)驗(yàn)環(huán)境如下：處理器為 Core i7-6500U @ 2.50GHz，運(yùn)行內(nèi)存8.0 GB，Windows 10操作系統(tǒng)，開發(fā)工具為python 3.6。

3.2評(píng)估方法

實(shí)驗(yàn)采用的評(píng)價(jià)方法為模塊度度量Q、歸一化互信息（NMI）。

1）采用模塊度Q進(jìn)行社區(qū)劃分的內(nèi)部度量。模塊度Q是由Newman等人提出的用于社區(qū)檢測(cè)算法中以檢測(cè)社區(qū)內(nèi)部結(jié)構(gòu)穩(wěn)定性的一個(gè)衡量指標(biāo)，表示復(fù)雜網(wǎng)絡(luò)社區(qū)劃分的結(jié)果是否合理，社區(qū)劃分內(nèi)部是否連接緊密，定義為：

其中E為網(wǎng)絡(luò)中總邊數(shù)， 為網(wǎng)絡(luò)的鄰接矩陣， 表示結(jié)點(diǎn)i的度， 為結(jié)點(diǎn)i所屬的社區(qū)，其取值越大表示社區(qū)劃分的質(zhì)量好，社區(qū)越穩(wěn)定。

2）NMI度量計(jì)算社區(qū)檢測(cè)結(jié)果與社區(qū)的真實(shí)劃分類別間的互信息，可以用來(lái)評(píng)價(jià)社區(qū)劃分類別標(biāo)志一致性的高低，表示為：

其中n為社區(qū)中結(jié)點(diǎn)的個(gè)數(shù)， 表示社區(qū)中公共結(jié)點(diǎn)的個(gè)數(shù)。NMI的計(jì)算結(jié)果值位于[0，1]之間，NMI值越高則表示社區(qū)檢測(cè)結(jié)果越良好，反之檢測(cè)結(jié)果越差。

3.3實(shí)驗(yàn)結(jié)果與分析

（a）、（b）、（c）分別表示本文算法在三個(gè)數(shù)據(jù)集上的社區(qū)劃分結(jié)果。從圖中可以看出本文提出的算法在三個(gè)數(shù)據(jù)集上都取得了良好的結(jié)果，可以很好的將用戶進(jìn)行社區(qū)劃分，并且對(duì)于邊緣結(jié)點(diǎn)也可以很準(zhǔn)確的進(jìn)行社區(qū)歸類，不存在被誤分的結(jié)點(diǎn)，結(jié)點(diǎn)劃分與實(shí)際網(wǎng)絡(luò)基本一致，社區(qū)劃分結(jié)果可視化強(qiáng)。

可以看出在NMI評(píng)估方法下三個(gè)數(shù)據(jù)集上，本文提出的算法都取得了最好的結(jié)果。相比DPC方法，本文算法的NMI值平均提高了0.042，得到了較好的NMI值。分析原因是本文利用了用戶的評(píng)論信息，并結(jié)合和用戶結(jié)點(diǎn)的跟隨度作為網(wǎng)絡(luò)簡(jiǎn)化過(guò)程中的權(quán)重，從而可以更加緊密了用戶之間的關(guān)系，而且劃分網(wǎng)絡(luò)的核心結(jié)點(diǎn)和邊緣結(jié)點(diǎn)進(jìn)行社區(qū)劃分提高了網(wǎng)絡(luò)中邊緣結(jié)點(diǎn)與核心中心結(jié)點(diǎn)的聯(lián)系，不至于出現(xiàn)邊緣結(jié)點(diǎn)被遺漏的問(wèn)題。而DPC算法沒有考慮用戶的內(nèi)容屬性而僅利用了網(wǎng)絡(luò)中結(jié)點(diǎn)間的拓?fù)浣Y(jié)構(gòu)來(lái)描述用戶關(guān)系，這給社區(qū)劃分結(jié)果帶來(lái)了一定的不準(zhǔn)確性。而DBSCAN算法則由于其參數(shù)的選擇問(wèn)題也是給其聚類效果帶來(lái)了一定的負(fù)面影響，使其產(chǎn)生了較差的聚類效果。K-means由于需要提前預(yù)知網(wǎng)絡(luò)劃分社區(qū)的個(gè)數(shù)，而沒有對(duì)結(jié)點(diǎn)進(jìn)行跟進(jìn)一步的分析，只是簡(jiǎn)單劃分，因此劃分結(jié)果也不理想。

4總結(jié)

在本文中，我們提出了一種新的基于用戶評(píng)論信息的網(wǎng)絡(luò)簡(jiǎn)化電商平臺(tái)社區(qū)發(fā)現(xiàn)算法。在新算法中，我們利用結(jié)點(diǎn)的領(lǐng)導(dǎo)度和跟隨度來(lái)衡量原始網(wǎng)絡(luò)中結(jié)點(diǎn)間的連接關(guān)系，并利用這兩個(gè)度量和電商網(wǎng)絡(luò)平臺(tái)中用戶的評(píng)論信息將原始無(wú)向無(wú)權(quán)網(wǎng)絡(luò)映射為簡(jiǎn)化的有向加權(quán)網(wǎng)絡(luò)，即形成加權(quán)樹或森林。簡(jiǎn)化后的網(wǎng)絡(luò)提供了對(duì)社區(qū)結(jié)構(gòu)非常直觀的理解和可解釋性，在此基礎(chǔ)上，提出用截?cái)鄻渲Φ姆椒ㄟM(jìn)行社區(qū)的劃分。在實(shí)驗(yàn)分析中將本文提出的算法與其他三種社區(qū)檢測(cè)算法進(jìn)行了比較，結(jié)果表明本文提出的算法對(duì)于網(wǎng)絡(luò)的可視化是非常有效的，并且社區(qū)劃分結(jié)果的準(zhǔn)確率也很高，能更好地劃分網(wǎng)絡(luò)，實(shí)用價(jià)值較高。

參考文獻(xiàn)

費(fèi)蓉，李莎莎，胡博，唐瑜，方金正.基于標(biāo)簽傳播的拓?fù)鋭?shì)社區(qū)檢測(cè)算法[J].計(jì)算機(jī)系統(tǒng)應(yīng)用，2020，29（10）：148-157.

作者單位

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