SLTA-PathSim：一種融合節(jié)點(diǎn)屬性和文本信息的相似性度量算法

劉輝林，閆 娜，羅夢(mèng)瑩

(東北大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，沈陽110169)

E-mail：liuhuilin@mail.neu.edu.cn

1 引 言

隨著在線社交媒體的發(fā)展，網(wǎng)絡(luò)交互變得極其復(fù)雜.現(xiàn)有的網(wǎng)絡(luò)大多是包含多種類型節(jié)點(diǎn)、鏈接以及豐富語義信息的異質(zhì)信息網(wǎng)絡(luò).通過在異質(zhì)信息網(wǎng)絡(luò)中建模數(shù)據(jù)，可以捕捉豐富的語義信息并應(yīng)用于其他網(wǎng)絡(luò)分析任務(wù).

異質(zhì)信息網(wǎng)絡(luò)分析的一個(gè)基本問題是確定合適的相似性度量指標(biāo)來表征節(jié)點(diǎn)之間的相似性.文獻(xiàn)信息網(wǎng)絡(luò)作為一種典型的異質(zhì)信息網(wǎng)絡(luò)，描述了科學(xué)文獻(xiàn)的體系結(jié)構(gòu)和客觀規(guī)律.在文獻(xiàn)信息網(wǎng)絡(luò)中搜索與指定作者相似的其他作者有利于各種數(shù)據(jù)挖掘任務(wù).例如，相似性結(jié)果可以指導(dǎo)作者發(fā)現(xiàn)潛在的合作者.因此，兩個(gè)作者可能會(huì)更早地進(jìn)行學(xué)術(shù)交流，有助于學(xué)術(shù)研究.此外，相似性搜索在推薦系統(tǒng)方面也有廣泛應(yīng)用，例如文章推薦，朋友推薦等.

相似性度量作為一種常用的評(píng)估節(jié)點(diǎn)對(duì)之間相似度的無監(jiān)督方法，一直是數(shù)據(jù)庫和web搜索領(lǐng)域的重要研究?jī)?nèi)容.目前，很多學(xué)者對(duì)相似性度量方法進(jìn)行了研究，大多針對(duì)于同質(zhì)信息網(wǎng)絡(luò).然而，隨著在線社交媒體的發(fā)展，包含多種類型節(jié)點(diǎn)以及交互關(guān)系的異質(zhì)信息網(wǎng)絡(luò)在真實(shí)世界中占據(jù)主要地位，圖1的文獻(xiàn)信息網(wǎng)絡(luò)就是一種常見的異質(zhì)信息網(wǎng)絡(luò).該網(wǎng)絡(luò)包含“作者”、“論文”、“會(huì)議”、“術(shù)語”四種不同類型的節(jié)點(diǎn)，這些節(jié)點(diǎn)之間構(gòu)成了多種交互關(guān)系.以作者A1和作者A2之間的關(guān)系為例，作者A1撰寫的論文P1和P2與作者A2撰寫的論文P4和P5都發(fā)表在“SIGMOD”會(huì)議上，論文P3和P6都包含相同的術(shù)語“Link Prediction”.

圖1 文獻(xiàn)信息網(wǎng)絡(luò)

異質(zhì)信息網(wǎng)絡(luò)中的兩個(gè)節(jié)點(diǎn)可以通過不同的路徑進(jìn)行連接，不同路徑表達(dá)的語義信息也不盡相同.2011年，孫等人[1]提出了元路徑的概念，為異質(zhì)信息網(wǎng)絡(luò)中的相似性度量提供了一個(gè)全新的視角.通過對(duì)現(xiàn)有方法進(jìn)行分析和總結(jié)，本文在PathSim算法的基礎(chǔ)上，設(shè)計(jì)了基于節(jié)點(diǎn)屬性和文本信息的SLTA-PathSim 算法.該算法考慮了論文中作者署名位置、論文標(biāo)題和摘要對(duì)挖掘結(jié)果的影響，其主要貢獻(xiàn)如下：

1)作者署名位置信息是論文的一個(gè)重要屬性，在一定程度上反映了作者對(duì)論文的貢獻(xiàn)程度.因此，本文提出了基于元路徑和作者署名位置的SL-PathSim算法，在計(jì)算交換矩陣時(shí)加入了作者署名位置的計(jì)算.

2)由于提交渠道的不同，同一個(gè)會(huì)議上發(fā)表的多篇論文研究?jī)?nèi)容可能存在差異[2].論文標(biāo)題和摘要反映了論文的主要研究方向，通過分析兩個(gè)作者發(fā)表文章的文本相似性可以了解作者的研究興趣是否相近.因此，本文提出了基于元路徑和文本內(nèi)容的TA-PathSim算法，實(shí)現(xiàn)了兩個(gè)節(jié)點(diǎn)之間相似性分?jǐn)?shù)的加權(quán)組合.

