基于P-Rank的RDF有向圖的分布式存儲(chǔ)

冷泳林，申 華，魯富宇

(1.渤海大學(xué) a.信息科學(xué)與技術(shù)學(xué)院;b.教務(wù)處，遼寧錦州 121000;2.鞍山師范學(xué)院數(shù)學(xué)與信息科學(xué)學(xué)院，遼寧鞍山 114005)

RDF(resource description framework)資源描述框架用于表達(dá)資源的元數(shù)據(jù)信息，實(shí)現(xiàn)了在萬維網(wǎng)上交換元數(shù)據(jù)的功能。RDF數(shù)據(jù)的表述方式有兩種形式:一種是使用三元組的形式，即〈subject，predicate，object〉，表示主語(subject)的屬性(predicate)對(duì)應(yīng)的值是(object);另一種是以圖的形式描述，其中主語(subject)和賓語(object)分別表示有向邊的兩個(gè)頂點(diǎn)，predicate表示由subject指向object的有向邊［1］。

隨著語義網(wǎng)的迅猛發(fā)展，RDF數(shù)據(jù)呈海量增長(zhǎng)趨勢(shì)，單機(jī)存儲(chǔ)和管理RDF數(shù)據(jù)已經(jīng)成為RDF數(shù)據(jù)發(fā)展的瓶頸。而當(dāng)采用分布式存儲(chǔ)方式解決RDF數(shù)據(jù)可擴(kuò)展問題時(shí)，基于關(guān)系和對(duì)象等數(shù)據(jù)模型的傳統(tǒng)管理方式難以同時(shí)滿足低數(shù)據(jù)冗余與高查詢性能這兩個(gè)要求。若以圖方式管理RDF數(shù)據(jù)則不僅可以避免RDF邏輯數(shù)據(jù)模型與物理數(shù)據(jù)模型之間的轉(zhuǎn)換，而且可利用成熟的圖算法優(yōu)化RDF 數(shù)據(jù)查詢［2-5］。

基于圖模式RDF數(shù)據(jù)分布式存儲(chǔ)的一項(xiàng)關(guān)鍵技術(shù)是圖的分割技術(shù)。P-Rank(penetrating rank)算法是針對(duì)SimRank相似度過分依賴入鄰點(diǎn)結(jié)構(gòu)的情況，由 Zhao 等［6］在 SimRank［7］基礎(chǔ)上提出的度量圖節(jié)點(diǎn)相似性的改進(jìn)算法。當(dāng)前P-Rank己成為一種重要的結(jié)構(gòu)相似度度量模型，被廣泛地應(yīng)用在協(xié)同過濾、網(wǎng)絡(luò)圖聚類、KNN查詢等數(shù)掘挖掘領(lǐng)域。本文首先利用P-Rank算法對(duì)RDF圖節(jié)點(diǎn)進(jìn)行相似性度量，然后利用AP(afinity propagation clustering)聚類算法根據(jù)節(jié)點(diǎn)間相似度對(duì)圖節(jié)點(diǎn)聚類，最后根據(jù)聚類結(jié)果實(shí)現(xiàn)RDF有向圖的分布式存儲(chǔ)［8］。

1 相關(guān)理論和技術(shù)

1.1 SimRank基本思想

SimRank是一種在有向網(wǎng)絡(luò)中度量節(jié)點(diǎn)相似性的方法，其基本思想是:如果兩個(gè)對(duì)象被相似的對(duì)象引用，則這兩個(gè)對(duì)象也是相似的。

給定圖G=(V，E)，V表示節(jié)點(diǎn)的集合，E表示邊的集合。對(duì)于任意節(jié)點(diǎn)v∈V，用 I(v)表示對(duì)象v的入鄰接點(diǎn)集合表示集合I(v)中的元素個(gè)數(shù)，關(guān)于SimRank的節(jié)點(diǎn)間相似度計(jì)算公式定義如下:

其中c是阻尼因子。為了防止式(1)中出現(xiàn)除以0的現(xiàn)象，SimRank規(guī)定當(dāng)=0或者=0 時(shí)，s(u，v)=0。

