摘 要： "網(wǎng)絡(luò)聚類模式發(fā)現(xiàn)是網(wǎng)絡(luò)分析中的一項重要任務(wù)，好的網(wǎng)絡(luò)布局應(yīng)能體現(xiàn)網(wǎng)絡(luò)中的聚類特征，并允許用戶從不同層次探索網(wǎng)絡(luò)結(jié)構(gòu)。為此，基于社團(tuán)劃分和多層次布局思想提出了聚類特征層次布局算法。首先利用種子節(jié)點(diǎn)和個性化PageRank對網(wǎng)絡(luò)實(shí)現(xiàn)社團(tuán)劃分；其次根據(jù)劃分結(jié)果對網(wǎng)絡(luò)進(jìn)行粗化，并設(shè)計了粗化網(wǎng)絡(luò)初始布局；然后利用節(jié)點(diǎn)度信息改進(jìn)力導(dǎo)向模型以完成細(xì)化；最后，為驗(yàn)證所提算法的有效性，設(shè)計了從整體到局部的實(shí)驗(yàn)。實(shí)驗(yàn)表明所提算法能夠在有效時間內(nèi)生成高質(zhì)量的布局結(jié)果，與現(xiàn)有布局算法相比，所提算法更能真實(shí)展示網(wǎng)絡(luò)聚類特征，同時兼顧網(wǎng)絡(luò)微觀結(jié)構(gòu)，能夠滿足用戶從不同層次探索網(wǎng)絡(luò)結(jié)構(gòu)的需要。

關(guān)鍵詞： "復(fù)雜網(wǎng)絡(luò)； 聚類特征； 個性化PageRank； 社團(tuán)劃分； 多層次布局

中圖分類號： "TP931 """文獻(xiàn)標(biāo)志碼： A

文章編號： "1001-3695（2022）02-026-0479-06

doi：10.19734/j.issn.1001-3695.2021.07.0272

Complex network clustering feature multi-level layout algorithm

Zhou Rui1， Wang Guijuan1， Deng Haotian1， Cai Mengjie1， Zhao Weixin1， Tan Boyou1， Wu Yadong2

（1.College of Computer Science amp; Technology， Southwest University of Science amp; Technology， Mianyang Sichuan 621000， China； 2.College of Computer Science amp; Engineering， Sichuan University of Science amp; Engineering， Zigong Sichuan 643000， China）

Abstract： "The discovery of network clustering patterns is an important task in network analysis.A good network layout should reflect the clustering characteristics of the network and allow users to explore the network structure from different levels.For this reason，based on the idea of community division and multi-level layout，this paper proposed a clustering feature hierarchical layout algorithm.First，used seed nodes and personalized PageRank to divide the network.Secondly，it coarsened the network according to the results of the division，and designed the initial layout of the coarsened network.Then it used the node degree information to improve the force-oriented model to complete the refinement.Finally，in order to verify the effectiveness of the algorithm，experiments from the whole to the part were carried out.The experiment shows that the algorithm can generate high-quality layout results within an effective time.Compared with the existing layout algorithms，the proposed algorithm can truly display the network.Clustering features，while taking into account the network microstructure，it can meet the needs of users to explore the network structure from different levels.

Key words： "complex network； clustering characteristics； personalized PageRank； community detection； multi-level layout

0 引言

復(fù)雜網(wǎng)絡(luò)是對現(xiàn)實(shí)世界復(fù)雜系統(tǒng)的抽象，對復(fù)雜網(wǎng)絡(luò)的分析有助于理解真實(shí)的復(fù)雜系統(tǒng)。網(wǎng)絡(luò)可視化作為分析網(wǎng)絡(luò)數(shù)據(jù)的有力工具之一，其將網(wǎng)絡(luò)數(shù)據(jù)表現(xiàn)為圖形以直觀地展示網(wǎng)絡(luò)的結(jié)構(gòu)和特征。網(wǎng)絡(luò)布局算法是網(wǎng)絡(luò)可視化的基礎(chǔ)，旨在通過優(yōu)化相關(guān)指標(biāo)來計算網(wǎng)絡(luò)中節(jié)點(diǎn)的位置，以實(shí)現(xiàn)網(wǎng)絡(luò)繪制。

在眾多的網(wǎng)絡(luò)布局算法中，力導(dǎo)向模型是一類經(jīng)典布局模型，通過給網(wǎng)絡(luò)中的節(jié)點(diǎn)、連邊添加力來實(shí)現(xiàn)自動布局。Eades［1］將節(jié)點(diǎn)模擬為鋼圈、將連邊模擬為彈簧，通過模擬鋼圈在彈簧力作用下的運(yùn)動來進(jìn)行布局。文獻(xiàn)［2］在此基礎(chǔ)上引入節(jié)點(diǎn)間理想距離，并通過最小化理想距離和歐氏距離差將布局轉(zhuǎn)換為能量優(yōu)化問題。FR（Fruchterman-Reingold）算法［3］基于“存在連邊的節(jié)點(diǎn)應(yīng)繪制得比較接近，而同時節(jié)點(diǎn)之間不應(yīng)繪制得太近”這一準(zhǔn)則，在所有節(jié)點(diǎn)之間添加斥力、在具有連邊的節(jié)點(diǎn)間添加引力來實(shí)現(xiàn)布局。

網(wǎng)絡(luò)數(shù)據(jù)規(guī)模的增加給算法效率和布局質(zhì)量都帶來了新的挑戰(zhàn)。為了提高布局算法的效率，空間分解［4］被引入網(wǎng)絡(luò)布局中來降低斥力計算所花費(fèi)的時間。Walshaw［5］提出多層次布局方法來加快布局速度，該方法通過遞歸合并節(jié)點(diǎn)來將原始網(wǎng)絡(luò)粗化以得到規(guī)模較小的粗化網(wǎng)絡(luò)，并在最粗化網(wǎng)絡(luò)上進(jìn)行布局，最后以該布局為基礎(chǔ)逐級還原展開網(wǎng)絡(luò)進(jìn)而完成布局。此后，一些基于空間分解、多層次布局思想的算法相繼被提出。Jacomy等人［6］整合不同的技術(shù)，包括空間分解、依賴度數(shù)的排斥力以及局部和全局的自適應(yīng)溫度提出了ForceAtlas2算法，并作為Gephi［7］的默認(rèn)布局算法。為同時保證布局質(zhì)量和算法性能，Hu［8］結(jié)合多層次布局思想和空間分解提出了Hu算法。Martin等人［9］通過結(jié)合邊切割、多層次思想、平均連接聚類提出了OpenOrd算法。

在布局質(zhì)量方面，網(wǎng)絡(luò)數(shù)據(jù)規(guī)模的增加使得網(wǎng)絡(luò)布局結(jié)果中出現(xiàn)毛球［10］。傳統(tǒng)網(wǎng)絡(luò)布局算法主要優(yōu)化美學(xué)標(biāo)來增強(qiáng)布局的可讀性，使得網(wǎng)絡(luò)結(jié)構(gòu)難以識別，然而最近的研究表明需要更具體的度量來發(fā)現(xiàn)網(wǎng)絡(luò)中的模式［11］。

