基于加權PageRank的異質網絡影響力最大化

韓 婷，周麗華*，黃亞群，姜懿庭

(1.云南大學 信息學院，云南 昆明 650504；

2.云南師范大學 信息學院，云南 昆明 650500)

0 引 言

隨著各種各樣社交網絡的出現，人與人之間的聯系越來越緊密，人們的學習、工作和生活正在不斷地被改變。社交網絡中信息的傳播和影響力無處不在，通過社交網絡，具有高影響力的名人可以影響他人的看法和行為。準確度量不同對象之間的影響力，有助于識別社交網絡中最具影響力的對象并促進信息的快速傳播，對謠言傳播、流行病傳播、產品營銷以及推薦系統等工作起著至關重要的作用[1-3]，因此影響力最大化研究受到了研究人員的極大關注。

影響力最大化問題被認為是對病毒營銷的一個直接數學刻畫。其目的就是希望利用病毒式營銷手段，在社交網絡找到少數重要的節點作為種子集，利用這些種子集進行信息的傳播從而達到在社交網絡中影響力的最大化[4]。目前，傳統的影響力最大化方法有基于中心度、PageRank、特征向量和啟發式算法等，其中PageRank[5]是一種重要的算法，該算法最初是Google公司為了衡量網頁等級和重要性而提出的，它從網頁數量和質量綜合考慮了頁面的重要性，能較好地刻畫頁面的性質，并描述對象之間的關系。這些傳統的算法在同質信息網絡中取得了較好的結果，但是同質信息網絡中的節點和鏈接關系類型單一，沒有區分對象及其關系的異質性[6]，這與實際的現實網絡不符。現實中的網絡大多是異質信息網絡，包含了多種類型的對象及多種關聯類型的鏈接關系[7-8]，網絡中的一個實體對象的影響力不僅受到同種類型對象的影響，還與其他類型對象有關。由此關于影響力最大化問題的研究正逐步從同質信息網絡轉向異質信息網絡。

異質信息網絡包含了多種類型的對象及鏈接關系，相對于同質信息網絡，節點和鏈接類型、語義關系更為豐富[8]，這些豐富的信息可以更全面地評價節點的影響力。如圖1所示的文獻信息網絡DBLP就是典型的異質信息網絡，它包含了四種類型的節點：A(作者)、P(文章)、C(會議)和T(主題)，六種關系：A-P(編寫/被編寫),P-C(發表/被發表),P-T(包含/被包含)。評價一個作者的影響力不僅要從作者發表的文章數量和質量來衡量，還要從他撰寫的文章的內容主題、所屬會議以及與他合作的作者等方面考慮，通過融合這些豐富的信息能更好地刻畫現實網絡中不同節點對象之間的影響力情況。

圖1 DBLP網絡

由于異質信息網絡包含了多種類型的對象及鏈接關系，并且網絡結構復雜，各節點之間不是相互獨立的，他們通過各種關系相互影響。如何有效地利用不同類型對象間的關系成為異質信息網絡分析的一個難點。Zhao等人[9]對異質信息網絡中兩種不同類型的節點使用PageRank，保留了節點間的連接關系，更好地考慮到不同類型節點彼此間的影響。但是他們只考慮了直接相連的兩種類型節點，忽略了異質網絡中同種類型節點和其他非直接相連的不同類型節點的影響，同時他們還將所有節點之間的初始連接關系的權重視為相同。然而，現實中并非所有節點間的連接關系都是同等重要的，為了能進一步區分連接關系的重要性并考慮到所有類型節點間的影響，該文針對異質信息網絡提出了一種基于加權PageRank的影響力最大化算法(Comprehensive Weighted PageRank，CWPR)。CWPR根據不同節點之間的連接關系賦予對應的權重，這樣可以更全面地考慮節點的重要性。

主要工作如下：

(1)將異質信息網絡分解為若干個只含一種連接類型的網絡，再根據各節點之間連接關系的次數分配對應的權重。網絡的分解簡化了復雜的網絡結構，權重的分配區分了節點間連接關系的重要性，有助于準確度量不同節點之間的影響力。

