摘要：隨著互聯(lián)網(wǎng)技術(shù)以及計(jì)算機(jī)技術(shù)的發(fā)展，網(wǎng)絡(luò)安全越來越受到人們的重視。在現(xiàn)實(shí)當(dāng)中，可以用復(fù)雜網(wǎng)絡(luò)的思想解釋和研究很多真實(shí)的網(wǎng)絡(luò)，而社區(qū)結(jié)構(gòu)正是復(fù)雜網(wǎng)絡(luò)的一個(gè)很重要的特征。因此，提出一種基于社區(qū)結(jié)構(gòu)的網(wǎng)絡(luò)布局算法，利用附在網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法劃分網(wǎng)絡(luò)當(dāng)中的節(jié)點(diǎn)，并且抽象社區(qū)為一個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)之間相互關(guān)聯(lián)，形成一個(gè)網(wǎng)絡(luò)。而社區(qū)中心點(diǎn)的位置采用物理類比的方法來確定，運(yùn)用條件擇優(yōu)方式完成網(wǎng)絡(luò)拓?fù)涞牟季謨?yōu)化。這種物理布局算法相比傳統(tǒng)的布局算法而言更加安全高效，結(jié)構(gòu)也更加清晰。

關(guān)鍵詞：復(fù)雜網(wǎng)絡(luò)；安全；布局

中圖分類號(hào)：TP393 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2014）19-4421-02

The Improve of Physical Layout Design Algorithm in Complex Network

Abstract： With the development of Internet and computer technology， network security attracts people's attention. In reality， you can use the network to explain complex ideas and analyse the actual network， and complex network is a very important feature of community structure . Therefore， a network layout algorithm is proposed based on the community structure using the online communities attached to the network discovery algorithm dividing the nodes， and abstracts the community as a node ， and the correlation between each node form sa network.The algorithm uses physical analogy method to determine the community center point and the conditions merit accomplishinglayout optimization of the network topology. Compared with the traditional layout algorithm，this physical layout algorithm is better at security， efficiency and structure.

Key words： complex network；security；layout

隨著互聯(lián)網(wǎng)技術(shù)和計(jì)算機(jī)技術(shù)的發(fā)展，網(wǎng)絡(luò)在人們生活當(dāng)中的重要性日益顯著。網(wǎng)絡(luò)規(guī)模日益龐大且關(guān)系復(fù)雜，因此如何直觀高效分析研究這些網(wǎng)絡(luò)中復(fù)雜的數(shù)據(jù)成為人們密切關(guān)注的熱點(diǎn)。通過網(wǎng)絡(luò)可視化模型可以解決上述的問題，網(wǎng)絡(luò)可視化是一種便利高效簡(jiǎn)潔的方法，但是網(wǎng)絡(luò)規(guī)模日益增大，大量的節(jié)點(diǎn)和邊出現(xiàn)在網(wǎng)絡(luò)當(dāng)中，將會(huì)導(dǎo)致可視化模型出現(xiàn)交叉擁塞的問題，大大影響到可視化的效果。通?？梢钥扛倪M(jìn)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的物理布局算法來優(yōu)化可視化的效果，其核心思想就是進(jìn)行物理類比。

1 傳統(tǒng)的物理布局算法

物理布局算法概念第一次出現(xiàn)在1984年由Peter Eaders提出的彈力模型當(dāng)中，該模型認(rèn)為每個(gè)定點(diǎn)是一個(gè)鋼圈，頂點(diǎn)間的邊是鋼圈之間的彈簧。起初，隨機(jī)放置頂點(diǎn)的位置，彈力也會(huì)隨機(jī)加在頂點(diǎn)之上，不斷的迭代，一定的次數(shù)之后會(huì)終止。算法的收斂速度相對(duì)不同的網(wǎng)絡(luò)而言也是不一樣的。Kamada針對(duì)這種情況提出了KK模型，這是一種改進(jìn)型的模型，這種模型的優(yōu)勢(shì)就是能夠大大的提高收斂的速度，但是仍然有很大的上升的空間。在此之后Davidson又提出了改進(jìn)型的DH模型，能量函數(shù)的思想第一次在該模型當(dāng)中被提出。每個(gè)布局被賦予一個(gè)能量，用能量的大小表示布局的優(yōu)化程度。DH模型能夠獲得比較好的布局，但是非常的消耗時(shí)間。

