畢璐琪 楊連賀

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

關鍵詞：社交網(wǎng)絡；可視化；差分進化；關鍵節(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）

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

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

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

2 相關研究（Related research）

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

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

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