3)最后，通過在著名的AMnier數(shù)據(jù)集上進(jìn)行多組相似性搜索實(shí)驗(yàn)，對(duì)本文提出算法的有效性進(jìn)行了驗(yàn)證.

2 相關(guān)工作

相似性度量作為一種常用的評(píng)估節(jié)點(diǎn)對(duì)之間相似度的無監(jiān)督方法，一直是復(fù)雜網(wǎng)絡(luò)分析領(lǐng)域的一個(gè)熱點(diǎn)話題.直觀地說，如果兩個(gè)節(jié)點(diǎn)交互得越頻繁則它們的相似程度越高.

2011年孫等人提出了用于單條對(duì)稱元路徑中同種類型節(jié)點(diǎn)間相似性計(jì)算的PathSim方法[1]，該方法綜合了兩個(gè)作者之間的所有路徑以獲得相似性，在搜索相似作者方面取得了良好的效果.為了評(píng)估不同類型節(jié)點(diǎn)的相似性，石川等人借鑒異質(zhì)信息網(wǎng)絡(luò)中SimRank算法[3]的基本思想，提出了HeteSim算法[4].該算法采用雙向隨機(jī)游走計(jì)算兩個(gè)節(jié)點(diǎn)通過給定元路徑的相遇概率，可以在任意元路徑下測(cè)量任何節(jié)點(diǎn)之間的相似性.2018年周等人通過對(duì)大量文獻(xiàn)進(jìn)行研究，發(fā)現(xiàn)現(xiàn)有方法大多基于用戶指定的元路徑，為此設(shè)計(jì)了一種基于元結(jié)構(gòu)的異質(zhì)SMSS框架[5]，能夠自動(dòng)構(gòu)建并捕獲豐富的語義信息.文獻(xiàn)[6]從信息論的角度出發(fā)，提出了一種基于元路徑的互信息模型MMI，通過路徑實(shí)例熵的數(shù)量來定義相似性分?jǐn)?shù)，減少了因節(jié)點(diǎn)之間缺少連通關(guān)系而造成的誤差.

上面介紹的方法均屬于根據(jù)專家的先前經(jīng)驗(yàn)來挖掘有用的知識(shí)，而如何自動(dòng)且有效地進(jìn)行網(wǎng)絡(luò)特征的學(xué)習(xí)推動(dòng)了網(wǎng)絡(luò)嵌入的發(fā)展.網(wǎng)絡(luò)嵌入旨在將每個(gè)網(wǎng)絡(luò)嵌入到低維空間中，學(xué)習(xí)節(jié)點(diǎn)的嵌入向量[7].在得到節(jié)點(diǎn)的向量表示之后就可以通過余弦相似性等距離度量方式計(jì)算節(jié)點(diǎn)之間的相似性.Bryan Perozzi等人于2014年提出了DeepWalk嵌入算法[8]，首先在網(wǎng)絡(luò)上采用隨機(jī)游走策略生成節(jié)點(diǎn)的鄰居集合，然后應(yīng)用Skip-Gram模型訓(xùn)練嵌入.付等人提出了一種針對(duì)異質(zhì)信息網(wǎng)絡(luò)的Hin2Vec網(wǎng)絡(luò)嵌入方法[9]，不同于DeepWalk，Hin2Vec的核心是一個(gè)神經(jīng)網(wǎng)絡(luò)模型，通過同時(shí)嵌入網(wǎng)絡(luò)中的節(jié)點(diǎn)和鏈接，更多地利用了網(wǎng)絡(luò)結(jié)構(gòu)和元路徑所表達(dá)的語義信息，使得生成的向量空間與實(shí)際網(wǎng)絡(luò)更加接近.盡管大多數(shù)現(xiàn)有的嵌入方法考慮了異質(zhì)關(guān)系，但它們通常對(duì)所有關(guān)系采用單一模型進(jìn)行嵌入，沒有區(qū)分不同的關(guān)系類型，這不可避免地限制了網(wǎng)絡(luò)嵌入的能力.2019年陸等人提出了RHINE模型[10]，從數(shù)學(xué)分析角度出發(fā)，將作者與論文之間的關(guān)系視為一種點(diǎn)對(duì)點(diǎn)結(jié)構(gòu)，論文與會(huì)議之間的關(guān)系看成一個(gè)以另一個(gè)為中心的結(jié)構(gòu)，針對(duì)不同的關(guān)系結(jié)構(gòu)采用不同的嵌入方法.