隨后，F(xiàn)ruchteman在此基礎(chǔ)上提出FR算法，這是一個(gè)比較經(jīng)典的算法，它對(duì)彈力模型進(jìn)行了優(yōu)化設(shè)計(jì)。在提出的FR算法模型當(dāng)中，節(jié)點(diǎn)被比作為原子或者天體。根據(jù)物理學(xué)的原理，原子或者天體之間具有相互作用，或者表現(xiàn)為斥力或者表現(xiàn)為引力。這些力會(huì)引起物體運(yùn)動(dòng)。和最初彈力模型不一樣的是，節(jié)點(diǎn)之間不但具有引力的作用，同時(shí)也會(huì)有斥力的作用，最終引力和斥力會(huì)達(dá)到一個(gè)平衡的狀態(tài)。FR算法具有布局效果好、易于實(shí)現(xiàn)，因此比較適用在結(jié)構(gòu)比較簡(jiǎn)單、數(shù)目比較小的簡(jiǎn)單的網(wǎng)絡(luò)。FR算法復(fù)雜度比較低，是現(xiàn)在比較常用的網(wǎng)絡(luò)布局算法之一。后期提出的GEM算法和LinLog算法都在一定程度上參考了FR算法。力導(dǎo)布局算法以及快速多級(jí)力導(dǎo)布局算法等也都屬于物理布局算法。

近些年來，人們對(duì)拓?fù)浣Y(jié)構(gòu)的物理算法的研究主要集中在對(duì)電子硬件元件的布局布線的算法比如FPGA或者芯片研究。隨著人們對(duì)于復(fù)雜網(wǎng)絡(luò)的研究取得一定的成功，這就給網(wǎng)絡(luò)布局算法帶來了新的研究思路，人們不再僅僅局限使用物理類比的方法來考慮布局的問題，利用復(fù)雜網(wǎng)絡(luò)抽象一些復(fù)雜的系統(tǒng)，充分研究了復(fù)雜系統(tǒng)小世界性、無標(biāo)度性、聚集性等等?，F(xiàn)實(shí)生活當(dāng)中的復(fù)雜的系統(tǒng)都可以表示成一些網(wǎng)絡(luò)，其中有信息網(wǎng)絡(luò)，生物網(wǎng)絡(luò)，技術(shù)網(wǎng)絡(luò)等等。研究分析表明，可以用一些節(jié)點(diǎn)劃分這些網(wǎng)絡(luò)，同一個(gè)節(jié)點(diǎn)組內(nèi)的節(jié)點(diǎn)相對(duì)于不同的節(jié)點(diǎn)更加具有相互連接的效應(yīng)。這樣就能形成社區(qū)結(jié)構(gòu)。這種結(jié)構(gòu)能夠很好的刻畫出網(wǎng)絡(luò)的局部聚集的性質(zhì)。好的布局算法能夠揭示復(fù)雜的數(shù)據(jù)的深刻含義，方便觀察者了解內(nèi)在的構(gòu)成。因此，該文在布局的時(shí)候通過社區(qū)劃分網(wǎng)絡(luò)，能夠更加細(xì)致刻畫連邊的局部性質(zhì)，從而提高物理布局算法的效果。由于真實(shí)網(wǎng)絡(luò)具有的社區(qū)結(jié)構(gòu)特性，因此這種算法具有良好的普遍適用性。endprint

2 算法的設(shè)計(jì)實(shí)現(xiàn)

2.1 算法的主要思想

若是存在這樣一個(gè)N網(wǎng)絡(luò)，網(wǎng)絡(luò)N可以用N（V，E）來表示，其中V（N）是頂點(diǎn)的集合，E（N）為邊的集合，那么網(wǎng)絡(luò)布局可能獲得一個(gè)層次清楚的拓?fù)鋱D，用如下的指標(biāo)衡量該拓?fù)鋱D：

