異質(zhì)網(wǎng)絡(luò)組合元路徑節(jié)點重要性分析方法

劉政君，梁 英，張 偉

1(中國科學(xué)院計算技術(shù)研究所，北京100190)

2(中國科學(xué)院大學(xué)，北京100190)

1 引 言

異質(zhì)信息網(wǎng)絡(luò)包含多種類型的對象或關(guān)系，與同質(zhì)信息網(wǎng)絡(luò)相比，異質(zhì)信息網(wǎng)絡(luò)可以包含更加豐富的語義信息.在異質(zhì)信息網(wǎng)絡(luò)中挖掘重要的節(jié)點具有很高的實用價值，可應(yīng)用于學(xué)術(shù)評審評議、優(yōu)化搜索引擎、推薦［1］、網(wǎng)絡(luò)可視化和鏈路預(yù)測等.

在異質(zhì)信息網(wǎng)絡(luò)中，對象間的關(guān)系主要包括內(nèi)部關(guān)系和相關(guān)關(guān)系.其中，內(nèi)部關(guān)系指的是相同類型的對象之間的關(guān)系;相關(guān)關(guān)系指的是不同類型的對象之間的關(guān)系.元路徑是定義在異質(zhì)信息網(wǎng)絡(luò)中鏈接兩類對象的一條路徑，不同的元路徑表達(dá)了不同的語義信息.圖1 表示了學(xué)術(shù)網(wǎng)絡(luò)的網(wǎng)絡(luò)模式.這個實例中包含了三種類型對象:論文、學(xué)者和會議，可以看出，學(xué)者之間的合作關(guān)系和論文之間的引用關(guān)系對應(yīng)的是內(nèi)部關(guān)系，學(xué)者和論文之間的發(fā)表關(guān)系、會議與論文之間的收錄關(guān)系對應(yīng)的是相關(guān)關(guān)系.同時，圖中還包含了“學(xué)者-論文-學(xué)者”、“學(xué)者-論文-會議-論文-學(xué)者”等元路徑信息.

圖1 學(xué)術(shù)異質(zhì)信息網(wǎng)絡(luò)的網(wǎng)絡(luò)模式Fig.1 Academic heterogeneous information network schema

在信息網(wǎng)絡(luò)的研究中，關(guān)鍵節(jié)點對整個網(wǎng)絡(luò)起著至關(guān)重要的作用，因而發(fā)掘其中的重要節(jié)點具有重要的理論意義與應(yīng)用價值.目前節(jié)點重要性分析方法主要分為同質(zhì)網(wǎng)絡(luò)的節(jié)點重要性分析和異質(zhì)網(wǎng)絡(luò)的節(jié)點重要性分析.其中，同質(zhì)網(wǎng)絡(luò)的節(jié)點重要性分析主要是基于節(jié)點之間的連接權(quán)重進(jìn)行重要性分析，而與同質(zhì)信息網(wǎng)絡(luò)相比，異質(zhì)信息網(wǎng)絡(luò)具有更全面的結(jié)構(gòu)信息和更豐富的語義信息，雖然同質(zhì)網(wǎng)絡(luò)的節(jié)點重要性分析方法取得了很好的效果，但遷移到異質(zhì)網(wǎng)絡(luò)時會造成語義信息的丟失，因此無法直接應(yīng)用于異質(zhì)網(wǎng)絡(luò)上，這導(dǎo)致異質(zhì)網(wǎng)絡(luò)的節(jié)點重要性分析成為研究難點.

異質(zhì)網(wǎng)絡(luò)中的節(jié)點重要性分析主要通過元路徑尋找不同類型節(jié)點之間的關(guān)系，目前的異質(zhì)信息網(wǎng)絡(luò)中分析節(jié)點重要性的方法大多使用不同對象之間的可達(dá)性對異質(zhì)信息網(wǎng)絡(luò)進(jìn)行分析，沒有更大范圍地捕捉存在于網(wǎng)絡(luò)中的語義信息，導(dǎo)致排名缺少可信度.