由于SimRank在度量節(jié)點(diǎn)相似性時(shí)只考慮了節(jié)點(diǎn)的入邊，存在大量節(jié)點(diǎn)之間相似性為0的情況，因此在對(duì)相似度結(jié)果進(jìn)行聚類時(shí)會(huì)產(chǎn)生大量的離群點(diǎn)［9-11］。

1.2 P-Rank基本思想

P-Rank算法是針對(duì)SimRank相似度過分依賴入鄰點(diǎn)結(jié)構(gòu)的不足，由Zhao等在SimRank基礎(chǔ)上提出的度量圖節(jié)點(diǎn)相似性的改進(jìn)算法。P-Rank的基本思想包含兩重含義:

1)如果兩個(gè)對(duì)象被相似對(duì)象引用，那么這兩個(gè)對(duì)象相似;

2)如果兩個(gè)對(duì)象引用了相似的對(duì)象，則這兩個(gè)對(duì)象相似。

其中:λ∈［0，1］表示權(quán)重系數(shù);Cin與 Cout∈(0，1)分別表示入邊和出邊的阻尼因子;當(dāng) I(u)或I(v)=φ時(shí)，入度部分為0;當(dāng)O(u)或 O(v)=φ時(shí)，出度部分為0;當(dāng)I(u)或I(v)=φ，并且O(u)或 O(v)= φ 時(shí)，s(u，v)=0。

1.3 P-Rank算法描述

P-Rank采用迭代算法:

步驟1 輸入 G=(V，E)，λ，C，k。

步驟2 初始化矩陣 s0(u，v)，當(dāng) u=v時(shí)，s0(u，v)=1;否則s0(u，v)=0。

步驟3 迭代執(zhí)行中，當(dāng)u≠v時(shí)，

當(dāng)u=v時(shí)，

直到達(dá)到指定迭代次數(shù)k。

步驟4 輸出相似度矩陣s(u，v)。

這里，sk+1(u，v)表示對(duì)象u，v之間在第k+1次迭代時(shí)的P-Rank相似度。當(dāng)k→∞時(shí)，迭代序列{sk(u，v)}以單調(diào)遞減的方式趨向于P-Rank的精確解s(u，v)。該算法參數(shù)比較典型的賦值是λ =0.5，C=0.8，k=ln(n)。

2 AP聚類算法

聚類分析是數(shù)據(jù)挖掘的重要手段，用來發(fā)現(xiàn)數(shù)據(jù)潛在信息。聚類是將數(shù)據(jù)集合劃分成多個(gè)類簇，同一類簇中的數(shù)據(jù)具有較高的相似度，不同類簇的數(shù)據(jù)之間具有最大程度的差異性。

信息傳遞聚類算法(afinity propagation clustering，AP聚類)是一種基于信息傳遞的高效聚類算法，由 Frey和Dueck提出［12］。AP聚類主要通過消息傳遞來逐步確定高質(zhì)量聚類中心集合，即迭代更新吸引度矩陣R=［r(i，k)］與歸屬度矩陣A=［a(i，k)］，滿足所有頂點(diǎn)到最近的聚類中心的相似度之和最大的要求，其更新規(guī)則如下:

1)用歸屬度矩陣與相似度矩陣S=［s(i，k)］更新吸引度矩陣R:

2)用吸引度矩陣R更新歸屬度矩陣A:

吸引度矩陣R和歸屬度矩陣A更新的結(jié)果都是由迭代過程中當(dāng)前的Ri和Ai與上一步迭代值Ri-1和Ai-1通過阻尼因子lam進(jìn)行加權(quán)得到。加權(quán)公式為:

其中:阻尼因子lam是聚類過程中為避免振蕩引入的一個(gè)重要參數(shù)，當(dāng)AP聚類算法發(fā)生振蕩而不能收斂時(shí)，增大lam可以消除振蕩，收斂算法。

相似度矩陣S對(duì)角線上的值s(i，i)表示節(jié)點(diǎn)i被選擇為聚類中心的傾向性，即偏向參數(shù)p。p越大，表示節(jié)點(diǎn)i作為聚類中心的可能性就越大，因?yàn)槌跏紩r(shí)，AP聚類算法將每一個(gè)節(jié)點(diǎn)都看做是潛在的聚類中心，因此所有節(jié)點(diǎn)具有相同的p值。通常情況下，p值越大，聚類輸出的簇?cái)?shù)越多;反之越小［13-15］。