1） 擁擠度。局部的邊過多會(huì)造成擁擠，合理的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)應(yīng)該盡可能的減少擁堵。社區(qū)算法使用了估計(jì)函數(shù)來合理的分析網(wǎng)絡(luò)布局的擁擠的程度。這種方法能夠方便高效的檢測(cè)到所有的擁擠的區(qū)域。

2） 邊交叉樹目。拓?fù)鋱D的交叉的數(shù)據(jù)應(yīng)該盡量的少，這樣圖的布局就會(huì)更加的清晰，布局更加的合理。

3） 節(jié)點(diǎn)的分布情況。節(jié)點(diǎn)的分布應(yīng)該盡可能的利用空間，應(yīng)該是劃分的區(qū)域內(nèi)節(jié)點(diǎn)數(shù)目的均方差值盡可能的小。

4） 具有連邊的節(jié)點(diǎn)之間的相對(duì)的位置：如果一個(gè)節(jié)點(diǎn)的附近有m個(gè)節(jié)點(diǎn)和它鄰近，那么這m個(gè)節(jié)點(diǎn)設(shè)置應(yīng)該盡可能的和它靠近，這樣才能清晰的表達(dá)出節(jié)點(diǎn)之間的關(guān)系，減小交叉的邊。

研究表明，可以用復(fù)雜網(wǎng)絡(luò)的方式對(duì)網(wǎng)絡(luò)進(jìn)行建模，即采用復(fù)雜網(wǎng)絡(luò)解釋真實(shí)網(wǎng)絡(luò)的性質(zhì)。在使用社區(qū)算法分析研究網(wǎng)絡(luò)性質(zhì)的時(shí)候，應(yīng)該先抽象社區(qū)為節(jié)點(diǎn)，使用社區(qū)間關(guān)聯(lián)構(gòu)建社區(qū)的網(wǎng)絡(luò)，然后采用物理類比方法完成對(duì)社區(qū)的布局。因?yàn)榫W(wǎng)絡(luò)劃分為社區(qū)，節(jié)點(diǎn)數(shù)目較少，這就避免節(jié)點(diǎn)過多造成的收斂速度慢的問題。最后使用擇優(yōu)算法填充節(jié)點(diǎn)，完成布局。

2.2 算法的設(shè)計(jì)

算法的設(shè)計(jì)主要分為4個(gè)步驟：

1） 建立節(jié)點(diǎn)社區(qū)網(wǎng)絡(luò)

為了得到優(yōu)秀的物理布局，F(xiàn)R算法會(huì)受到條件的約束，首先節(jié)點(diǎn)位置鄰近，其次要避免相互靠近。由于眾多的節(jié)點(diǎn)連邊，基于上述的約束條件，需要將社區(qū)看成一個(gè)節(jié)點(diǎn)來布局網(wǎng)絡(luò)，在布局的基礎(chǔ)上確定社區(qū)區(qū)域來填充內(nèi)部相互鄰近的節(jié)點(diǎn)，這樣做不僅符合布局的規(guī)范，也能夠簡(jiǎn)化一些布局的步驟。

2） 社區(qū)網(wǎng)絡(luò)布局引入物理類比算法

依據(jù)FR的思想，根據(jù)動(dòng)量守恒定律，系統(tǒng)在受到平衡力或者不受到外力作用的情況下，系統(tǒng)如果只具有內(nèi)部的力的作用，系統(tǒng)的動(dòng)量是守恒的。系統(tǒng)的初始的動(dòng)量是為0的，那么經(jīng)過一段的時(shí)間的內(nèi)力作用后，系統(tǒng)內(nèi)部的節(jié)點(diǎn)要么趨于靜止要么保持震蕩，利用這個(gè)性質(zhì)可以完成對(duì)社區(qū)的中心位置的布局。設(shè)R（x，y）表示節(jié)點(diǎn)x，y之間的斥力，網(wǎng)絡(luò)中的第i個(gè)和第j個(gè)社區(qū)分別用Ci和Cj表示，存在常量f和g，抽象后的斥力可以用下列式子表示：

