基于P-Rank的RDF有向圖的分布式存儲

冷泳林，申 華，魯富宇

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

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

隨著語義網的迅猛發展，RDF數據呈海量增長趨勢，單機存儲和管理RDF數據已經成為RDF數據發展的瓶頸。而當采用分布式存儲方式解決RDF數據可擴展問題時，基于關系和對象等數據模型的傳統管理方式難以同時滿足低數據冗余與高查詢性能這兩個要求。若以圖方式管理RDF數據則不僅可以避免RDF邏輯數據模型與物理數據模型之間的轉換，而且可利用成熟的圖算法優化RDF 數據查詢［2-5］。

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

1 相關理論和技術

1.1 SimRank基本思想

SimRank是一種在有向網絡中度量節點相似性的方法，其基本思想是:如果兩個對象被相似的對象引用，則這兩個對象也是相似的。

給定圖G=(V，E)，V表示節點的集合，E表示邊的集合。對于任意節點v∈V，用 I(v)表示對象v的入鄰接點集合表示集合I(v)中的元素個數，關于SimRank的節點間相似度計算公式定義如下:

其中c是阻尼因子。為了防止式(1)中出現除以0的現象，SimRank規定當=0或者=0 時，s(u，v)=0。

由于SimRank在度量節點相似性時只考慮了節點的入邊，存在大量節點之間相似性為0的情況，因此在對相似度結果進行聚類時會產生大量的離群點［9-11］。

1.2 P-Rank基本思想

P-Rank算法是針對SimRank相似度過分依賴入鄰點結構的不足，由Zhao等在SimRank基礎上提出的度量圖節點相似性的改進算法。P-Rank的基本思想包含兩重含義:

1)如果兩個對象被相似對象引用，那么這兩個對象相似;

2)如果兩個對象引用了相似的對象，則這兩個對象相似。

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

1.3 P-Rank算法描述

P-Rank采用迭代算法:

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

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

步驟3 迭代執行中，當u≠v時，

當u=v時，

直到達到指定迭代次數k。

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

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

2 AP聚類算法

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

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

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

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

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

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

相似度矩陣S對角線上的值s(i，i)表示節點i被選擇為聚類中心的傾向性，即偏向參數p。p越大，表示節點i作為聚類中心的可能性就越大，因為初始時，AP聚類算法將每一個節點都看做是潛在的聚類中心，因此所有節點具有相同的p值。通常情況下，p值越大，聚類輸出的簇數越多;反之越小［13-15］。

3 實驗分析

3.1 數據集和實驗環境

本文選擇數據集 DBLP［16］作為實驗數據，數據集中包括2555篇文章和6101個引用關系(表1)。數據集涉及計算機領域中的10個方向，通過對數據的處理，形成10個RDF子圖和1個RDF匯總圖，有向圖中頂點數和邊數如表1所示。實驗環境為:Inter i3處理器，4GB內存，Windows XP操作系統，C++編程環境。

表1 RDF有向圖基本信息

3.2 實驗分析

為驗證P-Rank算法度量RDF有向圖節點相似性對數據分割的性能影響，本文將P-Rank算法同SimRank算法進行對比。實驗中算法權重系數λ的值是0.5，阻尼因子C的值是0.8，為比較兩種度量方法，實驗從3個方面衡量聚類效果。

3.2.1 相似度節點對數量

對P-Rank和SimRank產生的相似度矩陣中節點對的取值進行統計。如果相似度節點對s(u，v)=0，表示節點u和v之間不存在相似性，否則存在相似性。

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

圖1 P-Rank與SimRank相似度節點對數量

3.2.2 聚類壓縮比

設兩個節點間u，v∈G的結構距離為d(u，v)，

其中，sf(u，v)表示由P-Rank算法或SimRank算法產生兩個節點之間的相似度。

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

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

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

3.2.3 聚類數目

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

圖3 P-Rank與SimRank聚類數目

4 結束語

圖聚類分割要解決的一個關鍵問題是圖中節點相似性的度量。SimRank和P-Rank算法都是基于結構相似性的度量算法。本文使用P-Rank算法作為節點相似性的度量方法生成圖中節點的相似度矩陣，然后利用AP聚類算法根據相似度矩陣實現RDF數據的聚類分割，進而完成RDF大數據的分布式存儲。分別從節點對相似度數目、聚類壓縮比和聚類數目3個方面對SimRank和P-Rank兩種算法實現的聚類分割進行對比。實驗結果表明，P-Rank能更加有效地完成RDF數據的聚類分割，使得類間相似度較小，而類內相似度較大。

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

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

［3］吳剛.RDF圖數據管理的關鍵技術研究［D］.北京:清華大學，2008.

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

［5］李小亮，丁曉明，尹然，等.基于RDF圖的測試用例生成［J］.西南大學學報:自然科學版，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］王旭叢，李翠平，陳紅.大數據下基于異步累積更新的高效P-Rank計算方法［J］.軟件學報，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］潘巍，李戰懷，伍賽，等.基于消息傳遞機制的MapReduc圖算法研究［J］.計算機學報，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.