3 實(shí)驗(yàn)分析

3.1 數(shù)據(jù)集和實(shí)驗(yàn)環(huán)境

本文選擇數(shù)據(jù)集 DBLP［16］作為實(shí)驗(yàn)數(shù)據(jù)，數(shù)據(jù)集中包括2555篇文章和6101個(gè)引用關(guān)系(表1)。數(shù)據(jù)集涉及計(jì)算機(jī)領(lǐng)域中的10個(gè)方向，通過對(duì)數(shù)據(jù)的處理，形成10個(gè)RDF子圖和1個(gè)RDF匯總圖，有向圖中頂點(diǎn)數(shù)和邊數(shù)如表1所示。實(shí)驗(yàn)環(huán)境為:Inter i3處理器，4GB內(nèi)存，Windows XP操作系統(tǒng)，C++編程環(huán)境。

表1 RDF有向圖基本信息

3.2 實(shí)驗(yàn)分析

為驗(yàn)證P-Rank算法度量RDF有向圖節(jié)點(diǎn)相似性對(duì)數(shù)據(jù)分割的性能影響，本文將P-Rank算法同SimRank算法進(jìn)行對(duì)比。實(shí)驗(yàn)中算法權(quán)重系數(shù)λ的值是0.5，阻尼因子C的值是0.8，為比較兩種度量方法，實(shí)驗(yàn)從3個(gè)方面衡量聚類效果。

3.2.1 相似度節(jié)點(diǎn)對(duì)數(shù)量

對(duì)P-Rank和SimRank產(chǎn)生的相似度矩陣中節(jié)點(diǎn)對(duì)的取值進(jìn)行統(tǒng)計(jì)。如果相似度節(jié)點(diǎn)對(duì)s(u，v)=0，表示節(jié)點(diǎn)u和v之間不存在相似性，否則存在相似性。

圖1描述對(duì)RDF的10個(gè)有向子圖統(tǒng)計(jì)節(jié)點(diǎn)對(duì)之間存在相似性的個(gè)數(shù)。從圖1可以看出:由于P-Rank通過入度和出度兩種信息傳遞方式計(jì)算節(jié)點(diǎn)相似度，而SimRank只根據(jù)節(jié)點(diǎn)入度度量相似性，僅度量了圖中的一部分頂點(diǎn)對(duì)，即在Sim-Rank中不相似的頂點(diǎn)有可能在P-Rank中是相似的，因此使用P-Rank算法產(chǎn)生的節(jié)點(diǎn)對(duì)相似性的個(gè)數(shù)明顯高于SimRank算法。

圖1 P-Rank與SimRank相似度節(jié)點(diǎn)對(duì)數(shù)量

3.2.2 聚類壓縮比

設(shè)兩個(gè)節(jié)點(diǎn)間u，v∈G的結(jié)構(gòu)距離為d(u，v)，

其中，sf(u，v)表示由P-Rank算法或SimRank算法產(chǎn)生兩個(gè)節(jié)點(diǎn)之間的相似度。

其中:K表示產(chǎn)生的聚類個(gè)數(shù);Ci表示第i個(gè)類;mi，mj分別表示類i和類j的聚類中心。式(7)中的分子表示類內(nèi)距離，分母表示類間距離。

圖2 P-Rank與SimRank聚類壓縮比

圖2描述使用P-Rank和SimRank聚類后的壓縮比。從圖2可以看出P-Rank使聚類產(chǎn)生更大的壓縮比，這主要是由于P-Rank算法使更多節(jié)點(diǎn)對(duì)具有相似性。

3.2.3 聚類數(shù)目

圖3描述了分別使用兩種不同的算法后產(chǎn)生的聚類數(shù)目的差別。AP聚類產(chǎn)生的聚類數(shù)目無需事先指定，由于P-Rank在同樣的數(shù)據(jù)集中使更多的節(jié)點(diǎn)具有相似性，因此節(jié)點(diǎn)聚集到一起的可能性高于SimRank，產(chǎn)生的聚類數(shù)據(jù)相對(duì)SimRank算法少。

圖3 P-Rank與SimRank聚類數(shù)目