其中d為節(jié)點(diǎn)間的歐幾里德距離，m為社區(qū)內(nèi)節(jié)點(diǎn)的質(zhì)量。

張力可以用如下的式子表示：

3） 確定社區(qū)的范圍

新網(wǎng)絡(luò)當(dāng)中每個(gè)節(jié)點(diǎn)的坐標(biāo)對(duì)應(yīng)著節(jié)點(diǎn)所代表社區(qū)的中心點(diǎn)的坐標(biāo)，在確定了社區(qū)中心點(diǎn)的方位之后，分配一個(gè)區(qū)域來填充每個(gè)社區(qū)的內(nèi)部的節(jié)點(diǎn)。可以采用以中心節(jié)點(diǎn)為圓心畫圓的方法。為了使節(jié)點(diǎn)均勻的布置，圓的半徑要根據(jù)社區(qū)的規(guī)模來確定。

4） 填充社區(qū)的內(nèi)部節(jié)點(diǎn)

在確定社區(qū)中心節(jié)點(diǎn)和半徑之后，開始進(jìn)行社區(qū)節(jié)點(diǎn)的填充，社區(qū)節(jié)點(diǎn)可以分為非邊緣節(jié)點(diǎn)和邊緣節(jié)點(diǎn)，非邊緣節(jié)點(diǎn)指的是一個(gè)節(jié)點(diǎn)和具有相同邊的節(jié)點(diǎn)都屬于一個(gè)社區(qū)，而邊緣節(jié)點(diǎn)就是它們跨社區(qū)了。填充需要受到下面3個(gè)條件約束：1） 邊緣節(jié)點(diǎn)盡量在社區(qū)共有區(qū)域之間。2） 度數(shù)較大的節(jié)點(diǎn)應(yīng)該盡量的靠近所屬的社區(qū)的中心位置。3） 邊緣節(jié)點(diǎn)應(yīng)該盡可能的和它有連邊的非邊緣的節(jié)點(diǎn)靠近。

3 總結(jié)

根據(jù)物理布局算法的要求，該文提出了劃分網(wǎng)絡(luò)社區(qū)的拓?fù)洳季炙惴ㄋ枷?，由于大多?shù)網(wǎng)絡(luò)具有復(fù)雜網(wǎng)絡(luò)的性質(zhì)，比如說聚類性質(zhì)以及社區(qū)性質(zhì)，因此使用社區(qū)算法進(jìn)行物理布局不僅僅反映了網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)，同時(shí)也減小了計(jì)算的規(guī)模，從而提高了運(yùn)算的速度。

參考文獻(xiàn)：

[1]李卓遠(yuǎn)，吳為民，洪先龍.優(yōu)化線長(zhǎng)和擁擠度的增量式布局算法[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2003，15（6）： 651-655

[2]程學(xué)旗，沈華偉.復(fù)雜網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)[J].復(fù)雜系統(tǒng)與復(fù)雜性科學(xué)，2011，8（1）：58.

[3]戴暉，周強(qiáng)，邊計(jì)年，等.層次式FPGA快速布局算法[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2010，22（9）： 1455-1462.

[4]呂亮，盧澤新，儷蘇丹，等.基于擴(kuò)展力學(xué)模型的網(wǎng)絡(luò)拓?fù)鋱D布局算法[J].計(jì)算機(jī)應(yīng)用研究，2010，27（7）： 2713-2715.

[5]程遠(yuǎn)，嚴(yán)偉，李曉明.基于斥力-張力模型的網(wǎng)絡(luò)拓?fù)鋱D布局算法[J].計(jì)算機(jī)工程，2004，30（3）：104.

2 算法的設(shè)計(jì)實(shí)現(xiàn)

2.1 算法的主要思想

