基于Web服務復雜網(wǎng)絡的服務社區(qū)構建方法

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

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

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

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

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

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

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

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

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

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

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

(1)

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

RS(wsA,wsB)

(2)

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

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

2 基于加權GN算法的社區(qū)構建方法

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

2.1 加權邊介數(shù)計算

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

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

(3)

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

在加權邊介數(shù)的計算中,最關鍵的是邊的權值即服務相似度的計算.節(jié)點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對輸出相似度的影響程度.在判斷參數(shù)的語義相似性時,本文采用的是計算概念的語義距離的方法[10].

2.2 加權強社團定義

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

(7)

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

2.3 加權GN算法流程

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

① 計算網(wǎng)絡中所有邊的加權邊介數(shù);

② 找到加權邊介數(shù)最大的邊,將其從網(wǎng)絡中移除;

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

④ 當網(wǎng)絡中分裂出的每個社區(qū)都滿足加權強社團的定義時,算法結(jié)束.

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

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

輸入:網(wǎng)絡信息文件(包含節(jié)點和邊的信息).

輸出:網(wǎng)絡的社團結(jié)構.

Begin

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

2 CalculateEB(); //計算整個網(wǎng)絡各邊的加權邊介數(shù)

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

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

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

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

7 if(Q<0)

8 break;

9 else

10 execute algorithm 2;//開始執(zhí)行算法2

11 End if

12 else

13 goto 2; //繼續(xù)尋找加權邊介數(shù)最大的邊

End

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

輸入:網(wǎng)絡信息文件(包含節(jié)點和邊的信息).

輸出:網(wǎng)絡的社團結(jié)構.

Begin

1 Initialize();

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

循環(huán)持續(xù)

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

4 break;

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

6 break;

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

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

9 InsertRear();

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

11 InsertRear();

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

13 DeleteEdge();

14 if(IsDevide())

15 InsertRear(NewCommunity);

16 GetNewQ();

17 if(Q<0)

18 break;

19 End if

20 End while

End

當整個算法流程結(jié)束時,可能會出現(xiàn)以下3種情況:

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

2) 網(wǎng)絡的模塊度小于0;

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

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

2.4 社區(qū)內(nèi)服務相似度模型

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

(8)

設網(wǎng)絡中有M個社區(qū)V1,V2,…,VM,則整個網(wǎng)絡的平均社區(qū)相似度定義為

(9)

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

3 實驗結(jié)果與分析

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

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

表1 網(wǎng)絡模型屬性值

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

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

表2 社區(qū)相似度比較

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

4 結(jié)語

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

)

[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服務復雜網(wǎng)絡的構建方法[J]. 小型微型計算機系統(tǒng),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] 汪小帆,李翔,陳關榮. 復雜網(wǎng)絡理論及其應用[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.