畢璐琪 楊連賀

摘 要：社交網(wǎng)絡(luò)對(duì)于個(gè)人及社會(huì)的重要性日益凸顯。隨著社交網(wǎng)絡(luò)數(shù)據(jù)規(guī)模的不斷擴(kuò)大，如何清晰美觀地展現(xiàn)社交網(wǎng)絡(luò)關(guān)系結(jié)構(gòu)成為信息可視化領(lǐng)域研究的一大難點(diǎn)。針對(duì)此研究難點(diǎn)，本文應(yīng)用網(wǎng)絡(luò)理論和實(shí)驗(yàn)領(lǐng)域的專家之間的合作關(guān)系數(shù)據(jù)集，通過(guò)度中心性、介數(shù)中心性指標(biāo)發(fā)現(xiàn)數(shù)據(jù)中的關(guān)鍵節(jié)點(diǎn)，改進(jìn)差分進(jìn)化算法的變異、交叉和選擇過(guò)程，提出了基于差分進(jìn)化的社交網(wǎng)絡(luò)可視化布局算法，有效減少初始位置對(duì)可視化結(jié)果的影響，并且最終呈現(xiàn)的可視化結(jié)果可以清楚美觀地展現(xiàn)社交網(wǎng)絡(luò)結(jié)構(gòu)。

關(guān)鍵詞：社交網(wǎng)絡(luò)；可視化；差分進(jìn)化；關(guān)鍵節(jié)點(diǎn)

中圖分類號(hào)：TP391.9 文獻(xiàn)標(biāo)識(shí)碼：A

Abstract：Social networks have become increasingly prominent for both individuals and the society.As social network data continues to grow in size， how to clearly and attractively display the social network relationship structure has become a major difficulty in the field of information visualization. In view of the difficulty of this research，this paper applies the cooperation relationship data between experts in network theory and experimentation to find key nodes in the data through degree-centrality and betweenness-centrality indicators to improve the variation，crossover and selection of differential evolution algorithms.Therefore，a social network visual layout algorithm based on differential evolution is proposed，which effectively reduces the impact of the initial position on the visualization results.The visual results presented finally can clearly and beautifully reflect the social network structure.

Keywords：social network；visualization；differential evolution；key nodes

1 引言（Introduction）

當(dāng)今時(shí)代，社交無(wú)處不在。隨著通訊技術(shù)的不斷進(jìn)步，社交形式更加趨于多樣化，其中包括面對(duì)面的人際交往型社交、網(wǎng)絡(luò)平臺(tái)如微博、微信、電子郵件等線上互動(dòng)型社交。在大數(shù)據(jù)和人工智能的時(shí)代背景下，對(duì)海量社交網(wǎng)絡(luò)數(shù)據(jù)的分析理解至關(guān)重要，因?yàn)樗欣诶砬鍌€(gè)人及群體之間的聯(lián)系，在好友推薦、個(gè)性化服務(wù)、輿情控制和信息傳播等方面發(fā)揮重大作用。

隨著數(shù)據(jù)規(guī)模的不斷擴(kuò)大，人們對(duì)實(shí)用性和美觀性的要求越來(lái)越高。在實(shí)用性上，必須提高布局算法的效率，盡可能在保持結(jié)構(gòu)的前提下達(dá)到全局優(yōu)化；在美觀性上，節(jié)點(diǎn)和邊應(yīng)均勻分布，盡量減少邊的交叉，整體效果應(yīng)對(duì)稱，等等。

本文針對(duì)無(wú)向圖，結(jié)合關(guān)鍵節(jié)點(diǎn)檢測(cè)指標(biāo)識(shí)別關(guān)鍵節(jié)點(diǎn)，結(jié)合差分進(jìn)化算法較強(qiáng)的全局收斂和魯棒性的優(yōu)點(diǎn)，以及力導(dǎo)引算法布局美觀、充分展現(xiàn)網(wǎng)絡(luò)數(shù)據(jù)自身結(jié)構(gòu)的優(yōu)點(diǎn)提出差分進(jìn)化布局算法，可有效降低初始位置對(duì)可視化結(jié)果的影響，使系統(tǒng)穩(wěn)定的同時(shí)，減少視覺(jué)混亂，得到美觀性和實(shí)用性兼具的可視化結(jié)果。

2 相關(guān)研究（Related research）

社交網(wǎng)絡(luò)可視化是信息可視化的一個(gè)重要領(lǐng)域，社交網(wǎng)絡(luò)可視化的核心是節(jié)點(diǎn)布局問(wèn)題，節(jié)點(diǎn)布局既要求符合社交網(wǎng)絡(luò)的自身結(jié)構(gòu)，也要求清晰美觀的效果。因社交網(wǎng)絡(luò)具有小世界和無(wú)尺度的特點(diǎn)，為使社交網(wǎng)絡(luò)的節(jié)點(diǎn)在有限空間內(nèi)合理分布，布局算法的選擇至關(guān)重要[1]。最常用的布局方法為節(jié)點(diǎn)-鏈接法。其中節(jié)點(diǎn)-鏈接法最常用的布局算法是力導(dǎo)引布局算法，最早由Eades提出，他將社交網(wǎng)絡(luò)假設(shè)成一個(gè)物理系統(tǒng)，節(jié)點(diǎn)為鋼環(huán)，鏈接為彈簧，用彈簧模擬兩個(gè)點(diǎn)之間的關(guān)系，在彈力的作用下節(jié)點(diǎn)的位置不斷移動(dòng)，經(jīng)過(guò)多次迭代，布局達(dá)到動(dòng)態(tài)平衡狀態(tài)[2]。此后，Kamada等人基于力導(dǎo)引算法，以整個(gè)系統(tǒng)能量最小為準(zhǔn)則確定節(jié)點(diǎn)的位置，從而提出KK算法[3]。Fruchterman等人在粒子物理學(xué)原理的基礎(chǔ)上，通過(guò)計(jì)算所有節(jié)點(diǎn)之間的作用力來(lái)確定節(jié)點(diǎn)的具體位置，提出FR布局算法[4]。劉芳等提出基于粒子群優(yōu)化的布局算法，設(shè)計(jì)了適應(yīng)社交網(wǎng)絡(luò)布局的目標(biāo)函數(shù)，減少邊交叉，用曲線替代直線，使布局效果更清晰[5]。

差分進(jìn)化算法（Differential Evolution，DE）是一種高效的啟發(fā)式搜索算法[6]，具有控制參數(shù)少、收斂快、優(yōu)化結(jié)果穩(wěn)健等優(yōu)點(diǎn)，并在神經(jīng)網(wǎng)絡(luò)優(yōu)化、機(jī)器智能、醫(yī)學(xué)等工程領(lǐng)域獲得了廣泛應(yīng)用[7]。同時(shí)，差分進(jìn)化算法在可視化領(lǐng)域也有應(yīng)用，如YUE等人研究了基于差分進(jìn)化算法構(gòu)建地理信息可視化建模的環(huán)境[8]。關(guān)于差分進(jìn)化的優(yōu)化研究，Skanderova等探索了基于復(fù)雜網(wǎng)絡(luò)對(duì)差分進(jìn)化動(dòng)力學(xué)進(jìn)行建模[9]。研究表明，差分進(jìn)化算法對(duì)于網(wǎng)絡(luò)數(shù)據(jù)的可視化是可行且有效的。

3 差分進(jìn)化布局算法（Differential evolution layout algorithm）