基于改進(jìn)隨機(jī)分塊模型的電商網(wǎng)絡(luò)鏈路預(yù)測算法

史玉林 錢曉東

摘 要：通過改進(jìn)的隨機(jī)分塊模型（SBM）鏈路預(yù)測算法，研究電子商務(wù)網(wǎng)絡(luò)的演化過程與社團(tuán)結(jié)構(gòu)。針對原始SBM模型塊之間的度分布為二項(xiàng)式分布，引入度衰減參數(shù)使得隨機(jī)分塊模型中塊之間的度分布遵循冪律分布。針對原始SBM模型中節(jié)點(diǎn)之間的連接僅僅取決于節(jié)點(diǎn)所屬塊的假設(shè)，引入度控制參數(shù)使其更接近真實(shí)網(wǎng)絡(luò)的度數(shù)分布?；诖颂岢鰞?yōu)化后的隨機(jī)分塊模型，并利用阿里巴巴淘寶數(shù)據(jù)集驗(yàn)證該算法，結(jié)果顯示該算法精確度高于隨機(jī)分塊模型（SBM）、度修正的隨機(jī)分塊模型（DCSBM）以及層次結(jié)構(gòu)模型（HBM）。說明改進(jìn)后的算法能較好地刻畫電商網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)，準(zhǔn)確地發(fā)現(xiàn)網(wǎng)絡(luò)中的缺失鏈接。

關(guān)鍵詞：隨機(jī)分塊模型； 電商網(wǎng)絡(luò)； 鏈路預(yù)測； 推薦

中圖分類號：TP630.40?? 文獻(xiàn)標(biāo)志碼：A

文章編號：1001-3695（2024）03-026-0824-07

doi：10.19734/j.issn.1001-3695.2023.07.0329

E-commerce network link prediction algorithm based on

improved stochastic block model

Shi Yulin， Qian Xiaodong

（School of Economics & Management， Lanzhou Jiaotong University， Lanzhou 730070， China）

Abstract：To study the evolution process and community structure of e-commerce networks， this paper used an improved stochastic block model（SBM） link prediction algorithm. Since the degree distribution among blocks in the original SBM model was binomial， to make the degree distribution among blocks follow the power law distribution in the stochastic block model， this paper introduced the degree attenuation parameter. Aiming at the assumption that the connection between nodes depended only on the block to which nodes belong in the original SBM model， to make the degree distribution closer to the real network， the paper introduced the degree control parameter. Based on this， the paper proposed an optimized random block model， and used the Alibaba Taobao data set to verify the proposed algorithm. The results show that the accuracy of the proposed algorithm is higher than the SBM， the degree-corrected stochastic block model（DCSBM） and the hierarchical structure model（HBM）. It shows that the improved algorithm can describe the community structure of the e-commerce network well and find the missing link in the network accurately.

Key words：stochastic block model（SBM）; e-commerce network; link prediction; recommendation

移動電子商務(wù)網(wǎng)絡(luò)的迅猛發(fā)展，逐漸改變了人們傳統(tǒng)的購物方式。通過使用移動設(shè)備，擺脫了傳統(tǒng)電子商務(wù)的束縛，使得購物在時(shí)間、地點(diǎn)上更加靈活。消費(fèi)者可以隨時(shí)隨地利用碎片時(shí)間進(jìn)行網(wǎng)頁瀏覽和消費(fèi)，大大提高了交易的效率。近幾年，各品牌、中間商和商家紛紛走進(jìn)電商平臺，想趕上電商平臺帶來的紅利，這使得各大電商平臺中商品的數(shù)量與品類呈指數(shù)增加。與此同時(shí)，用戶在購買前后的瀏覽、購買、收藏、評論等行為也使得電子商務(wù)網(wǎng)絡(luò)中的數(shù)據(jù)呈指數(shù)上升。那么，如何在海量的商品中根據(jù)消費(fèi)者的以往消費(fèi)行為為其提供個(gè)性化推薦，是目前研究的一個(gè)熱點(diǎn)。通過將整個(gè)電商網(wǎng)絡(luò)的數(shù)據(jù)進(jìn)行分塊處理，然后對不同社區(qū)的消費(fèi)者進(jìn)行推薦，會大大提高推薦的準(zhǔn)確度，增加商品銷量。

鏈路預(yù)測是推薦系統(tǒng)中的一個(gè)重要研究方向，其可用于提取信息、識別虛假的交互、評估網(wǎng)絡(luò)演化機(jī)制等［1］。除了幫助分析具有缺失數(shù)據(jù)的網(wǎng)絡(luò)之外，鏈接預(yù)測算法還可以用于預(yù)測未來可能出現(xiàn)在不斷發(fā)展網(wǎng)絡(luò)中的鏈接。例如，在電子商務(wù)網(wǎng)絡(luò)中，非常可能但尚未存在的鏈接可以被推薦為有希望的被購買的產(chǎn)品，這可以幫助用戶找到有潛在需求的商品，從而提高他們對網(wǎng)站的忠誠度。然而鏈路預(yù)測算法在電子商務(wù)網(wǎng)絡(luò)中的研究尚屬于起步階段，如何利用鏈路預(yù)測算法遏制失真信息，預(yù)測節(jié)點(diǎn)間連接的概率，提高推薦的精確性，還有待商榷。因此，本文基于傳統(tǒng)的隨機(jī)分塊模型，結(jié)合電商網(wǎng)絡(luò)中的消費(fèi)者購買特性，對該模型進(jìn)行優(yōu)化改進(jìn)，使得實(shí)驗(yàn)結(jié)果更加符合實(shí)際情況，為電子商務(wù)網(wǎng)絡(luò)個(gè)性化推薦研究提供參考。

1 相關(guān)研究綜述

