邱慶羽，李 婧，全 兵，童 超，張利君，張海仙*

(1．四川大學 計算機學院，成都610065; 2．中移(蘇州)軟件技術有限公司，江蘇 蘇州215000;3．成都瑞貝英特信息技術有限公司，成都610041)

(*通信作者電子郵箱zhanghaixian@scu．edu．cn)

0 引言

信息網(wǎng)絡由一系列的節(jié)點以及連接節(jié)點的關系組成，現(xiàn)實世界中大多數(shù)對象都可以抽象為一個龐大的網(wǎng)絡，例如:文獻信息網(wǎng)絡［1］、生物信息網(wǎng)絡［2］、電影網(wǎng)絡［3］等。根據(jù)節(jié)點和關系的類型，信息網(wǎng)絡可以具體劃分為同構信息網(wǎng)絡和異構信息網(wǎng)絡。由于現(xiàn)實信息網(wǎng)絡中節(jié)點類型多樣，而且不同節(jié)點間的關系包含豐富的語義信息，所以目前研究的工作主要圍繞異構信息網(wǎng)絡展開。

隨著異構網(wǎng)絡的信息量呈指數(shù)級增長，用戶往往難以從大量的數(shù)據(jù)中篩選出感興趣的信息。相似性搜索作為異構信息網(wǎng)絡的重要研究分支，可以從大量的數(shù)據(jù)集中發(fā)現(xiàn)與查詢對象最為相關的信息，現(xiàn)已廣泛應用于諸多領域。例如，在文獻網(wǎng)絡中，用戶希望找到與給定作者最為相似的作者信息［4］;在醫(yī)學領域中，人們希望利用異構網(wǎng)絡識別出潛在的microRNA與疾病之間的關聯(lián)，從而解釋人類多源性疾病的發(fā)病機理［5］;在電商領域中，商家可能感興趣于推薦與指定產(chǎn)品最為相似的其他產(chǎn)品，輔助用戶作購買決策［6］。因此，基于異構信息網(wǎng)絡尋找與查詢對象最為相似的對等實體具有重要的研究價值和應用場景。

近年來，眾多學者探索設計不同的相似性度量方法，涌現(xiàn)了大量優(yōu)秀的工作。目前的研究工作大致可以分為以下3類:

1)基于節(jié)點特征的相似性度量［7－8］。借助計算特征相似性從而得到網(wǎng)絡節(jié)點間的相似性，然而該方法并不適用于不同類型節(jié)點間的相似性計算。

2)基于圖論的相似性度量［9－10］。通過圖拓撲概念將節(jié)點間的相似性轉(zhuǎn)化為與節(jié)點有關的圖結構的相似性進行計算。

3)基于元路徑的相似性度量［11－13］。借助領域知識定義幾種包含節(jié)點、關系操作的序列來計算節(jié)點在全局中的相似性。

本文提出了基于文獻網(wǎng)絡語義特征的相似性搜索算法(Similarity computation based on Vectorand meta Path，VPSim)，其主要貢獻包括:

1)從節(jié)點特征出發(fā)，提出了一種基于向量的文獻網(wǎng)絡特征提取的方法。該方法可用于衡量同類型節(jié)點間的語義關系，通過分析語義得到向量間相關概率作為節(jié)點間路徑權重。

2)結合元路徑設計了一種基于語義特征的節(jié)點相似性度量算法。在傳統(tǒng)的元路徑基礎上，增加了節(jié)點的語義信息，從而對節(jié)點的相似性分數(shù)進行加權組合。

3)基于文獻網(wǎng)絡數(shù)據(jù)的特點，設計了剪枝策略用以提高相似性搜索算法的執(zhí)行效率。通過在真實數(shù)據(jù)集上的實驗驗證了提出算法的有效性、執(zhí)行效率和可擴展性。

1 相關工作

1．1 語義特征提取

語義特征提取工作的前提是為文本尋求一種恰當?shù)谋硎痉绞?。目前研究工作處理的文本表示模型共有三種:布爾模型(Boolean Model)、向量空間模型(Vector Space Model)［14］和概率模型(Probabilistic Model)［15］。其中，向量空間模型因其操作性強、易于計算分析的優(yōu)點得到了廣泛的應用。然而，隨著對文本語義研究的深入，向量空間模型的不足日益顯現(xiàn)，如:實際的文本難以滿足特征項間相互獨立;只關注特征項的頻率信息從而丟失了文本上下文的語義及潛在的概念結構等信息。