系統(tǒng)回顧所有相關(guān)研究，我們發(fā)現(xiàn)以往的研究并沒有考慮節(jié)點(diǎn)屬性和豐富的文本信息來量化相似性.因此，本文在PathSim基礎(chǔ)上提出了一種融合節(jié)點(diǎn)屬性和文本信息的SLTA-PathSim算法，并通過在AMiner數(shù)據(jù)集上進(jìn)行多組對(duì)比實(shí)驗(yàn)，證明了SLTA-PathSim的有效性.

3 問題定義

本節(jié)將簡(jiǎn)要介紹文獻(xiàn)信息網(wǎng)絡(luò)中涉及的一些概念、符號(hào)以及交換矩陣的定義和計(jì)算.

定義1.異質(zhì)信息網(wǎng)絡(luò)(Heterogeneous Information Network)通常被定義為G=(V，E，A，R)，其中V表示網(wǎng)絡(luò)中的節(jié)點(diǎn)，E表示這些節(jié)點(diǎn)所形成的鏈接.節(jié)點(diǎn)類型映射函數(shù)為θ:V→A，鏈接類型映射函數(shù)φ:E→R.對(duì)于任意節(jié)點(diǎn)v∈V，屬于一個(gè)特定的節(jié)點(diǎn)類型θ(v)∈A，對(duì)于任意一條邊e∈E，屬于一個(gè)特定的鏈接類型φ(e)∈R，并且滿足節(jié)點(diǎn)類型|A|>1或者鏈接類型|R|>1[1，2].

定義2.文獻(xiàn)信息網(wǎng)絡(luò)(Bibliographic Information Network)是一種典型的異質(zhì)信息網(wǎng)絡(luò).圖1展示了一個(gè)包含作者(Author)、論文(Paper)、會(huì)議(Venue)以及術(shù)語(Term)四種節(jié)點(diǎn)類型的文獻(xiàn)信息網(wǎng)絡(luò).

圖2 網(wǎng)絡(luò)模式與典型元路徑

定義3.網(wǎng)絡(luò)模式(Network Schema)通常被定義成TG=(A，R).類似數(shù)據(jù)庫中的E-R圖，網(wǎng)絡(luò)模式是網(wǎng)絡(luò)的一種元描述.圖2(a)為文獻(xiàn)信息網(wǎng)絡(luò)的網(wǎng)絡(luò)模式示意圖.

4 SLTA-PathSim算法

文獻(xiàn)信息網(wǎng)絡(luò)包含多種類型的節(jié)點(diǎn)和鏈接.由于網(wǎng)絡(luò)的異質(zhì)性，同質(zhì)網(wǎng)絡(luò)方法不能簡(jiǎn)單地應(yīng)用到異質(zhì)信息網(wǎng)絡(luò)中，進(jìn)而吸引了大量研究人員對(duì)異質(zhì)信息網(wǎng)絡(luò)研究的興趣.孫等人提出的PathSim算法雖然在作者相似性評(píng)估方面取得了一定的成果，但該方法依賴于路徑實(shí)例的數(shù)量，通過整合節(jié)點(diǎn)間有限的路徑數(shù)計(jì)算相似性.

給定一條對(duì)稱元路徑P，對(duì)于任意兩個(gè)節(jié)點(diǎn)ai和aj，PathSim(ai，aj)定義如公式(1)所示，其中pai→aj指在元路徑P下從節(jié)點(diǎn)ai到達(dá)節(jié)點(diǎn)aj的路徑實(shí)例.

(1)

由公式(1)可知，PathSim由兩部分組成：一是給定元路徑P下源節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)之間的路徑實(shí)例數(shù)，二是節(jié)點(diǎn)到自身的路徑實(shí)例數(shù).如果兩個(gè)節(jié)點(diǎn)之間的元路徑實(shí)例越多，相似性就越高.對(duì)于單一查詢來說，PathSim算法的時(shí)間復(fù)雜度為O(n*d)，其中n表示目標(biāo)節(jié)點(diǎn)的數(shù)量，d為交換矩陣MP中目標(biāo)節(jié)點(diǎn)的平均鄰居數(shù).

盡管PathSim后續(xù)被應(yīng)用于文獻(xiàn)信息網(wǎng)絡(luò)中的多種數(shù)據(jù)挖掘任務(wù)，但忽略了節(jié)點(diǎn)屬性和文本信息的影響.針對(duì)PathSim的不足，本文提出了一種融合節(jié)點(diǎn)屬性和文本信息的SLTA-PathSim算法.下面幾小節(jié)，將對(duì)該算法進(jìn)行詳細(xì)描述.

4.1 基于元路徑和作者署名位置的SL-PathSim算法

