2024年基于稀疏矩陣面向論文索引排名的啟發(fā)式算法

第頁(yè)2024年基于稀疏矩陣面向論文索引排名的啟發(fā)式算法總結(jié)全文，并給出了本課題將來(lái)的研究?jī)?nèi)容和方向。

1理論基礎(chǔ)與研究背景

網(wǎng)頁(yè)排名算法的改進(jìn)包括：基于主題敏感的研究[9-10]、基于主題漂移的研究[11]、基于自適應(yīng)方法的研究[12]、基于網(wǎng)頁(yè)縮放更新規(guī)則的研究[13-14]、基于無(wú)超鏈接情況下的研究[15]等。本文所關(guān)注的排名算法均是假定以網(wǎng)頁(yè)之間的鏈接關(guān)系為基礎(chǔ)的，經(jīng)典的算法有PageRank算法[2]、HITS算法[5]以及SALSA（StochasticApproachforLinkStructureAnalysis）算法[16]等。這些算法都是基于網(wǎng)絡(luò)鏈接的結(jié)構(gòu)關(guān)系，而與網(wǎng)頁(yè)內(nèi)的文本內(nèi)容無(wú)關(guān)[17]。

1.3SALSA鏈接分析算法

SALSA算法的初衷希望能夠結(jié)合PageRank算法和HITS算法兩者的主要特點(diǎn)，既可以利用HITS算法與查詢相關(guān)的特點(diǎn)，也可以采納PageRank的“隨機(jī)游走模型”[10]。PageRank算法與HITS算法均利用了特征向量作為收斂性依據(jù)，在文獻(xiàn)[19]中詳細(xì)敘述了它們的不同點(diǎn)。實(shí)際應(yīng)用中，用戶大多數(shù)情況下是向前瀏覽網(wǎng)頁(yè)，但是也會(huì)回退瀏覽網(wǎng)頁(yè)?；谏鲜鲋庇X(jué)知識(shí)，Lempel和Moran提出了SALSA算法[16]，具體計(jì)算迭代細(xì)節(jié)在文獻(xiàn)[10，16]中有明確說(shuō)明。

本文研究的問(wèn)題是論文排名。由于論文間的引用關(guān)系與網(wǎng)頁(yè)間的鏈接關(guān)系相似，所以利用網(wǎng)頁(yè)排名算法的技術(shù)手段，來(lái)解決所關(guān)注的問(wèn)題。注意：由于論文發(fā)表存在先后關(guān)系，因此，論文引用關(guān)系形成的圖是拓?fù)鋱D，這點(diǎn)與網(wǎng)頁(yè)鏈接關(guān)系圖不同，這就導(dǎo)致了排名值傳遞有極大的方向性。

2基于稀疏矩陣與Hash索引技術(shù)的排名算法

本章將利用Hash索引技術(shù)減少稀疏矩陣對(duì)內(nèi)存的消耗，同時(shí)引入一種啟發(fā)式的策略來(lái)定義圖密集程度均衡值。最后，詳細(xì)描述面向論文索引排名的啟發(fā)式算法的實(shí)現(xiàn)。

2.1鏈接關(guān)系的稀疏矩陣表示

計(jì)算機(jī)算法永遠(yuǎn)是在時(shí)間與空間中權(quán)衡與妥協(xié)。第1章介紹了鄰接矩陣表示鏈接結(jié)構(gòu)的方法。但在實(shí)際中，一篇論文的引用論文數(shù)量是有限的，搜索得到的論文集所生成的鄰接矩陣極大且稀疏。如果不利用Hash索引技術(shù)，在2GB的內(nèi)存主機(jī)中，本文介紹的排名算法是處理不了表1后7行實(shí)驗(yàn)數(shù)據(jù)的。本節(jié)介紹的Hash索引技術(shù)表示稀疏矩陣的方法，就是用來(lái)緩解內(nèi)存空間有限性所帶來(lái)的問(wèn)題。

本文實(shí)驗(yàn)所用到的表示論文之間引用關(guān)系的數(shù)據(jù)格式如圖2所示。加載進(jìn)HashMap的數(shù)據(jù)結(jié)構(gòu)形式如圖3所示，不記錄論文之間沒(méi)有引用的0項(xiàng)。在搜索HashMap數(shù)據(jù)結(jié)構(gòu)的內(nèi)容時(shí)，可以用迭代器來(lái)進(jìn)行搜索。所以在每次更新某一篇論文的排名值時(shí)，只需要計(jì)算引用（映射）到這篇論文的那些論文的HashMap結(jié)構(gòu)的內(nèi)容就可以了。

