朱繼陽(yáng)

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

0 引言

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

1 提出的方法

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

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

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

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

MPl=Wk1k2Wk2k3…Wkl-1kl

(1)

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

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

1.2 基于信息熵的社會(huì)影響測(cè)度

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

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

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

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

(2)

(3)

(4)

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

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

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

(5)

(6)

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

(7)

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

(8)

1.3 融合影響

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

(9)

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

通過(guò)2個(gè)應(yīng)用程序來(lái)評(píng)估MPIE：影響的傳播范圍和影響的排名。

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

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

2.2 baseline方法

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

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

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

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

(1) 影響范圍

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

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

(a) 4-area

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

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

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

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

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

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

3 總結(jié)

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