因此，目前文本特征提取問題的研究工作，逐漸從傳統(tǒng)方法向深度學習方法轉(zhuǎn)移。深度學習的方法可以更好地提高模型的泛化能力，結合詞向量Word2Vec［16］技術，以及神經(jīng)網(wǎng)絡的層次化設計機制，更好地解決文檔表達的多元性和層次性問題。然而像傳統(tǒng)方法一樣，Word2Vec只是基于詞的維度進行語義分析，忽視了上下文的語義。由 Quoc等提出Doc2Vec［17］模型，在 Word2Vec模型的基礎上作了改進，通過在訓練文檔過程中增添一個共享段落向量，保留了文本上下文的語義信息。

1．2 信息網(wǎng)絡相似性搜索

相似性搜索作為眾多數(shù)據(jù)挖掘任務如聚類、推薦等的基礎受到廣泛關注也誕生了很多優(yōu)秀的工作?；谕瑯嬓畔⒕W(wǎng)絡的工作有 Jeh等［18］提出的個性化 PageRank算法和SimRank算法［11］等;Kusumoto等［19］提出了 SimRank 的線性遞歸表達式便于并行計算，使得大規(guī)模圖計算成為可能。然而這些算法并不直接適用于異構信息網(wǎng)絡的相似性搜索。

考慮到由不同類型對象組成的元路徑包含豐富的語義信息，Sun等［4］提出了PathSim算法用于計算基于單個對稱元路徑同類型節(jié)點的相似性，但該方法不適用于不同類型的節(jié)點。進而Shi等［20］提出了HeteSim算法用于計算不同類型實體間的相似性。以上方法均需用戶具備相關領域知識，具有一定局限性。Huang等［21］在元路徑的基礎上提出了基于 Meta Structure在大規(guī)模文獻異構網(wǎng)絡中的相似性搜索算法。此外，通過引入用戶導向，預測與用戶搜索相關元路徑的方法可以縮小元路徑指定范圍，目前也有一些研究工作，如MineRank算法［22］等。這些方法都是基于異構網(wǎng)絡的結構進行相似性搜索，雖然也取得了較好的效果，但它們均忽略了節(jié)點包含的語義信息，從而使得挖掘結果不準確。而語義信息作為節(jié)點的重要屬性，對相似性搜索具有重要的作用。

本文從信息網(wǎng)絡的語義出發(fā)，結合元路徑提出了一個面向文獻信息網(wǎng)絡，基于語義特征的相似性搜索算法。該算法考慮了公認的領域知識，不需要用戶指定，同時利用了節(jié)點自身攜帶的語義信息，使得相似性搜索的結果更為準確。同時結合文獻數(shù)據(jù)的特點，設計了剪枝策略，降低了計算候選路徑的規(guī)模，為文獻網(wǎng)絡計算相似性提供了一種新的解決思路。

2 問題定義

2．1 信息網(wǎng)絡

信息網(wǎng)絡是結構化文本表示知識的一種方式，它由一系列的節(jié)點和連接節(jié)點的邊組成。

定義1 信息網(wǎng)絡［4］。信息網(wǎng)絡可以用一個有向圖G=(V，E)來表示，其中V表示對象，E表示連接對象的邊。且對象V和邊E均有相應的類型映射函數(shù)，s:V→T，表示對于每個對象v∈V均屬于對象類型集合T:s(v)∈T以及關系映射函數(shù)t:E→R，對于任意一條邊e∈E都屬于一種特定類型邊的集合R:t(e)∈R。

文獻信息網(wǎng)絡是典型的異構信息網(wǎng)絡，它包含了三種不同對象類型:作者(A)、論文(P)、會議(C)，同時包含兩種類型的邊:作者撰寫文章，文章發(fā)表在會議上。值得注意的是，在其他的應用場景中，可能涵蓋類型為術語(V)的對象以及文章涉及到某個術語的邊，但本文工作主要針對會議上文章的相關性，所以在圖1中并未展示術語類型的對象。具體的文獻信息網(wǎng)絡如圖1所示。

