基于差分進化的社交網絡可視化研究

畢璐琪 楊連賀

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

關鍵詞：社交網絡；可視化；差分進化；關鍵節點

中圖分類號：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）

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

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

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

2 相關研究（Related research）

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

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

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