對(duì)于計(jì)算文獻(xiàn)信息網(wǎng)絡(luò)中兩個(gè)作者之間的相似性，論文這一類型節(jié)點(diǎn)起著關(guān)鍵性作用，很多基于元路徑的方法都可以圍繞論文進(jìn)行擴(kuò)展.通過對(duì)論文中存在的多種屬性和文本內(nèi)容進(jìn)行分析，與現(xiàn)有方法不同，本文抓住了作者署名位置這一重要屬性對(duì)計(jì)算結(jié)果的影響.一般來說，作者的署名位置越靠前，作者對(duì)論文的貢獻(xiàn)程度越大.基于這樣的想法，本文提出了基于元路徑和作者署名位置的SL-PathSim(Signature Location-PathSim)算法，其時(shí)間復(fù)雜度同樣為O(n*d).下面將給出該算法的定義，并通過分析實(shí)例對(duì)該算法進(jìn)行介紹.

根據(jù)交換矩陣的定義，給定對(duì)稱元路徑P，對(duì)于兩個(gè)相同類型的節(jié)點(diǎn)ai和aj，SL-PathSim算法的定義如公式(2)所示.其中sl(ai)表示作者ai的署名位置，sl(ai)=slmax+1-slcur，slmax是ai發(fā)表的所有論文中署名位置的最大值，slcur指作者在當(dāng)前論文中的署名位置.若作者與論文之間不存在寫作關(guān)系，則sl(ai)為0.

(2)

圖3是作者Jim和Mike之間基于元路徑APVPA的一個(gè)簡(jiǎn)單文獻(xiàn)信息網(wǎng)絡(luò)實(shí)例，其中包含作者、論文、會(huì)議三種不同類型的節(jié)點(diǎn).

在元路徑APVPA下，交換矩陣M=WAPWPV…WVPWPA，其中WPA=WAPT，WVP=WPVT.鄰接矩陣WAP表明作者和論文之間是否存在寫作關(guān)系.以圖3中的Jim為例，該作者發(fā)表了三篇論文P1、P2、P5，并沒有發(fā)表論文P3、P4和P6，因此本例中通過PathSim算法計(jì)算得到的WAP如表1所示.

圖3 基于元路徑APVPA的文獻(xiàn)信息網(wǎng)絡(luò)實(shí)例

表1 PathSim計(jì)算的鄰接矩陣WAP

Table 1 Adjacency matrixWAPcalculated by PathSim

P1P2P3P4P5P6Jim110010Mike001101

作為論文節(jié)點(diǎn)的一個(gè)重要屬性，作者署名位置信息在一定程度上反映了該作者對(duì)論文的貢獻(xiàn)程度.因此，本文在計(jì)算交換矩陣時(shí)，增加了作者署名位置.同樣以圖3示例中的Jim為例，該作者發(fā)表的三篇文章P1、P2、P5中最大署名位置為2，根據(jù)公式slmax+1-slcur，可以得到：slP1(Jim)=2+1-1=2，slP2(Jim)=2+1-2=1，slP5(Jim)=2+1-1=2.因此，本例中通過SL-PathSim計(jì)算得到的WAP如表2所示.

表2 SL-PathSim計(jì)算的鄰接矩陣WAP

Table 2 Adjacency matrixWAPcalculated by SL-PathSim

P1P2P3P4P5P6Jim210020Mike001102

鄰接矩陣WPV表示論文與會(huì)議之間的發(fā)表關(guān)系，其通過PathSim算法計(jì)算的結(jié)果可以表示為表3.由于作者署名位置僅存在于作者和論文之間，在論文和會(huì)議之間并不存在，所以這里直接將PathSim計(jì)算的WPV結(jié)果作為SL-PathSim算法的WPV鄰接矩陣.

表3 PathSim計(jì)算的鄰接矩陣WPV

Table 3 Adjacency matrixWPVcalculated by PathSim

KDDSIGMODP110P210P310P410P501P601

4.2 基于元路徑和文本信息的TA-PathSim算法

文獻(xiàn)信息網(wǎng)絡(luò)中的論文節(jié)點(diǎn)包含多種文本信息，例如論文標(biāo)題，摘要，關(guān)鍵詞等，其中論文標(biāo)題是對(duì)文章最簡(jiǎn)要的概括.這也與現(xiàn)實(shí)情況相符，兩個(gè)作者所撰寫的論文標(biāo)題越相似表明其研究方向越相近，但通過標(biāo)題僅能了解作者的大致研究方向.設(shè)想兩位作者在同一會(huì)議上發(fā)表了文章，標(biāo)題都是“網(wǎng)絡(luò)表征學(xué)習(xí)的研究與應(yīng)用”，但二者分別基于同質(zhì)信息網(wǎng)絡(luò)和異質(zhì)信息網(wǎng)絡(luò)，雖然兩篇文章的標(biāo)題完全相同，但是研究?jī)?nèi)容卻存在很大差異.如果僅僅考慮論文標(biāo)題之間的相似性，反映的只是論文的部分信息，計(jì)算的準(zhǔn)確性就會(huì)下降.因此，本文提出了基于元路徑和文本信息的TA-PathSim算法，同時(shí)計(jì)算論文標(biāo)題和摘要之間的相似性，并取它們的平均值作為兩篇文章的最終文本相似度.