若是存在這樣一個(gè)N網(wǎng)絡(luò)，網(wǎng)絡(luò)N可以用N（V，E）來表示，其中V（N）是頂點(diǎn)的集合，E（N）為邊的集合，那么網(wǎng)絡(luò)布局可能獲得一個(gè)層次清楚的拓?fù)鋱D，用如下的指標(biāo)衡量該拓?fù)鋱D：

1） 擁擠度。局部的邊過多會(huì)造成擁擠，合理的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)應(yīng)該盡可能的減少擁堵。社區(qū)算法使用了估計(jì)函數(shù)來合理的分析網(wǎng)絡(luò)布局的擁擠的程度。這種方法能夠方便高效的檢測(cè)到所有的擁擠的區(qū)域。

2） 邊交叉樹目。拓?fù)鋱D的交叉的數(shù)據(jù)應(yīng)該盡量的少，這樣圖的布局就會(huì)更加的清晰，布局更加的合理。

3） 節(jié)點(diǎn)的分布情況。節(jié)點(diǎn)的分布應(yīng)該盡可能的利用空間，應(yīng)該是劃分的區(qū)域內(nèi)節(jié)點(diǎn)數(shù)目的均方差值盡可能的小。

4） 具有連邊的節(jié)點(diǎn)之間的相對(duì)的位置：如果一個(gè)節(jié)點(diǎn)的附近有m個(gè)節(jié)點(diǎn)和它鄰近，那么這m個(gè)節(jié)點(diǎn)設(shè)置應(yīng)該盡可能的和它靠近，這樣才能清晰的表達(dá)出節(jié)點(diǎn)之間的關(guān)系，減小交叉的邊。

研究表明，可以用復(fù)雜網(wǎng)絡(luò)的方式對(duì)網(wǎng)絡(luò)進(jìn)行建模，即采用復(fù)雜網(wǎng)絡(luò)解釋真實(shí)網(wǎng)絡(luò)的性質(zhì)。在使用社區(qū)算法分析研究網(wǎng)絡(luò)性質(zhì)的時(shí)候，應(yīng)該先抽象社區(qū)為節(jié)點(diǎn)，使用社區(qū)間關(guān)聯(lián)構(gòu)建社區(qū)的網(wǎng)絡(luò)，然后采用物理類比方法完成對(duì)社區(qū)的布局。因?yàn)榫W(wǎng)絡(luò)劃分為社區(qū)，節(jié)點(diǎn)數(shù)目較少，這就避免節(jié)點(diǎn)過多造成的收斂速度慢的問題。最后使用擇優(yōu)算法填充節(jié)點(diǎn)，完成布局。

2.2 算法的設(shè)計(jì)

算法的設(shè)計(jì)主要分為4個(gè)步驟：

1） 建立節(jié)點(diǎn)社區(qū)網(wǎng)絡(luò)

為了得到優(yōu)秀的物理布局，F(xiàn)R算法會(huì)受到條件的約束，首先節(jié)點(diǎn)位置鄰近，其次要避免相互靠近。由于眾多的節(jié)點(diǎn)連邊，基于上述的約束條件，需要將社區(qū)看成一個(gè)節(jié)點(diǎn)來布局網(wǎng)絡(luò)，在布局的基礎(chǔ)上確定社區(qū)區(qū)域來填充內(nèi)部相互鄰近的節(jié)點(diǎn)，這樣做不僅符合布局的規(guī)范，也能夠簡(jiǎn)化一些布局的步驟。

2） 社區(qū)網(wǎng)絡(luò)布局引入物理類比算法

依據(jù)FR的思想，根據(jù)動(dòng)量守恒定律，系統(tǒng)在受到平衡力或者不受到外力作用的情況下，系統(tǒng)如果只具有內(nèi)部的力的作用，系統(tǒng)的動(dòng)量是守恒的。系統(tǒng)的初始的動(dòng)量是為0的，那么經(jīng)過一段的時(shí)間的內(nèi)力作用后，系統(tǒng)內(nèi)部的節(jié)點(diǎn)要么趨于靜止要么保持震蕩，利用這個(gè)性質(zhì)可以完成對(duì)社區(qū)的中心位置的布局。設(shè)R（x，y）表示節(jié)點(diǎn)x，y之間的斥力，網(wǎng)絡(luò)中的第i個(gè)和第j個(gè)社區(qū)分別用Ci和Cj表示，存在常量f和g，抽象后的斥力可以用下列式子表示：