聚類是網(wǎng)絡(luò)中的一個重要模式，網(wǎng)絡(luò)中的聚類體現(xiàn)在網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)，處于同一社團(tuán)內(nèi)的節(jié)點(diǎn)間連接更為緊密，而位于不同社團(tuán)的節(jié)點(diǎn)間連接更為稀疏。社團(tuán)結(jié)構(gòu)是復(fù)雜網(wǎng)絡(luò)普遍存在的特征之一，社團(tuán)發(fā)現(xiàn)也是網(wǎng)絡(luò)分析中的一項重要任務(wù)。因此在布局的時候?qū)儆谕簧鐖F(tuán)的節(jié)點(diǎn)應(yīng)彼此靠攏而不同社團(tuán)的節(jié)點(diǎn)應(yīng)相互分開，以體現(xiàn)網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)。為此，一些專注于表達(dá)網(wǎng)絡(luò)中社團(tuán)結(jié)構(gòu)的布局算法相繼被提出。文獻(xiàn)［12］改進(jìn)Louvain算法來防止網(wǎng)絡(luò)中大社團(tuán)的過度合并，同時及時合并小的社團(tuán)，并引入社區(qū)力來展示網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)。文獻(xiàn)［13］結(jié)合社團(tuán)力和K-means算法來實(shí)現(xiàn)網(wǎng)絡(luò)中的社團(tuán)展示。這些算法在規(guī)模小的網(wǎng)絡(luò)數(shù)據(jù)上有較好的布局效果，但其本身時間復(fù)雜度較高難以擴(kuò)展至較大規(guī)模的數(shù)據(jù)上。文獻(xiàn)［14］將力導(dǎo)向布局算法與社團(tuán)結(jié)構(gòu)特征相結(jié)合，對網(wǎng)絡(luò)進(jìn)行壓縮以展示網(wǎng)絡(luò)的中觀尺度結(jié)構(gòu)，但壓縮讓用戶無法觀察到網(wǎng)絡(luò)的微觀結(jié)構(gòu)，也導(dǎo)致了社團(tuán)內(nèi)部的結(jié)構(gòu)信息丟失。文獻(xiàn)［15，16］利用Infomap、Louvain等社團(tuán)劃分算法和多層次布局思想來對網(wǎng)絡(luò)進(jìn)行布局，并比較了不同劃分算法對布局結(jié)果在算法性能和布局質(zhì)量上的差異。但其算法主要針對網(wǎng)絡(luò)的整體結(jié)構(gòu)而忽略了網(wǎng)絡(luò)局部信息，得到的布局結(jié)果往往不能很好地兼顧網(wǎng)絡(luò)局部結(jié)構(gòu)。Huang等人［17］利用社團(tuán)劃分算法預(yù)先對網(wǎng)絡(luò)進(jìn)行劃分以得到社團(tuán)結(jié)構(gòu)，并根據(jù)社團(tuán)信息計算社團(tuán)內(nèi)部和社團(tuán)之間節(jié)點(diǎn)間的加權(quán)引力和斥力以凸顯網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)。對于規(guī)模較大的網(wǎng)絡(luò)，該方法還可利用社團(tuán)結(jié)構(gòu)對網(wǎng)絡(luò)進(jìn)行壓縮，以擴(kuò)展為多層布局算法。同樣地，該方法未能較好地保持網(wǎng)絡(luò)的局部結(jié)構(gòu)?；谏鐖F(tuán)結(jié)構(gòu)的網(wǎng)絡(luò)布局使得社團(tuán)之間的連接容易察覺，而社團(tuán)內(nèi)部的結(jié)構(gòu)往往不能充分呈現(xiàn)。

復(fù)雜網(wǎng)絡(luò)由眾多社團(tuán)構(gòu)成，如果一個布局清晰地展示了網(wǎng)絡(luò)社團(tuán)內(nèi)部和社團(tuán)間的結(jié)構(gòu)，那么網(wǎng)絡(luò)就會被很好地顯示［17］?；谠撍枷?，本文結(jié)合社團(tuán)劃分算法和多層次布局思想來突出展示網(wǎng)絡(luò)中社團(tuán)結(jié)構(gòu)的聚類特征，同時兼顧網(wǎng)絡(luò)社團(tuán)內(nèi)部的結(jié)構(gòu)信息。

本文主要貢獻(xiàn)如下：a）結(jié)合基于個性化PageRank的局部社團(tuán)劃分算法和多層次布局提出了復(fù)雜網(wǎng)絡(luò)聚類特征層次布局算法，用于突出展示網(wǎng)絡(luò)中的聚類模式；b）提出了個性化理想距離來改進(jìn)FR算法以清晰展示網(wǎng)絡(luò)社團(tuán)內(nèi)部結(jié)構(gòu)，更加真實(shí)地還原社團(tuán)的形狀；c）設(shè)計了從整體到局部的實(shí)驗(yàn)驗(yàn)證了本文算法的有效性。

1 相關(guān)算法

1.1 社團(tuán)劃分算法

社團(tuán)劃分算法旨在檢測出網(wǎng)絡(luò)中存在的社團(tuán)結(jié)構(gòu)，可分為全局社團(tuán)劃分和局部社團(tuán)劃分。全局社團(tuán)劃分算法從全局出發(fā)，通過圖分割、層次聚類來實(shí)現(xiàn)社團(tuán)劃分。常見的全局劃分算法包括基于模塊度優(yōu)化的社團(tuán)劃分算法、基于標(biāo)簽傳播的社團(tuán)劃分算法等［18］。

而局部社團(tuán)劃分往往從網(wǎng)絡(luò)中的一個或多個節(jié)點(diǎn)出發(fā)，尋找包含這些節(jié)點(diǎn)的社團(tuán)。局部社團(tuán)劃分算法主要通過擴(kuò)展種子節(jié)點(diǎn)來實(shí)現(xiàn)劃分，因此算法通常包含三個步驟［19］：a）根據(jù)策略選中網(wǎng)絡(luò)中的種子節(jié)點(diǎn)；b）計算所有節(jié)點(diǎn)與種子節(jié)點(diǎn)的相似度或接近度，并按相似度對所有節(jié)點(diǎn)進(jìn)行降序排序；c）根據(jù)排序依次將節(jié)點(diǎn)加入種子節(jié)點(diǎn)所在社團(tuán)，并在“合適”的時候停止。

1.2 FR算法

FR算法是經(jīng)典的力導(dǎo)向算法，因其算法思想簡單、易于實(shí)現(xiàn)被廣泛使用。在FR算法中，網(wǎng)絡(luò)中的連邊被模擬為彈簧、節(jié)點(diǎn)被模擬為具有相同電荷的電子，分別對應(yīng)這基于胡克定律的引力和基于庫侖力的斥力。在力的作用下，節(jié)點(diǎn)會向著力的方向運(yùn)動直到達(dá)到穩(wěn)定狀態(tài)。

通常引力、斥力計算公式為

f r= k2 d

f a= d2 k """"（1）

其中： d 表示節(jié)點(diǎn)間的歐氏距離。由式（1）可知，當(dāng)真實(shí)距離 d=k 時，斥力等于引力。因此 k 表示節(jié)點(diǎn)間的理想距離，定義為

k= "S |V| """"（2）

