基于Web服務復雜網絡的服務社區構建方法

劉 瑩 劉國奇 任介夫 姜琳穎 張 斌

(1東北大學軟件學院, 沈陽 110819)

(2東北大學信息科學與工程學院, 沈陽 110819)

互聯網上Web服務的數量不斷增加,領域也不斷擴展,為了有效地管理散落于網絡上的Web服務,Web服務社區這一組織形式應運而生[1].基于服務社區進行服務發現、替換,有助于提高服務組合的效率[2].傳統的Web服務社區的構建方法是通過用戶手動注冊實現的,難以對服務資源進行有效的組織和管理.因此,如何自動構建Web服務社區成為服務發現研究中的一個重要方面[3].

本質上,Web服務社區對網絡中的服務資源起到分類的作用,而聚類技術可以實現對服務的無指導分類[4].目前廣泛使用K-Means算法進行聚類,但該算法在聚類過程中性能依賴于聚類中心的初始位置,而且對孤立點和噪聲點數據很敏感.依據Web服務信息,已有的研究采用信息匹配算法將Web服務構建成復雜網絡[5],并且驗證了該網絡具備復雜網絡的特性[6].社團結構是復雜網絡中廣泛存在的一個拓撲屬性[7],通過挖掘Web服務復雜網絡(Web service network, WSN)中的社團結構,可以有效地自動構建Web服務社區.

傳統的復雜網絡社團劃分算法與計算機科學中的圖形分割和社會學中的分級聚類具有密切關系.圖形分割算法中常用的2個算法是Kernighan-Lin算法和基于Laplace圖特征值的譜平分法[8].Kernighan-Lin算法要求必須事先知道該網絡中2個社團的大小,譜平分法主要應用于網絡能夠近似分為2個社團的情形,這些缺陷導致它們在WSN的分析中難以得到應用.分級聚類算法中最具代表性的是GN算法,其缺陷在于對網絡的社團結構沒有一個量的定義[8].Radicchi等[9]針對GN算法的這一缺陷提出了自包含GN算法,在計算機生成的隨機網絡中取得較好的效果,但應用到WSN中,劃分出的社團規模分布嚴重不均,且社團內服務的平均相似度整體偏低.

針對WSN的加權網絡特性,本文提出了一種基于加權GN算法的Web服務社區構建方法.首先從語義層面上構建了WSN模型,其中連邊的權值等于2個節點所代表的Web服務的輸入輸出信息的語義相似程度;然后在WSN模型上使用加權GN算法進行社團劃分,通過挖掘社團結構實現Web服務社區的自動構建;最后,定義社區內服務相似度模型,對Web服務社區的構建結果進行評價.

1 基于語義相似關系的WSN模型

在基于語義相似關系的WSN模型的建模過程中,首先搜索服務庫中可用的Web服務,抽取出這些服務的輸入輸出信息,并計算這些信息的語義相似程度;其次將Web服務抽象成網絡中的節點,將服務之間語義層次的關聯關系抽象成邊.基于以上描述,本文給出如下定義.

定義1(網絡節點(node)) 在基于語義相似關系的WSN模型中,節點是抽象的Web服務,可用五元組表示:

WS=(ID,Porttype,Operation,Message,Description)

(1)

式中,ID是Web服務的唯一標識;Porttype表示特定端口類型的具體協議和數據格式規范;Operation表示對服務所支持的操作的抽象描述;Message表示通信數據的抽象類型化定義;Description表示服務實現功能的描述信息.

RS(wsA,wsB)

(2)

定義3(網絡邊(edge)) 設A,B是網絡中任意2個節點,若A,B代表的Web服務wsA和wsB滿足關系RS(wsA,wsB),則節點A和B間的連線即為網絡邊.

在構建WSN模型時,通過判定服務輸入輸出的語義信息是否匹配將不同Web服務建立關聯.在構建基于語義相似關系的WSN模型后,需要對模型的網絡特性進行度量,具體的度量指標包括:網絡的平均路徑長度、網絡的平均聚類系數、節點的度和度分布.本文通過分析上述特性來分析構建的WSN模型的性質,如果WSN模型滿足復雜網絡的特征,就可以采用相應的方法進行Web服務社區的構建.

2 基于加權GN算法的社區構建方法