目前文本特征提取問題的研究工作，逐漸從傳統(tǒng)方法向深度學(xué)習(xí)方法轉(zhuǎn)移[12].傳統(tǒng)的“Bag-of-Words”忽略了詞的順序和單詞之間表達(dá)的語義信息.雖然“N-Grams”模型考慮了順序，但效果沒有顯著改善.為此，本文采用Doc2Vec模型來實(shí)現(xiàn)論文標(biāo)題及摘要相似度的計(jì)算，該模型通過PV-DM模型將文本映射成向量，在一定程度上保留了文本的語義信息[13].

算法1詳細(xì)介紹了Doc2Vec模型的使用流程.首先根據(jù)文獻(xiàn)信息網(wǎng)絡(luò)中論文節(jié)點(diǎn)提供的標(biāo)題集對(duì)Doc2Vec模型進(jìn)行訓(xùn)練，然后利用訓(xùn)練出來的模型M將論文標(biāo)題和摘要轉(zhuǎn)化為特征向量，最后通過距離計(jì)算公式計(jì)算論文標(biāo)題及摘要的相似度.關(guān)于距離公式本文使用的是余弦相似性度量方法，其時(shí)間復(fù)雜度為O(n*m)，n代表作者的個(gè)數(shù)，m是兩位作者在同一個(gè)會(huì)議上發(fā)表文章的數(shù)量.

算法1.文本相似性的計(jì)算

輸入：文獻(xiàn)信息網(wǎng)絡(luò)G，作者集合A，給定作者a1

輸出：論文標(biāo)題相似性St，論文摘要相似性Sa，論文相似性Sta

1. 初始化相似性值列表St，Sa，Sta為φ

2. 使用論文標(biāo)題集訓(xùn)練Doc2Vec模型得到M

3.Va1←a1參加的會(huì)議

4. FOR eacha2inADO

5.Va2←a2參加的會(huì)議

6. IFVa1∩Va2=φ

7.Sta=0

8. END IF

9. ELSE

10. FOR eachvinVa1∩Va2DO

11.P1，P2←v中a1，a2發(fā)表的論文

12.T1，T2←a1，a2發(fā)表論文的標(biāo)題

13.A1，A2←a1，a2發(fā)表論文的摘要

14.v1，v2←M(T1)，M(T2)

15.v3，v4←M(A1)，M(A2)

16.St，Sa←cos(v1，v2)，cos(v3，v4)

Sta←(St+Sa)/2.0

17. END FOR

18. END ELSE

19. END FOR

20. RETURNSta

給定元路徑P，雖然PathSim能夠捕捉節(jié)點(diǎn)之間微妙的語義信息，但是節(jié)點(diǎn)自身存在很多屬性信息和豐富的文本信息，如何考慮這些信息對(duì)挖掘結(jié)果的影響是個(gè)關(guān)鍵.因此，在PathSim算法的基礎(chǔ)上，本文將論文標(biāo)題和摘要的相似性作為兩位作者之間基于元路徑相似性分?jǐn)?shù)的權(quán)重.對(duì)于相同類型的作者ai和aj，TA-PathSim(ai，aj)定義如公式(3)所示，其中Sta(ai，aj)表示ai和aj在同一會(huì)議上發(fā)表論文的標(biāo)題相似性和摘要相似性的平均值.

(3)

由于TA-PathSim加入了標(biāo)題和摘要文本相似度的計(jì)算，在執(zhí)行和計(jì)算過程中會(huì)花費(fèi)相應(yīng)的時(shí)間，因此執(zhí)行效率要低于PathSim，其時(shí)間復(fù)雜度為O(n*d*m)，m是兩位作者在同一個(gè)會(huì)議上發(fā)表的文章篇數(shù).由于對(duì)于任意兩位作者a和a′，若不存在一個(gè)滿足APV的元路徑使得作者a與作者a′關(guān)聯(lián)，那兩個(gè)作者a和a′一定不相似[12].因此，本文計(jì)算文本相似度的前提是判斷兩位作者是否在同一會(huì)議發(fā)表了論文，如果存在這樣的目標(biāo)作者，則執(zhí)行計(jì)算，避免查找網(wǎng)絡(luò)中的所有作者，大大縮減了計(jì)算時(shí)間.

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

本節(jié)利用PathSim算法對(duì)所提出的算法進(jìn)行了定性評(píng)估，基于元路徑APVPA搜索并分析與“Christos Faloutsos”相似的Top-10作者，對(duì)本文提出算法的有效性進(jìn)行了驗(yàn)證.

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