鏈路預(yù)測是社交網(wǎng)絡(luò)研究的一個(gè)重要分支。社交網(wǎng)絡(luò)中的鏈路預(yù)測能夠給社交網(wǎng)絡(luò)中的用戶提供個(gè)性化的推薦，給可能交互的用戶提供接觸的橋梁［2］。21世紀(jì)初，文獻(xiàn)［3］首先提出鏈路預(yù)測，并將其應(yīng)用在社交網(wǎng)絡(luò)中。隨后鏈路預(yù)測在不同的網(wǎng)絡(luò)領(lǐng)域中采用，例如信息檢索、生物信息學(xué)、電子商務(wù)和信息計(jì)量學(xué)［4］?，F(xiàn)有鏈路預(yù)測領(lǐng)域的研究方法有基于相似性的鏈路預(yù)測算法、概率模型、最大似然模型等［5］。

1）基于相似性的鏈路預(yù)測算法 在該方法中，基本假設(shè)是將兩個(gè)節(jié)點(diǎn)之間的相似性得分視為它們之間形成鏈接概率的重要因素［6］，對于所有未觀察到的鏈接，計(jì)算相似性分?jǐn)?shù)，并且較高的分?jǐn)?shù)意味著將來節(jié)點(diǎn)之間形成鏈接的概率較高［7］。如果兩個(gè)節(jié)點(diǎn)具有共同的特征，那么可以直接測量節(jié)點(diǎn)相似性;否則，必須使用涉及鏈接屬性的結(jié)構(gòu)相似性來測量節(jié)點(diǎn)相似性［8］。目前研究中，具有代表性的算法指標(biāo)有局部社團(tuán)范式系列增強(qiáng)指標(biāo)（local-community-paradigm，LCP）［9］、資源分配指標(biāo)（resource allocation，RA）［10］、共同鄰居指標(biāo)（common neighbor，CN）［3］。大部分基于相似性的鏈路預(yù)測算法都在二階路徑框架下設(shè)計(jì)，但也有少量但重要的算法更關(guān)注節(jié)點(diǎn)間的局部連接范式，如LCP系列指標(biāo)［6］。

2）基于概率模型的鏈路預(yù)測算法 該算法是通過對網(wǎng)絡(luò)中已有節(jié)點(diǎn)之間的連接進(jìn)行概率建模，來預(yù)測未來節(jié)點(diǎn)之間的連接。其中主流概率模型包括貝葉斯網(wǎng)絡(luò)、馬爾可夫隨機(jī)場、隨機(jī)關(guān)系模型和考慮了實(shí)體之間依賴關(guān)系的圖模型［11］等。文獻(xiàn)［3］最先將機(jī)器學(xué)習(xí)方法應(yīng)用在鏈路預(yù)測中，并且獲得了較高的準(zhǔn)確度。Asil等人［12］采用了一種基于模糊規(guī)則的監(jiān)督學(xué)習(xí)算法，并通過實(shí)驗(yàn)證明在監(jiān)督算法中，決策樹算法和隨機(jī)森林算法比基于模糊規(guī)則的算法具有更好的性能。Gupta等人［13］通過樸素貝葉斯方法將鏈路預(yù)測視為一個(gè)二元分類問題來識別網(wǎng)絡(luò)中缺失的連接。但在這些模型中，需要輸入節(jié)點(diǎn)信息以及網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，因此無法高效地應(yīng)用在僅具有連邊關(guān)系的網(wǎng)絡(luò)數(shù)據(jù)中。

3）基于最大似然模型的鏈路預(yù)測算法 最大似然模型的基本思路是首先對數(shù)據(jù)去除噪聲、填充缺失值、標(biāo)準(zhǔn)化等，通過統(tǒng)計(jì)學(xué)方法對節(jié)點(diǎn)之間的聯(lián)系進(jìn)行建模，并利用已知的社交網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行模型訓(xùn)練，通過交叉驗(yàn)證等方法優(yōu)化模型參數(shù)，最后利用訓(xùn)練好的模型對未知節(jié)點(diǎn)之間的鏈接進(jìn)行預(yù)測。Clauset等人［14］提出一種簡單的層次結(jié)構(gòu)模型（hierarchical structure model，HSM），該模型的精確度雖然較高，但計(jì)算復(fù)雜度卻很大。文獻(xiàn)［15］在傳統(tǒng)的隨機(jī)分塊模型基礎(chǔ)上，提出一種適用于動態(tài)網(wǎng)絡(luò)的混合結(jié)構(gòu)獎勵預(yù)測算法來預(yù)測網(wǎng)絡(luò)中丟失的鏈接。Pan等人［16］提出一種算法框架，用預(yù)先定義的結(jié)構(gòu)哈密頓量計(jì)算網(wǎng)絡(luò)概率，并通過大量的數(shù)值模擬表明該算法在預(yù)測缺失的鏈接和識別虛假的鏈接方面比最先進(jìn)的方法具有更高的精度。

以上三種鏈路預(yù)測算法中，基于相似性的鏈路預(yù)測方法通過判斷節(jié)點(diǎn)之間的相似性確定節(jié)點(diǎn)之間出現(xiàn)新的連邊的可能性，然而這種方法并不能充分考慮網(wǎng)絡(luò)結(jié)構(gòu)的復(fù)雜性和動態(tài)性，所以其預(yù)測準(zhǔn)確度有限?；诟怕誓Ｐ偷姆椒ǔ浞挚紤]了網(wǎng)絡(luò)節(jié)點(diǎn)間的關(guān)系，預(yù)測準(zhǔn)確度相對于基于相似性的方法有所提高，但是其計(jì)算復(fù)雜度較高，且對數(shù)據(jù)的依賴程度較高。最大似然方法中，雖然同樣面臨著計(jì)算復(fù)雜度高和依賴數(shù)據(jù)的問題，但該方法在預(yù)測準(zhǔn)確度上相比其他方法具有優(yōu)勢。因此，本文選取在預(yù)測精度上具有優(yōu)勢的最大似然鏈路預(yù)測算法，并且選取了在時(shí)間復(fù)雜度和準(zhǔn)確性、效率性上有很大優(yōu)勢的隨機(jī)分塊模型。