其中： S 表示布局面積； |V| 表示網(wǎng)絡(luò)節(jié)點(diǎn)的數(shù)量。

1.3 多層次布局

多層次布局算法通常包括網(wǎng)絡(luò)粗化、初始布局和網(wǎng)絡(luò)細(xì)化［5］三個步驟。在粗化階段，網(wǎng)絡(luò)中的節(jié)點(diǎn)被逐步壓縮、合并，直到網(wǎng)絡(luò)的規(guī)模達(dá)到某一閾值或壓縮效率比達(dá)到某一閾值。粗化階段的產(chǎn)物是最粗化網(wǎng)絡(luò)，該網(wǎng)絡(luò)規(guī)模應(yīng)遠(yuǎn)小于原始網(wǎng)絡(luò)。初始布局階段是對最粗化網(wǎng)絡(luò)的布局。此后，細(xì)化階段以上一階段的布局為基礎(chǔ)，插值、細(xì)化網(wǎng)絡(luò)直到達(dá)到原始網(wǎng)絡(luò)。

2 本文算法

2.1 設(shè)計需求

面對大規(guī)模復(fù)雜網(wǎng)絡(luò)數(shù)據(jù)，布局算法首先需考慮的仍是效率問題。其次，社團(tuán)結(jié)構(gòu)作為復(fù)雜網(wǎng)絡(luò)普遍存在的特征之一，算法布局應(yīng)能清晰展示網(wǎng)絡(luò)中社團(tuán)和社團(tuán)間的連接關(guān)系，即要求布局能體現(xiàn)網(wǎng)絡(luò)的聚類特征；同時應(yīng)能夠揭示社團(tuán)內(nèi)節(jié)點(diǎn)是如何組織的，即對應(yīng)網(wǎng)絡(luò)的微觀結(jié)構(gòu)。因此，本文算法提出以下需求：R1表示算法能在有效時間內(nèi)得到布局；R2表示算法能體現(xiàn)網(wǎng)絡(luò)的聚類特征；R3表示算法能兼顧網(wǎng)絡(luò)微觀特征。

2.2 設(shè)計細(xì)節(jié)

為體現(xiàn)網(wǎng)絡(luò)中的聚類特征，需預(yù)先對網(wǎng)絡(luò)進(jìn)行社團(tuán)劃分以得到社團(tuán)結(jié)構(gòu)。社團(tuán)劃分部分會增加算法的總體耗時，為減少該部分的計算時間，需要選擇一個低時間復(fù)雜度的社團(tuán)劃分算法（R1）。相比于全局社團(tuán)劃分算法，局部社團(tuán)劃分算法從種子節(jié)點(diǎn)出發(fā)，通過擴(kuò)展種子節(jié)點(diǎn)來獲得社團(tuán)結(jié)構(gòu)，具有天然的并行性。此外，局部社團(tuán)劃分算法自下而上地尋找種子節(jié)點(diǎn)所屬的社團(tuán)，更好地保留了網(wǎng)絡(luò)的局部社團(tuán)結(jié)構(gòu)。

結(jié)合多層次布局思想，利用社團(tuán)結(jié)構(gòu)對網(wǎng)絡(luò)進(jìn)行壓縮以得到規(guī)模更小的粗化網(wǎng)絡(luò)。為體現(xiàn)網(wǎng)絡(luò)中的聚類特征并展示各個聚類間連接關(guān)系，利用加權(quán)排斥力和吸引力對最粗化網(wǎng)絡(luò)進(jìn)行布局使得布局能體現(xiàn)網(wǎng)絡(luò)整體結(jié)構(gòu)（R2）。

在細(xì)化階段，為兼顧社團(tuán)內(nèi)部的結(jié)構(gòu)，利用節(jié)點(diǎn)度信息得到各節(jié)點(diǎn)對間個性化理想距離，以改進(jìn)FR算法完成細(xì)化（R3）。

2.2.1 數(shù)據(jù)預(yù)處理

本文算法考慮的復(fù)雜網(wǎng)絡(luò)為無向、無權(quán)的網(wǎng)絡(luò)，因此對于有向網(wǎng)絡(luò)或帶權(quán)網(wǎng)絡(luò)需經(jīng)過預(yù)處理轉(zhuǎn)換為無向、無權(quán)的網(wǎng)絡(luò)。對于有向網(wǎng)絡(luò)，有兩種處理方式：a）如果一對節(jié)點(diǎn)之間存在兩條有向邊則合并為一條無向邊，否則刪除。這種方式可能會導(dǎo)致網(wǎng)絡(luò)中的連邊大量減少，也會造成部分節(jié)點(diǎn)成為孤立節(jié)點(diǎn)。b）合并節(jié)點(diǎn)間雙向連邊的同時將節(jié)點(diǎn)間只有一條有向邊改為無向邊，為了盡可能保留更多的節(jié)點(diǎn)和邊，本文選擇了第二種方式。對于帶權(quán)的網(wǎng)絡(luò)，將所有邊權(quán)重設(shè)置為1。此外，對于存在自環(huán)邊的網(wǎng)絡(luò)，刪除其中的自環(huán)邊。

2.2.2 基于個性化PageRank社團(tuán)劃分的粗化

局部社團(tuán)劃分算法通常包含種子節(jié)點(diǎn)選擇、種子節(jié)點(diǎn)擴(kuò)展和社團(tuán)合并三個步驟。算法首先選擇部分節(jié)點(diǎn)作為種子節(jié)點(diǎn)，并基于種子節(jié)點(diǎn)擴(kuò)展以獲得包含該種子節(jié)點(diǎn)的社團(tuán)結(jié)構(gòu)。種子節(jié)點(diǎn)的選擇較為重要，理想的種子節(jié)點(diǎn)應(yīng)隸屬于不同社團(tuán)且為社團(tuán)的中心。有關(guān)研究表明，網(wǎng)絡(luò)中度高的節(jié)點(diǎn)易成為社團(tuán)的中心節(jié)點(diǎn)［20］，因此本文基于節(jié)點(diǎn)的度來實(shí)現(xiàn)種子節(jié)點(diǎn)的選擇。同時，為了使種子節(jié)點(diǎn)更好地覆蓋網(wǎng)絡(luò)，在選擇種子節(jié)點(diǎn)時忽略已經(jīng)選擇節(jié)點(diǎn)的鄰居節(jié)點(diǎn)及其二階鄰居節(jié)點(diǎn)。種子節(jié)點(diǎn)算法步驟描述如下：

算法1 種子節(jié)點(diǎn)選擇算法

輸入：鄰接矩陣 A ；種子節(jié)點(diǎn)數(shù)量K 。

輸出：種子節(jié)點(diǎn)集合 seeds 。

a）基于鄰接矩陣 A ，計算出各個節(jié)點(diǎn)的度信息。

b）根據(jù)度信息對節(jié)點(diǎn)進(jìn)行降序排序，得到節(jié)點(diǎn)序列 seq 。

c）根據(jù)序列 seq 依次將節(jié)點(diǎn)加入 seeds 。