針對上述問題，本文提出了一種異質(zhì)信息網(wǎng)絡(luò)中基于組合元路徑的節(jié)點重要性排名方法(Combination-Path Rank)，通過組合多個包含特定語義的元路徑，捕捉異質(zhì)信息網(wǎng)絡(luò)豐富的語義信息，使得重要性排名結(jié)果更加精準(zhǔn).該方法使用指數(shù)加權(quán)平均數(shù)法(EWA)［2］確定對象內(nèi)部關(guān)系與相關(guān)關(guān)系的組合參數(shù)尋優(yōu)步長，以最大化排名向量的信息熵為貪心目標(biāo)，尋找組合參數(shù)的局部最優(yōu)值，最終得到一個穩(wěn)定可信的重要性排名.

本文的貢獻(xiàn)包括:

1)提出了一種基于組合元路徑的重要性排名方法.組合了多種含有特定語義的元路徑，可以兼顧更豐富的信息，使重要性排名更精準(zhǔn).

2)以信息熵為標(biāo)準(zhǔn)對隨機(jī)游走的比重進(jìn)行優(yōu)化.確保組合元路徑的組合參數(shù)收斂于某個數(shù)值范圍內(nèi)，使重要性排名更可信.

2 相關(guān)工作

目前，有許多方法用于解決節(jié)點重要性分析問題，主要分為同質(zhì)信息網(wǎng)絡(luò)的重要性分析方法、二分圖的重要性分析方法和基于元路徑的重要性排名方法.

許多學(xué)者在同質(zhì)信息網(wǎng)絡(luò)節(jié)點的重要性進(jìn)行分析進(jìn)行了深入的研究.Page［3］等人提出了類似投票機(jī)制的 PageRank 算法，通過隨機(jī)游走分析同質(zhì)信息網(wǎng)絡(luò)中節(jié)點的重要性.Kleinberg［4］提出了 HITS 算法，使用 authority 和 hub 分?jǐn)?shù)來對節(jié)點進(jìn)行重要性排名.Jeh［5］提出了SimRank 算法，基于向量空間模型的相似性高效的對節(jié)點進(jìn)行重要性排名，并用于對節(jié)點的評分.這三種方法針對單一類型節(jié)點的同質(zhì)信息網(wǎng)絡(luò)進(jìn)行重要性排名，并不適用于包含多種節(jié)點和關(guān)系的異質(zhì)信息網(wǎng)絡(luò).

二分圖的節(jié)點重要性排名方法將節(jié)點分為兩類，用以構(gòu)建兩個子圖來對節(jié)點進(jìn)行重要性分析.Zhou［6］通過兩個隨機(jī)游走來對二分圖的學(xué)者和出版物進(jìn)行重要性排名，出版物和學(xué)者的重要性排名在迭代計算中相互增強(qiáng)，從而利用了異質(zhì)信息網(wǎng)絡(luò)中隱含的語義信息.Deng［7］提出了co-HITS 算法，將二分圖的內(nèi)容信息和約束結(jié)合起來進(jìn)行重要性排名，并提出了一個代價函數(shù)來考慮兩個實體集之間的直接關(guān)系.Soulier［8］提出了一種通過組合不同特征的重要性排名算法.但是二分圖的重要性分析方法只能處理含有兩類對象的信息網(wǎng)絡(luò)，不適用于多關(guān)系網(wǎng)絡(luò)的重要性分析.

現(xiàn)實中真實的網(wǎng)絡(luò)數(shù)據(jù)組織形式多為異質(zhì)信息網(wǎng)絡(luò)，包含不同類型的對象和關(guān)系，元路徑作為一種有效的語義捕獲方法，通過不同的元路徑進(jìn)行重要性分析可以獲得不同的排名結(jié)果.Sun［9］提出了 PathSelClus 算法，通過學(xué)習(xí)元路徑的權(quán)重，元路徑權(quán)重在迭代過程中不斷更新用以提高聚類質(zhì)量，但是該方法挑選的元路徑之間相互獨立，不具備信息共享的特性.Meng［10］等提出了一種自動發(fā)現(xiàn)元路徑的方法，通過高接近度的節(jié)點對來貪心的尋找可以解釋節(jié)點對之間關(guān)系的元路徑，并整合對象之間的關(guān)系用以捕捉重要的元路徑，但是該方法沒有考慮元路徑之間信息互補，使得元路徑包含的語義只是局部最優(yōu).Shi［11］等提出了SemRec 集成異構(gòu)信息并獲得表示用戶對路徑的偏好優(yōu)先級和個性化權(quán)重，實現(xiàn)了更好的推薦性能，但是該方法沒有考慮元路徑之間組合關(guān)系，重要性分析缺乏一定的網(wǎng)絡(luò)信息.Cao［12］提出了 LiPaP 算法，設(shè)計了一個元路徑生成的算法，按照相關(guān)性順序提取元路徑，并學(xué)習(xí)被提取的元路徑的權(quán)重，由于該方法提取的元路徑有較高的相似性，在用于節(jié)點重要性分析時會忽略掉其他元路徑包含的網(wǎng)絡(luò)信息.Wang［13］提出了一種無監(jiān)督的元路徑選擇方法，自動在異質(zhì)信息網(wǎng)絡(luò)上尋找有用的元路徑，并提出了一種新的相似性度量方法KnowSim 應(yīng)用于文本聚類和分類問題改進(jìn)聚類和分類結(jié)果，但是該方法沒有考慮元路徑之間信息互補，使得在進(jìn)行重要性分析時缺乏需要的語義.Li［14］提出了HRank，利用約束元路徑來捕獲網(wǎng)絡(luò)中的豐富語義.HRank 應(yīng)用張量分析同時評估多種類型的對象和元路徑的重要性，但該方法只考慮到了對象之間的可達(dá)性或簡單的組合元路徑，無法針對元路徑上的不同對象選取不同的元路徑進(jìn)行語義補充，重要性分析缺乏針對性.