2 隨機(jī)分塊模型與改進(jìn)

2.1 隨機(jī)分塊模型

1983 年，文獻(xiàn)［17］將隨機(jī)模型與塊模型結(jié)合，從而提出隨機(jī)塊模型（stochastic block model，SBM）。該模型是建立在一定的先驗(yàn)知識的基礎(chǔ)上的，它的主要思想是將網(wǎng)絡(luò)中的節(jié)點(diǎn)分成若干個(gè)群，兩個(gè)節(jié)點(diǎn)是否連接的概率只取決于節(jié)點(diǎn)所在的群［18］。即該模型認(rèn)為處于同一組中所有節(jié)點(diǎn)的地位是相同的，它主要由兩部分信息決定，一是網(wǎng)絡(luò)被分成若干群的方案，二是分屬于兩個(gè)群的兩點(diǎn)之間產(chǎn)生連邊的概率矩陣［18］。

綜上，本文選擇了在建模靈活性、挖掘精度和應(yīng)用上都有著巨大優(yōu)勢的模型——隨機(jī)塊模型（SBM）［13］。但傳統(tǒng)的隨機(jī)塊模型（SBM）在刻畫電商網(wǎng)絡(luò)中存以下局限。a）模型中假設(shè)塊之間的度分布為二項(xiàng)式分布［19］，在實(shí)際電子商務(wù)網(wǎng)絡(luò)中，商品之間的關(guān)系復(fù)雜且密集，其結(jié)構(gòu)通常由少數(shù)幾個(gè)超級節(jié)點(diǎn)主導(dǎo)，這些節(jié)點(diǎn)有著極高的度數(shù)和影響力。在此情況下，如果僅用二項(xiàng)式分布假設(shè)各商品之間的連接概率，得到的推薦結(jié)果可能與用戶實(shí)際需求不相符。因此傳統(tǒng)的隨機(jī)分塊模型假設(shè)塊之間的度為二項(xiàng)式分布，并不能反映電子商務(wù)網(wǎng)絡(luò)中消費(fèi)者與商品之間的關(guān)系。b）在傳統(tǒng)隨機(jī)分塊模型中，假設(shè)節(jié)點(diǎn)之間的連接僅僅取決于節(jié)點(diǎn)所屬的塊［20］，并沒有考慮節(jié)點(diǎn)的度數(shù)對推薦結(jié)果的影響，這會導(dǎo)致一些節(jié)點(diǎn)被過度推薦或者被低估，從而影響鏈路預(yù)測的精確度。因此本文對SBM模型作出以下優(yōu)化：a）通過引入度衰減參數(shù)，使得隨機(jī)分塊模型中的塊之間的度分布遵循冪律分布；b）通過引入節(jié)點(diǎn)的度控制參數(shù)，從而調(diào)整網(wǎng)絡(luò)中邊的生成概率，合理限制節(jié)點(diǎn)的度數(shù)，使模擬出的網(wǎng)絡(luò)更接近真實(shí)網(wǎng)絡(luò)的度數(shù)分布，并且利用真實(shí)的消費(fèi)者數(shù)據(jù)對優(yōu)化后的模型進(jìn)行實(shí)證模擬，以期提高推薦準(zhǔn)確度。

2.2 改進(jìn)隨機(jī)分塊模型

2.2.1 基于度衰減參數(shù)的SBM模型塊間的度分布優(yōu)化

1）傳統(tǒng)SBM模型塊間度分布的不足

由于傳統(tǒng)的隨機(jī)分塊模型（SBM）在塊之間的節(jié)點(diǎn)連接時(shí)用相同的參數(shù)處理塊中的所有節(jié)點(diǎn)，即該模型假設(shè)塊之間的度分布是二項(xiàng)式分布。但是在真實(shí)的電子商務(wù)網(wǎng)絡(luò)中，每個(gè)個(gè)體的購買力大小不同，所以隨機(jī)分塊模型（SBM）在研究電子商務(wù)網(wǎng)絡(luò)的演化過程中存在不足。

一般來說，當(dāng)個(gè)體擁有更強(qiáng)購買力時(shí)就更有可能購買新的產(chǎn)品，從而與新的個(gè)體產(chǎn)生連接。因?yàn)樗麄円呀?jīng)有了更大的交際圈，所以更有可能通過現(xiàn)有的關(guān)系結(jié)交到新的朋友，擁有更多朋友可以創(chuàng)造更多交新朋友的機(jī)會。實(shí)際上，當(dāng)一個(gè)個(gè)體已經(jīng)擁有很多朋友時(shí)，這表明他們可能有某種能力或者親和力來交更多的新朋友，這種能力會吸引其他人產(chǎn)生新的關(guān)系，就像流行網(wǎng)站上鏈接到其他網(wǎng)站和博客上的鏈接一樣，已經(jīng)建立的城市會招來新的鐵路和航線規(guī)劃。這種特征符合無標(biāo)度網(wǎng)絡(luò)結(jié)構(gòu)中“偏好依附”這一原則。偏好依附是一個(gè)大者愈大的網(wǎng)絡(luò)增長規(guī)則：一個(gè)有著更多連接的節(jié)點(diǎn)相比于連接更少的節(jié)點(diǎn)會有更大可能性獲得新的連接。因此傳統(tǒng)的隨機(jī)分塊模型（SBM）不能對普遍存在于現(xiàn)實(shí)電商網(wǎng)絡(luò)中的這種冪律分布特征進(jìn)行建模。在電商網(wǎng)絡(luò)中，一些節(jié)點(diǎn)可能具有很高的度數(shù)，比如熱門商品或者廣告；而一些節(jié)點(diǎn)可能具有很低的度數(shù)，比如稀有商品或者少有人關(guān)注的店鋪。加入度衰減參數(shù)可以更好地處理這些不同類型的節(jié)點(diǎn)。具體來說，度衰減參數(shù)可以降低節(jié)點(diǎn)度數(shù)與其他節(jié)點(diǎn)之間的連接概率，這樣能夠更好地反映網(wǎng)絡(luò)中度數(shù)大的節(jié)點(diǎn)對網(wǎng)絡(luò)結(jié)構(gòu)的影響，并避免一些不合理的連接，從而更好地?cái)M合電商網(wǎng)絡(luò)結(jié)構(gòu)。