4 結(jié)束語

圖聚類分割要解決的一個(gè)關(guān)鍵問題是圖中節(jié)點(diǎn)相似性的度量。SimRank和P-Rank算法都是基于結(jié)構(gòu)相似性的度量算法。本文使用P-Rank算法作為節(jié)點(diǎn)相似性的度量方法生成圖中節(jié)點(diǎn)的相似度矩陣，然后利用AP聚類算法根據(jù)相似度矩陣實(shí)現(xiàn)RDF數(shù)據(jù)的聚類分割，進(jìn)而完成RDF大數(shù)據(jù)的分布式存儲(chǔ)。分別從節(jié)點(diǎn)對(duì)相似度數(shù)目、聚類壓縮比和聚類數(shù)目3個(gè)方面對(duì)SimRank和P-Rank兩種算法實(shí)現(xiàn)的聚類分割進(jìn)行對(duì)比。實(shí)驗(yàn)結(jié)果表明，P-Rank能更加有效地完成RDF數(shù)據(jù)的聚類分割，使得類間相似度較小，而類內(nèi)相似度較大。

［1］汪錦嶺，金蓓弘，李京.一種高效的RDF圖模式匹配算法［J］.計(jì)算機(jī)研究與發(fā)展，2005，42(10):1763-1770.

［2］杜方，陳躍國，杜小勇.RDF數(shù)據(jù)查詢處理技術(shù)綜述［J］.軟件學(xué)報(bào)，2013，24(6):1222-1241.

［3］吳剛.RDF圖數(shù)據(jù)管理的關(guān)鍵技術(shù)研究［D］.北京:清華大學(xué)，2008.

［4］姜龍翔，王鑫，李旭，等.一種大規(guī)模RDF語義數(shù)據(jù)的分布式存儲(chǔ)方案［J］.計(jì)算機(jī)應(yīng)用與軟件，2011，28(11):30-32.

［5］李小亮，丁曉明，尹然，等.基于RDF圖的測(cè)試用例生成［J］.西南大學(xué)學(xué)報(bào):自然科學(xué)版，2014，36(1):146-151.

［6］Zhao Peixiang，Han Jiawei，Sun Yizhou.P-rank:A comprehensive structural similarity measure over information networks［C］//International Conference on Information and Knowledge Management，2009:553-562.

［7］Glen Jeh，Jennifer Widom.SimRank:a measure of structural-context similarity［J］.Proceedings on KDD，2002，538-543.

［8］王旭叢，李翠平，陳紅.大數(shù)據(jù)下基于異步累積更新的高效P-Rank計(jì)算方法［J］.軟件學(xué)報(bào)，2014，25(9):2136-2148.

［9］Satu Elisa Schaeffer.Graph clustering，Computer Science Review［Z］.2007:27-64.

［10］Hadi Khosravi Farsani，Mohammadali Nematbaksh，George Lausen.Structure attribute computation of similarities between nodes of a RDF graph with application tolinked data clustering［J］.Intelligent Data Analysis，2013，17(2):179-194.

［11］Pascal Pons，Matthieu Latapy.Computing Communities in Large Networks Using Random Walks［J］.Journal of Graph Algorithms and Applications，2006，10(2):191-218.

［12］Brendan J Frey，Delbert Dueck.Clustering by passing messages between data points［J］.Science，2007，315(5814):972-976.

［13］Roberto Santana，Concha Bielza，Pedro Larra?aga.Affinity Propagation Enhanced by Estimation of Distribution Algorithms［J］.Proceedings on Genetic and evolutionary computation，2011，331-338.

［14］潘巍，李戰(zhàn)懷，伍賽，等.基于消息傳遞機(jī)制的MapReduc圖算法研究［J］.計(jì)算機(jī)學(xué)報(bào)，2011，34(10)，1768-1784.

［15］Huang Liang，Li Ruixuan，Chen Hong，et al.Detecting network communities using regularized spectral clustering algorithm［J］.Artificial Intelligence Review，2012(3):1-16.

［16］Seok-Ho Yoon，Sang-Wook Kim，Sunju Park.A Linkbased Similarity Measure for Scientific Literature［J］.Proceedings on World wide web，2010，1213-1214.