本文提出基于組合元路徑的重要性排名方法，通過組合元路徑有針對性地捕捉與重要性排名相關(guān)的語義信息，避免了使用單一的語義信息分析節(jié)點的重要性的局限，從而使重要性排名更加可信.

3 基本定義

在介紹重要性排名算法之前，先給出符號解釋和定義.

定義1.異質(zhì)信息網(wǎng)絡(luò)G.給定一個有向圖G=(V，E，τ，φ，A，R).V 代表節(jié)點集，E 代表邊集.τ 表示對象類型映射函數(shù)，φ表示關(guān)系類型映射函數(shù).τ(v)∈A 表示每個節(jié)點v∈V都屬于一個節(jié)點類.φ(e)∈R 表示每個邊e∈E 都屬于一類關(guān)系.當(dāng)對象類型數(shù)量∣A ∣＞1 或關(guān)系類型數(shù)量∣R ∣＞1時，網(wǎng)絡(luò)被稱為異質(zhì)信息網(wǎng)絡(luò).當(dāng)對象類型數(shù)量 ∣A ∣=1且關(guān)系類型數(shù)量∣R ∣=1 為同質(zhì)信息網(wǎng)絡(luò).

令Vi表示Ai對象對應(yīng)的V 中節(jié)點的集合，滿足:對于Av∈Vi，Vi≤V，都有 τ(v)=Ai，并且對于Av∈V－Vi，都有τ(v)≠Ai.其中，Ai表示 G 中的對象類型，Ai∈A.

定義2.元路徑 P.給定異質(zhì)信息網(wǎng)絡(luò) G=(V，E，τ，φ，A，R)，長度為m 的元路徑P 定義為鏈接兩類對象的一條路徑.即.其中:Ai表示G 中的對象類型，Ai∈A;Ri表示 G 中的關(guān)系類型，Ri∈R.元路徑P 的長度用Plen(P)表示，代表元路徑中對象的個數(shù)，即m=Plen(P).

為了方便，規(guī)定元路徑P 的表示縮寫為A1A2…Ai…Am，Ai∈A.A1稱為元路徑 P 的源對象，Am稱為元路徑 P 的目標(biāo)對象.

元路徑P 包含的對象對應(yīng)一個對象序列(A1A2…Ai…Am)，假定有一條元路徑tp=Astart…Aend，如果tp 對應(yīng)的對象序列(Astart…Aend)是(A1A2…Ai…Am)的連續(xù)子序列，則稱元路徑tp 為P 的子路徑.

元路徑刻畫了節(jié)點之間的語義信息，以學(xué)術(shù)網(wǎng)絡(luò)為例，假設(shè)A，P，C 分別表示學(xué)者、論文和會議，則元路徑APCPA 表示的語義是不同學(xué)者在同一個會議上發(fā)表論文.元路徑APA 表示的語義是不同的學(xué)者合作發(fā)表同一篇論文.

定義3.組合元路徑CP.在異質(zhì)信息網(wǎng)絡(luò)G=(V，E，τ，φ，A，R)中，定義組合元路徑為 CP=(FP，LP，λ).其中:

FP 是一條以被排名對象為目標(biāo)對象的元路徑，稱FP 為主元路徑(Main meta-path)，F(xiàn)P 的長度為m.

LP 是由m 個輔助元路徑(Auxiliary meta-path)組成的元路徑集合，即 LP={LPA1，LPA2，…，LPAi，…，LPAm}，稱 LP 為輔助元路徑集合.LPAi為輔助元路徑，0＜i＜m，是一條鏈接在主元路徑的Ai對象上用于補充Ai對象語義信息的元路徑，Ai∈A.

λ={λA1，λA2，…，λAi，…，λAm}表示輔助元路徑集合 LP與主元路徑FP 的組合參數(shù)集合，λAi為主元路徑FP 與輔助元路徑 LPAi的組合參數(shù)，0＜i＜m.

組合元路徑通過多個輔助元路徑對主元路徑的語義進(jìn)行補充，使得組合元路徑可以適應(yīng)異質(zhì)信息網(wǎng)絡(luò)中復(fù)雜的網(wǎng)絡(luò)結(jié)構(gòu)和多種對象關(guān)系.

定義4.相關(guān)關(guān)系轉(zhuǎn)移鄰接矩陣WAlAk.相關(guān)關(guān)系轉(zhuǎn)移鄰接矩陣WAlAk是表示Al對象與Ak對象之間關(guān)系的鄰接矩陣，Al∈A，Ak∈A.將 Al對象對應(yīng)的節(jié)點類 Vl中的第 i 個節(jié)點表示為 vl，i，Ak對象對應(yīng)的節(jié)點類 Vk中的第 j 個節(jié)點表示為vk，j，則 WAlAk={wi，j}的計算公式見式(1).

相關(guān)關(guān)系轉(zhuǎn)移鄰接矩陣Wpaper，author表示的是論文對象與學(xué)者對象之間的發(fā)表關(guān)系.

定義5.內(nèi)部關(guān)系轉(zhuǎn)移鄰接矩陣MAlAl.內(nèi)部關(guān)系轉(zhuǎn)移鄰接矩陣MAlAl是表示Al對象內(nèi)部關(guān)系的鄰接矩陣，Al∈A.MAlAl={mi，j}的計算見式(2).

其中relation_num 表示節(jié)點之間的路徑數(shù)，以學(xué)術(shù)網(wǎng)絡(luò)為例，兩個學(xué)者之間的relation_num 可以代表合作次數(shù).內(nèi)部關(guān)系轉(zhuǎn)移鄰接矩陣Mpaper，paper表示的是論文對象的互相引用關(guān)系.

4 基于組合元路徑的節(jié)點重要性排名方法

基于組合元路徑的節(jié)點重要性排名方法首先選取主元路徑和輔助元路徑集合構(gòu)建組合元路徑，沿主元路徑進(jìn)行重要性排名的循環(huán)迭代計算，并對組合參數(shù)進(jìn)行更新，最大化排名向量的信息熵，使排名向量更加可信.

步驟1.確定主元路徑，根據(jù)主元路徑選取輔助元路徑，構(gòu)建組合元路徑.

步驟2.計算相關(guān)關(guān)系排名和內(nèi)部關(guān)系排名，通過參數(shù)線性組合得到重要性排名.

步驟3.沿主元路徑循環(huán)迭代計算直至重要性排名穩(wěn)定，迭代同時進(jìn)行組合參數(shù)更新.

圖2 基于組合元路徑的節(jié)點重要性排名方法Fig.2 Node importance ranking method based on combine meta-path

圖2 展示了該方法的基本思想，①通過主元路徑FP 可以確定不同對象之間的相關(guān)關(guān)系，計算相關(guān)關(guān)系排名;②通過Ai對象的輔助元路徑LPAi確定Ai對象的內(nèi)部關(guān)系，計算內(nèi)部關(guān)系排名;③線性組合相關(guān)關(guān)系排名和內(nèi)部關(guān)系排名得到該對象的重要性排名，并沿主元路徑進(jìn)行下一個對象的重要性排名計算.并將主元路徑的目標(biāo)對象連入源對象，構(gòu)建可循環(huán)迭代的計算結(jié)構(gòu)，計算不同迭代次數(shù)的重要性排名.

4.1 組合元路徑的選取