GN算法在社會網等復雜網絡中得到了成功應用.但是在本文構建的WSN模型中,節點之間連邊的重要性受到節點代表的Web服務的輸入輸出語義相似程度的影響,該相似程度被定義為網絡中的權值.本文將該權值引入到傳統GN算法中,改進了算法的刪邊條件和終止條件,提出了加權邊介數和加權強社團的概念,并在此基礎上提出了基于加權GN算法的Web服務社區構建方法.

2.1 加權邊介數計算

在復雜網絡中,社團內部的緊密程度比社團之間的緊密程度要高.原有的GN算法中社團內部的緊密程度通過各節點之間連邊的條數計算,在本文提出的WSN模型中,社團內部的緊密程度通過節點的語義相似程度即邊的權值計算.為了能夠在WSN模型中有效區分一個社團的內部邊和連接社團之間的邊,本文提出了加權邊介數的概念,其表達式如下:

Eweighted=(1-Weight(A,B))Eunweighted

(3)

式中,Eweighted表示加權邊介數；Eunweighted表示傳統GN算法中的邊介數；Weight(A,B)表示節點A和節點B之間連邊的權值,它的值等于節點A,B代表的Web服務的語義相似度Sim(A,B).從式(3)可看出,采用本文提出的加權邊介數,可以保證邊的權值越大(即2個Web服務的相似度越大),得到的邊介數越小,從而該邊被移除的概率就越小.這樣就保證社團內部的節點相似度明顯高于不同社團節點的相似度,因而能夠滿足在基于語義相似關系的WSN模型中構建Web服務社區的需要.

在加權邊介數的計算中,最關鍵的是邊的權值即服務相似度的計算.節點A,B的服務相似度(即綜合考慮輸入輸出相似程度)Sim(A,B)定義如下:

Sim(A,B)=w1SimI(A,B)+w2SimO(A,B)

w1+w2=1

(4)

式中,w1和w2分別為輸入、輸出相似度的權值；輸入相似度SimI(A,B)的定義為

w3+w4=1

(5)

式中,w3表示wsA對輸入相似度的影響程度;w4表示wsB對輸入相似度的影響程度.

輸出相似度SimO(A,B)的定義為

w5+w6=1

(6)

式中,w5表示wsA對輸出相似度的影響程度;w6表示wsB對輸出相似度的影響程度.在判斷參數的語義相似性時,本文采用的是計算概念的語義距離的方法[10].

2.2 加權強社團定義

在傳統的自包含GN算法中,Radicchi等[9]提出的強社團結構的定義被用作判斷社團劃分效果的標準.為了更好地衡量加權WSN中的社團結構,本文改進了強社團定義,將本文構建的WSN模型中的權值和強社團定義相結合,提出了加權強社團的概念,其表達式如下:

(7)

式(7)的物理意義是:社團V內的任意一個節點i與這個社團內部其他所有節點的連邊的權值之和,大于它與該社團外部的所有節點的連邊的權值之和.滿足該條件的社團V被稱為網絡中的加權強社團.本文提出的加權GN算法在強社團的概念中引入權值,以便更有效地將Web服務節點之間的關系強度量化,從而為定量分析WSN模型中的社團結構提供一個更加精確的定義.

2.3 加權GN算法流程

在WSN中,社區之間所存在的連接往往是社區間通訊的瓶頸,是社區間通信時通信流量的必經之路.如果考慮網絡中節點之間的通信并尋找到具有最高通信量的邊,則該邊就是連接不同社區的通道.若去掉這樣的邊,網絡就可以自然分解成若干合理的社區.因此,加權GN算法的基本流程是不斷地從網絡中去掉加權邊介數最大的邊.加權GN算法的具體步驟如下:

① 計算網絡中所有邊的加權邊介數;

② 找到加權邊介數最大的邊,將其從網絡中移除;

③ 計算剩余邊的加權邊介數,重復步驟②;

④ 當網絡中分裂出的每個社區都滿足加權強社團的定義時,算法結束.

對于一個具有n個節點,m條邊的網絡來說,整個算法的復雜度為O(m2n)[8].移除一條邊僅影響到與它屬于同一個部分的那些邊的加權邊介數.因此,在反復計算時,只需重新計算與該邊屬于同一部分的那些邊的加權邊介數,而不必考慮其他的邊.社團結構較強的網絡往往很快就分裂成幾個獨立的部分,這樣就大大減少了后續的計算量.對于尚未分解開的網絡和已經分出一些社區的網絡,算法的流程略有不同,算法流程分別如算法1和算法2所示.

算法1加權GN算法(初始網絡)

輸入:網絡信息文件(包含節點和邊的信息).