圖1 文獻信息網(wǎng)絡Fig．1 Bibliographic information network

定義2 元路徑［4］。元路徑P是定義在網(wǎng)絡G上的一種基礎路徑，如:，表示了從類型T1到類型Tl+1的復合關系R，即R=R1。R2?！?。Rl，其中。表示定義在關系上的復合操作。

圖2中列出了文獻信息網(wǎng)絡中典型的元路徑，具體地，元路徑實例則如表1所示。值得注意，本文只用到了“APCPA”元路徑進行計算。

表1 文獻信息網(wǎng)絡中的元路徑實例Tab．1 Instances of meta paths in bibliographic information network

圖2 元路徑Fig．2 Meta paths

2．2 語義特征向量

定義3 語義特征向量，是指利用神經(jīng)網(wǎng)絡語言模型對文本信息進行特征提取，從而將任意文本映射成特征向量(feature vector)的形式。具體地可以表示為:

v= ［v1，v2，…，v(k－1)，vk］

其中k代表向量的維度。在本文中使用Doc2Vec［17］神經(jīng)網(wǎng)絡語言模型對文本信息進行特征提取。

定義4 語義特征相似度。在文獻信息網(wǎng)絡中，語義特征相似度采用余弦相似度對發(fā)表在同一個會議上的論文標題集合特征向量進行計算。具體如式(1)所示:

N最大值，cos()表示余弦相似度，×代表笛卡爾積。由于余弦相似度的取值范圍在［－1，1］內(nèi)，不便于后續(xù)的計算，因此本文對式(1)進行歸一化，具體如式(2)所示:

具體的算法描述見算法2。

2．3 相似性

定義5 相似性。給定對象a1和對象a2，利用文獻信息網(wǎng)絡語義特征可以定義二者之間的相似性，具體如式(3):

其中:|C|表示會議的數(shù)量，pa1～a2表示從對象a1出發(fā)在滿足元路徑的前提下到對象a2的路徑實例，Pc為定義在會議c上元路徑代表作者a發(fā)表在會議c上所有論文標題的特征向量集合。

3 文獻信息網(wǎng)絡語義特征提取

本文提出的基于文獻信息網(wǎng)絡語義特征的相關性搜索主要分為兩個步驟:1)文獻信息網(wǎng)絡語義特征提取;2)使用步驟1)中得到的文獻信息網(wǎng)絡的語義特征進行相似性搜索。接下來詳細闡述如何從大規(guī)模的文獻信息網(wǎng)絡中提取語義特征。

本文采用的數(shù)據(jù)集是目前公認的 DBLP“4-area dataset”［23］，該數(shù)據(jù)集提供了數(shù)據(jù)庫、數(shù)據(jù)挖掘、機器學習和信息檢索4個領域頂級會議上所有文章的相關信息。而通常文章標題是對文章主要內(nèi)容的精簡概括，涵蓋文章大部分的語義信息，因此標題信息可以作為信息網(wǎng)絡的重要特征。我們工作的重點則是對標題進行語義特征提取，從而利用該特征衡量文章間的相關性。

在語義特征提取過程中，本文采用目前較為成熟的Doc2Vec算法。該算法的核心是PV-DM(Distributed Memory of Paragraph Vectors)模型［17］，其結構如圖3所示。對于每一個標題，它均可以通過PV-DM模型被映射成一個可以唯一表示的特征向量。PV-DM模型采用交叉訓練的方式，具體步驟可分為以下兩個階段:1)訓練階段，訓練模型得到詞向量矩陣W，Softmax權重矩陣U，偏置向量b和標題向量矩陣D。2)推理階段，如果發(fā)現(xiàn)新的標題文本，則在D中添加相應的列，在保持W、U、b不變的情況下，對D采用梯度下降法訓練。

圖3 PV-DM模型Fig．3 PV-DM model

算法1給出了使用Doc2Vec算法在文獻信息網(wǎng)絡中語義特征提取的詳細過程。它的主要思想是根據(jù)輸入的文獻標題信息，生成特征向量集合并輸出。

算法1 文獻信息網(wǎng)絡語義特征提取。

輸入 文獻信息網(wǎng)絡G;

