基于元路徑的異構(gòu)信息網(wǎng)絡(luò)的影響力建模

朱繼陽

(國家電網(wǎng)內(nèi)蒙古東部電力有限公司信息通信分公司，內(nèi)蒙古，呼和浩特 010010)

0 引言

隨著在線社交網(wǎng)絡(luò)的出現(xiàn)和快速發(fā)展，極大地促進(jìn)了信息、經(jīng)驗(yàn)和思想在社會網(wǎng)絡(luò)中的傳播，使越來越多的人在他人的影響下改變自己的決策和行為[1-2]。定性和定量地衡量個人對他人的影響，有助于識別有影響的個人，了解人們的社會行為，促進(jìn)政治、經(jīng)濟(jì)和文化活動的傳播，為社會平臺的設(shè)計(jì)和應(yīng)用提供重要的見解。社會影響力的強(qiáng)弱取決于個體之間的關(guān)系、網(wǎng)絡(luò)距離、時間、網(wǎng)絡(luò)和個體的特征等。為了衡量社會影響力，提出了話題不經(jīng)意、基于話題和基于對的影響力評價(jià)模型。大多數(shù)影響評估模型都集中在包含相同類型節(jié)點(diǎn)或邊的同質(zhì)信息網(wǎng)絡(luò)上。然而，在現(xiàn)實(shí)世界中，網(wǎng)絡(luò)通常包含多種類型的節(jié)點(diǎn)或邊，稱為異構(gòu)信息網(wǎng)絡(luò)(HIN)[3-5]。由于HIN比同類信息網(wǎng)絡(luò)能夠建立更為復(fù)雜的關(guān)系、結(jié)構(gòu)和豐富的語義信息，因此對異類信息網(wǎng)絡(luò)的影響評價(jià)可能比同類信息網(wǎng)絡(luò)的影響評價(jià)更為全面和有效。然而，節(jié)點(diǎn)和邊緣的異質(zhì)性給影響評估帶來了新的挑戰(zhàn)，傳統(tǒng)的同質(zhì)網(wǎng)絡(luò)影響評估模型不能直接應(yīng)用于HIN[6-9]。因此，本文提出了一個基于元路徑的信息熵模型來模擬異質(zhì)信息網(wǎng)絡(luò)中的社會影響。該模型首先通過相應(yīng)的元路徑從HIN中提取出多個同質(zhì)網(wǎng)絡(luò)，然后度量這些同質(zhì)網(wǎng)絡(luò)中的直接影響和間接影響，通過整合鏈接熵來評估朋友數(shù)量對社會影響的影響，而互動頻率熵則從互動次數(shù)來評價(jià)對社會影響力的影響。最后，將同質(zhì)網(wǎng)絡(luò)學(xué)習(xí)到的直接影響和間接影響融合在一起。

1 提出的方法

本文提出了一個基于元路徑的信息熵模型來模擬HIN中的社會影響，稱為MPIE。它由三個部分組成，將一個原始的HIN轉(zhuǎn)換成幾個同質(zhì)網(wǎng)絡(luò);用信息熵來描述社會影響的復(fù)雜性和不確定性;融合元路徑下節(jié)點(diǎn)的影響[10-11]。

1.1 基于元路徑的同構(gòu)網(wǎng)絡(luò)

社會影響是兩個實(shí)體為某一特定行為而建立的關(guān)系。特別地，一個實(shí)體通過執(zhí)行動作來影響其他實(shí)體。在HIN中，有多條對稱的元路徑連接同一類型的節(jié)點(diǎn)，如DBLP中的“作者—論文—作者”和“作者—論文—會議論文—作者”?；谶@些路徑，作者具有不同的影響力。這里利用一組元路徑P={P0,P1,…,Pl,…,P|p|}來提取語義信息，并將HIN G轉(zhuǎn)換成若干個同構(gòu)網(wǎng)絡(luò)GP={Gp0,Gp1,…,Gpl,…,Gp|P|}。每個同構(gòu)網(wǎng)絡(luò)Gpl包含一種語義信息，即每個節(jié)點(diǎn)都通過元路徑Pll與其鄰居相連。

定義1 交互矩陣。給定一個基于元路徑Pl=(k1k2…kl)的齊次網(wǎng)絡(luò)Pi，齊次網(wǎng)絡(luò)Gpi的交互矩陣Mpi描述如下：

MPl=Wk1k2Wk2k3…Wkl-1kl

(1)

其中，Wkikj是ki類型和kj類型之間的鄰接矩陣，如果對象i∈ki連接到對象j∈kj，則Wkikj(i,j)=1。例如，在DBLP中，如果作者a1∈A發(fā)表了一篇論文p1∈P，WAp(a1,p1)，其中A是作者集，P是論文集。

