基于差分進化的社交網(wǎng)絡(luò)可視化研究

畢璐琪 楊連賀

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

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

中圖分類號：TP391.9 文獻標識碼：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）

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

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

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

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

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

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

3 差分進化布局算法（Differential evolution layout algorithm）