2）改進(jìn)SBM模型塊間度分布的優(yōu)化

基于上述分析，本文提出一種適應(yīng)現(xiàn)實(shí)世界電商網(wǎng)絡(luò)中冪律分布特征的方法，從而提高商品推薦的精確性。將網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)i與另一個(gè)潛在變量αi≥0相關(guān)聯(lián)，并用它來調(diào)整節(jié)點(diǎn)度的分布，即

p（αi|λ）=λe-λαi（1）

其中：αi為度衰減變量，且該變量與節(jié)點(diǎn)之間的概率呈負(fù)相關(guān)。令αi服從指數(shù)先驗(yàn)exp（λ），從而得到不同的取值范圍。αi取值越大代表節(jié)點(diǎn)的度衰減得越快，取值越小，則表示節(jié)點(diǎn)的度衰減得越慢。因此，節(jié)點(diǎn)度的變化規(guī)律應(yīng)滿足：a）當(dāng)αi=0，即所有節(jié)點(diǎn)的度不發(fā)生變化時(shí)，節(jié)點(diǎn)度數(shù)對社區(qū)結(jié)構(gòu)沒有影響，所有節(jié)點(diǎn)被等概率地分配到各個(gè)社區(qū)中，模型退化至傳統(tǒng)的隨機(jī)分塊SBM；b）當(dāng)αi=1，即所有節(jié)點(diǎn)的度不斷變化時(shí)，節(jié)點(diǎn)度數(shù)對社區(qū)結(jié)構(gòu)的影響最大，節(jié)點(diǎn)度數(shù)越大，被分配到同一社區(qū)的概率越大，節(jié)點(diǎn)的度分布最終演化為冪律分布。

在電商網(wǎng)絡(luò)中，同一個(gè)社區(qū)中節(jié)點(diǎn)之間的連接是構(gòu)成該社區(qū)的主要因素，而該社區(qū)與其他社區(qū)的連接則相對較少。在這一假設(shè)的基礎(chǔ)上，本文考慮集群內(nèi)或等效的單集群情況來證明優(yōu)化后的隨機(jī)分塊模型的建模能力。

3）改進(jìn)SBM模型塊間度分布優(yōu)化分析

假設(shè)一個(gè)社團(tuán)內(nèi)有m0個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)都與潛在度衰減變量αi～exp（λ）相關(guān)聯(lián)，兩個(gè)社區(qū)之間的邊緣概率為p0?；趶?qiáng)大的大數(shù)定律 （SLLN），隨著m0的增加，可以證明，優(yōu)化后的隨機(jī)分塊模型節(jié)點(diǎn)i的歸一化度將收斂到僅取決于 αi的隨機(jī)變量di［21］，即

將式（3）看作優(yōu)化后的隨機(jī)分塊模型的冪律度特征，當(dāng) λ 較小時(shí)，式（3）中形狀參數(shù)γ=1+λ/ln p0的值接近1。雖然這小于實(shí)際網(wǎng)絡(luò)的典型值（介于2～4）。但是較小的形狀參數(shù)使優(yōu)化后的模型能夠更加符合電商網(wǎng)絡(luò)度分布的重尾特征。

4）模擬實(shí)驗(yàn)

通過仿真實(shí)驗(yàn)驗(yàn)證引入度衰減參數(shù)后的SBM模型有較好的性能，兩個(gè)模型的初始網(wǎng)絡(luò)均有200個(gè)節(jié)點(diǎn)，網(wǎng)絡(luò)的平均度數(shù)k=10，社區(qū)間的連邊概率p0=0.25，網(wǎng)絡(luò)中的社區(qū)數(shù)c=5，引入度衰減參數(shù)的模型將參數(shù)αi設(shè)置為0.52，將傳統(tǒng)的隨機(jī)分塊模型和引入度衰減參數(shù)的隨機(jī)分塊模型生成的網(wǎng)絡(luò)（圖1）進(jìn)行比較，生成網(wǎng)絡(luò)的度分布的變化如圖2所示。

圖1（a）為傳統(tǒng)隨機(jī)分塊模型生成的復(fù)雜網(wǎng)絡(luò)，圖1（b）為引入度衰減參數(shù)生成的復(fù)雜網(wǎng)絡(luò)；圖2（a）為傳統(tǒng)隨機(jī)分塊模型生成網(wǎng)絡(luò)的度分布直方圖，圖2（b）為引入度衰減參數(shù)生成網(wǎng)絡(luò)的度分布直方圖。從實(shí)驗(yàn)結(jié)果來看，傳統(tǒng)隨機(jī)分塊模型生成網(wǎng)絡(luò)（圖1（a））的度數(shù)相關(guān)性為-0.007，引入度衰減參數(shù)的SBM模型生成網(wǎng)絡(luò)（圖1（b））的度數(shù)相關(guān)性為-0.226，表明優(yōu)化后的模型節(jié)點(diǎn)傾向于連接到度數(shù)比本身小的節(jié)點(diǎn)，得到的節(jié)點(diǎn)的度分布更分散；另外，圖1（a）的冪律指數(shù)為13.995，圖1（b）的冪律指數(shù) 為4.73，表明加入度衰減參數(shù)后的模型得到的網(wǎng)絡(luò)呈現(xiàn)出冪律分布的特征，這一特點(diǎn)在圖2中同樣得到驗(yàn)證，圖1（b）的節(jié)點(diǎn)度分布圖擁有明顯的長尾特征。因此，引入度衰減參數(shù)的隨機(jī)分塊模型有利于模擬更加真實(shí)的電商網(wǎng)絡(luò)。