其中d為節(jié)點(diǎn)間的歐幾里德距離，m為社區(qū)內(nèi)節(jié)點(diǎn)的質(zhì)量。

張力可以用如下的式子表示：

3） 確定社區(qū)的范圍

新網(wǎng)絡(luò)當(dāng)中每個(gè)節(jié)點(diǎn)的坐標(biāo)對(duì)應(yīng)著節(jié)點(diǎn)所代表社區(qū)的中心點(diǎn)的坐標(biāo)，在確定了社區(qū)中心點(diǎn)的方位之后，分配一個(gè)區(qū)域來填充每個(gè)社區(qū)的內(nèi)部的節(jié)點(diǎn)?？梢圆捎靡灾行墓?jié)點(diǎn)為圓心畫圓的方法。為了使節(jié)點(diǎn)均勻的布置，圓的半徑要根據(jù)社區(qū)的規(guī)模來確定。

4） 填充社區(qū)的內(nèi)部節(jié)點(diǎn)

在確定社區(qū)中心節(jié)點(diǎn)和半徑之后，開始進(jìn)行社區(qū)節(jié)點(diǎn)的填充，社區(qū)節(jié)點(diǎn)可以分為非邊緣節(jié)點(diǎn)和邊緣節(jié)點(diǎn)，非邊緣節(jié)點(diǎn)指的是一個(gè)節(jié)點(diǎn)和具有相同邊的節(jié)點(diǎn)都屬于一個(gè)社區(qū)，而邊緣節(jié)點(diǎn)就是它們跨社區(qū)了。填充需要受到下面3個(gè)條件約束：1） 邊緣節(jié)點(diǎn)盡量在社區(qū)共有區(qū)域之間。2） 度數(shù)較大的節(jié)點(diǎn)應(yīng)該盡量的靠近所屬的社區(qū)的中心位置。3） 邊緣節(jié)點(diǎn)應(yīng)該盡可能的和它有連邊的非邊緣的節(jié)點(diǎn)靠近。

3 總結(jié)

根據(jù)物理布局算法的要求，該文提出了劃分網(wǎng)絡(luò)社區(qū)的拓?fù)洳季炙惴ㄋ枷?，由于大多?shù)網(wǎng)絡(luò)具有復(fù)雜網(wǎng)絡(luò)的性質(zhì)，比如說聚類性質(zhì)以及社區(qū)性質(zhì)，因此使用社區(qū)算法進(jìn)行物理布局不僅僅反映了網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)，同時(shí)也減小了計(jì)算的規(guī)模，從而提高了運(yùn)算的速度。

參考文獻(xiàn)：

[1]李卓遠(yuǎn)，吳為民，洪先龍.優(yōu)化線長(zhǎng)和擁擠度的增量式布局算法[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2003，15（6）： 651-655

[2]程學(xué)旗，沈華偉.復(fù)雜網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)[J].復(fù)雜系統(tǒng)與復(fù)雜性科學(xué)，2011，8（1）：58.

[3]戴暉，周強(qiáng)，邊計(jì)年，等.層次式FPGA快速布局算法[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2010，22（9）： 1455-1462.

[4]呂亮，盧澤新，儷蘇丹，等.基于擴(kuò)展力學(xué)模型的網(wǎng)絡(luò)拓?fù)鋱D布局算法[J].計(jì)算機(jī)應(yīng)用研究，2010，27（7）： 2713-2715.

[5]程遠(yuǎn)，嚴(yán)偉，李曉明.基于斥力-張力模型的網(wǎng)絡(luò)拓?fù)鋱D布局算法[J].計(jì)算機(jī)工程，2004，30（3）：104.

2 算法的設(shè)計(jì)實(shí)現(xiàn)

2.1 算法的主要思想