(2)提出了一種基于加權PageRank的影響力最大化算法CWPR，其中影響力的度量考慮了不同類型節點的直接影響和間接影響，從而更好地描述了節點影響力的復雜性和異質性，全面保留了異質信息網絡中的信息，使找到的種子節點具有較高的影響力。

(3)在DBLP和Yelp兩個數據集上進行了實驗，通過與其他同質和異質影響力最大化算法的對比，驗證了CWPR的合理性和準確性。同時討論了參數和邊權重對于算法性能的影響。

1 相關工作

Kempe等人[10]首次將影響力最大化問題表示成離散的優化問題，證明了該問題是一個NP-hard問題，并基于單調次模性提出了有效的貪心算法。該算法能得到最優解，但是不能改進算法的時間復雜度。后來Leskovec等人[11]提出了CELF算法，CELF算法在實驗中的效率得到了很大的提升。隨著對影響力最大化問題研究的進一步深入，相關工作也越來越多，Goyal等人[12]又進一步改進了CELF算法，提出CELF++算法。當問題規模較大時，CELF++算法并不適用，于是Chen等人[13-15]又提出了DegreeDiscount、PMIA、LDAG等算法，大大提高了運算速度。周明洋等人[16]從多節點的綜合影響力角度出發,基于Rayleigh熵機制,提出了一種指標刻畫多節點的綜合影響力算法。曹玖新等人[17]基于用戶交互的主題偏好計算不同類別信息下節點間的影響概率,并結合擴展的傳播模型和信息擴散的特點,提出基于節點子圖的影響力計算算法。楊書新等人[18]基于三度影響力原則,綜合考慮局部度量的適宜層次及大規模網絡的可擴展性,提出一種基于3級鄰居的節點影響力度量算法。Oriedi等人[19]提出選擇性廣度優先遍歷算法，對來自社交網絡成員之間實際社交行為進行影響力建模，有效地生成影響最大化的最佳種子集。目前從運算效率、網絡結構等方面對影響力最大化問題的研究工作越來越多，影響力最大化問題也正逐步從同質信息網絡轉向異質信息網絡。

在異質信息網絡中，Deng等人[20]設計了一個基于互動記錄、社交友誼、標簽和話題的MIF模型來衡量用戶之間的社交影響力，還有基于同元路徑考慮信息熵[21-22]來定位有影響力的節點等。Keikhar和Rahgoza等人[23]利用深度學習技術獲得異質信息網絡節點的特征，根據節點的本地和全局結構特性得到最具影響力的節點。然而，由于異質信息網絡相對于同質信息網絡的網絡結構、性質更為復雜，目前對于異質信息網絡影響力最大化的研究還未足夠成熟，因此在異質信息網絡中對于影響力最大化的研究還存在很大的進步空間。

2 相關概念及問題定義

該文的主要目的是利用加權PageRank綜合考慮各種類型節點之間的影響關系，從而挖掘出異質信息網絡中影響力最大的節點。本節主要介紹所涉及到的一些相關概念及問題定義。

2.1 相關概念

定義1 異質信息網絡[7,24]：信息網絡由一個帶有對象類型的映射函數τ:V→A和關系類型映射函數φ:E→R的有向圖G=(V,E,τ,φ)組成，其中V={v1,v2,…,vn}是對象集合，它屬于對象類型集合A的某一個特定對象類型集合，E={e1,e2,…,en}是對象之間的鏈接集合，屬于關系類型集合R的某一個特定關系類型集合，當信息網絡中的對象類型數|A|或者關系類型數|R|大于1時，稱這個信息網絡為異質信息網絡。

定義2 網絡模式[7,24]：網絡模式是定義在對象類型A上的有向圖，它的邊為R中的關系，記為TG=(A,R)，表示信息網絡的元模式。