對于節(jié)點(diǎn) i，如其未被標(biāo)記則加入seeds ，并將其鄰居節(jié)點(diǎn)和二階鄰居節(jié)點(diǎn)標(biāo)記；

若 seeds 中節(jié)點(diǎn)數(shù)量大于 K 或到達(dá) seq 尾部則停止算法，否則繼續(xù)執(zhí)行步驟c）。

值得注意的是，種子節(jié)點(diǎn)數(shù)量 K 的設(shè)置可以根據(jù)網(wǎng)絡(luò)規(guī)模進(jìn)行調(diào)整。同時 K 的設(shè)置并不會影響算法的結(jié)果，當(dāng) K 過大時后續(xù)流程會對重合度較高的社團(tuán)進(jìn)行合并；當(dāng) K 過小時，后續(xù)流程會在未覆蓋的節(jié)點(diǎn)中選擇新的種子節(jié)點(diǎn)以繼續(xù)算法。

在得到種子節(jié)點(diǎn)后，基于種子節(jié)點(diǎn)進(jìn)行擴(kuò)展以完成社團(tuán)劃分。擴(kuò)展階段需要計算種子節(jié)點(diǎn)與其余節(jié)點(diǎn)間的相似度，與種子節(jié)點(diǎn)越相似則越可能屬于種子節(jié)點(diǎn)所屬社團(tuán)。本文使用個性PageRank來計算網(wǎng)絡(luò)中其余節(jié)點(diǎn)與種子節(jié)點(diǎn)的相關(guān)性。個性化PageRank繼承了PageRank的思想，模擬用戶通過鏈接隨機(jī)訪問網(wǎng)絡(luò)中節(jié)點(diǎn)的行為來計算穩(wěn)定狀態(tài)下各個節(jié)點(diǎn)受訪問的概率。與PageRank不同的是個性化PageRank在隨機(jī)游走中的跳轉(zhuǎn)行為具有偏好性。因此，個性化PageRank可被用于計算其余節(jié)點(diǎn)與種子節(jié)點(diǎn)的相關(guān)性?；陔S機(jī)游走的個性化PageRank給定一個參數(shù) α 表示跳轉(zhuǎn)概率，則在隨機(jī)游走過程中，在任意一個節(jié)點(diǎn)式會以 α 的概率選擇該節(jié)點(diǎn)的鄰居節(jié)點(diǎn)進(jìn)行游走；以 1-α 的概率回到偏好初始節(jié)點(diǎn)。個性化PageRank值計算公式為

ppr "s（v）=（1-α） 1 |S| +α∑ n u=1 "A uv d u "ppr "s（v） ""（3）

式（3）表示，隨機(jī)游走過程中，對于當(dāng)前點(diǎn) u 會以 αA uv/d u 跳轉(zhuǎn)到點(diǎn) v ，同時有 1-α 的概率回到種子節(jié)點(diǎn)集 s 。其中向量 ppr "s 被稱為與種子節(jié)點(diǎn)集 s 相關(guān)聯(lián)的個性化PageRank向量。

對于種子節(jié)點(diǎn) s ，首先基于種子節(jié)點(diǎn) s 計算網(wǎng)絡(luò)中所有節(jié)點(diǎn)與之相關(guān)聯(lián)的個性化PageRank值。直接使用冪迭代計算個性化PageRank向量所花費(fèi)的時間開銷太大，因此本文使用書簽著色法［21］來計算。然后根據(jù) ppr "s 對節(jié)點(diǎn)進(jìn)行降序得到序列 n 1，n 2，…，n m，其中 ppr "s（n i）gt; ppr "s（n i+1） 。并根據(jù)排序依次將節(jié)點(diǎn) n i 加入種子節(jié)點(diǎn)所處的社團(tuán) c ，并計算此刻的傳導(dǎo)率。選擇取得最大傳導(dǎo)率的節(jié)點(diǎn)作為切點(diǎn)，將切點(diǎn)及切點(diǎn)前的節(jié)點(diǎn)所構(gòu)成的社團(tuán)作為基于種子節(jié)點(diǎn) s 擴(kuò)展得到的社團(tuán) c s 。傳導(dǎo)率計算公式為

cond（ c i） = cut （c i） "min（links （c i，V） ，links（ "V c i ，V））

cut （c i） =links（ c i， V c i ） """"（4）

其中：links（ c i，c j） 表示集合 c i 中節(jié)點(diǎn)與集合 c j 中節(jié)點(diǎn)間連邊之和； V 表示全體節(jié)點(diǎn)組成的集合。算法步驟描述如下：

算法2 基于個性化PageRank的社團(tuán)劃分算法

輸入：鄰接矩陣 A ，種子節(jié)點(diǎn)集S 。

輸出：種子節(jié)點(diǎn)集 S 擴(kuò)展得到的社團(tuán) c s 。

a）適用書簽著色算法得到基于 S 的個性化PageRank值 ppr "s 。

b）根據(jù) ppr "s 對節(jié)點(diǎn)進(jìn)行降序排序得到序列 seq 。

c）根據(jù)序列 seq 依次將節(jié)點(diǎn)加入社團(tuán) C 。

對于節(jié)點(diǎn) i "，將其加入社團(tuán) C ；

計算此時的傳導(dǎo)率 Con i ；

若已達(dá)到序列尾則執(zhí)行步驟d），否則繼續(xù)執(zhí)行步驟c）。

d）尋找 Con 中的最大值 Con max ，以 max 作為切點(diǎn)，將 seq 中 max 及 max 前的節(jié)點(diǎn)組成的社團(tuán)記為 c s ，并返回以結(jié)束算法。

對于 K 個種子節(jié)點(diǎn)，經(jīng)過上述步驟可得到 K 個社團(tuán)，若網(wǎng)絡(luò)中節(jié)點(diǎn)重復(fù)率過低可繼續(xù)在未覆蓋的節(jié)點(diǎn)中選擇新的種子并重復(fù)上述步驟，直到所有節(jié)點(diǎn)均被覆蓋或節(jié)點(diǎn)覆蓋率超過預(yù)設(shè)定的值。然而，基于種子節(jié)點(diǎn)擴(kuò)展得到的社團(tuán)可能存在高度重合的情況，為此，在完成社團(tuán)劃分后需對重合度高的社團(tuán)進(jìn)行合并。本文使用式（5）來計算社團(tuán)間的重合度

overlap= |c i∩c j| "max （|c i|，|c j|） """（5）

當(dāng)兩個社團(tuán)的重合度較高時，對其進(jìn)行合并。同時對于一些規(guī)模超大的網(wǎng)絡(luò)，劃分后的社團(tuán)仍具有大量節(jié)點(diǎn)，可對社團(tuán)內(nèi)部進(jìn)行二次劃分以形成多層結(jié)構(gòu)。