輸出 文獻信息網(wǎng)絡語義特征向量集合V，Doc2Vec模型M。

2) P←all papers in G;

3) M←train Doc2Vec model with P;

4) for each p∈P do

5) v←M(p); //transform paper using model into vector

6) V← V∪{v}; //update V with element v

7) end for

8) return V，M

算法1的流程具體可以分為3個步驟:1)遍歷文獻信息網(wǎng)絡，得到文章標題集合;2)將得到的文章標題輸入到Doc2Vec算法中進行訓練，得到最終模型M;3)利用模型M對屬于文章標題集合中的每一個標題進行特征提取，生成特征向量并輸出。

算法1將文獻信息網(wǎng)絡中的文章標題轉(zhuǎn)換為特征向量集合，方便后續(xù)的語義特征相似性計算。算法1是本文進行文獻網(wǎng)絡語義特征相關性搜索的基礎。

4 基于文獻信息網(wǎng)絡語義特征的相似性搜索

4．1 VPSim算法框架

基于算法1得到的文章特征向量，本文設計了基于文獻信息網(wǎng)絡語義特征的相似性搜索算法VPSim算法。該算法在考慮了元路徑“APCPA”的基礎上，同時也考慮了文章標題攜帶的語義信息對挖掘結果的影響。設想，有些作者在同一個會議上發(fā)表了文章，但是文章的研究方向可能存在很大的區(qū)別，如圖挖掘、序列模式挖掘等。以往的工作僅僅考慮了元路徑對作者相似性的影響，但忽略了文章本身內(nèi)容也會對搜索相似的作者產(chǎn)生一定的影響。

同時，不同的作者在同一會議上發(fā)表文章的數(shù)目可能不統(tǒng)一，如何更為準確地計算兩個作者間文章的相關性需要定義統(tǒng)一的規(guī)范。為此，本文設計了算法2來解決此問題。

算法2 作者在會議c上發(fā)表所有文章的語義相似度計算 VSim(Vp1，Vp2)。

輸入 作者a1在會議c上發(fā)表的論文集合p1對應的向量集合Vp1，作者a2在會議c上發(fā)表的論文集合p2對應的向量集合Vp2;

輸出 作者a1、a2在會議c上的語義相似度s。

10)return s

算法2主要是計算任意兩名作者在同一會議c上發(fā)表的所有文章集合的語義相似度。步驟7)提到的sort函數(shù)采用降序排列，步驟8)的表示取p1和p2集合元素個數(shù)的最小值，步驟9)表示對前 k 個元素求和。

通過算法2計算出作者在會議上發(fā)表文章的語義相似度，根據(jù)式(2)可知，語義相似度的值表示兩位作者在會議上發(fā)表的文章越相似，基于算法2并結合式(3)本文設計了VPSim算法對文獻信息網(wǎng)絡進行相似性搜索。

算法3 VPSim算法框架。

輸入 文獻信息網(wǎng)絡G，參數(shù)k，網(wǎng)絡語義特征向量集合V，查詢作者a;

輸出 top-k相似作者R。

17) sum2←sum2+pNuma*pNuma+pNuma'*pNuma';

18) end for

19) update simList with(sum1/sum2);

20)end for

21)sort(simList);

22)R ← simList．topK(k);

23)return R;

算法3給出了VPSim算法的基本框架。算法3主要是從大量的文獻信息網(wǎng)絡對給定的查詢作者進行相似性搜索，并按照相似度對全部候選作者集合進行降序排序，最后輸出top-k相似作者集合，完成相似性搜索。由于算法3處理對象為文獻信息網(wǎng)絡中所有作者，因此進行相似性搜索速度較慢，不利于實際應用，在4．2節(jié)中給出了帶剪枝策略的VPSim算法。

4．2 VPSim 算法

分析算法3可知，VPSim算法在查找文章對應的特征向量以及計算候選作者與查詢作者之間相似度時會耗費大量計算開銷，尤其當候選作者的規(guī)模增加時，執(zhí)行效率會極大降低。主要原因在于文獻信息網(wǎng)絡規(guī)模通常較大，即存在大量的候選作者。因此，本文基于如下觀察設計了針對候選作者集合的剪枝策略。