定義4 加權PageRank[25]：根據信息網絡中對象的連接結構及連接頻次對每個對象的質量進行排名，進而利用鏈接和對象質量排名來衡量整個網絡對象的重要性。其重要性的表示如下。

(1)

2.2 問題定義

S*=argmaxS0σ(S0)

(2)

3 CWPR算法

該文提出了一種基于加權PageRank的影響力最大化算法(CWPR)，用于解決異質信息網絡中的影響力最大化問題。該算法包含兩個步驟。第一，首先將原始異質信息網絡分解成若干個只含一種連接類型的網絡，并根據節點間的連接關系分配對應的邊權重。第二，利用加權PageRank來衡量節點的直接和間接影響力，最終融合所有影響力得到節點的最終影響力，并篩選出影響力最大的前k個節點。

3.1 邊權重的分配

由于異質信息網絡結構復雜，每個節點都能通過不同的元路徑與其他類型節點相連得到不同類型的連接邊并產生不同的影響關系，其中每條連接邊的權重都不盡相同，這與連接邊的兩個節點間的交互程度密切關聯，若兩節點間交互次數過多，則對應的邊權重也大。為了能減少不同類型邊的差異性，簡化整個復雜的異質信息網絡，同時保留網絡的異質性和不同類型節點之間的影響關系，并為影響關系分配相應的權重，該文將包含多種連接關系的異質信息網絡分解成若干個只含一種連接類型的網絡。如圖1中的DBLP網絡，APTC四種類型節點，直接相連關系A-P/P-A,P-T/T-P,P-C/C-P，故可以分解成只含有AP,PT,PC類型的三個異質信息網絡，使每條邊的權重分別為對應的連接次數，如圖2所示。

(a) (b) (c)

一個節點的影響力除了與它直接相連的鄰居有關，還與它鄰居的鄰居有關，因此可以基于單中介元路徑獲得節點的間接相連關系，若一個節點到達另一個間接相連的節點的路徑數越多，則說明它們之間的聯系越緊密，因此根據路徑數為節點的間接相連關系分配對應的權重。對圖1中的DBLP網絡而言，A能通過P與A、C、T間接相連，則對應的間接相連關系有A-A,A-C/C-A,A-T/T-A,將圖1中的間接相連關系提取出來，例如A1和C2只能通過元路徑A1P2C2相連，路徑數為1，而A4和C2可以通過元路徑A4P2C2,A4P3C2相連，路徑數為2，則A1和C2的邊權重為1，A4和C2的邊權重為2，如圖3所示。

(a) (b) (c)

3.2 影響力度量

加權PageRank延續了PageRank的優點，能夠通過節點間的連接數量和質量來綜合描述節點的重要性，同時又根據節點之間的交互程度分配對應的權重。該文利用加權PageRank來度量節點對不同類型節點的影響力，其綜合影響力主要由直接影響力和間接影響力組成。

3.2.1 直接影響力

為給定的若干個直接相連兩種不同類型節點，只包含一種類型邊的異質信息網絡G構建一個加權有向圖，i,j是兩種不同類型A,B的節點，若j指向i，則j到i有邊，邊的權重等于j到i邊的個數k，即wj,i=k，否則wi,j=0，使用加權PageRank計算得到j對i貢獻的PR值，即i對j的重要性為：

(3)

(4)

其中,N(i)為與i直接相連的不同類型節點的集合，故得i對所有與它相連的B類型節點的直接影響力為：

(5)

3.2.2 間接影響力

IIi1,t1=Pi1,t1PRt1

(6)

那么i1對所有與它相連的類型C的節點的間接影響力為：

(7)

其中，ii(i)為與i1間接相連的節點類型的集合。

圖4 間接相連關系圖

3.2.3 綜合影響力

異質信息網絡中，節點類型豐富，它們之間的影響力是通過直接或間接關系相連去傳播的。該文將融合節點的直接影響力和間接影響力，作為節點的最終綜合影響力Ii，Ii的表示如下：

(8)

