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

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

關(guān)鍵詞：繪圖；主干子圖；聚類；冪律

中圖分類號(hào)：TP393.08 文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：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



繪圖技術(shù)是解決實(shí)體關(guān)系可視化問題的關(guān)鍵技術(shù)之一，通俗地說就是按照一定的要求為圖中的節(jié)點(diǎn)分配坐標(biāo)，為邊的連線指定路線。繪圖技術(shù)面臨的一個(gè)難點(diǎn)就是處理大型圖，當(dāng)圖的規(guī)模變大時(shí)，一方面大量的節(jié)點(diǎn)和連接會(huì)導(dǎo)致算法性能低下；另一方面，布局結(jié)果也將因?yàn)橛邢薜牟季挚臻g而變得混亂。對(duì)大型圖進(jìn)行布局的重要方法之一就是采用混合布局方法，其基本思想是利用圖自身的特性，通過聚類方法將圖分成不同的簇，然后對(duì)不同類別的簇使用不同的布局算法進(jìn)行布局。

1 相關(guān)工作

1.1 冪律特征

Faloutsos等人^[1]對(duì)Internet實(shí)測拓?fù)鋽?shù)據(jù)的研究指出，Internet拓?fù)渚哂袃缏商卣鳎渲械亩确植悸煽擅枋鋈缦拢撼龆泉玠的頻度fd與d成比例，即f點(diǎn)度不是隨機(jī)的^[2]，也不像Tiers模型^[3]中描述的那樣規(guī)整，而是具有高度的非均一性，即少數(shù)節(jié)點(diǎn)的度非常高（d取值較大時(shí)，do的值一定較小），而大多數(shù)節(jié)點(diǎn)的度卻很小。從實(shí)測數(shù)據(jù)來看，根據(jù)對(duì)62.9萬個(gè)因特網(wǎng)IP節(jié)點(diǎn)的統(tǒng)計(jì)分析，其中90.5%的節(jié)點(diǎn)處在無圈子圖上，55%的節(jié)點(diǎn)處在樹上^[4]。文獻(xiàn)[1]進(jìn)一步指出，樹上節(jié)點(diǎn)中有超過95%的節(jié)點(diǎn)度為1（懸掛點(diǎn)）。

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

1.2 基于冪律特征的繪圖

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

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

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

2.1 冪律特征的直觀分析

針對(duì)冪律中的度分布律特征，可以對(duì)圖進(jìn)行分解，將其中類似樹的局部拓?fù)渥R(shí)別出來，將圖分解成一個(gè)主干分量和若干子樹，如圖1所示。

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

3.1 主干子圖生成算法

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

算法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é)點(diǎn)。

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

3.2 樁樹生長算法

樁樹生長算法對(duì)于給定的任意樹根節(jié)點(diǎn)r，通過遞歸方式生成以r為根的整個(gè)樁樹，用于識(shí)別子樹。由于該算法是一個(gè)遞歸算法，調(diào)用時(shí)先令輔助集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)個(gè)節(jié)點(diǎn)一定都屬于樁樹節(jié)點(diǎn)，它們都將在樁樹生長過程中被處理。樁樹生長算法相當(dāng)于樹的廣度優(yōu)先遍歷算法，最壞時(shí)間復(fù)雜度為O(n-s)。

4 結(jié)束語

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

參考文獻(xiàn)：

［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