基于主干子圖的冪律特征圖聚類算法

摘 要：從Internet拓撲的冪律特征（度分布律）出發(fā)，定義了主干子圖的相關概念，證明了主干子圖的若干性質(zhì)，并在此基礎上給出了基于主干子圖的聚類算法。該算法可應用于有冪律特征的大型圖的混合布局，也可為冪律特征網(wǎng)絡的研究提供參考。冪律特征圖可以被分解為一個主干子圖和多個子樹。主干子圖是一些度相對較高節(jié)點的集合；而子樹則正好相反，冪律特征有效地保證了節(jié)點度分布的非均一特性。基于主干子圖理論的圖聚類算法可以分成兩個步驟，即主干子圖生成算法和樁樹生成算法。主干子圖與原始圖G(V，E)之間的同態(tài)等價關系保證了繼承了的眾多特性，進而保證了該算法可以被很好地應用于大型冪律特征圖的混合布局。

關鍵詞：繪圖；主干子圖；聚類；冪律

中圖分類號：TP393.08 文獻標志碼：A

文章編號：1001-3695(2008)09-2610-03



Powerlaw graph clustering algorithm based on skeleton subgraph

ZHANG Weiming，ZHANG Kai，WANG Qingxian

(Dept. of Network Engineering，Institute of Information Engineering， PLA Information Engineering University， Zhengzhou 450002，China)