3.2.4 篩選種子節點

通過融合節點的直接影響力和間接影響力得到節點的最終影響力，因此可以對所有節點的最終影響力進行排序。為了避免種子節點影響力重合，該文采用邊際增益策略篩選種子節點。先選擇一個影響力最大的節點作為種子節點，然后去除其余節點與其影響重疊的部分，再選擇剩余節點中影響力最大作為種子節點，不斷重復此過程，直到篩選出給定數量的節點作為種子集為止。

CWPR是基于加權PageRank迭代計算獲得節點的影響力，因此使用鄰接矩陣對節點間的關系進行表示存儲，需要的空間復雜度為O(n2)，其中n為節點數，而PR值的計算是一個迭代過程，向量與矩陣相乘所需要的時間復雜度為O(n2)，經過若干次迭代達到收斂所需的時間復雜度為O(cn2)，其中c為迭代次數。

4 實驗評估

4.1 實驗準備

數據集：使用了兩個最常見的文獻網絡數據集DBLP和Yelp，數據集的情況分別如表1和表2所示。

表1 DBLP數據集詳細信息

表2 Yelp數據集詳細信息

對比算法：為了驗證CWPR方法的有效性，該文將與已有的同質信息網絡影響力度量方法Degree(DC)、PageRank(PR)以及異質的方法APR和CWPR的變種方法CWPR-II進行實驗對比。由于目前對于網絡中關鍵節點的度量方法大多都是針對同質信息網絡的，而本實驗是利用異質信息網絡的關鍵節點進行影響力最大化研究，為了進行對比實驗，故將常用的同質信息網絡關鍵節點的度量方法直接運用于異質信息網絡，在使用這些方法時，忽略不同類型節點之間關系的差異，根據度量方法計算得到每個節點對應的度量值。在選取種子集時，由于不同類型節點在信息擴散中扮演的角色不同，為了減少實驗的差異性，種子集類型固定，本實驗以人作為目標類型，選取度量值最大的目標類型節點作為種子集。對比算法描述如下。

Degree centrality(DC)：一個節點v與它直接相連的鄰居節點的個數，稱為度，一個節點度越大，就意味著這個節點越重要。

PageRank(PR)：網頁重要性度量方法，如果一個網頁被很多網頁鏈接，或者被知名度很高的網頁鏈接，則這個網頁的重要性就越大，也可以用于社交網絡節點分析。

APR：一種在異質的文獻網絡中的節點重要性度量方法，利用PageRank度量的異質信息網絡中作者和文章兩種類型節點之間的影響力，對于DBLP、Yelp則分別考慮了作者和文章，用戶和商業之間的影響力。

CWPR-II：該文提出的CWPR的變體，在異質網絡中只考慮人與人之間的影響力。

CWPR：該文提出的異質信息網絡影響力的度量算法，基于異質信息網絡的連接結構，考慮了不同類型節點之間的影響力。

擴散模型：采用線性閾值模型LT作為傳播模型，將每一節點的入度邊的度數歸一化，作為每個節點被自己入鄰居節點激活的概率，使它們和為1，每個非激活節點都有一個[0,1]的激活閾值，當非激活節點的已激活鄰居節點對其影響總和超過該閾值，則此節點被激活。該文的擴散指標分別為在k個有影響力的作者和用戶作為種子集時被影響的作者和用戶的個數，影響的人越多說明實驗效果越好。為了減小實驗的偶然性，進行了10 000次蒙特卡洛仿真來估計影響擴散結果

4.2 實驗結果

4.2.1 算法參數的影響

圖5 算法參數的影響

對以上實驗結果分析可知，在數據集DBLP中，當λAP=0.4,ηAA=0.2,ηAC=0.2,ηAT=0.2時，影響范圍的值達到最大，這表明在信息擴散過程中作者對論文的影響力是作者的綜合影響力的重要組成部分。而對于數據集Yelp，當λUB=0.3,ηUU=0.3,ηBC=0.3,ηBCat=0.1時，影響范圍的值達到最大，此時在信息擴散過程中，用戶和領域的之間的影響力在用戶的綜合影響力所占的比重最小。用戶和用戶、商業、城市之間的影響力則是用戶綜合影響力的重要組成部分。