定理1 在文獻信息網(wǎng)絡中，對任意作者a，C(a)表示所有與a通過“作者－文章－會議”路徑連通的會議的集合，簡寫為“APC”即C(a)={c∈C|-APC路徑連通c和a}，如果P(a)∩P(a')=，那么作者a與作者a'必定不相似。

證明 用反證法證明。若作者a與作者a'相似，那么他們之間必然存在一條滿足APC的路徑實例通過會議節(jié)點C使得作者a與作者a'連通。反之，若C(a)∩C(a')=，即不存在任意一個滿足APC路徑的會議使得作者a與作者a'關聯(lián)，那么兩個作者必定不相似。

根據(jù)定理1，本文設計了剪枝策略。算法4給出了帶剪枝策略的VPSim算法。

算法4 VPSim算法

輸入 文獻信息網(wǎng)絡G，參數(shù)k，網(wǎng)絡語義特征向量集合V，查詢作者a。

輸出 top-k相似作者R。

算法4在算法3的基礎上增加了對候選作者集合元素的剪枝策略，主要思想是在計算查詢作者與候選作者相似度之前判斷當前候選作者與查詢作者所發(fā)表文章的會議是否有交集，如果沒有交集則直接將當前候選作者剪掉，如果有交集則繼續(xù)計算當前候選作者與查詢作者之間的相似度。

5 實驗

5．1 實驗環(huán)境

本文設計VPSim算法使用Python語言實現(xiàn)，Python版本為 3．5，所有實驗均在配置為 AMD FX-8300，3．30 GHz CPU，8 GB內(nèi)存，120 GB+1 TB硬盤，Windows 10操作系統(tǒng)的PC上完成。

5．2 數(shù)據(jù)集與相關參數(shù)

實驗數(shù)據(jù)采用真實世界中 DBLP的“4-area dataset”(http://web．cs．ucla．edu/～ yzsun/data/)。該數(shù)據(jù)集包括來自于4個不同研究領域的20個會議，5 000位作者和28 569篇論文。實驗數(shù)據(jù)集具體特征如表2所示。需要說明的是，同一位作者可能會同時在不同領域發(fā)表論文，所以不同領域的作者數(shù)量總和會大于作者總數(shù)5000。

表2 實驗數(shù)據(jù)集Tab．2 Experimental data set

在實驗中涉及的Doc2Vec算法采用gensim機器學習庫中的接口實現(xiàn)，訓練Doc2Vec模型使用到的具體參數(shù)如表3所示，在沒有特殊說明時，VPSim算法執(zhí)行參數(shù)默認值為:k=10，即在文獻信息網(wǎng)絡中搜索出與查詢作者相似度最高的10個作者。

表3 Doc2Vec訓練參數(shù)Tab．3 Training parameters of Doc2Vec

5．3 語義特征向量搜索有效性驗證

利用“4-area dataset”中28 569篇學術論文的標題使用Doc2Vec模型進行訓練，并使用該模型將每一篇學術論文的標題轉(zhuǎn)換成特征向量。然后，利用算法2對某一篇學術論文標題進行搜索，輸出與之語義最為相似的top-10學術論文標題，并對實驗結果進行分析，驗證算法2的有效性。

由表4可以看出，與文章編號為“13624”相似的top-10的文章標題中都包含有“XML”字樣，另外單詞“query”也是頻繁出現(xiàn)。從字面含義來看，10個標題表示的內(nèi)容也大體相同，由此可以證明，提出的算法2是有效的，它能夠通過特征向量搜索到與查詢文章最為近似的文章集合，而且，文章間的相似值對以后的研究也具有一定的參考價值。

5．4 VPSim算法有效性驗證

我們在APCPA路徑下分別使用PathSim算法和VPSim算法對給定的查詢作者進行搜索，計算出與其最為相似的top-10作者，并對實驗結果進行比較分析，從而驗證VPSim算法的有效性。

表4 與編號為“13624”文章相似的top-10文章Tab．4 Top-10 most similar articles to the number“13624”

觀察表5可以看出，PathSim和 VPSim算法在搜索與“Jiawei Han”作者最為相似的top-10的作者在結果比較接近，在執(zhí)行VPSim算法搜索出的結果中只有一名作者(Jian Per)沒有出現(xiàn)在PathSim算法搜索的結果列表中;VPSim計算前八名的結果與PathSim計算的結果完全一致，其余作者總體排序相近，然而在計算出的相似度有細微差別。原因在于PathSim算法只是簡單基于元路徑“APCPA”計算得出的相似度，只是考慮了在同一個會議上發(fā)表了文章的作者是相似的，并未考慮作者發(fā)表的文章之間是否相似，即作者的研究領域是否相似。由于同一個會議中可能會收錄從事不同研究方向作者的文章，因此傳統(tǒng)的PathSim算法存在著不足。而本文提出的VPSim算法在考慮“APCPA”元路徑的同時也將文章間的語義相似度考慮了進來，因此計算出的結果更接近作者真實的情況。通過表5可以得出結論，VPSim算法是有效的。

表5 APCPA路徑下PathSim與VPSim計算的和“Jiawei Han”相似的top-10作者Tab．5 Top-10 most similar authors to“Jiawei Han”under meta path APCPA between PathSim and VPSim

在PathSim搜索到與“Jiawei Han”最為相似的top-10的作者中有“Nick Koudas”，而在VPSim算法搜索的結果列表中不包含“Nick Koudas”卻增加了“Jian Pei”。通過對比分析“Jiawei Han”“Nick Koudas”和“Jian Pei”三位作者在會議上發(fā)表的文章，可以發(fā)現(xiàn):1)三位作者的文章均都屬于數(shù)據(jù)庫、數(shù)據(jù)挖掘領域;2)“Nick Koudas”共發(fā)表了79篇文章，在這79篇文章的標題中共有11篇文章提到了“XML”技術;3)“Jian Pei”共發(fā)表了70篇文章，其中只有1篇文章提到了“XML”技術;4)“Jiawei Han”共發(fā)表了168篇文章，其中沒有文章涉及到“XML”技術。因此可以得出結論，雖然三位作者都屬于數(shù)據(jù)庫、數(shù)據(jù)挖掘領域，但是他們研究方向略有區(qū)別，經(jīng)過對他們發(fā)表的文章進行比較，本文認為“Jian Pei”與“Jiawei Han”更加相似。