選取主元路徑和輔助元路徑集合構(gòu)建組合元路徑用以捕捉語義信息.主元路徑可以按照如下規(guī)則選取:首先根據(jù)異質(zhì)信息網(wǎng)絡(luò)的網(wǎng)絡(luò)結(jié)構(gòu)得到元路徑集合MP，當(dāng)對Ai對象進(jìn)行重要性排名時，在MP 中篩選出以Ai為目標(biāo)對象的元路徑，當(dāng)篩選結(jié)果中包含多條元路徑時，為了更大范圍地捕捉語義信息，從中選取包含對象類型數(shù)目最多的元路徑作為主元路徑FP.

針對主元路徑 FP=A1A2…Ai…Am上的每類對象 Ai，Ai∈A，在元路徑集合MP 中選取一條輔助元路徑LPAi用于補充Ai對象的語義信息，輔助元路徑的選取遵循3 個規(guī)則:

規(guī)則1.類型相同規(guī)則.輔助元路徑的源對象與目標(biāo)對象類型相同，即輔助元路徑As…Ae滿足As=Ae.

規(guī)則2.語義不重復(fù)規(guī)則.輔助元路徑與主元路徑中包含的語義不能重復(fù)，即主元路徑與輔助元路徑不可互為子路徑.

規(guī)則3.長度最短規(guī)則.當(dāng)對Ai對象的輔助元路徑LPAi進(jìn)行選取時，若滿足規(guī)則1 和規(guī)則2 的元路徑有r 條(r＞1)，符合規(guī)則的元路徑記為 candp1，candp2，…，candpr，選取長度最短、包含對象類型最少的元路徑作為輔助元路徑LPAi.即LPAi=min(Plen(candpt)).

輔助元路徑的設(shè)計原則遵循進(jìn)一步補充語義信息，同時避免語義重復(fù)，使補充的語義信息更具有針對性.因此，選擇長度最短、包含對象類型最少的元路徑作為輔助元路徑，既能更大范圍的捕捉語義信息，又能避免語義重復(fù).輔助元路徑的確定過程如算法1 所示.

算法1 的算法時間復(fù)雜度為O(mk)，第4 ～9 行是遍歷元路徑集合MP，尋找符合規(guī)則1 和規(guī)則2 的元路徑candpt，將符合選取規(guī)則的元路徑 candpt放入集合 candp 中.第11 ～13行表示當(dāng)candpt不為空集時，從集合中挑選出長度最短、包含對象類型最少的元路徑作為Ai對象的輔助元路徑LPAi加入到輔助元路徑集合LP 中.

4.2 組合排名的計算

根據(jù)輔助元路徑集合LP 可以得到A1，A2…Ai…Am對象的內(nèi)部關(guān)系轉(zhuǎn)移鄰接矩陣 MA1A1，MA2A2，…，MAiAi，…，MAmAm.Ai對象的內(nèi)部關(guān)系轉(zhuǎn)移鄰接矩陣為 MAiAi，Ai∈A，第 j－1(j＞1)次迭代計算得到的 Ai對象的重要性排名為 RankAi，j－1，通過 MAiAi和 RankAi，j－1可以得到 Ai對象在第 j 次沿主元路徑 FP循環(huán)迭代計算得到的內(nèi)部關(guān)系排名 R1Ai，j，i=1，2，…，m.計算方法見式(3).

根據(jù)主元路徑FP 上相鄰對象的相關(guān)關(guān)系，得到m－1 個相關(guān)關(guān)系轉(zhuǎn)移鄰接矩陣 WA1A2，WA2A3，…，WAi－1Ai，…，WAm－1Am.Ai對象與Ai－1對象之間的相關(guān)關(guān)系轉(zhuǎn)移鄰接矩陣為 WAi－1Ai，第j－1 次沿主元路徑FP 循環(huán)迭代時Ai對象的重要性排名為RankAi，j－1，通過 WAi－1Ai和 RankAi，j－1可以計算得到 Ai對象在第j 次迭代時的相關(guān)關(guān)系排名R2Ai，j，計算方法見式(4).

使用組合參數(shù) λAi(0＜λAi＜1)對 R1Ai，j和 R2Ai，j進(jìn)行線性組合，得到Ai對象在第j 次沿主元路徑FP 迭代計算得的重要性排名 RankAi，j，組合方法見式(5).

4.3 組合參數(shù)尋優(yōu)