由于加入了論文標(biāo)題及摘要的相似性計(jì)算，數(shù)據(jù)集的獲取成為了本文的難點(diǎn).以往的研究大多采用DBLP的“4-area-dataset”數(shù)據(jù)集，但該數(shù)據(jù)集包含的標(biāo)題和摘要信息基本一致.因此，本文使用AMiner數(shù)據(jù)集進(jìn)行實(shí)驗(yàn).AMiner是清華大學(xué)計(jì)算機(jī)科學(xué)系開發(fā)的數(shù)據(jù)分析與服務(wù)平臺(tái)，為計(jì)算機(jī)領(lǐng)域的研究者提供了許多前沿知識(shí)和研究方向.為了使計(jì)算出來的結(jié)果更加真實(shí)，本文選取了AMiner數(shù)據(jù)集中1992年到2011年的數(shù)據(jù)，并刪除了不包含摘要的論文.此外，考慮到大多數(shù)研究者關(guān)注頂級(jí)會(huì)議上發(fā)表的論文以及每個(gè)研究領(lǐng)域都有相應(yīng)的社區(qū)，本文根據(jù)谷歌學(xué)術(shù)指標(biāo)提取了6個(gè)領(lǐng)域的數(shù)據(jù)，即人工智能(AI)、計(jì)算機(jī)視覺(CV)、數(shù)據(jù)挖掘(DM)、數(shù)據(jù)庫(DB)、計(jì)算語言學(xué)(CL)和信息系統(tǒng)(IS)[14].處理后的數(shù)據(jù)集包括1.46M論文、476K作者和4K會(huì)議.

5.2 SL-PathSim算法分析

首先對(duì)數(shù)據(jù)集進(jìn)行處理，從而獲得每篇論文中每位作者的署名位置.在計(jì)算交換矩陣時(shí)，如果作者發(fā)表了一篇論文，slmax+1-slcur可用來表示兩個(gè)節(jié)點(diǎn)間的連通性，其中slmax為作者在所有發(fā)表論文中署名位置的最大值，slcur為作者在當(dāng)前論文中的署名位置.

分析表4中SL-PathSim，PathSim查找的與“Christos Faloutsos”相似的Top-10作者，“Heikki Mannila”和“Ravi Kumar”之間的順序略有不同.“Heikki Mannila”共發(fā)表論文19篇，其中2篇作為第一作者，9篇作為第二作者，7篇作為第三作者，1篇作為第六作者.作者“Ravi Kumar”發(fā)表論文43篇，第一作者7篇，第二作者25篇，第三作者7篇，第四作者3篇，第五作者1篇.根據(jù)上述數(shù)據(jù)以及作者署名位置計(jì)算公式我們可以得出結(jié)論，作者“Heikki Mannila”對(duì)論文的貢獻(xiàn)程度要大于“Ravi Kumar”.如果目標(biāo)作者和源作者在同一會(huì)議上發(fā)表論文，目標(biāo)作者對(duì)論文貢獻(xiàn)程度越大，該作者與源作者越相似.因此，“Heikki Mannila”的相似度得分應(yīng)高于“Ravi Kumar”.

表4 APVPA下PathSim和SL-PathSim搜索的與“Christos Faloutsos”相似的Top-10作者

Table 4 Top-10 authors similar to “Christos Faloutsos” searched by PathSim and SL-PathSim under APVPA

PathSimSL-PathSimChristos Faloutsos1.0000Christos Faloutsos1.0000Jiawei Han0.9212Jiawei Han0.8794Philip S.Yu0.8921Philip S.Yu0.8551Jian Pei0.8714Jian Pei0.7404Charu C.Aggarwal0.6943Jieping Ye0.6502Ravi Kumar0.6847Heikki Mannila0.6491Eamonn J.Keogh0.6845Ravi Kumar0.6198Heikki Mannila0.6753Huan Liu0.5752Vipin Kumar0.6715Bing Liu0.5585Hui Xiong0.6677Hui Xiong0.5513

從表4中我們可以看出，關(guān)于與“Christos Faloutsos”相似的Top-10作者，SL-PathSim和PathSim的查找結(jié)果存在細(xì)微的差別.原因是PathSim算法只是基于元路徑的實(shí)例數(shù)量計(jì)算節(jié)點(diǎn)對(duì)之間的相似度，僅僅考慮作者是否發(fā)表了一篇論文，并沒有考慮作者對(duì)該篇論文的貢獻(xiàn)程度.本文提出的SL-PathSim算法在考慮元路徑實(shí)例數(shù)量的同時(shí)考慮了作者署名位置的影響，所以它的結(jié)果更接近事實(shí).

5.3 TA-PathSim算法分析