注意，1.1節(jié)引入縮放因子所改進(jìn)的縮放網(wǎng)頁(yè)排名算法（PageRankScale）不能利用HashMap思想，因?yàn)樗鼘⑺蠳ij=0的項(xiàng)都變?yōu)楹苄〉闹?，以防止排名泄漏的情況。

2.2啟發(fā)式策略

論文引用關(guān)系形成的圖為有向圖，在有向圖中，設(shè)計(jì)啟發(fā)式策略的主要定義如下。

定義1圖的密集程度定義為D（density）：D=L/N。其中：L為論文間的引用鏈接數(shù)，N為總的論文節(jié)點(diǎn)數(shù)。D越大，則圖越密集；反之越稀疏。

定義2圖中有出度的節(jié)點(diǎn)的占比定義為ODR（OutDegreeRatio）：ODR=ODN/N。其中：ODN（OutDegreeNode）為有出度的論文節(jié)點(diǎn)數(shù)，N為總的論文節(jié)點(diǎn)數(shù)。

定義3圖密集程度均衡值IEV（IntensiveEquilibriumValue）：IEV=D×ODR。其中：D為圖的密集程度，ODR為圖中有出度的節(jié)點(diǎn)占比。在論文引用關(guān)系圖中，有些節(jié)點(diǎn)只有出度或只有入度，是圖當(dāng)中較為“劣質(zhì)”的節(jié)點(diǎn)，沒(méi)有緊密地連接到圖中其他的節(jié)點(diǎn)。沒(méi)有出度的節(jié)點(diǎn)會(huì)可能造成排名泄露的情況，排名算法的迭代次數(shù)將會(huì)有所變化?；谝陨显颍xIEV，在計(jì)算IEV時(shí)，考慮到有出度節(jié)點(diǎn)的占比，可以較全面地把握?qǐng)D的整體屬性，并保證IEV作為一個(gè)表示圖性質(zhì)的比值，單位為1。本文通過(guò)實(shí)驗(yàn)分析不同算法的迭代次數(shù)與所定義的IEV之間的關(guān)系。

2.3排名算法描述

算法1是論文排名算法的入口，可以在四種排名算法中選擇，得出相應(yīng)算法的迭代次數(shù)以及對(duì)應(yīng)算法每篇論文重新排名的次序以及排名值。在SALSA排名算法中，本文只進(jìn)行一次前向與后退更新，所以迭代次數(shù)始終為2。算法2是PageRank算法排名過(guò)程。注意并不排序所有的論文，只是排序所關(guān)注的被引頻次降序排序方式的檢索得到的前1000篇論文。算法3是HITS算法實(shí)現(xiàn)一次更新的偽代碼，主要進(jìn)行每篇論文中樞排名值（authority）和權(quán)威排名值（hub）的一次更新，在執(zhí)行HITS算法達(dá)到收斂后，綜述類文章的中樞排名值將會(huì)排名較高，因?yàn)榫C述類文章相當(dāng)于樞紐會(huì)被較多論文引用。排名算法判斷迭代收斂的依據(jù)是所有每篇論文的排名值一次更新前后相差均少于10E-6，即精度為10E-6，如HITSOnceUpdate（）方法。注意：在HITS算法中以每篇論文的權(quán)威排名值收斂作為迭代結(jié)束標(biāo)志。本節(jié)只介紹算法中比較有代表性的方法。另外本文介紹的SALSA沒(méi)有極限值的概念，即不存在算法迭代次數(shù)的討論，SALSA算法的實(shí)現(xiàn)要注意mapData集的雙向索引，具體實(shí)現(xiàn)方法請(qǐng)參照文獻(xiàn)[20]中的內(nèi)容。

算法1PapersRank（）。

3實(shí)驗(yàn)及其結(jié)果分析

這一節(jié)將分析實(shí)驗(yàn)結(jié)果。實(shí)驗(yàn)代碼可從文獻(xiàn)[20]中獲得。

3.1迭代次數(shù)與IEV的關(guān)系