組合參數(shù)決定了相關(guān)關(guān)系排名和內(nèi)部關(guān)系排名在重要性排名中的占比，本節(jié)通過組合參數(shù)尋優(yōu)最大化重要性排名向量的信息熵，最大化排名向量的信息熵可以使排名更具有區(qū)分度.計算第j 次迭代時Ai對象的排名向量RankAi，j的信息熵及其與第j－1次迭代的排名向量 RankAi，j－1的信息增益 ΔH.信息熵的計算方法見式(6).

其中，X 為排名向量，p(xi)表示X 分布中離散值xi的出現(xiàn)概率，一般H(X)＞0.X 變量的不確定性越大，熵就越大.

信息增益ΔH 的計算公式見式(7).

這里，RankAi，j是第 j 次迭代時 Ai對象的重要性排名向量，RankAi，j－1是第j－1次迭代時 Ai對象的重要性排名向量.

利用指數(shù)加權(quán)平均法計算出Ai對象在第j 次迭代計算時組合參數(shù)λAi的尋優(yōu)步長PAAi，j，計算方法見式(8).

其中，μ 是指數(shù)加權(quán)平均法的超參數(shù).

把主元路徑FP 上的目標(biāo)對象連入源對象，構(gòu)建循環(huán)迭代的計算結(jié)構(gòu)，在循環(huán)迭代計算的過程中，以最大化重要性排名的信息熵為目標(biāo)，使用指數(shù)加權(quán)平均法計算組合參數(shù)的尋優(yōu)步長對組合參數(shù)進(jìn)行更新，直到組合參數(shù)和重要性排名向量趨于穩(wěn)定.

通過以上步驟可以將主元路徑與多個輔助元路徑進(jìn)行組合并循環(huán)迭代的進(jìn)行重要性排名計算，如算法2 所示.

當(dāng)每類對象對應(yīng)的節(jié)點類包含x 個節(jié)點時，算法2 的時間復(fù)雜度為O(mx3)，第1 ～3 行為主元路徑FP 上的每類對象初始化重要性排名.

算法的第7 行計算第j 次迭代計算時Ai對象的內(nèi)部關(guān)系排名.

第8 行計算第j 次迭代計算時Ai對象的相關(guān)關(guān)系排名.

第9 行線性組合相關(guān)關(guān)系排名和內(nèi)部關(guān)系排名得到第j次迭代計算時Ai對象的重要性排名.

第10 行對計算得到的排名向量進(jìn)行歸一化.

第11 行通過指數(shù)加權(quán)平均法計算參數(shù)的尋優(yōu)步長，并對參數(shù)進(jìn)行更新，最大化重要性排名的信息熵.

第15 行確定迭代結(jié)束條件.

5 實驗與效果評估

本節(jié)在AMiner［15］數(shù)據(jù)集上測試了基于組合元路徑的重要性排名方法，并使用匹配準(zhǔn)確率和收斂速度對實驗結(jié)果進(jìn)行分析評估.

5.1 實驗數(shù)據(jù)

使用AMiner 數(shù)據(jù)集作為實驗數(shù)據(jù)集，AMiner 數(shù)據(jù)集包括了1702575 個學(xué)者數(shù)據(jù)、1932381 篇論文數(shù)據(jù)、255407 個會議數(shù)據(jù)、5181440 個學(xué)者與論文的發(fā)表數(shù)據(jù)、8008836 個論文之間的引用數(shù)據(jù)和4249520 個作者之間的合作數(shù)據(jù).

選取包含學(xué)術(shù)領(lǐng)域信息的學(xué)術(shù)文本，對該學(xué)術(shù)文本進(jìn)行LDA［16］主題提取，得到主題集合 RZ 和 RZ 中各主題元素的比重得分SZ.

選取AMiner 數(shù)據(jù)集中數(shù)據(jù)挖掘領(lǐng)域的會議，將每個會議對應(yīng)的學(xué)術(shù)文本進(jìn)行拼接，并同樣進(jìn)行LDA 主題提取得到第j 個會議的主題集合RCj和主題集合RCj對應(yīng)的各主題比重得分SCj.計算每個會議的主題集合與學(xué)術(shù)文本的主題集合RZ 的加權(quán)相似度得分.