5．5 執(zhí)行效率

本節(jié)實驗主要驗證了VPSim算法的執(zhí)行效率。本文對提出的兩種算法不包含剪枝策略的VPSim-baseline算法和包含剪枝策略的VPSim-pruning算法的查詢時間進行了對比。

圖4給出了不帶剪枝策略的VPSim算法，記為VPSimbaseline與帶剪枝策略的VPSim算法，記為VPSim-pruning的效率對比，本文隨機抽取了10%的數(shù)據(jù)集，即500個作者進行查詢，圖中橫、縱坐標分別表示 VPSim-baseline算法和VPSim-pruning算法執(zhí)行500次查詢的執(zhí)行時間。圖中的直線則為使用一次函數(shù)得到的擬合曲線。由圖4可以看出本文設計的剪枝策略是有效的，使得執(zhí)行效率提高了約15．5%。

圖4 VPSim-baseline與VPSim-pruning效率對比Fig．4 VPSim-baseline vs．VPSim-pruning execution time

表6展示了VPSim-pruning算法與PathSim算法執(zhí)行效率的對比情況。該實驗列出了兩種算法分別執(zhí)行500次隨機查詢所需執(zhí)行時間的統(tǒng)計特征。觀察表6可以看出，VPSimpruning算法的執(zhí)行效率略低于PathSim算法，原因在于VPSim-pruning算法考慮了文獻信息網(wǎng)絡中標題的語義相似度，然而標題語義的特征向量文件較大，在執(zhí)行和計算過程中會花費時間消耗，因此VPSim-pruning算法進行相似性搜索所花費的時間較長。同時，表6給出了兩種算法執(zhí)行查詢所需時間的最大值，可以發(fā)現(xiàn)相差較大。分析原因如下，當作者發(fā)表的論文數(shù)量過多時，算法查找和計算所需要的時間也會相應地增加。然而VPSim-pruning算法執(zhí)行時間的最小值要遠低于PathSim算法，主要是由于本文設計的剪枝策略起到了作用。綜合表6的結果可以看出，雖然VPSim-pruning算法的執(zhí)行效率略有降低，但時間開銷在可控的范圍內(nèi)，而且由于其考慮了文獻信息網(wǎng)絡中語義的相似性，從而極大地提高了相似性搜索的結果的準確性。