Abstract:Powerlaw graph can be segmented into a skeleton graph and several sub trees with recursively hung vertexes filetering. Skeleton subgraph is a set of relatively important vertexes with high degree， sub trees are just in the opposite situation. Powerlaw characteristic guarantees the nonuniform distribution of nodes’ degree. Based on this characteristic，this paper defined some related concepts of skeleton graph. The clustering algorithm based on skeleton subgraph could be divided into two parts:skeleton subgraph generation algorithm and stub tree growing algorithm. The homomorphically equivalence between skeleton subgraph Gs(V，Etics from G，which ensured this clustering algorithm could be applied to the hybrid layout of large graph with powerlaw characteristic. Meanwhile， it could also supply certain reference to the research of powerlaw network.

Key words:graph drawing； skeleton subgraph； clustering； powerlaw



繪圖技術是解決實體關系可視化問題的關鍵技術之一，通俗地說就是按照一定的要求為圖中的節(jié)點分配坐標，為邊的連線指定路線。繪圖技術面臨的一個難點就是處理大型圖，當圖的規(guī)模變大時，一方面大量的節(jié)點和連接會導致算法性能低下；另一方面，布局結(jié)果也將因為有限的布局空間而變得混亂。對大型圖進行布局的重要方法之一就是采用混合布局方法，其基本思想是利用圖自身的特性，通過聚類方法將圖分成不同的簇，然后對不同類別的簇使用不同的布局算法進行布局。

1 相關工作

1.1 冪律特征

Faloutsos等人^[1]對Internet實測拓撲數(shù)據(jù)的研究指出，Internet拓撲具有冪律特征，其中的度分布律可描述如下：出度d的頻度fd與d成比例，即f點度不是隨機的^[2]，也不像Tiers模型^[3]中描述的那樣規(guī)整，而是具有高度的非均一性，即少數(shù)節(jié)點的度非常高（d取值較大時，do的值一定較小），而大多數(shù)節(jié)點的度卻很小。從實測數(shù)據(jù)來看，根據(jù)對62.9萬個因特網(wǎng)IP節(jié)點的統(tǒng)計分析，其中90.5%的節(jié)點處在無圈子圖上，55%的節(jié)點處在樹上^[4]。文獻[1]進一步指出，樹上節(jié)點中有超過95%的節(jié)點度為1（懸掛點）。

現(xiàn)實世界里有很多網(wǎng)絡都具有這樣的特征，如人類的呼吸系統(tǒng)、公路網(wǎng)、社交網(wǎng)、WWW鏈接網(wǎng)等^[1]。冪律特征的發(fā)現(xiàn)為復雜網(wǎng)絡系統(tǒng)的研究拓展了視野。

1.2 基于冪律特征的繪圖

圖論自產(chǎn)生至今已超過250年的歷史，但針對冪律特征圖的研究卻是在近年來隨著對復雜網(wǎng)絡系統(tǒng)研究的深入而展開。尤其是冪律特征圖的布局問題，是解決復雜網(wǎng)絡可視化問題的關鍵。

Andersen等人^[5]利用局部網(wǎng)絡流的混合模型分析了小世界現(xiàn)象，他們將冪律特征圖稱之為全局圖。該圖是通過圖中潛在的局部圖不斷相加而得到的；局部圖則是指局部高度互連的圖分量。他們以子圖的大小和邊的長度為依據(jù)將圖的邊分成局部邊和全局邊，并在此基礎上給出了計算局部/全局劃分的近似算法，得到圖的劃分后再用力導向布局算法對其進行布局^[6]。全局/局部圖的概念與本文所定義的主干子圖和樁樹的概念有類似之處，但其劃分方法有著本質(zhì)區(qū)別。

2 主干子圖及其性質(zhì)

2.1 冪律特征的直觀分析

針對冪律中的度分布律特征，可以對圖進行分解，將其中類似樹的局部拓撲識別出來，將圖分解成一個主干分量和若干子樹，如圖1所示。

由圖1的分解過程可以看出，主干分量所包含的節(jié)點數(shù)相對較少，但對圖的連通性有著重要作用；相比而言，子樹則涵蓋了大多數(shù)節(jié)點，但重要性相對較低。主干子圖的概念正是基于以上觀察提出的。一方面，主干子圖保留了原圖的多數(shù)重要特性；另一方面，主干子圖相比原圖在規(guī)模上下降了一個數(shù)量級。以上兩方面的特性使得主干子圖在研究冪律特征網(wǎng)絡時可發(fā)揮重要作用。

3.1 主干子圖生成算法

主干子圖生成算法的核心思想就是對圖反復進行懸掛點過濾，直到無法濾除任何節(jié)點時停止，用于識別圖的主干分量。其具體描述如下：

算法1 skeleton_identify(V)

Vs←V，T←，i←|Vs|

while(i≠0)

i←|Vs|

for all v∈Vs且degree(v)=1

Vs←Vs-{v}

T←T∪{v}

end for

i←i-|Vs| 

end while

算法結(jié)束后，Vs中存放的是所有主干子圖上的節(jié)點。

當整個圖等價于樹且其深度最大時，算法迭代次數(shù)最多；節(jié)點數(shù)多于1的樹最少有兩個度為1的節(jié)點（葉子節(jié)點），所以對于圖G來說，最多迭代次數(shù)為「n/2。主干子圖生成過程的執(zhí)行次數(shù)最多為(n2/2)，即最壞計算復雜度為O(n2)。

3.2 樁樹生長算法

樁樹生長算法對于給定的任意樹根節(jié)點r，通過遞歸方式生成以r為根的整個樁樹，用于識別子樹。由于該算法是一個遞歸算法，調(diào)用時先令輔助集T′=。具體描述如下：

算法2 grow_stub_tree(r)

N←neighbor(r)

N←N-T′

T′←T′∪N

for all v∈N，且vVs

add_child(r，v)

grow_stub_tree(v)

end for

根據(jù)主干子圖的性質(zhì)，圖G上所有不屬于其主干子圖的(n-s)個節(jié)點一定都屬于樁樹節(jié)點，它們都將在樁樹生長過程中被處理。樁樹生長算法相當于樹的廣度優(yōu)先遍歷算法，最壞時間復雜度為O(n-s)。

4 結(jié)束語

冪律特征為復雜網(wǎng)絡的研究拓展了視野。主干子圖是冪律特征圖中度較高且相對重要的節(jié)點的集合，而子樹則正好相反。冪律特征保證了節(jié)點度分布的非均一性。本文正是基于這一特性定義了主干子圖的相關概念，證明了其若干性質(zhì)，并在此基礎上給出了基于主干子圖的聚類算法。主干子圖Gs(Vs，Es)與原圖G(V，E)的同態(tài)等價保證了Gs繼承G的多數(shù)性質(zhì)，這使得該聚類算法可應用于有冪律特征的大型圖的混合布局，很多對冪律特征圖的分析研究可以轉(zhuǎn)換為對其主干子圖的分析研究。后續(xù)的主要工作可歸結(jié)為兩方面：豐富主干子圖理論，如利用主干子圖識別冪律特征圖的關鍵節(jié)點；將基于主干子圖的聚類算法與繪圖算法結(jié)合，尋求更高效的冪律特征圖布局方法。

參考文獻：

［1］FALOUTSOS M，F(xiàn)ALOUTSOS P，F(xiàn)ALOUTSOS C.On powerlaw relationships of the Internet topology[C]//Proc of Conference on Applications，Technologies，Architectures，and Protocols for Computer Comunication.New York:ACM Press，1999:251-262.

[2]WAXMAN B M.Routing of multipoint connections[J].IEEE Journal on Selected Areas in Communications，1988，6(9):16171625.

[3]DOAR M B.A better model for generating test networks[C]//Proc of Global Telecommunications Conference.1996:86-93.

[4]BROIDO A，CLAFFY K C.Internet topology:connectivity of IP graphs[C]//Proc of SPIE.2001:172187.

[5]ANDERSON R，CHUNG F，LU L.Analyzing the small world phenomenon using a hybrid model with local network flow[C]//Proc of the3rd International Workshop on Algorithms and Models for the WebGraph.2004:19-30.

[6]ANDERSEN R，CHUNG F，LU L.Drawing powerlaw graphs using a local/global decomposition[J].Algorithmica，2007，47(4):397