輸出:網絡的社團結構.

Begin

1 Initialize(); //初始化網絡信息

2 CalculateEB(); //計算整個網絡各邊的加權邊介數

3 DeleteEdge(); //刪除加權邊介數最大的邊

4 if(IsDevide()) //判斷是否產生新社團

5 InsertRear(NewCommunity); //新社團編號入隊列

6 GetNewQ(); //計算模塊度

7 if(Q<0)

8 break;

9 else

10 execute algorithm 2;//開始執行算法2

11 End if

12 else

13 goto 2; //繼續尋找加權邊介數最大的邊

End

算法2加權GN算法(分解過程中網絡)

輸入:網絡信息文件(包含節點和邊的信息).

輸出:網絡的社團結構.

Begin

1 Initialize();

2 While(not TerminateCondition) //未滿足終止條件時,

循環持續

3 if(TerminateCondition1) //判斷網絡是否完全退化

4 break;

5 if(TerminateCondition2) //判斷是否所有社團均為加權強社團

6 break;

7 GetQueueFront(); //獲取將要處理的社團(隊首社團)

8 if(IsStrong()) //判斷該社團是否為加權強社團

9 InsertRear();

10 if(IsSingle()) //判斷該社團是否為單點社團

11 InsertRear();

12 CalculateEB(); //計算該社團各邊的加權邊介數

13 DeleteEdge();

14 if(IsDevide())

15 InsertRear(NewCommunity);

16 GetNewQ();

17 if(Q<0)

18 break;

19 End if

20 End while

End

當整個算法流程結束時,可能會出現以下3種情況:

1) 所有社團均為強社團結構;

2) 網絡的模塊度小于0;

3) 少量社團為單點社團.

情況1)是算法最理想的情況,此時挖掘出的網絡社團結構即為本文要構建的Web服務社區.情況2)涉及到模塊度Q的概念,模塊度是Newman等[11]引進的衡量網絡劃分的標準.模塊度越大,說明社團結構越明顯.通常,模塊度的局部峰值僅有1～2個.當模塊度小于0時,如果繼續分解網絡,社團結構將變得更加不明顯,因此在Q<0時立刻終止算法可得到相對良好的社團結構.情況3)涉及到單點社團,單點社團雖然不能再分,但它對構建Web服務社區不具備任何意義,事實上將其歸并到其他社團會更加合理.對此,本文采取的做法是比較該單點社團所有連邊的權值,將該節點加入到與其連邊的權值最大的節點所在的社團中.

2.4 社區內服務相似度模型

為了驗證構建出的社區結構的合理性,需制訂一個相似度度量標準.為此,本文提出了一種基于語義相似關系的WSN社區內服務相似度模型.

(8)

設網絡中有M個社區V1,V2,…,VM,則整個網絡的平均社區相似度定義為

(9)

本文在得到各個社區的服務相似度后,還將計算這些相似度的方差,以觀察社區內服務相似度的穩定性,從而分析所構建的Web服務社區在網絡中分布的合理性.

3 實驗結果與分析

實驗所用的測試數據來源于首屆全國Web服務競賽的數據集[12],數據集中Web服務輸入輸出的語義信息存儲在WSDL文檔和OWL文檔中.本文采用DOM解析技術,從WSDL文檔和OWL文檔中將Web服務輸入輸出信息和相應的語義關系提取出來.然后將提取出的服務輸入輸出信息映射到概念層,分析任意2個服務之間的相似語義關系,建立節點之間的連接邊.同時,計算2個服務之間的輸入輸出的相似度,作為邊的權值存入數據庫.

在完成數據的預處理工作后,為保證實驗所得結論的準確性,以Web服務數據集中的服務作為節點,進行了多次實驗. 分別以449,1 301和4 031個Web服務的服務集合作為實驗對象,計算3個網絡模型的聚類系數和平均最短路徑長度,結果如表1所示.可看出,本文所構建的3個WSN模型具有較高的聚類系數和較小的平均最短路徑長度,滿足小世界特性.同時,3個WSN模型的度分布近似滿足冪律分布的形態,說明它們具有無標度特性.

表1 網絡模型屬性值

本文分別采用Newman算法、自包含GN算法和提出的加權GN算法來構建Web服務社區.由實驗結果可看出,Newman算法將網絡分解為較多的細粒度社區,不能有效地完成Web服務社區的劃分.自包含GN算法劃分出的社區,規模極度不均衡,這種規模過大或過小的社區對實現Web服務社區的功能缺乏實際意義.在Internet中分布著各種不同功能的Web服務,不同種類的服務在數量上會有差異,但不應出現某一類服務的數量過度偏高的情況.本文提出的加權GN算法構建出的Web服務社區內服務數量較為均勻,符合實際情況.