為粗化網(wǎng)絡(luò)，根據(jù)劃分結(jié)果對網(wǎng)絡(luò)中的節(jié)點(diǎn)進(jìn)行壓縮。將網(wǎng)絡(luò)中的社團(tuán) c i 抽象為節(jié)點(diǎn) n i ，則 n i 與 n j 間的連邊權(quán)重為社團(tuán) c i 與 c j 的連邊和。由于劃分得到的社團(tuán)結(jié)構(gòu)可能重疊，所以在對網(wǎng)絡(luò)進(jìn)行抽象時需要考慮重疊社團(tuán)的處理。本文將屬于且僅屬于同一個社團(tuán)的節(jié)點(diǎn)抽象為一個節(jié)點(diǎn)，并將重疊的社團(tuán)單獨(dú)抽象為節(jié)點(diǎn)。即將全部屬于且僅屬于社團(tuán) i 的節(jié)點(diǎn)抽象為節(jié)點(diǎn) c i ，把同時屬于且僅屬于社團(tuán) i 和 j 的節(jié)點(diǎn)抽象為 c ij ，依此類推，以得到一個節(jié)點(diǎn)代表一個社團(tuán)的粗化網(wǎng)絡(luò)。

2.2.3 改進(jìn)FR算法的多層次布局

在粗化網(wǎng)絡(luò)中，一個節(jié)點(diǎn)代表一個或多個社團(tuán)，為了清晰地展示網(wǎng)絡(luò)各個社團(tuán)間的連接關(guān)系、使社團(tuán)邊界明顯，設(shè)計了粗化網(wǎng)絡(luò)初始布局。計算粗化網(wǎng)絡(luò)布局時引力、斥力及重力公式為

f r=k×num i×num j/d

f a=d2×w ij/（ k×num i×num j ×w max）

f g=k g×num i×d """"（6）

其中： num i 表示社團(tuán) i 內(nèi)部的節(jié)點(diǎn)數(shù)量； w ij 表示邊權(quán)重； k 為距離系數(shù)用于調(diào)節(jié)節(jié)點(diǎn)間距離。

在得到初始布局后，根據(jù)初始布局對網(wǎng)絡(luò)進(jìn)行細(xì)化、還原，即對應(yīng)社團(tuán)內(nèi)部節(jié)點(diǎn)的布局。傳統(tǒng)FR布局算法基于節(jié)點(diǎn)均勻分布和邊長統(tǒng)一等原則， 因此不能很好地體現(xiàn)網(wǎng)絡(luò)的結(jié)構(gòu)信息，如網(wǎng)絡(luò)中的中心節(jié)點(diǎn)、網(wǎng)絡(luò)形狀等信息。本文利用節(jié)點(diǎn)度來改進(jìn)FR布局，即度大的節(jié)點(diǎn)之間的距離應(yīng)較大，度小的節(jié)點(diǎn)之間的距離應(yīng)較小。為了實(shí)現(xiàn)這一目標(biāo)，本文改變了FR算法中節(jié)點(diǎn)間統(tǒng)一理想距離，為每一對節(jié)點(diǎn)分別計算理想距離 tk 。

tk（i，j）= k d id j "|V| """（7）

其中： d i 表示節(jié)點(diǎn) i 在社團(tuán)內(nèi)的度； |V| 表示節(jié)點(diǎn) i 所屬社團(tuán)內(nèi)節(jié)點(diǎn)的數(shù)量； k 為距離系數(shù)，與節(jié)點(diǎn)的數(shù)量相關(guān)。

引力、斥力計算公式為

f r= tk2 dis