TA-PathSim算法的實(shí)現(xiàn)主要包含四個(gè)步驟：首先訓(xùn)練論文標(biāo)題集以獲取Doc2Vec模型，然后利用Doc2Vec模型將論文的標(biāo)題和摘要轉(zhuǎn)化為特征向量，再利用余弦相似性度量方法分別計(jì)算標(biāo)題和摘要的相似度，最后計(jì)算得到兩個(gè)作者的相似度.

表5 APVPA下PathSim和TA-PathSim搜索的與“Christos Faloutsos”相似的Top-10作者

Table 5 Top-10 authors similar to “Christos Faloutsos” searched by PathSim and TA-PathSim under APVPA

PathSimTA-PathSimChristos Faloutsos1.0000Christos Faloutsos1.0000Jiawei Han0.9212Jiawei Han0.6268Philip S.Yu0.8921Philip S.Yu0.6058Jian Pei0.8714Jian Pei0.5917Charu C.Aggarwal0.6943Ravi Kumar0.4703Ravi Kumar0.6847Charu C.Aggarwal0.4676Eamonn J.Keogh0.6845Vipin Kumar0.4666Heikki Mannila0.6753Heikki Mannila0.4645Vipin Kumar0.6715Hui Xiong0.4634Hui Xiong0.6677Eamonn J.Keogh0.4549

表5給出了TA-PathSim與PathSim搜索到的與“Christos Faloutsos”相似的Top-10作者，其中“Heikki Mannila”和“Eamonn J.Keogh”的排名順序有較大差異.“Heikki Mannila”發(fā)表的文章共有19篇，其中6篇關(guān)于“similarity”，3篇關(guān)于“cluster”.“Eamonn J.Keogh”共發(fā)表21篇論文，其中15篇論文關(guān)于“time series”，4篇論文關(guān)于“similarity”.源作者“Christos Faloutsos”發(fā)表了8篇關(guān)于“proximity measures”和“similarity queries”的論文，2篇論文關(guān)于“time series”，2篇關(guān)于“cluster”.通過上面對(duì)作者發(fā)表文章主要內(nèi)容的分析，“Heikki Mannila”的研究興趣與源作者的研究興趣更為相似.因此，“Heikki Mannila”應(yīng)該排在“Eamonn J.Keogh”之前.

PathSim算法僅僅考慮在同一會(huì)議上發(fā)表論文的作者之間的交互關(guān)系，而不考慮作者發(fā)表的論文內(nèi)容是否相似，即作者的研究興趣是否接近.因此，TA-PathSim搜索出來的結(jié)果更加可信.

5.4 SLTA-PathSim分析

基于上述算法分析，我們已經(jīng)知道SL-PathSim和TA-PathSim都取得了很好的效果，為此本文對(duì)SL-PathSim和TA-PathSim進(jìn)行了整合，將其作為一個(gè)擴(kuò)展，即SLTA-PathSim算法.對(duì)于相同類型的作者ai和aj，SLTA-PathSim(ai，aj)定義如公式(4)所示，其時(shí)間復(fù)雜度為O(n*d*m).為了證明SLTA-PathSim算法的有效性，本文同樣查找了與“Christos Faloutsos”相似的Top-10作者.

(4)

表6 APVPA下PathSim和SLTA-PathSim搜索的與“Christos Faloutsos”相似的Top-10作者

Table 6 Top-10 authors similar to “Christos Faloutsos” searched by PathSim and SLTA-PathSim under APVPA

PathSimSLTA-PathSimChristos Faloutsos1.0000Christos Faloutsos1.0000Jiawei Han0.9212Jiawei Han0.5982Philip S.Yu0.8921Philip S.Yu0.5806Jian Pei0.8714Jian Pei0.5027Charu C.Aggarwal0.6943Heikki Mannila0.4520Ravi Kumar0.6847Jieping Ye0.4465Eamonn J.Keogh0.6845Ravi Kumar0.4205Heikki Mannila0.6753Huan Liu0.3861Vipin Kumar0.6715Bing Liu0.3828Hui Xiong0.6677Hui Xiong0.3826

分析表6，SLTA-PathSim算法的搜索結(jié)果與PathSim的搜索結(jié)果相近，但順序略有不同.在元路徑APVPA下，表4中“Heikki Mannila”和“Ravi Kumar”之間的排名順序與表5中的順序相反.通過上面的分析我們已經(jīng)知道“Ravi Kumar”共發(fā)表43篇論文，其中14篇關(guān)于“similarity”和“social network”.如果僅僅考慮源作者和目標(biāo)作者之間所發(fā)表文章的文本內(nèi)容，“Ravi Kumar”與源作者更為相似.但通過分析作者署名位置信息，作者“Heikki Mannila”對(duì)文章的貢獻(xiàn)程度比“Ravi Kumar”要大得多.因此，“Heikki Mannila”的相似性分?jǐn)?shù)相對(duì)較高，與作者“Christos Faloutsos”更加相似.