根據(jù)相似度得分選定 SIGKDD、SIGMOD、VLDB、ICDE、CIKM、DASFAA 這六個會議用以縮小信息網(wǎng)絡(luò)的分析范圍，增強(qiáng)重要性分析的針對性.表1 統(tǒng)計了AMiner 數(shù)據(jù)集中這六個會議收錄的論文數(shù)以及與會議存在發(fā)表關(guān)系的學(xué)者數(shù).

表1 會議的數(shù)據(jù)統(tǒng)計Table 1 Conference statistics

5.2 評價指標(biāo)

選取實驗結(jié)果的匹配準(zhǔn)確率以及排名向量的收斂速度作為對重要性排名方法的評價指標(biāo).

1)匹配準(zhǔn)確率accuracy

匹配準(zhǔn)確率可以說明算法的可信程度，計算公式見式(9).

式(9)中Calset(Top_num)表示排名方法結(jié)果中前Top_num 個元素構(gòu)成的集合，Baseset 表示用于計算匹配準(zhǔn)確率的匹配集合.

2)收斂速度

隨著迭代次數(shù)的增加，重要性排名向量趨于穩(wěn)定，收斂速度快的方法可以在較少的迭代次數(shù)中得到穩(wěn)定的重要性排名.

計算相鄰兩次迭代結(jié)果的重要性排名向量之間的歐幾里得距離dis，并使用dis 作為判斷迭代是否結(jié)束的依據(jù)，當(dāng)Ai對象相鄰兩次迭代計算得到的排名向量之間的dis 值小于某一給定的閾值σ 時，方法停止迭代，歐幾里得距離dis 的計算公式見式(10).

式(10)中，RankAi，r表示的是 Ai對象第 r 次迭代計算時得到的重要性排名向量，RankAi，r－1表示的是 Ai對象第r－1次迭代計算時得到的重要性排名向量.

5.3 實驗內(nèi)容

以AMiner 數(shù)據(jù)集構(gòu)建學(xué)術(shù)異質(zhì)信息網(wǎng)絡(luò)，使用基于組合元路徑的節(jié)點重要性分析方法對Author 節(jié)點進(jìn)行重要性分析，選取包含對象類型數(shù)目最多的元路徑CPA 作為主元路徑FP，主元路徑長度m=3.由于Conference 對象對應(yīng)的節(jié)點之間沒有相互影響的關(guān)系，選取表示論文之間互相引用的關(guān)系的元路徑PP 作為LPpaper來補充Paper 對象語義信息，選取表示學(xué)者之間相互合作的關(guān)系的元路徑APA 作為LPauthor補充Author 對象的語義信息.

將主元路徑FP 的目標(biāo)對象Author 連接入源對象Conference，構(gòu)建循環(huán)迭代的計算結(jié)構(gòu)，得到不同迭代次數(shù)下的重要性排名，直至重要性排名穩(wěn)定.

表2給出了基于組合元路徑的重要性排名方法在AMiner 數(shù)據(jù)集上運行結(jié)果的前5 名學(xué)者的信息，同時也給出在AMiner 數(shù)據(jù)集中按照引用數(shù)和H 指數(shù)(h-index)排序的前5名的學(xué)者信息進(jìn)行學(xué)者之間的比對.這里，H 指數(shù)是一個量化學(xué)者個體科研成果的評價指標(biāo)，學(xué)者的H 指數(shù)是指至多有H篇論文分別被引用了至少H 次.

基于組合元路徑的重要性排名方法的實驗結(jié)果都可以在引用數(shù)或H 指數(shù)的排名結(jié)果中找到對應(yīng)，說明了實驗結(jié)果的合理性.并且可以看出基于組合元路徑的重要性排名方法更具有針對性，在一定程度上排除在其他學(xué)術(shù)領(lǐng)域有較多成果的學(xué)者，提高排名的精準(zhǔn)性，體現(xiàn)了基于組合元路徑的重要性排名方法相對于統(tǒng)計方法的優(yōu)勢.

清洗數(shù)據(jù)使PageRank 和HITS 算法可以進(jìn)行重要性分析，PageRank、HITS 和基于組合元路徑的節(jié)點重要性排名方法的實驗結(jié)果與AMiner1https://www.aminer.cn/于2019 年4 月公布的知名學(xué)者之間進(jìn)行匹配.將學(xué)者按H 指數(shù)、A 指數(shù)(A-index)排名得到H指數(shù)排名和A 指數(shù)排名，并計算出H 指數(shù)排名和A 指數(shù)排名的匹配結(jié)果，得到的匹配準(zhǔn)確率如圖3 所示.