f a= dis2 tk """"（8）

其中： dis 表示節(jié)點(diǎn)之間的歐氏距離；同時為了使布局位于畫圖中心，為每個節(jié)點(diǎn)添加了指向布局中心的重力。

f g=k g×dis×d i ""（9）

其中： dis 表示節(jié)點(diǎn) i 與畫布中心的歐氏距離； k g 為系數(shù)用于控制重力的強(qiáng)度。如此，網(wǎng)絡(luò)中度大的節(jié)點(diǎn)所受到的重力越大、越容易處于布局中心。

圖1中展示本文提出的個性化理想邊長度布局和統(tǒng)一理想邊長度布局，對比可知圖（a）中度大的節(jié)點(diǎn)間距離遠(yuǎn)大于度小的節(jié)點(diǎn)間距離，突出展示了網(wǎng)絡(luò)中度大的中心節(jié)點(diǎn)。

此外，基于隨機(jī)初始節(jié)點(diǎn)位置的布局算法得到的布局結(jié)果不唯一，因此本文使用初始化布局來唯一確定布局結(jié)果。同時，一個好的初始化布局有利于節(jié)點(diǎn)快速達(dá)到收斂位置。

初始化布局算法基于“度大的節(jié)點(diǎn)應(yīng)位于布局中心，與外部社團(tuán)有連接的節(jié)點(diǎn)應(yīng)位于相應(yīng)方向的布局邊緣”這一原則來實(shí)現(xiàn)對社團(tuán)內(nèi)部節(jié)點(diǎn)位置的初始化。此時節(jié)點(diǎn)的度指社團(tuán)內(nèi)部的度，即計算節(jié)點(diǎn)度時僅考慮與社團(tuán)內(nèi)節(jié)點(diǎn)間的連邊。如圖2所示，初始布局使用圓形布局，并根據(jù)社團(tuán)內(nèi)節(jié)點(diǎn)數(shù)量來計算初始布局面積。首先將社團(tuán)內(nèi)的節(jié)點(diǎn)分為只與社團(tuán)內(nèi)節(jié)點(diǎn)相連的節(jié)點(diǎn)和與其他社團(tuán)內(nèi)節(jié)點(diǎn)有連邊的節(jié)點(diǎn)兩類，分別記為內(nèi)部節(jié)點(diǎn)和邊緣節(jié)點(diǎn)。社團(tuán)內(nèi)與其他社團(tuán)相連的邊緣節(jié)點(diǎn)的理想分布位置是區(qū)域A和B所組成的扇形，而其余內(nèi)部節(jié)點(diǎn)的分布位置應(yīng)在區(qū)域C和D中。其中邊緣節(jié)點(diǎn)中度大的節(jié)點(diǎn)表示與社團(tuán)聯(lián)系較為緊密，應(yīng)放置在區(qū)域B，而其他度較小的節(jié)點(diǎn)應(yīng)放置在區(qū)域A。區(qū)域A和B所組成扇形的面積由邊緣節(jié)點(diǎn)占所有節(jié)點(diǎn)比例計算而得。

因此，社團(tuán)內(nèi)部節(jié)點(diǎn)的初始位置計算公式為

x i=r× cos "α

y i=r× sin "α

r= d i d max

α= "2π- （θ 1-θ 2） |V inner| ×i ""（10）

邊緣節(jié)點(diǎn)的初始位置計算為

x i=r× cos "α

y i=r× sin "α "r= d i d max

α= （θ 1-θ 2） |V outer| ×i ""（11）

此外，為了提高算法效率，在細(xì)化階段本文還使用了四叉樹空間分解［4］來加速布局算法。

2.3 算法復(fù)雜度分析

本文算法耗時主要由粗化階段、初始布局和細(xì)化階段組成。 對于一個網(wǎng)絡(luò) G=（V，E） ，在粗化階段中，局部社團(tuán)劃分使用標(biāo)簽著色法來計算基于某一種子節(jié)點(diǎn)的個性化PageRank向量，其時間復(fù)雜度接近線性。則社團(tuán)劃分階段通過 K 種子進(jìn)行社團(tuán)劃分的時間復(fù)雜度為 O（|V|） ；對于初始布局階段，最粗化網(wǎng)絡(luò)往往僅包含少量的節(jié)點(diǎn)和邊，記為 G 1=（V 1，E 1） ，則初始布局階段斥力、引力計算時間復(fù)雜度為 O（|V 1|2+|E 1|） ；在細(xì)化階段，布局的規(guī)模變成了某個社團(tuán)內(nèi)部，記為 G 2=（V 2，E 2） ，其中 |V 2|lt;|V|/K ，由于使用了空間分解來近似計算斥力，其布局時間復(fù)雜度為 O（|V 2| "log "|V 2|+|E 2|） 。

3 實(shí)驗(yàn)結(jié)果與分析

3.1 實(shí)驗(yàn)設(shè)計

為展示本文算法的布局效果并驗(yàn)證算法的有效性，選取了如表1所示的不同規(guī)模、 不同類型的復(fù)雜網(wǎng)絡(luò)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。所選數(shù)據(jù)集［22，23］主要包括社交網(wǎng)絡(luò)、引文網(wǎng)絡(luò)以及樹型網(wǎng)絡(luò)等。表1中所示的模塊度和社團(tuán)數(shù)量均是louvain算法［24］計算得到的結(jié)果，其中部分?jǐn)?shù)據(jù)為有向網(wǎng)絡(luò)、帶權(quán)網(wǎng)絡(luò)，統(tǒng)計的信息均為經(jīng)過數(shù)據(jù)預(yù)處理后得到無向、無權(quán)網(wǎng)絡(luò)信息。

其次，為進(jìn)行對比實(shí)驗(yàn)，選取了FM3［25］、OpenOrd［9］、Hu［8］、ForceAtlas2［6］以及GRA［17］算法用做對比。其中FM3、OpenOrd、Hu、GRA均是基于多層次布局思想實(shí)現(xiàn)的、用于大規(guī)模網(wǎng)絡(luò)的經(jīng)典布局算法；同時GRA算法還利用社團(tuán)信息來計算社團(tuán)內(nèi)部與社團(tuán)間節(jié)點(diǎn)之間的加權(quán)排斥力和吸引力。

對應(yīng)第2章提出的三個需求設(shè)計了如下三部分實(shí)驗(yàn)。首先在算法的效率方面，統(tǒng)計并比較不同數(shù)據(jù)在不同算法上的運(yùn)行時間；其次，在布局質(zhì)量方面，從整體上主要驗(yàn)證本文算法是否能有效展示網(wǎng)絡(luò)中的聚類特征以及各個聚類間的連接關(guān)系；在局部上主要驗(yàn)證本文算法生成的布局是否能夠清晰地展示各個聚類內(nèi)結(jié)構(gòu)信息。

所有實(shí)驗(yàn)結(jié)果均在同一設(shè)備上運(yùn)行所得，設(shè)備相關(guān)配置如下：CPU為Intel i5-8500@3.00 GHz，內(nèi)存大小為12 GB。其中OpenOrd、Hu、ForceAtlas2算法布局結(jié)果通過Gephi［7］運(yùn)行得到，F(xiàn)M3算法代碼來自O(shè)GDF［26］。

3.2 實(shí)驗(yàn)結(jié)果

3.2.1 算法耗時對比

各算法在不同數(shù)據(jù)集上運(yùn)行時間如表2所示，其中由于ForceAtlas2算法為持續(xù)式算法，需人為停止算法，其收斂較快，所以本文將其停止條件設(shè)置為算法迭代500次；GRA算法收斂速度較慢，迭代次數(shù)太多，在此統(tǒng)計了最多2 000次迭代時間。再者，GRA算法在部分?jǐn)?shù)據(jù)上耗時太久，在有限時間內(nèi)未得到結(jié)果，故未統(tǒng)計。

實(shí)驗(yàn)結(jié)果如表2所示， 除部分規(guī)模較小的網(wǎng)絡(luò)外，本文算法的耗時均低于其他算法。本文算法利用社團(tuán)劃分對網(wǎng)絡(luò)進(jìn)行粗化以實(shí)現(xiàn)多層次布局，而對于小規(guī)模的網(wǎng)絡(luò)而言，使用社團(tuán)劃分所帶來的耗時遠(yuǎn)高于多層次布局所節(jié)約的時間。隨著網(wǎng)絡(luò)規(guī)模的增加，使用多層次布局思想的算法會體現(xiàn)出更好的優(yōu)越性。

3.2.2 網(wǎng)絡(luò)聚類特征展示評估

blogs數(shù)據(jù)集是2005年記錄的關(guān)于美國政治的博客之間超鏈接組成的網(wǎng)絡(luò)。由表1可知，該網(wǎng)絡(luò)共包含12個社團(tuán)。但除兩個社團(tuán)外其余社團(tuán)均只包含少量的節(jié)點(diǎn)。因此，其布局結(jié)果能明顯地被分為兩部分。如圖3所示，除FM3和Hu算法外，其余算法的布局結(jié)構(gòu)都能明顯地將網(wǎng)絡(luò)分為兩部分，但OpenOrd和ForceAtlas2算法的布局節(jié)點(diǎn)分布密集以至于較多重疊。相比而言，本文算法的布局結(jié)果中兩個聚類邊界更為清晰。

圖4展示了Facebook_4039數(shù)據(jù)集在不同布局算法下得到的布局結(jié)果，該數(shù)據(jù)是典型性的社交網(wǎng)絡(luò)數(shù)據(jù)，具有較強(qiáng)的社團(tuán)結(jié)構(gòu)。對比可知，F(xiàn)orceAtlas2的布局結(jié)果和OpenOrd的布局結(jié)果中聚類內(nèi)的節(jié)點(diǎn)布局過于緊湊，以至于出現(xiàn)大量節(jié)點(diǎn)重疊，無法從中獲取聚類規(guī)模和內(nèi)部結(jié)構(gòu)等信息；GRA得到的布局符合傳統(tǒng)美學(xué)標(biāo)準(zhǔn)，具有對稱性、節(jié)點(diǎn)分布均勻等特點(diǎn)，但各個聚類邊界較為模糊，同時各個聚類間存在邊大量交叉的情況；Hu和FM3的布局能有效展示網(wǎng)絡(luò)的骨架結(jié)構(gòu)，同時在一定程度上兼顧網(wǎng)絡(luò)宏觀和中觀結(jié)構(gòu)，但不能體現(xiàn)各個聚類內(nèi)的結(jié)構(gòu)特征。與這些算法相比，本文算法能同時展示網(wǎng)絡(luò)整體結(jié)構(gòu)、各個聚類間的結(jié)構(gòu)信息，兼顧整體與局部。并且能體現(xiàn)各個聚類的規(guī)模以及形狀，這一點(diǎn)將在后續(xù)進(jìn)一步驗(yàn)證。

除視覺效果外，本文采用文獻(xiàn)［11］的度量指標(biāo)來定量評估本文算法在聚類模式展示的有效性，該度量指標(biāo)被提出用于衡量布局算法是否真實(shí)表現(xiàn)了網(wǎng)絡(luò)的聚類模式。對于一個布局，首先忽略其連邊、僅考慮節(jié)點(diǎn)位置，并根據(jù)節(jié)點(diǎn)位置對其聚類，通過計算聚類結(jié)果與網(wǎng)絡(luò)真實(shí)社團(tuán)結(jié)構(gòu)相似度來評價布局的好壞。根據(jù)其思想，對于沒有真實(shí)社團(tuán)結(jié)構(gòu)的網(wǎng)絡(luò)可使用社團(tuán)劃分算法得到的結(jié)果作為真實(shí)社團(tuán)結(jié)構(gòu)。本文使用的聚類算法是DBSCAN，使用調(diào)整互信息（adjusted mutual information，AMI）來衡量聚類間的相似性，該值越高表示兩組聚類越相似，即布局算法越能真實(shí)表現(xiàn)網(wǎng)絡(luò)聚類特征。

實(shí)驗(yàn)結(jié)果如表3所示。由于DBSCAN需設(shè)置參數(shù)，表中的AMI值均是循環(huán)多次不同參數(shù)得到的最高值。由表3可知，與其他算法相比，本文算法在大部分?jǐn)?shù)據(jù)集上能取得最高的AMI值。在少部分?jǐn)?shù)據(jù)集上的AMI值接近或略低于取得最高值的算法，但遠(yuǎn)高于最低值。說明本文算法在布局上能夠較好地還原網(wǎng)絡(luò)的真實(shí)社團(tuán)結(jié)構(gòu)，有效反映網(wǎng)絡(luò)中的真實(shí)聚類特征。

3.2.3 網(wǎng)絡(luò)局部結(jié)構(gòu)展示評估

在上述實(shí)驗(yàn)中，一個布局可通過聚類算法得到多個的聚類，本文算法能夠較好地體現(xiàn)網(wǎng)絡(luò)的聚類特征。然而一個好的布局算法還應(yīng)能清晰、正確地展示網(wǎng)絡(luò)聚類即社團(tuán)內(nèi)部結(jié)構(gòu)，以給予用戶探索網(wǎng)絡(luò)局部結(jié)構(gòu)的能力。為驗(yàn)證本文算法展示網(wǎng)絡(luò)局部結(jié)構(gòu)的有效性，選擇了FM3、Hu以及GRA算法與本文算法進(jìn)行對比實(shí)驗(yàn)，因在3.2.2節(jié)實(shí)驗(yàn)中OpenOrd和ForceAtlas2算法的布局結(jié)果中社團(tuán)內(nèi)部節(jié)點(diǎn)重疊過多，難以體現(xiàn)局部結(jié)構(gòu)，故未選擇。

對于Facebook_4039數(shù)據(jù)集，F(xiàn)M3算法的布局被劃分為八個聚類；Hu算法的布局被劃分為九個聚類；GRA算法的布局被劃分為11個聚類；而本文算法的布局被劃分為14個聚類。其中，聚類的數(shù)量均為有效聚類，即刪除掉部分僅包含小于10個節(jié)點(diǎn)的聚類。

圖5分別展示了本文算法、FM3、Hu和GRA算法在Facebook_4039上的三個聚類。對比可知GRA算法的布局圖（l）（n）中節(jié)點(diǎn)分布較為均勻、邊長較為統(tǒng)一；FM3算法的布局圖（d）（f）未能完全展開，無法體現(xiàn)聚類本來的結(jié)構(gòu)和形狀；圖（g）（h）（m）同理；而本文算法的布局中，其結(jié)構(gòu)相對展開完全，能還原局部結(jié)構(gòu)的形狀、特征。

文獻(xiàn)［17］中列舉了社團(tuán)常見的三種結(jié)構(gòu)，其中包括中心節(jié)點(diǎn)—邊緣節(jié)點(diǎn)結(jié)構(gòu)和類全連接結(jié)構(gòu)。圖5中，對于中心節(jié)點(diǎn)—邊緣節(jié)點(diǎn)這一結(jié)構(gòu)，例如圖（c）（f）（k）以及（h），所有算法的布局均能體現(xiàn)出中心節(jié)點(diǎn)，而本文算法的布局圖（c）更還原了其原本的形狀。對于類全連接結(jié)構(gòu)，例如圖（a）（e）（m），F(xiàn)M3和GRA算法的布局節(jié)點(diǎn)重疊較多，以至于無法判斷節(jié)點(diǎn)數(shù)量，呈現(xiàn)“毛球”形狀，與本文算法相比，其無法體現(xiàn)聚類的規(guī)模。

進(jìn)一步，本文使用了以下三個指標(biāo)［27］來評估上述算法在各個聚類上的布局質(zhì)量：a） M c 邊交叉最小化，用于衡量布局中邊交叉數(shù)量的多少；b） M s 形狀度量指標(biāo)，用于衡量布局是否真實(shí)反映了網(wǎng)絡(luò)的形狀；c） M a 該指標(biāo)的量化標(biāo)準(zhǔn)為最大化節(jié)點(diǎn)連邊的最小入射角，通過計算相鄰入邊射角度的平均差獲得。

實(shí)驗(yàn)結(jié)果從圖6中可知，對于 M c 指標(biāo)而言，四個算法都能取得較高的值且差異不大；而對于 M s和M a 指標(biāo)，F(xiàn)M3、Hu和GRA算法大部分聚類評分較低，僅個別聚類分值較高。

取平均值后結(jié)果見表4，可知本文算法的平均值在各個指標(biāo)上均高于其他算法。其中 M s和M a 顯著高于其他算法。表明本文算法生成的布局在局部上與其他算法相比表現(xiàn)出邊交叉更少、相鄰邊入射邊角度差更小，同時能更好還原其局部結(jié)構(gòu)的形狀，表現(xiàn)出較好的布局效果。

綜上，本文算法能在有效時間內(nèi)生成較高質(zhì)量的布局，在整體上本文算法能夠突出網(wǎng)絡(luò)的聚類特征，在局部上也能清晰展示聚類內(nèi)部結(jié)構(gòu)，給予用戶從不同層次探索網(wǎng)絡(luò)結(jié)構(gòu)的能力。

4 結(jié)束語

針對復(fù)雜網(wǎng)絡(luò)聚類特征展示需要，本文基于局部社團(tuán)劃分和多層次布局思想提出了一個兼顧網(wǎng)絡(luò)整體結(jié)構(gòu)和局部細(xì)節(jié)的網(wǎng)絡(luò)布局算法。算法利用種子節(jié)點(diǎn)和個性化PageRank對網(wǎng)絡(luò)進(jìn)行社團(tuán)劃分，并利用社團(tuán)結(jié)構(gòu)對網(wǎng)絡(luò)進(jìn)行粗化。設(shè)計加權(quán)引力和斥力來計算粗化網(wǎng)絡(luò)布局，并利用節(jié)點(diǎn)度信息改進(jìn)FR算法來細(xì)化網(wǎng)絡(luò)。實(shí)驗(yàn)結(jié)果表明，在效率方面，本文算法在絕大部分網(wǎng)絡(luò)上運(yùn)行時間少于其他的算法；在布局質(zhì)量方面，整體上能較好地體現(xiàn)網(wǎng)絡(luò)的真實(shí)聚類特征，在局部上兼顧了聚類內(nèi)的網(wǎng)絡(luò)結(jié)構(gòu)、真實(shí)還原其結(jié)構(gòu)形狀。滿足用戶對不同層次探索復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)的需要。在后續(xù)的工作中，將繼續(xù)改進(jìn)本文算法，并結(jié)合動態(tài)網(wǎng)絡(luò)布局，將基于社團(tuán)結(jié)構(gòu)的布局算法擴(kuò)展到動態(tài)網(wǎng)絡(luò)中。相較于靜態(tài)網(wǎng)絡(luò)而言，時變的動態(tài)網(wǎng)絡(luò)更加貼切真實(shí)變化的復(fù)雜系統(tǒng)。

參考文獻(xiàn)：

［1］ "Eades P.A heuristic for graph drawing［J］. Congressus Numerantium ，1984， 42 ：149-160.

［2］ Kamada T，Kawai S.An algorithm for drawing general undirected graphs［J］. Information Processing Letters ，1989， 31 （1）：7-15.

［3］ Fruchterman T M J，Reingold E M.Graph drawing by force-directed placement［J］. Software：Practice and Experience ，1991， 21 （11）：1129-1164.

［4］ Barnes J，Hut P.A hierarchical "O（N "log "N ） force-calculation algorithm［J］. Nature ，1986， 324 （6096）：446-449.

［5］ Walshaw C.A multilevel algorithm for force-directed graph drawing［C］//Proc of the 19th International Symposium on Graph Drawing.Heidelberg，Berlin：Springer，2011：171-182.

［6］ Jacomy M，Venturini T，Heymann S， et al. "ForceAtlas2，a continuous graph layout algorithm for handy network visualization designed for the Gephi software［J］. PLoS One ，2014， 9 （6）：e98679.

［7］ Bastian M，Heymann S，Jacomy M.Gephi：an open source software for exploring and manipulating networks［C］//Proc of the 3rd International AAAI Conference on Weblogs and Social Media.Palo Alto，CA：AAAI Press，2009：361-362.

［8］ Hu Yifan.Efficient，high-quality force-directed graph drawing［J］. Mathematica Journal ，2005， 10 （1）：37-71.

［9］ Martin S，Brown W M，Klavans R， et al. OpenOrd：an open-source toolbox for large graph layout［C］//Proc of Visualization and Data Analysis.2011：786806.

［10］ Eades P，Hong S H，Klein K， et al. Shape-based quality metrics for large graph visualization［C］//Proc of the 23rd International Symposium on Graph Drawing and Network Visualization.2015：502-514.

［11］ Meidiana A，Hong S H，Eades P， et al. A quality metric for visualization of clusters in graphs［M］//Archambault D，Tóth C.Graph Drawing and Network Visualization.Cham：Springer，2019：125-138.

［12］ 趙潤乾，吳渝，陳昕.大規(guī)模社交網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)及可視化算法［J］.計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報，2017， 29 （2）：328-336. （Zhao Runqian，Wu yu，Chen Xin.Large-scale social network community discovery and visualization algorithm［J］. Journal of Computer-Aided Design and Computer Graphics ，2017， 29 （2）：328-336.）

［13］ 吳渝，李藻旭，李紅波，等.展示復(fù)雜網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)的社團(tuán)引力導(dǎo)引的布局算法［J］.計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報，2015， 27 （8）：1460-1467. （Wu Yu，Li Zaoxu，Li Hongbo， et al. "Layout algorithm of community gravitational guidance showing complex network community structure［J］. Journal of Computer-Aided Design and Computer Graphics ，2015， 27 （8）：1460-1467.）

［14］ 吳玲達(dá)，張喜濤，孟祥利.基于社團(tuán)結(jié)構(gòu)節(jié)點(diǎn)重要性的網(wǎng)絡(luò)可視化壓縮布局［J］.北京航空航天大學(xué)學(xué)報，2019， 45 （12）：2423-2430. （Wu lingda，Zhang Xitao，Meng Xiangli.Compression layout for network visualization based on node importance for community structure［J］. Journal of Beijing University of Aeronautics and Astronautics ，2019， 45 （12）：2423-2430.）

［15］ Hong S H，Eades P，Torkel M， et al. Multi-level graph drawing using infomap clustering［C］//Proc of International Symposium on Graph Drawing and Network Visualization.Berlin：Springer，2019：139-146.

［16］ Hong S H，Eades P，Torkel M， et al .Louvain-based multi-level graph drawing［C］//Proc of the 14th Pacific Visualization Symposium.Piscataway，NJ：IEEE Press，2021：151-155.

［17］ Huang Zhenhua，Wu Junxian，Zhu Wentao， et al. Visualizing complex networks by leveraging community structures［J］. Physica A：Statistical Mechanics and its Applications ，2021， 565 （3）：125506.

［18］ 李輝，陳福才，張建朋，等.復(fù)雜網(wǎng)絡(luò)中的社團(tuán)發(fā)現(xiàn)算法綜述［J］.計算機(jī)應(yīng)用研究，2021， 38 （6）：1611-1618. （Li Hui，Chen Fucai，Zhang Jianpeng， et al. Survey of community detection algorithms in complex network［J］. Application Research of Computers ，2021， 38 （6）：1611-1618.）

［19］ Hollocou A，Bonald T，Lelarge M.Multiple local community detection［J］. ACM SIGMETRICS Performance Evaluation Review ，2018， 45 （3）：76-83.

［20］ Whang J J，Gleich D F，Dhillon I S.Overlapping community detection using neighborhood-inflated seed expansion［J］. IEEE Trans on Knowledge and Data Engineering ，2016， 28 （5）：1272-1284.

［21］ Berkhin P.Bookmark-coloring algorithm for personalized PageRank computing［J］. Internet Mathematics ，2006， 3 （1）：41-62.

［22］ Leskovec J，Krevl A.SNAP datasets：Stanford large network dataset collection［DB/OL］. （2014）.http：//snap.stanford.edu/data/.

［23］ Davis T A，Hu Yifan.The University of Florida sparse matrix collection［J］. ACM Trans on Mathematical Software ，2011， 38 （1）：article No.1.

［24］ Blondel V D，Guillaume J L，Lambiotte R， et al. Fast unfolding of communities in large networks［J］. Journal of Statistical Mechanics：Theory and Experiment ，2008， 10 ：P10008.

［25］ Hachul S，Jünger M.Drawing large graphs with a potential-field-based multilevel algorithm［C］//Proc of the 12th International Symposium of Graph Drawing.Heidelberg，Berlin：Springer，2004：285-295.

［26］ Chimani M，Gutwenger C，Jünger M， et al. The open graph drawing framework（OGDF）［M］//Tamassia R.Handbook of Graph Drawing and Visualization.2014.

［27］ Kwon O H，Crnovrsanin T，Ma K L.What would a graph look like in this layout？A machine learning approach to large graph visualization［J］. IEEE Trans on Visualization and Computer Graphics， 2018， 24 （1）：478-488. "