在同構(gòu)網(wǎng)絡(luò)GPl中，如果對象ki和對象kj通過元路徑Pl連接m次，則MPi(ki,kj)=m，其中，m表示元路徑p下對象ki∈Ki和對象kj∈Kj之間的路徑實(shí)例Pl的個數(shù)。

1.2 基于信息熵的社會影響測度

對于同質(zhì)信息網(wǎng)絡(luò)中節(jié)點(diǎn)的影響，可以發(fā)現(xiàn)其背后的直覺是，一個對象的影響不僅應(yīng)該是直接的強(qiáng)關(guān)聯(lián)，而且應(yīng)該是間接的強(qiáng)關(guān)聯(lián)。正式給出了社會影響的定義。

全球影響力與直接/間接影響力有著密切的關(guān)系。例如，如果一個用戶對其他用戶有很強(qiáng)的影響力，那么他很可能在全球范圍內(nèi)有影響力。在這項(xiàng)工作中，只考慮同一類型節(jié)點(diǎn)之間的影響，例如用戶之間的影響。不同類型節(jié)點(diǎn)之間的影響，如作者對論文的影響或論文對作者的影響，由于難以進(jìn)行有意義的解釋和定量的度量，的工作中沒有包括這些節(jié)點(diǎn)之間的影響。

(1) 直接影響計(jì)算

在社會網(wǎng)絡(luò)中，如果兩個節(jié)點(diǎn)通過邊連接，則節(jié)點(diǎn)u對節(jié)點(diǎn)v有影響，稱為鏈接熵。如果節(jié)點(diǎn)u和節(jié)點(diǎn)v多次交互，則節(jié)點(diǎn)u對節(jié)點(diǎn)v的影響較大，稱為交互熵，例如在DBLP網(wǎng)絡(luò)中，作者A和作者B之間的合作越多，A對B的影響就越大，因此，節(jié)點(diǎn)的直接影響由兩部分組成：鏈路熵和交互熵。

(2)

(3)

(4)

(2) 間接影響計(jì)算

圖1 只有一個公共節(jié)點(diǎn)

圖2 三個公共節(jié)點(diǎn)

(5)

(6)

根據(jù)以上分析，均勻網(wǎng)絡(luò)GPl中的間接影響描述如下：

(7)

(3) 計(jì)算節(jié)點(diǎn)總影響

(8)

1.3 融合影響

在不同的元路徑下，節(jié)點(diǎn)的影響是不同的。為了計(jì)算更全面的影響，給每個元路徑分配1個統(tǒng)一的權(quán)重，這意味著影響在路徑上的擴(kuò)散偏好。該權(quán)重向量表示為ω∈R1×|P|，并且ωl表示元路徑Pl上的權(quán)重。HIN中節(jié)點(diǎn)i的最終影響表示為Ii，可以是每個元路徑下影響的加權(quán)和。

(9)

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

通過2個應(yīng)用程序來評估MPIE：影響的傳播范圍和影響的排名。

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

采用了2種廣泛使用的不同領(lǐng)域的數(shù)據(jù)集，包括來自學(xué)術(shù)領(lǐng)域的DBLP數(shù)據(jù)集[12]和來自商業(yè)領(lǐng)域的Yelp數(shù)據(jù)集[13]。包括20個地點(diǎn)和前5 000名作者，其中13 245個術(shù)語來自4個領(lǐng)域：數(shù)據(jù)庫、數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)和信息檢索。Yelp數(shù)據(jù)集記錄了用戶對本地業(yè)務(wù)的評分，包括16 239個用戶和14 282個本地業(yè)務(wù)，其中198 397個評分從1到5。

2.2 baseline方法

為了證明所提出的MPIE的有效性，將MPIE與齊次方法和MPIE的一個變種進(jìn)行了比較。一般來說，大多數(shù)影響測量方法只能用于同質(zhì)網(wǎng)絡(luò)。為了使這些方法在同構(gòu)網(wǎng)絡(luò)中適用于HIN，在實(shí)驗(yàn)中忽略了對象和關(guān)系之間的語義差異，將它們視為同一類型?？紤]采用以下方法進(jìn)行比較：度中心度(DC)、PageRank、基于熵、MPIE direct、MPIE。

在這些方法中，基于HIN的方法需要使用不同的元路徑。根據(jù)小世界現(xiàn)象，可以推斷，當(dāng)元路徑長度大于5時，這種關(guān)系非常弱。而且長的元路徑可能會引入噪聲語義[13]，所以只選擇最多4步的短元路徑。同時，由于節(jié)點(diǎn)間的邊限制，選擇了節(jié)點(diǎn)間關(guān)系密切的元路徑。在表1中給出了使用的元路徑。另外，為了得到每種算法的影響擴(kuò)散，選取top-k個影響節(jié)點(diǎn)作為種子，其中k分別選取5,10,20,30,40,50。

表1 兩個數(shù)據(jù)集選擇元路徑

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

(1) 影響范圍