4.2.2 邊權重參數的影響

在異質信息網絡中，包含了多種類型的邊，每種類型的邊在信息擴散中同不同類型的節點一樣也是扮演著不同的角色。同不同類型節點一樣，該文也假設異質信息網絡中不同類型邊的權重等于1，則數據集DBLP中有WAP+WPC+WPT=1,數據集Yelp中有WUB+WBC+WBCat=1。通過設置多種不同的權重并選出k=50個種子所得到的影響范圍大小進行結果對比，從而獲得一組合理的邊權值。實驗結果如圖6所示。

圖6 邊權重的影響

由實驗結果可知，在數據集DBLP中，當WAP=0.5,WPC=0.4,WPT=0.1時，影響范圍的值達到最大，此時作者與論文之間的邊權值是三個中間最大的，這說明在信息擴散過程中作者與論文之間的關系起著重要作用，同時發現對于每一組權重，若是論文與主題之間的邊權重是三者中最大的一個，則影響范圍的值將會下降，則可以認為在信息擴散中，論文與主題之間的關系影響作用較小。在數據集Yelp中，當WUB=0.5,WBC=0.25,WBCat=0.25，影響范圍的值達到最大，此時用戶和商業之間的關系在信息擴散過程中起著重要的作用。通過對這兩個數據集的邊權重分析發現，均是人和與人直接相連的類型節點的邊權重在所有邊權重所占的比重是最大的，這也表明了直接的影響會比間接影響更有力。

通過對算法參數和邊權重設置不同值，分別選取了各自最好的結果，作為該算法有效性驗證的參數。

4.2.3 有效性驗證

對于數據集DBLP和Yelp，本實驗的種子集的類型分別設為作者和用戶，由于本實驗基于不同元路徑考慮了不同類型的節點直接的影響，在數據集DBLP中，對不同類型的邊權重設為WAP=0.5,WPC=0.4,WPT=0.1。在數據集Yelp中，設各類型的邊權重為WUB=0.5,WBC=0.25,WBCat=0.25，實驗對比方法中的同質方法DC和PageRank不區分邊的類型，權重都為0.5。實驗效果如圖7所示。

圖7 影響范圍

由這些實驗對比結果可知，保留各種類型節點信息的三種異質方法要明顯優于其他兩種同質方法，在DBLP中該文所提出的CWPR方法明顯優于其他兩種異質方法CWPR-II、APR，而在Yelp中CWPR也同樣優于其他兩種異質方法，但是差距并不如DBLP明顯。該文給出的三種異質方法都區分了不同類型的邊的權重，但CWPR考慮了不同類型節點之間的影響，而APR,CWPR-II只考慮了部分的類型節點的影響。通過以上實驗結果可以表明，在異質信息網絡中，保留節點與其他類型節點之間的語義信息比只保留部分信息能更全面地評價節點的特征，得到更好的實驗效果，從而可以借助這種方法得到最有影響力的節點。

5 結束語

該文提出了一種基于加權PageRank的異質信息網絡影響力最大化算法CWPR，該算法將包含多種類型節點的異質信息網絡分解成若干個只含一種連接類型的網絡，然后通過節點之間的連接方式考慮了所有不同類型節點之間的影響關系，去獲得影響力最大的節點作為信息擴散的種子節點，從而實現異質信息網絡影響力的最大化。通過在兩個真實數據集的實驗結果表明，在異質信息網絡中，保留節點與其他節點之間的信息越多，篩選出的種子節點得到的影響效果越好。但是該算法的不足在于對異質信息網絡中不同類型的邊權重的設置是基于先驗知識設定的，在未來的研究中，可以通過機器學習去自主獲得不同類型的邊權重，使得邊權重結果更加真實可靠。