圖3 匹配準(zhǔn)確率Fig.3 Matching accuracy

圖3 的橫軸表示的是算法結(jié)果的匹配范圍，即對算法結(jié)果中前top 個結(jié)果求匹配準(zhǔn)確率.縱軸表示的是對應(yīng)的匹配范圍內(nèi)的匹配準(zhǔn)確率.

從圖3 可以看到，隨著匹配范圍的不斷擴(kuò)大，基于組合元路徑的節(jié)點重要性分析方法的匹配準(zhǔn)確率較高，使用單一語義進(jìn)行重要性分析的PageRank 和HITS 算法，由于忽略了語義信息，匹配準(zhǔn)確率稍低.

由于HITS 算法易受“垃圾鏈接”的影響，當(dāng)不同對象之間存在一對多的關(guān)系時會引起HITS 的重要性分?jǐn)?shù)的不正常增加，從而影響匹配準(zhǔn)確率偏低;而直接使用學(xué)術(shù)指標(biāo)進(jìn)行重要性排名只是對學(xué)者發(fā)表的學(xué)術(shù)成果進(jìn)行了簡單的統(tǒng)計，無法針對某個學(xué)術(shù)范圍進(jìn)行學(xué)者的重要性分析，匹配準(zhǔn)確率較低.

PageRank、HITS 和基于組合元路徑的節(jié)點重要性排名方法的實驗結(jié)果都與AMiner 公布的知名學(xué)者有差別，部分學(xué)者跨多個研究領(lǐng)域，導(dǎo)致對學(xué)者重要性的分析出現(xiàn)偏差;部分學(xué)者的成果發(fā)表時間較短，未被AMiner 收錄，導(dǎo)致重要性分析缺乏時效性;還有一些學(xué)者的信息沒有包含在AMiner 數(shù)據(jù)集中，導(dǎo)致無法對此類學(xué)者進(jìn)行重要性分析.

在循環(huán)迭代計算的過程中，各學(xué)者的重要性得分會收斂于一個穩(wěn)定值，即重要性排名向量會趨于穩(wěn)定.圖4 顯示了PageRank 算法、HITS 算法、基于組合元路徑的節(jié)點重要性分析方法的排名向量的收斂速度.圖4 的橫坐標(biāo)表示算法迭代計算的次數(shù)，縱坐標(biāo)代表的是相鄰兩次計算得到排名之間的距離.

通過圖4 可以發(fā)現(xiàn)基于組合元路徑的重要性分析方法可以使排名向量更快速地收斂，而PageRank 算法和HITS 算法的收斂速度較慢，需要更多次的迭代計算才可以使排名收斂.

圖4 迭代計算時排名的收斂Fig.4 Convergence of rankings in iterative calculations

基于組合元路徑的重要性分析方法使用組合參數(shù)對相關(guān)關(guān)系排名和內(nèi)部關(guān)系排名進(jìn)行線性組合，并在迭代計算中不斷的對組合參數(shù)進(jìn)行更新.

圖5 參數(shù) λpaper和 λauthor的收斂Fig.5 Convergence of parameters λpaper and λauthor

Paper 節(jié)點的組合參數(shù)λpaper和Author 節(jié)點的組合參數(shù)λauthor的收斂情況如圖5(a)和圖5(b)所示.從圖5 中可以看到，通過指數(shù)加權(quán)平均法確定步長并對組合參數(shù)進(jìn)行更新之后，組合參數(shù)最終會收斂于某一個較小的范圍內(nèi).

6 總 結(jié)

本文研究了異質(zhì)信息網(wǎng)絡(luò)中的節(jié)點重要性分析問題.提出了一種基于組合元路徑的節(jié)點重要性排名方法，根據(jù)異質(zhì)信息網(wǎng)絡(luò)的結(jié)構(gòu)確定組合元路徑，進(jìn)行循環(huán)迭代計算，同時更新組合參數(shù)使排名向量的信息熵最大化，直至重要性排名穩(wěn)定.通過實驗驗證了所提方法有效，并可以快速收斂.后續(xù)工作中，我們將考慮沿元路徑進(jìn)行多循環(huán)迭代運算時不同組合參數(shù)收斂速度的差異性，開展進(jìn)一步的研究.