Dataset1～Dataset3是為了描述本文實(shí)驗(yàn)所構(gòu)造的人工數(shù)據(jù)集。SogouT_Link為搜狗實(shí)驗(yàn)室提供的數(shù)據(jù)集，Link_First和Link_Second為SogouT_Link進(jìn)行的前后部分隨機(jī)拆分形成的數(shù)據(jù)集，Link_OddOver為進(jìn)行奇偶行拆分形成的數(shù)據(jù)集，這4個(gè)數(shù)據(jù)集增加了數(shù)據(jù)隨機(jī)性。recommended_system為在SCI數(shù)據(jù)庫(kù)輸入“recommendedsystem”后獲得的論文引用關(guān)系數(shù)據(jù)集；同理獲得“data_mining”。表中最后三列為選擇相應(yīng)的算法，“A1”代表PageRank，“A2”代表HITS，“A3”代表PageRankScale。

在圖4中，橫坐標(biāo)為圖密集程度均衡值IEV，縱坐標(biāo)為排名算法的迭代次數(shù)。

從圖4可看出，在小數(shù)據(jù)集上（Dataset1～Dataset3）呈現(xiàn)的規(guī)律是：隨著圖密集程度均衡值的增加，3種排名算法的迭代次數(shù)都相對(duì)增加。在大數(shù)據(jù)集上PageRank與HITS也基本呈現(xiàn)這樣的規(guī)律。另外，在引用鏈接數(shù)與節(jié)點(diǎn)數(shù)較多的圖中，PageRank與HITS的迭代次數(shù)都會(huì)很小，即在大規(guī)模數(shù)據(jù)的論文的排名中，迭代次數(shù)并不高。因?yàn)榕琶惴ǖ牡螖?shù)與有向圖的結(jié)構(gòu)有關(guān)，所以如果其他有向圖與本文分析的鏈接圖同構(gòu)，則有相同的迭代次數(shù)等性質(zhì)。

3.2基于SCI數(shù)據(jù)庫(kù)的數(shù)據(jù)集

以圖2介紹的論文引用形式作為實(shí)驗(yàn)數(shù)據(jù)的格式，采用唯一表示一篇文獻(xiàn)的方法是：用該論文的題目，去掉非英文字母以外的所有字符，并且統(tǒng)一轉(zhuǎn)換為小寫(xiě)的形式。利用正則表達(dá)式來(lái)寫(xiě)網(wǎng)絡(luò)爬蟲(chóng)可以非常容易得到想要的網(wǎng)頁(yè)信息[21]，獲得的文件格式為：

論文名論文被引論文信息的一條鏈接URL被引用頻次

本實(shí)驗(yàn)先暫定第1層搜索的論文數(shù)為1000；進(jìn)入某篇論文的被引論文集后，相當(dāng)于第2層，每篇論文爬取的被引用論文數(shù)為50。第1層的1000篇論文中有些被引頻次不足50，所以本應(yīng)得到的連接數(shù)為1000×50=50000個(gè)鏈接，實(shí)驗(yàn)只得到了46763個(gè)鏈接。

3.3參考文獻(xiàn)排名的實(shí)驗(yàn)結(jié)果與分析

圖5～6是應(yīng)用了PageRank排名算法，對(duì)“recommendedsystem”集文獻(xiàn)按照原排序方式（被引頻次降序）的前1000文章重新排名的結(jié)果。圖5、圖7、圖8的橫坐標(biāo)為某篇論文在原排序方式（被引頻次降序）中的排名次序（OriginalRank），縱坐標(biāo)為運(yùn)行不同排名方法（分別為PageRank、HITS、SALSA）后論文的排名值（RankValue）。以圖5為例分析，這1000篇論文的排名值整體呈緩慢的下降趨勢(shì)，這說(shuō)明在原排序方式中排名靠后的論文，PageRank排名值也較低。同時(shí)，這1000篇論文的排名值都在0.001附近，說(shuō)明論文引用關(guān)系圖中的排名值基本集中在這1000篇論文中，流動(dòng)到其他42770篇論文的排名值較少，這是因?yàn)樵谡撐囊面溄雨P(guān)系圖中，這1000篇論文多以入度節(jié)點(diǎn)的形式存在，而不一定有出度，所以排名值會(huì)慢慢流向這1000篇論文。在論文引用鏈接關(guān)系圖中，很多論文處于圖中的相同的地位，即出度結(jié)構(gòu)與入度結(jié)構(gòu)相同，所以這些論文的排名值是相同的。圖6的橫坐標(biāo)仍為排名次序，縱坐標(biāo)為不同排名方式重新排名次序（Rank），即在原排序方式中排名第一的論文，運(yùn)用了PageRank方式的論文排名算法后，在這1000論文中排名第300名。圖5中，在PageRank方式中排名值最高的論文名轉(zhuǎn)化處理后的形式是“theinternationalassociationforthestudyoflungcancerinternationalstagingprojectonlungcancer”，排名值為0.00684258624628742。由圖6觀察得到論文重新排名的趨勢(shì)與原排序方式擬合，呈上升趨勢(shì)，這與圖5同樣證明了這個(gè)理論。但圖6中PageRank方式走勢(shì)高低差距較大，說(shuō)明了PageRank方式的論文排名結(jié)果與原排名結(jié)果還是有一定差距的。注意：在HITS方式（見(jiàn)圖7）排名算法分析中，一篇論文有權(quán)威排名值也有中樞排名值，本文均以這篇論文的權(quán)威（authority）排名值（RankValue）進(jìn)行重排名，這是因?yàn)檎撐牡臋?quán)威排名值才真實(shí)反映其在關(guān)鍵領(lǐng)域具體技術(shù)方便的價(jià)值，所以圖7縱坐標(biāo)為權(quán)威排名值。