若是存在這樣一個(gè)N網(wǎng)絡(luò)，網(wǎng)絡(luò)N可以用N（V，E）來表示，其中V（N）是頂點(diǎn)的集合，E（N）為邊的集合，那么網(wǎng)絡(luò)布局可能獲得一個(gè)層次清楚的拓?fù)鋱D，用如下的指標(biāo)衡量該拓?fù)鋱D：

1） 擁擠度。局部的邊過多會(huì)造成擁擠，合理的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)應(yīng)該盡可能的減少擁堵。社區(qū)算法使用了估計(jì)函數(shù)來合理的分析網(wǎng)絡(luò)布局的擁擠的程度。這種方法能夠方便高效的檢測(cè)到所有的擁擠的區(qū)域。

2） 邊交叉樹目。拓?fù)鋱D的交叉的數(shù)據(jù)應(yīng)該盡量的少，這樣圖的布局就會(huì)更加的清晰，布局更加的合理。

3） 節(jié)點(diǎn)的分布情況。節(jié)點(diǎn)的分布應(yīng)該盡可能的利用空間，應(yīng)該是劃分的區(qū)域內(nèi)節(jié)點(diǎn)數(shù)目的均方差值盡可能的小。

4） 具有連邊的節(jié)點(diǎn)之間的相對(duì)的位置：如果一個(gè)節(jié)點(diǎn)的附近有m個(gè)節(jié)點(diǎn)和它鄰近，那么這m個(gè)節(jié)點(diǎn)設(shè)置應(yīng)該盡可能的和它靠近，這樣才能清晰的表達(dá)出節(jié)點(diǎn)之間的關(guān)系，減小交叉的邊。

研究表明，可以用復(fù)雜網(wǎng)絡(luò)的方式對(duì)網(wǎng)絡(luò)進(jìn)行建模，即采用復(fù)雜網(wǎng)絡(luò)解釋真實(shí)網(wǎng)絡(luò)的性質(zhì)。在使用社區(qū)算法分析研究網(wǎng)絡(luò)性質(zhì)的時(shí)候，應(yīng)該先抽象社區(qū)為節(jié)點(diǎn)，使用社區(qū)間關(guān)聯(lián)構(gòu)建社區(qū)的網(wǎng)絡(luò)，然后采用物理類比方法完成對(duì)社區(qū)的布局。因?yàn)榫W(wǎng)絡(luò)劃分為社區(qū)，節(jié)點(diǎn)數(shù)目較少，這就避免節(jié)點(diǎn)過多造成的收斂速度慢的問題。最后使用擇優(yōu)算法填充節(jié)點(diǎn)，完成布局。

2.2 算法的設(shè)計(jì)

算法的設(shè)計(jì)主要分為4個(gè)步驟：

1） 建立節(jié)點(diǎn)社區(qū)網(wǎng)絡(luò)

為了得到優(yōu)秀的物理布局，F(xiàn)R算法會(huì)受到條件的約束，首先節(jié)點(diǎn)位置鄰近，其次要避免相互靠近。由于眾多的節(jié)點(diǎn)連邊，基于上述的約束條件，需要將社區(qū)看成一個(gè)節(jié)點(diǎn)來布局網(wǎng)絡(luò)，在布局的基礎(chǔ)上確定社區(qū)區(qū)域來填充內(nèi)部相互鄰近的節(jié)點(diǎn)，這樣做不僅符合布局的規(guī)范，也能夠簡(jiǎn)化一些布局的步驟。

2） 社區(qū)網(wǎng)絡(luò)布局引入物理類比算法

依據(jù)FR的思想，根據(jù)動(dòng)量守恒定律，系統(tǒng)在受到平衡力或者不受到外力作用的情況下，系統(tǒng)如果只具有內(nèi)部的力的作用，系統(tǒng)的動(dòng)量是守恒的。系統(tǒng)的初始的動(dòng)量是為0的，那么經(jīng)過一段的時(shí)間的內(nèi)力作用后，系統(tǒng)內(nèi)部的節(jié)點(diǎn)要么趨于靜止要么保持震蕩，利用這個(gè)性質(zhì)可以完成對(duì)社區(qū)的中心位置的布局。設(shè)R（x，y）表示節(jié)點(diǎn)x，y之間的斥力，網(wǎng)絡(luò)中的第i個(gè)和第j個(gè)社區(qū)分別用Ci和Cj表示，存在常量f和g，抽象后的斥力可以用下列式子表示：