2.2.2 基于度控制參數(shù)的節(jié)點(diǎn)之間連接概率的優(yōu)化

1）傳統(tǒng)SBM模型節(jié)點(diǎn)之間連接概率的不足

傳統(tǒng)隨機(jī)分塊模型（SBM）中任意節(jié)點(diǎn)vi和vj之間是否有鏈接取決于兩者所屬的塊及塊和塊之間的鏈接概率。但在真實(shí)的電子商務(wù)網(wǎng)絡(luò)中，擁有相似購買喜好的消費(fèi)者在未來的消費(fèi)行為中，購買同樣或類似產(chǎn)品的概率也不盡相同。因此傳統(tǒng)的隨機(jī)分塊模型應(yīng)用在實(shí)際的電商網(wǎng)絡(luò)中存在不足之處。

在小世界網(wǎng)絡(luò)節(jié)點(diǎn)之間連接的研究中，研究較多的是通過在原有的連邊基礎(chǔ)上隨機(jī)化加邊或者隨機(jī)化重連來形成具有冪律分布特性的網(wǎng)絡(luò)，這些方法可以從不同方面刻畫出特定的網(wǎng)絡(luò)，也都有其自身的優(yōu)點(diǎn)和不足。現(xiàn)實(shí)世界中的網(wǎng)絡(luò)千變?nèi)f化，在將具有相同特征的節(jié)點(diǎn)劃分到同一區(qū)塊后，還需對同一區(qū)塊中的節(jié)點(diǎn)再作出區(qū)分。

2）改進(jìn)SBM模型節(jié)點(diǎn)連接概率的優(yōu)化

基于上述分析，本文提出一種新的決定節(jié)點(diǎn)之間連接概率的方法。在該方法中，節(jié)點(diǎn)依然會劃分到各個(gè)不同的區(qū)塊，不同的是任意兩個(gè)節(jié)點(diǎn)之間的連接概率是由節(jié)點(diǎn)所屬的區(qū)塊與節(jié)點(diǎn)的期望度參數(shù)共同決定的，將新引入的節(jié)點(diǎn)度控制參數(shù)與已有的塊參數(shù)相乘，可以合并成為新的期望鏈接數(shù)。具體的計(jì)算方法如下：

a）構(gòu)建網(wǎng)絡(luò)。將一個(gè)無向網(wǎng)絡(luò)記為G（V，E），該網(wǎng)絡(luò)包含自邊和多邊的無向網(wǎng)絡(luò)，其鄰接矩陣記為A，并按如下方式進(jìn)行定義：

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

4.3.1 改進(jìn)后的SBM模型對真實(shí)網(wǎng)絡(luò)的影響分析

Clauset等人［23］的研究表明，度衰減參數(shù)可以在0.1～1.0取值，當(dāng)衰減參數(shù)取值較小（0.1左右）時(shí)，生成的網(wǎng)絡(luò)具有更巨大的社區(qū)結(jié)構(gòu)，而當(dāng)衰減參數(shù)取值較大（0.9左右）時(shí)，生成的網(wǎng)絡(luò)更為分散。Monroy等人［24］通過實(shí)驗(yàn)表明，當(dāng)度控制參數(shù)的值在（0.5，1］時(shí)，節(jié)點(diǎn)度數(shù)分布呈現(xiàn)冪律分布特性。因此，本文選取度衰減參數(shù)為0.3、0.9，度控制參數(shù)為0.6、0.9排列組合而成的四組數(shù)據(jù)進(jìn)行仿真模擬。

運(yùn)用仿真軟件得出度衰減參數(shù)αi和度控制參數(shù)βi為（0.3，0.6）（0.9，0.6）（0.3，0.9）和（0.9，0.9）的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖，如圖3（a）～（d）所示。圖3（a）有197個(gè)節(jié)點(diǎn)和834條邊，（b）有197個(gè)節(jié)點(diǎn)和1 278條邊，（c）有197個(gè)節(jié)點(diǎn)和1 481條邊，（d）有197個(gè)節(jié)點(diǎn)和1 947條邊，并且表1列出了上述四個(gè)網(wǎng)絡(luò)的基本拓?fù)湫再|(zhì)。其中，從網(wǎng)絡(luò)的平均集聚系數(shù)來看，該網(wǎng)絡(luò)具有很強(qiáng)的集聚性，說明任意兩個(gè)節(jié)點(diǎn)之間都存在很多共同的鄰居節(jié)點(diǎn)；四個(gè)網(wǎng)絡(luò)的同配系數(shù)均為負(fù)數(shù)，說明度數(shù)不同的節(jié)點(diǎn)相互連接的概率更高，即所有網(wǎng)絡(luò)都是異配的。通過計(jì)算得到四個(gè)網(wǎng)絡(luò)冪律指數(shù)分別為1.9、2.4、2.7、2.8，均符合電商網(wǎng)絡(luò)的冪律指數(shù)為（1.5，3）［25］，因此該網(wǎng)絡(luò)可用于進(jìn)行電商網(wǎng)絡(luò)預(yù)測的研究。

