基于差分进化的社交网络可视化研究
毕璐琪 杨连贺
摘 要：社交网络对于个人及社会的重要性日益凸显。随着社交网络数据规模的不断扩大，如何清晰美观地展现社交网络关系结构成为信息可视化领域研究的一大难点。针对此研究难点，本文应用网络理论和实验领域的专家之间的合作关系数据集，通过度中心性、介数中心性指标发现数据中的关键节点，改进差分进化算法的变异、交叉和选择过程，提出了基于差分进化的社交网络可视化布局算法，有效减少初始位置对可视化结果的影响，并且最终呈现的可视化结果可以清楚美观地展现社交网络结构。
关键词：社交网络；可视化；差分进化；关键节点
中图分类号：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）
摘 要：社交网络对于个人及社会的重要性日益凸显。随着社交网络数据规模的不断扩大，如何清晰美观地展现社交网络关系结构成为信息可视化领域研究的一大难点。针对此研究难点，本文应用网络理论和实验领域的专家之间的合作关系数据集，通过度中心性、介数中心性指标发现数据中的关键节点，改进差分进化算法的变异、交叉和选择过程，提出了基于差分进化的社交网络可视化布局算法，有效减少初始位置对可视化结果的影响，并且最终呈现的可视化结果可以清楚美观地展现社交网络结构。
关键词：社交网络；可视化；差分进化；关键节点
中图分类号：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）