其中d為節(jié)點(diǎn)間的歐幾里德距離，m為社區(qū)內(nèi)節(jié)點(diǎn)的質(zhì)量。

張力可以用如下的式子表示：

3） 確定社區(qū)的范圍

新網(wǎng)絡(luò)當(dāng)中每個(gè)節(jié)點(diǎn)的坐標(biāo)對(duì)應(yīng)著節(jié)點(diǎn)所代表社區(qū)的中心點(diǎn)的坐標(biāo)，在確定了社區(qū)中心點(diǎn)的方位之后，分配一個(gè)區(qū)域來填充每個(gè)社區(qū)的內(nèi)部的節(jié)點(diǎn)?？梢圆捎靡灾行墓?jié)點(diǎn)為圓心畫圓的方法。為了使節(jié)點(diǎn)均勻的布置，圓的半徑要根據(jù)社區(qū)的規(guī)模來確定。

4） 填充社區(qū)的內(nèi)部節(jié)點(diǎn)

在確定社區(qū)中心節(jié)點(diǎn)和半徑之后，開始進(jìn)行社區(qū)節(jié)點(diǎn)的填充，社區(qū)節(jié)點(diǎn)可以分為非邊緣節(jié)點(diǎn)和邊緣節(jié)點(diǎn)，非邊緣節(jié)點(diǎn)指的是一個(gè)節(jié)點(diǎn)和具有相同邊的節(jié)點(diǎn)都屬于一個(gè)社區(qū)，而邊緣節(jié)點(diǎn)就是它們跨社區(qū)了。填充需要受到下面3個(gè)條件約束：1） 邊緣節(jié)點(diǎn)盡量在社區(qū)共有區(qū)域之間。2） 度數(shù)較大的節(jié)點(diǎn)應(yīng)該盡量的靠近所屬的社區(qū)的中心位置。3） 邊緣節(jié)點(diǎn)應(yīng)該盡可能的和它有連邊的非邊緣的節(jié)點(diǎn)靠近。

3 總結(jié)

根據(jù)物理布局算法的要求，該文提出了劃分網(wǎng)絡(luò)社區(qū)的拓?fù)洳季炙惴ㄋ枷?，由于大多?shù)網(wǎng)絡(luò)具有復(fù)雜網(wǎng)絡(luò)的性質(zhì)，比如說聚類性質(zhì)以及社區(qū)性質(zhì)，因此使用社區(qū)算法進(jìn)行物理布局不僅僅反映了網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)，同時(shí)也減小了計(jì)算的規(guī)模，從而提高了運(yùn)算的速度。

參考文獻(xiàn)：

[1]李卓遠(yuǎn)，吳為民，洪先龍.優(yōu)化線長(zhǎng)和擁擠度的增量式布局算法[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2003，15（6）： 651-655

[2]程學(xué)旗，沈華偉.復(fù)雜網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)[J].復(fù)雜系統(tǒng)與復(fù)雜性科學(xué)，2011，8（1）：58.

[3]戴暉，周強(qiáng)，邊計(jì)年，等.層次式FPGA快速布局算法[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2010，22（9）： 1455-1462.

[4]呂亮，盧澤新，儷蘇丹，等.基于擴(kuò)展力學(xué)模型的網(wǎng)絡(luò)拓?fù)鋱D布局算法[J].計(jì)算機(jī)應(yīng)用研究，2010，27（7）： 2713-2715.

[5]程遠(yuǎn)，嚴(yán)偉，李曉明.基于斥力-張力模型的網(wǎng)絡(luò)拓?fù)鋱D布局算法[J].計(jì)算機(jī)工程，2004，30（3）：104.