從圖3可以得出：若度衰減參數(shù)αi不變，度控制參數(shù)βi在一定范圍內(nèi)設(shè)置越小，網(wǎng)絡(luò)就越稀疏；若度控制參數(shù)βi不變，度衰減參數(shù)αi在一定范圍內(nèi)設(shè)置越小，網(wǎng)絡(luò)就越密集。在一定范圍內(nèi)度衰減參數(shù)越小，度控制參數(shù)越大，網(wǎng)絡(luò)就越密集。本文分析這是由于度衰減參數(shù)αi越大時(shí)，節(jié)點(diǎn)對相似度的影響就越小， 節(jié)點(diǎn)之間成為鄰居的可能性就越小，形成的網(wǎng)絡(luò)便越稀疏；度控制參數(shù)βi越大時(shí)，節(jié)點(diǎn)的鄰居數(shù)量會越多，節(jié)點(diǎn)之間的連接就更加密集，網(wǎng)絡(luò)也就更加密集。因此，度衰減參數(shù)在一定范圍內(nèi)應(yīng)設(shè)置得較小，度控制參數(shù)在一定范圍內(nèi)應(yīng)設(shè)置得較大。

4.3.2 實(shí)驗(yàn)對比分析

由于現(xiàn)實(shí)網(wǎng)絡(luò)中隨機(jī)發(fā)生、不確定因素的存在，常常造成網(wǎng)絡(luò)中的許多缺失、不準(zhǔn)確的信息。例如在建構(gòu)社會網(wǎng)絡(luò)時(shí)，一些涉及到被調(diào)查者隱私的信息，往往會被隱瞞不愿告知，或者由于暫時(shí)被遺忘而導(dǎo)致搜集到的信息不完整。其次在人工處理信息時(shí)，也會因?yàn)橐恍┦д`造成最終構(gòu)造的網(wǎng)絡(luò)不準(zhǔn)確。以上各種因素在網(wǎng)絡(luò)連接過程中均會導(dǎo)致邊的隨機(jī)缺失現(xiàn)象。

為驗(yàn)證本文算法具備較高的預(yù)測準(zhǔn)確率，使用阿里巴巴消費(fèi)者數(shù)據(jù)構(gòu)建的實(shí)際網(wǎng)絡(luò)，按照缺失邊比例f=|EL|/|ET|，f∈［0.05，0.95］生成若干“缺失邊”，然后檢驗(yàn)改進(jìn)后的算法識別這些邊的能力。針對傳統(tǒng)的SBM、Degree-corrected stochastic block model（DCSBM）、優(yōu)化后的SBM（Optimized-SBM）和基于最大似然方法的層次結(jié)構(gòu)模型（hierarchical structure model，HSM）四種鏈路預(yù)測的算法，將其分別與同一個(gè)缺失比例的真實(shí)網(wǎng)絡(luò)所獲得的預(yù)測結(jié)果進(jìn)行對比，計(jì)算相應(yīng)的AUC指標(biāo)，每個(gè)取值均為四種算法在真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集運(yùn)行100次取平均值所得，結(jié)果如圖4所示。

實(shí)驗(yàn)過程中，Optimized-SBM算法在度衰減參數(shù)和度控制參數(shù)變化時(shí)得到的網(wǎng)絡(luò)節(jié)點(diǎn)和邊的數(shù)量與其他三種算法保持一致。橫坐標(biāo)f表示缺失邊的設(shè)置比例，計(jì)算公式為f=|EL|/|ET|，變化為0.05～0.95；縱坐標(biāo)為AUC值，圖4中的每條曲線都表示對應(yīng)算法在f變化時(shí)AUC的變化。

由圖4可以看出，在度衰減參數(shù)不變的前提下，隨著度控制參數(shù)的減小，四種算法的精確度都有明顯提高，僅在度衰減參數(shù)較小時(shí)，隨著度控制參數(shù)的變大，HSM算法的精確度降低。本文分析出現(xiàn)該現(xiàn)象的原因是在密集網(wǎng)絡(luò)中，節(jié)點(diǎn)的度數(shù)相對較高，導(dǎo)致許多節(jié)點(diǎn)之間具有相同的共同鄰居數(shù)，從而降低HSM算法的預(yù)測精度；在度控制參數(shù)不變的前提下，隨著度衰減參數(shù)的變小，即網(wǎng)絡(luò)越密集的情況下，四種算法的預(yù)測精確度基本都有不同程度的提高。

另外，Optimized-SBM算法不論在稀疏網(wǎng)絡(luò)還是密集網(wǎng)絡(luò)的精確度都比HSM算法要好很多，僅在度衰減參數(shù)為0.3的網(wǎng)絡(luò)中Optimized-SBM算法在缺失邊比例較小時(shí)表現(xiàn)不如DCSBM和SBM算法，當(dāng)缺失邊比例超過65%時(shí)該算法才能給出更好的預(yù)測精確度，而在其他網(wǎng)絡(luò)中，該算法的精確度都比DCSBM和SBM算法要高。本文分析出現(xiàn)該現(xiàn)象的原因是：

a）加入度控制參數(shù)的隨機(jī)分塊算法依賴節(jié)點(diǎn)度數(shù)和所在塊的度數(shù)之和，這種方法在處理度衰減參數(shù)較小的網(wǎng)絡(luò)時(shí)容易受到塊大小的影響，即塊大小相近的情況下，節(jié)點(diǎn)在不同塊中的度數(shù)和并不會有很大的差別。因此，節(jié)點(diǎn)的分配可能不夠精確，導(dǎo)致算法性能下降。

b）傳統(tǒng)隨機(jī)分塊算法和度修正的隨機(jī)分塊算法不依賴節(jié)點(diǎn)度數(shù)和所在塊的度數(shù)之和，而是基于節(jié)點(diǎn)之間的連接關(guān)系進(jìn)行劃分，這種方法在處理度衰減參數(shù)較小的網(wǎng)絡(luò)時(shí)仍然能夠保持較好的精確度。

4.3.3 實(shí)驗(yàn)結(jié)果

從圖4可以看出，隨著度衰減參數(shù)αi和度控制參數(shù)βi的變小，四種算法在預(yù)測缺失邊時(shí)精確度都有提高，以O(shè)ptimized-SBM算法為例，度衰減參數(shù)αi和度控制參數(shù)βi為0.9時(shí)（圖4（a）），當(dāng)f=0.05時(shí)，該算法的AUC值接近0.725；而當(dāng)度衰減參數(shù)αi為0.9，度控制參數(shù)βi為0.3時(shí)，同樣f=0.05的情況下，該算法的AUC值達(dá)到了0.87，即使在缺失邊比例達(dá)到0.95時(shí)，預(yù)測的精確度也達(dá)到了0.625以上。充分證明了考慮到節(jié)點(diǎn)度分布和節(jié)點(diǎn)之間的連接概率的SBM算法能夠更加準(zhǔn)確地預(yù)測電商網(wǎng)絡(luò)邊的連接。

表2展示了所有算法在不同比例的缺失邊數(shù)據(jù)下的預(yù)測效果。從結(jié)果數(shù)據(jù)中可以得出：不同的算法對于不同大小的網(wǎng)絡(luò)和不同缺失邊比例的情況有不同的預(yù)測效果。在節(jié)點(diǎn)大小較小（α1=0.9，β1=0.6）和缺失邊比例較低（如10%）的情況下，四種算法的預(yù)測效果都相對較好，MCC得分普遍在0.8以上。而在節(jié)點(diǎn)大小較大（α2=0.3，β2=0.9）和缺失邊比例較高（如80%）的情況下，四種算法的預(yù)測效果都有所下降，MCC得分普遍在0.5左右。在同一網(wǎng)絡(luò)中，本文Optimized-SBM算法的預(yù)測效果相對較好。無論節(jié)點(diǎn)大小和缺失邊比例如何變化，Optimized-SBM算法的AUC和MCC得分都保持在較高水平，且recall、precision和F1得分也相對平衡。說明Optimized-SBM算法可以較好地捕捉到網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)。

HSM算法在大部分情況下的預(yù)測效果較差。無論是在節(jié)點(diǎn)大小較小還是缺失邊比例較低的情況下，HSM算法的MCC得分都明顯低于其他三種算法，且recall、precision和F1得分也較低。這可能是因?yàn)镠SM算法更適用于節(jié)點(diǎn)之間存在較多有效路徑的情況，而在缺失邊較多的網(wǎng)絡(luò)中，有效路徑減少導(dǎo)致了預(yù)測效果的下降。

DCSBM和SBM算法在大部分情況下的預(yù)測效果介于Optimized-SBM和HSM之間。雖然它們的預(yù)測效果沒有Optimized-SBM算法那么好，但仍然相對穩(wěn)定，并且在某些情況下能夠取得比HSM算法更好的結(jié)果。

綜上所述，本文Optimized-SBM算法在大多數(shù)情況下表現(xiàn)較好，而HSM算法在缺失邊較多的情況下表現(xiàn)較差。DCSBM和SBM算法在某些情況下能夠取得較好的預(yù)測效果。

4.4 建議

針對以上實(shí)驗(yàn)結(jié)果，本文針對賣家與消費(fèi)者分別給予以下建議：

對于賣家而言，可以通過提高自己的度，即增加其他店鋪和消費(fèi)者與其連接，來提高自己在電商網(wǎng)絡(luò)中的影響力和曝光率。同時(shí)，店鋪可以選擇與度控制參數(shù)較大的其他店鋪合作，共同推廣產(chǎn)品，通過合作來增加自己在電商網(wǎng)絡(luò)中的度，以提高自己的銷售量和收益。

對于消費(fèi)者而言，應(yīng)該通過參與電商網(wǎng)絡(luò)中的社交活動、評論和評分等方式，增加自己與其他店鋪和消費(fèi)者之間的連接，提高自己在電商網(wǎng)絡(luò)中的度和影響力。此外，消費(fèi)者可以選擇購買與其他店鋪和消費(fèi)者聯(lián)系較多的店鋪產(chǎn)品，以獲取更多的優(yōu)惠和折扣。

5 結(jié)束語

本文提出一種基于改進(jìn)的SBM模型的鏈路預(yù)測算法?？紤]到真實(shí)電商網(wǎng)絡(luò)的特點(diǎn)，從節(jié)點(diǎn)的度分布和節(jié)點(diǎn)連接概率兩個(gè)方面改進(jìn)SBM模型。

針對原始SBM模型假設(shè)模型中塊之間的度分布為二項(xiàng)式分布的問題，提出基于度衰減參數(shù)來調(diào)整節(jié)點(diǎn)度數(shù)的優(yōu)化機(jī)制，即減少熱門商品對分塊結(jié)果的影響，使得商品分布更加均勻，提高分塊結(jié)果準(zhǔn)確性；針對SBM模型中節(jié)點(diǎn)之間是否連接僅取決于塊之間的連接概率，提出將度控制參數(shù)用來調(diào)整節(jié)點(diǎn)所在的塊的度之和，從而影響塊的大小分布。通過兩方面的改進(jìn)，SBM 模型可以更好地刻畫電子商務(wù)網(wǎng)絡(luò)中的演化規(guī)律，更準(zhǔn)確地預(yù)測電子商務(wù)網(wǎng)絡(luò)中的節(jié)點(diǎn)潛在連接。選取真實(shí)的淘寶商品數(shù)據(jù)集，研究電子商務(wù)網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)，將本文算法在不同度衰減參數(shù)和度控制參數(shù)下得到的網(wǎng)絡(luò)與SBM和DCSBM、HSM三種算法預(yù)測缺失邊的能力進(jìn)行比較。實(shí)驗(yàn)結(jié)果表明，本文算法的預(yù)測準(zhǔn)確率優(yōu)于其他三種算法，能夠較為準(zhǔn)確地預(yù)測出電子商務(wù)網(wǎng)絡(luò)中原有的連邊，同時(shí)也更加符合電子商務(wù)網(wǎng)絡(luò)的真實(shí)結(jié)構(gòu)，有助于從微觀層面了解電子商務(wù)網(wǎng)絡(luò)的演化機(jī)制。

參考文獻(xiàn)：

［1］Lyu Linyuan， Zhou Tao. Link prediction in complex networks： a survey［J］. Physica A： Statistical Mechanics and Its Applications， 2011，390（6）： 1150-1170.

［2］Zhang Yinuo， Shen Subin， Wu Zhenyu. Improve link prediction accuracy with node attribute similarities［J］. IEEE Trans on Know-ledge and Data Engineering， 2020，32（11）： 2159-2172.

［3］Liben N， Kleinberg J. The link-prediction problem for social networks［J］. Journal of the American Society for Information Science and Technology， 2007，58（7）： 1019-1031.

［4］Shahriary S R， Shahriari M， MD Noor R. A community-based approach for link prediction in signed social networks［J］. Scientific Programming， 2015， 2015： article ID 602690.

［5］李艷麗， 周濤. 鏈路預(yù)測中的局部相似性指標(biāo)［J］. 電子科技大學(xué)學(xué)報(bào)， 2021，50（3）： 422-427 （Li Yanli， Zhou Tao. Local similarity indices in link prediction［J］. Journal of University of Electronic Science and Technology of China， 2021，50（3）： 422-427.）

［6］Lin Dekang. An information-theoretic definition of similarity［C］//Proc of the 15th International Conference on Machine Learning. ［S.l.］： Morgan Kaufmann Publishers Inc.， 1998： 296-304.

［7］Biswas A， Biswas B. Community-based link prediction［J］. Multimedia Tools and Applications， 2017，76： 18619-18639.

［8］Sun Duo， Zhou Tao， Liu Jianguo， et al. Information filtering based on transferring similarity［J］. Physical Review E， 2009，80（1）： 17101.

［9］Muscoloni A， Abdelhamid I， Cannistraci C V. Local-community network automata modelling based on length-three-paths for prediction of complex network structure sin protein interactomes， food webs and more［EB/OL］. （2018-06-14）. https：//doi.org/10.1101/346916.

［10］Zhou Tao， Lyu Linyuan， Zhang Yicheng. Predicting missing links via local information［J］. The European Physical Journal B， 2009，71（4）： 623-630.

［11］Neville J， Jensen D. Relational dependency networks［J］. Journal of Machine Learning Research， 2007，8（3）： 653-692.

［12］Asil A， Gürgen F. Supervised and fuzzy rule based link prediction in weighted co-authorship networks［C］//Proc of International Confe-rence on Computer Science and Engineering. Piscataway， NJ： IEEE Press， 2017： 407-411.

［13］Gupta A K， Sardana N. Naive Bayes approach for predicting missing links in ego networks［C］//Proc of IEEE International Symposium on Nanoelectronic and Information Systems. Piscataway， NJ： IEEE Press， 2016： 161-165.

［14］Clauset A， Moore C， Newman M E J. Hierarchical structure and the prediction of missing links in networks［J］. Nature， 2008，453（7191）： 98-101.

［15］Liu Jia， Wang Tong， He Xingsheng， et al. Link prediction in dyna-mic networks based on reward mode［J］. Journal of Network and Computer Applications， 2017， 86： 28-36.

［16］Pan Liming， Zhou Tao， Lyu Linyuan， et al. Predicting missing links and identifying spurious links via likelihood analysis［J］. Scientific Reports， 2016， 6（1）： 1-10.

［17］劉厚忠， 張勝， 鐘玲玲， 等. 基于邊界節(jié)點(diǎn)的局部擴(kuò)展社區(qū)發(fā)現(xiàn)算法［J］. 南昌航空大學(xué)學(xué)報(bào)： 自然科學(xué)版， 2022，36（2）： 44-50，57. （Liu Houzhong， Zhang Sheng， Zhong Lingling， et al. Local extended community discovery algorithm based on boundary nodes［J］. Journal of Nanchang Hangkong University： Natural Science Edition， 2022，36（2）： 44-50， 57.）

［18］呂琳媛， 周濤. 鏈路預(yù)測［M］. 北京： 高等教育出版社， 2013： 85-88. （Lyu Linyuan， Zhou Tao. Link prediction［M］. Beijing： Higher Education Press， 2013： 85-88.）

［19］Li Yang， Chen Hechang， Yang Bo. Reparameterized stochastic block model adaptive to heterogeneous degree and block distributions［J］. IEEE Access， 2018，6： 37615-37626.

［20］Newman M E. The probability of link formation in network dynamics［J］. Physical Review E， 2001， 64（2）： 025102.

［21］Qiao Maoying， Yu Jun， Bian Wei， et al. Adapting stochastic block models to power-law degree distributions［J］. IEEE Trans on Cybernetics， 2019，49（2）： 626-637.

［22］Chen Kehui， Lei Jing. Network cross-validation for determining the number of communities in network data［J］. Journal of the American Statistical Association， 2018，113（521）： 241-251.

［23］Clauset A， Newman M E J， Moore C. Finding community structure in very large networks［J］. Physical Review E， 2004，70（6）： 066111.

［24］Monroy D L， Naumis G G. Description of mesoscale pattern formation in shallow convective cloud fields by using time-dependent Ginzburg-Landau and Swift-Hohenberg stochastic equations［J］. Physical Review E， 2021，103（3）： 032312.

［25］Ko?a C， Dogerlioglu D K. The 1 in 1，000，000： context effects of how numbers cue different kinds of incidental environmental anchoring in marketing communications［J］. Journal of Business Research， 2020，109： 536-544.

［26］Newman M E， Leicht E A. Mixture models and exploratory analysis in networks［J］. Proceedings of the National Academy of Scie-nces， 2007，104（23）： 9564-9569.