為了進(jìn)一步驗(yàn)證SLTA-PathSim算法的性能，本文將PathCount、Hin2Vec和SLTA-PathSim進(jìn)行了對(duì)比.表7是三種算法查找到的與“Christos Faloutsos”相似的Top-10作者.在元路徑APVPA下，Path Count算法只是簡(jiǎn)單地判斷兩位作者是否在同一個(gè)會(huì)議上發(fā)表了文章，如果存在這樣的元路徑就把兩位作者之間的路徑實(shí)例數(shù)量加1.因此，如果目標(biāo)作者與源作者之間存在的路徑實(shí)例數(shù)量越多，兩個(gè)作者越相似.由于“Philip S.Yu”與源作者多次在同一會(huì)議上發(fā)表文章，所以Path Count查找結(jié)果為“Philip S.Yu”與源作者相似程度比較高.路徑數(shù)僅僅反映了網(wǎng)絡(luò)的局部結(jié)構(gòu)信息，而每個(gè)會(huì)議包含不同的主題，路徑數(shù)越多僅能說明兩個(gè)作者研究領(lǐng)域相似，但具體的研究興趣可能存在較大的區(qū)別.Hin2Vec算法返回一些作者(例如“Andrew Tomkins”)，在特定的研究興趣上不同于“Christos Faloutsos”.出現(xiàn)這種現(xiàn)象的原因可能是網(wǎng)絡(luò)嵌入適用于大規(guī)模網(wǎng)絡(luò)，而本文使用的數(shù)據(jù)集是20年內(nèi)的作者發(fā)表論文數(shù)據(jù)，并且刪除了沒有摘要的數(shù)據(jù)，因此其效果低于SLTA-PathSim.

本文提出的SLTA-PathSim算法，從網(wǎng)絡(luò)結(jié)構(gòu)、節(jié)點(diǎn)屬性和文本內(nèi)容等多角度出發(fā)，綜合了能夠影響作者之間相似性的多方面因素.此外，由于存在多個(gè)作者與源作者之間的路徑數(shù)相等的情況，具體哪位作者與“Christos Faloutsos”更相似則無法判斷，為此本文進(jìn)一步證明了SLTA-PathSim算法的有效性.

表7 APVPA下Path Count、Hin2Vec和SLTA-PathSim搜索的與“Christos Faloutsos”相似的Top-10作者

Table 7 Top-10 authors similar to “Christos Faloutsos” searched by Path Count、Hin2Vec and SLTA-PathSim under APVPA

Path CountHin2VecSLTA-PathSimChristos Faloutsos78.0000Christos Faloutsos1.0000Christos Faloutsos1.0000Philip S.Yu39.0000Ravi Kumar0.8576Jiawei Han0.5982Jiawei Han33.0000Jiawei Han0.8376Philip S.Yu0.5806Hans-Peter Kriegel27.0000Philip S.Yu0.8349Jian Pei0.5027Hector Garcia-Molina27.0000Andrew Tomkins0.8268Heikki Mannila0.4520JianPei23.0000ChengXiang Zhai0.8234Jieping Ye0.4465Haixun Wang23.0000Jian Pei0.8217Ravi Kumar0.4205Wei Wang′23.0000Charu C.Aggarwal0.8197Huan Liu0.3861H.V.Jagadish22.0000Jimeng Sun0.8144Bing Liu0.3828RaghuRamakrishnan22.0000Bing Liu0.8007Hui Xiong0.3826

6 總 結(jié)

通過閱讀大量文獻(xiàn)，對(duì)現(xiàn)有相似性計(jì)算方法進(jìn)行分析和總結(jié)，發(fā)現(xiàn)一些算法沒有評(píng)估節(jié)點(diǎn)屬性和文本信息對(duì)挖掘結(jié)果的影響.為了更好地表達(dá)信息，本文提出了SL-PathSim算法，該算法考慮了作者對(duì)論文的貢獻(xiàn)程度.此外，本文還從文本內(nèi)容角度進(jìn)行分析，設(shè)計(jì)了基于論文標(biāo)題與摘要相似度的TA-PathSim算法以實(shí)現(xiàn)相似性分?jǐn)?shù)的加權(quán)組合.在指定元路徑APVPA下，利用著名的AMiner數(shù)據(jù)集設(shè)計(jì)了多組實(shí)驗(yàn)，通過查找與“Christos Faloutsos”相似的Top-10作者，證明了本文所提算法的查找結(jié)果更接近于事實(shí).

雖然SLTA-PathSim在作者相似性度量方面效果很好，但使用的是預(yù)先定義好的元路徑.如何在大規(guī)模的復(fù)雜異質(zhì)信息網(wǎng)絡(luò)中自動(dòng)挖掘有用的元路徑是一個(gè)極具前景的方向.