為了驗證所提算法的有效性,本文獲得了3個不同規模的網絡,使用3種算法分別進行服務的社區劃分.針對每種算法獲得的社區劃分結果,使用社區內服務相似度模型計算社區內平均服務相似度以及相似度的波動情況,實驗結果如表2所示.

表2 社區相似度比較

從表2可看出,本文算法構建出的Web服務社區的平均社區相似度更高.社區內的服務只有保持一定的相似度,才能使Web服務社區幫助完成服務分類和發現等工作.同時,本文算法構建出的Web服務社區,不同社區之間服務相似度的波動很小,相似程度趨于穩定,說明本文算法使不同類型的服務分布得更加合理.

4 結語

針對傳統自包含GN算法應用于Web服務社區構建所存在的問題,本文提出了新的基于加權GN算法的Web服務社區構建方法.該方法克服了傳統自包含GN算法僅考慮網絡中節點連邊情況的問題,在算法中加入了連邊的權值信息,通過改進算法的刪邊條件和終止條件來完成Web服務社區的構建.實驗結果表明,本文算法能夠有效地在基于語義相似關系的WSN模型中完成Web服務社區的構建.與傳統的自包含GN算法相比,本文算法提高了社區內服務的平均相似度,減小了網絡中不同Web服務社區平均相似度的差別.由于本文實驗采用的是首屆全國Web服務競賽的仿真數據集,和實際的Web服務環境可能會有所差異.以后的工作將著重研究如何為真實的Web服務庫構建自身相應的語義體系,并在此基礎上進行Web服務社區的構建.

)

[1] Popa V, Constantinescu L, Moise M, et al. Management of Web services communities, WSC system [J].StudiesinInformaticsandControl,2010,19(3):295-308.

[2] Chantal C, Vincent L, Jean-Francois S. Benefits of semantics on Web service composition from a complex network perspective [C]//ProceedingsofInternationalConferenceonNetworkedDigitalTechnologies. Berlin, Germany, 2010:80-90.

[3] Perryea C A. Community-based service discovery[C]//Proceedingsof2006IEEEInternationalConferenceonWebServices. Chicago, IL, USA, 2006:903-906.

[4] Zhang Xizhe, Yin Ying, Zhang Mingwei, et al. Web service community discovery based on spectrum clustering [C]//Proceedingsofthe2009InternationalConferenceonComputationalIntelligenceandSecurity. Beijing, China, 2009:187-191.

[5] Fortunato S. Community detection in graphs [J].PhysicsReports, 2010,486(3/4/5):75-174.

[6] 朱志良,邱媛源,李丹程,等. 一種Web服務復雜網絡的構建方法[J]. 小型微型計算機系統,2012,33(2):199-205.

Zhu Zhiliang, Qiu Yuanyuan, Li Dancheng, et al. Approach for building complex network of Web service [J].JournalofChineseComputerSystems, 2012,33(2):199-205. (in Chinese)

[7] Fan Y, Li M H, Zhang P, et al. Accuracy and precision of methods for community identification in weighted networks [J].PhysicaA:StatisticalMechanicsanditsApplications, 2007,377(1): 363-372.

[8] 汪小帆,李翔,陳關榮. 復雜網絡理論及其應用[M].北京:清華大學出版社,2006:164-169.

[9] Radicchi F, Castellano C, Cecconi F, et al. Defining and identifying communities in networks [J].ProcNatlAcadSci, 2004,101(9):2658-2663.

[10] 彭暉,史忠植,邱莉榕,等. 基于本體概念相似度的語義Web服務匹配算法[J]. 計算機工程,2008,34(15):51-53.

Peng Hui, Shi Zhongzhi, Qiu Lirong, et al. Matching algorithm of semantic Web service based on similarity of ontology concepts [J].ComputerEngineering, 2008,34(15):51-53.(in Chinese)

[11] Newman M E J, Girvan M. Finding and evaluating community structure in networks [J].PhysicalReviewE, 2004,69(2):026113-01-026113-15.

[12] China Web Service Cup (CWSC2011) [EB/OL]. (2011)[2012-10-15].http://debs.ict.ac.cn/cwsc2011/technical_details.html.