表6 VPSim-pruning算法與PathSim算法執(zhí)行效率對比Tab．6 Execution time of VPSim-pruning and PathSim

圖5則展示了在500次查詢中，通過剪枝策略剪掉的候選作者的數(shù)量，其中橫坐標表示剪枝作者的數(shù)量區(qū)間，縱坐標則表示符合該數(shù)量區(qū)間內(nèi)的查詢個數(shù)。分析圖5可知，在500次查詢實驗中，VPSim-pruning算法最多可以剪掉4716個候選作者，最少也可以剪掉283個候選作者，平均可以剪枝掉2685個作者，而且大部分的剪枝數(shù)量在(2 500，3 200］區(qū)間內(nèi)。雖然VPSim-pruning可以用來降低候選作者的規(guī)模，提高查詢速度，但由于VPSim-pruning先需要從28 569篇論文生成的特征向量集合中計算文章的相似度，所以也花費了一定資源，導致雖然剪枝掉大量的無關作者，但執(zhí)行效率提升幅度略小。

圖5 VPSim-pruning算法剪枝效果統(tǒng)計Fig．5 Pruning results of VPSim-pruning

圖6展示了VPSim算法在維度不同的特征向量中查詢500次的平均執(zhí)行時間折線圖。由圖6中的結果可以看出VPSim的執(zhí)行時間隨著向量維度的變大而增加。但是當特征向量的維度過低時，特征向量不能將文章標題的特征完全提取出來，從而導致搜索結果不準確，而當特征向量維度過大時，向量中會包含大量的冗余信息，從而降低搜索的效率。經(jīng)過實驗可知，當特征向量維度取值為128時，既能將文章標題特征準確地提取出來，同時不會降低算法的搜索效率。

圖6 VPSim算法在不同特征向量維度下查詢時間折線圖Fig．6 Execution time of VPSim under different feature vector dimensions

5．6 可擴展性實驗

為了驗證VPSim算法的可擴展性，本文設計了隨節(jié)點數(shù)目變化對VPSim算法執(zhí)行效率影響的實驗。在圖7的實驗中，以作者節(jié)點數(shù)目為變量，可以看出隨著節(jié)點數(shù)目的增加兩個算法的執(zhí)行時間大致呈現(xiàn)相同規(guī)律變化，即線性增長，而且VPSim-pruning算法的執(zhí)行時間始終要低于VPSim-baseline算法，由此可以看出帶剪枝策略的VPSim-pruning算法可以高效地處理大規(guī)模文獻信息網(wǎng)絡的搜索查詢。

6 結語

隨著研究學者對異構信息網(wǎng)絡的認識不斷加深，如何基于其有效地開展數(shù)據(jù)挖掘工作成為研究的熱點。目前，在異構信息網(wǎng)絡進行節(jié)點相似性搜索的工作，為我們提供了一種新的研究方向。如何從大量的文獻信息網(wǎng)絡中抽取特征以及如何基于語義特征設計高效的相似性搜索算法輔助完成聚類、推薦等特定任務具有重要意義。然而目前工作僅考慮了元路徑的組合，并未考慮節(jié)點本身的語義特征，降低了搜索結果的準確性。此外，候選節(jié)點的規(guī)模也會影響相似性搜索算法的執(zhí)行效率，也會耗費大量的計算代價。針對這些問題，本文提出了VPSim算法，同時設計了高效的剪枝策略。最后在真實數(shù)據(jù)集上驗證了VPSim算法的有效性、執(zhí)行效率和可擴展性。

圖7 節(jié)點數(shù)目對VPSim算法的影響Fig．7 Execution time of VPSim under different numbers of nodes

下一步，將考慮進一步提取文獻信息網(wǎng)絡中更多具有代表性的語義特征，如摘要、文章內(nèi)容等，從而更全面、更真實地評價作者之間的相似性;同時，還將根據(jù)需要，考慮結合不同的元路徑，進而從不同角度分析作者間關系;此外，還考慮將VPSim算法與其他應用場景結合，如影視、醫(yī)學等，以便在實際的應用中進一步驗證VPSim的有效性。