在社交網(wǎng)絡(luò)中，有影響力的用戶可以在短時間內(nèi)將信息傳播給大量用戶。為了評估影響的擴(kuò)散范圍，借用線性閾值(LT)來模擬影響在HIN中的擴(kuò)散，在相同的種子數(shù)下，激活節(jié)點(diǎn)數(shù)越多，影響度量就越有效。圖3顯示了具有不同k個影響節(jié)點(diǎn)的不同算法的影響擴(kuò)散范圍，其中MPIE融合了表1中的3條元路徑，統(tǒng)一權(quán)重為0.33?？梢杂^察到，由于數(shù)據(jù)分布的不同，不同的算法在不同的數(shù)據(jù)集上表現(xiàn)出不同的性能，并且隨著k值的增加，影響擴(kuò)散的數(shù)量也隨之增加。這歸因于這樣一個事實(shí)，即節(jié)點(diǎn)種子集越大，受影響的節(jié)點(diǎn)就越多。

首先，在這些基線中，所提出的MPIE方法比基線(DC、PageRank和Entropy-base)具有更好的性能，這表明異質(zhì)信息可以改善擴(kuò)散范圍?？傮w而言，基于DC、PageRank和熵的算法的性能并不穩(wěn)定，更多地依賴于數(shù)據(jù)集中特定數(shù)據(jù)的特征和分布。例如，Yelp中的節(jié)點(diǎn)分布比4區(qū)域更均勻，因此在Yelp中DC的性能更好。當(dāng)使用元路徑來表示HIN時，忽略節(jié)點(diǎn)和鏈接類型的基于熵的方法的性能比MPIE差，MPIE可能包含有用的證據(jù)來驗(yàn)證在HIN中考慮節(jié)點(diǎn)類型的重要性。

(a) 4-area

接下來，考慮到MPIE變體MPIE direct，很容易看出MPIE direct的性能比MPIE差。主要區(qū)別在于影響成分。MPIE direct只考慮直接影響，忽略了間接影響。因此，在HIN中考慮間接影響是有意義的，這使得影響測量更有效，傳播更廣泛。

(2) 節(jié)點(diǎn)的秩

在大多數(shù)情況下，人們更多地關(guān)注一些有影響力的節(jié)點(diǎn)，通過融合表1中的3條元路徑，基于MPIE評估節(jié)點(diǎn)的重要性。

表2顯示了這5種方法估計(jì)的總影響排名前十位的作者，忽略了對象的異質(zhì)性，直接在整個4區(qū)域網(wǎng)絡(luò)上運(yùn)行基線方法，因?yàn)樗鼈兊慕Y(jié)果混合了所有類型的對象，所以從排名列表中選擇作者類型作為最終結(jié)果。根據(jù)5種方法返回的結(jié)果，可以得到四區(qū)數(shù)據(jù)集中的5個候選作者排名表。這些方法對作者的排名結(jié)果都是合理的，如MPIE排名前三位的作者是Philip S.Yu、Christos Falutos和JiaWei Han，他們都是計(jì)算機(jī)科學(xué)領(lǐng)域非常有影響力的研究者。為了定量地評價(jià)排名結(jié)果，使用了作者從aminer1的排名作為基本事實(shí)。然后使用Kendall’s tau(值介于-1和1之間，越高越好)來比較候選排名列表和標(biāo)準(zhǔn)排名列表之間的差異。表3顯示了作者排名表的差異。可以看到，基于熵的方法是最糟糕的，因?yàn)楹唵蔚貙⒉煌愋偷墓?jié)點(diǎn)視為相同類型的節(jié)點(diǎn)會丟失潛在的鏈接信息(例如，2個作者通過論文或地點(diǎn)連接的次數(shù))。MPIE在人類直覺方面給出了最好的排名。

表2 四區(qū)域數(shù)據(jù)集上不同方法

表3 Kendall’s tau測量的四區(qū)域數(shù)據(jù)集上5種測量方法

3 總結(jié)

本文研究了異構(gòu)信息網(wǎng)絡(luò)中的影響度量問題，旨在研究如何利用豐富的語義信息來度量節(jié)點(diǎn)的影響。提出了一種基于元路徑的信息熵模型MPIE，通過元路徑獲取HIN中豐富的語義信息，并用信息熵來度量。然后，簡單地融合相應(yīng)的元路徑。此外，在不同類型的異構(gòu)網(wǎng)絡(luò)上做了大量的實(shí)驗(yàn)，展示了一些有趣的案例，并證明了的方法和節(jié)點(diǎn)等級的影響擴(kuò)散優(yōu)于基線。但是在本文中，只是通過統(tǒng)一的權(quán)值來融合元路徑，因此在將來，準(zhǔn)備自動學(xué)習(xí)不同元路徑的權(quán)值，這有助于在實(shí)際系統(tǒng)中提供準(zhǔn)確的影響度量，并發(fā)現(xiàn)對象之間有趣的關(guān)系。