在這三種論文排名算法的比較中，就論文排名值的比較而言，HITS方式（圖7）論文之間的排名值差距較大，PageRank方式（圖5）次之，SALSA（圖8）最小，SALSA方式排名值平穩(wěn)過(guò)渡，與原被引頻次降序排列比較擬合。就論文重排名次序比較而言，PageRank方式論文的排名次序與原排序方式擬合程度較差，HITS方式較好，SALSA方式最好。由于SALSA方式的論文排名算法，不更新到極限值，運(yùn)行時(shí)間也較短，所以SALSA方式的論文排名算法比較適合文后參考文獻(xiàn)的排名。

4結(jié)語(yǔ)

本文基于經(jīng)典的網(wǎng)頁(yè)排名算法，研究了SCI數(shù)據(jù)庫(kù)論文檢索的有效方式，主要考慮到檢索到的論文之間的相關(guān)性。介紹了利用Hash索引技術(shù)減少排名算法對(duì)內(nèi)存的消耗，并研究了排名算法的迭代次數(shù)與IEV的關(guān)系。在實(shí)驗(yàn)部分，分析不同的論文索引排名的啟發(fā)式算法對(duì)實(shí)驗(yàn)數(shù)據(jù)的排名結(jié)果的影響，并給出評(píng)價(jià)。最后關(guān)于如何唯一標(biāo)識(shí)一個(gè)作者及確定這個(gè)作者寫(xiě)過(guò)某篇文章需要更多的研究。

參考文獻(xiàn)：

[1]PAGEL，BRINS，MOTWANIR，etal.ThePageRankcitationranking：bringingordertotheWeb[EB/OL].[20241010].http：///422/1/1999-66.pdf.

[2]LANGVILLEAN，MEYERCD.GooglesPageRankandbeyond：thescienceofsearchenginerankings[M].Princeton：PrincetonUniversityPress，2024：1-4.

[3]QIUZ，F(xiàn)UT，WANGX.Developitsownsearchengine[M].2nded.Beijing：PeoplesPostsandTelecommunicationsPress，2024：4-6.（邱哲，符滔滔，王學(xué)松.開(kāi)發(fā)自己的搜索引擎[M].2版.北京：人民郵電出版社，2024：4-6.）

[4]BRINS，PAGEL.TheanatomyofalargescalehypertextualWebsearchengine[J].ComputerNetworksandISDNSystems，1998，30（1）：107-117.

[5]KLEINBERGJM.Authoritativesourcesinahyperlinkedenvironment[J].JournaloftheACM，1999，46（5）：604-632.

[6]MIHALCEAR，TARAUP，F(xiàn)IGAE.PageRankonsemanticnetworks，withapplicationtowordsensedisambiguation[C]//COLING2024：Proceedingsofthe20thInternationalConferenceonComputationalLinguistics.NewYork：ACMPress，2024：1126.

[7]ESULIA，SEBASTIANIF.PagerankingWordNetsynsets：anapplicationtoopinionmining[EB/OL].[20241010].http：///detail/waxdhgj/8428995.（萬(wàn)曉松.網(wǎng)