MSNV：基于多层次社团划分的网络结构可视化方法

王贤刚 姚中华 宋汉辰

摘要：针对大规模网络节点数目庞大、结构复杂性高，有限的屏幕空间难以展示其结构特征的问题，提出了一种基于社团划分的多层次网络可视化方法。首先，使用基于网络模块度的社团划分算法对网络节点进行划分，并采用贪婪算法寻找最大模块度的社团划分，得到不同层次粒度的社团；其次，通过设置层次约束力以改进经典力导引算法（FDA），使改进的算法能对不同层次粒度的社团实现分层布局，解决FDA无法展示网络节点层次性的问题；最后，使用多窗口视图、Overview+Detail等交互方法分别展示高层社团和底层节点，实现兼顾网络高层次宏观结构和低层次局部细节的显示。仿真实验中，该算法的社团划分相较于自包含GN算法在效率和准确率上有所提高。案例分析表明，所提方法在大规模网络结构的显示和交互方面具有良好的效果和性能。

关键词：大规模网络；多层次；可视化；社团划分；力导引算法

中图分类号：TP393.02 文献标志码：A

Abstract：Focused on the issue that largescale network has characteristics of huge number of nodes， high structural complexity and difficulty to demonstrate its structural characteristics by the limited screen space， a multilevel network visualization method based on community detection was proposed. Firstly， a community detection algorithm based on network modularity was used to detect the network node and a greedy algorithm was used to find the community detection with maximum modularity to get different level of granularity communities. Then， in order to solve the problem that the ForceDirected Algorithm （FDA） could not display network nodes hierarchically， the classic FDA was improved by setting the level blinding force to achieve hierarchical layout of different level of granularity communities. Finally， high level communities and low level nodes were displayed respectively by using the interactive method such as multiwindow view and Overview+Detail， meeting the requirement of both network highlevel macrostructure and lowlevel details of the display. In the simulation test， the community detection algorithm is faster and more accurate compared to selfcontained GN （GirvanNewman） algorithm. The theoretical analysis and simulation results show that the proposed method has good effect and performance in display and interaction of largescale network structure.

Key words：largescale network； multilevel； visualization； community detection； ForceDirected Algorithm （FDA）

0 引言

大规模网络数据规模庞大、拓扑结构复杂，直接对其进行可视化会导致显示重叠、层次信息难以观察，无法有效降低网络分析人员的负担。为解决这一问题，学者们提出了很多策略和方法，对大规模网络进行层次划分和改进布局算法是提高网络可视化质量的有效途径。

单纯的节点布局无法有效展示大规模网络的宏观结构，网络层次划分是分析网络结构和功能的主流方法。Chan等[1]提出了出度布局（Out Degree Layout， ODL）算法，以网络节点的出度为依据将整个网络划分为不同的层次，但没有考虑节点间的联系，分级波动性较大。为提高布局质量，展示网络整体结构，Agapito等[2]提出了网络节点的分级显示，通过分级算法将节点分为多个等级，并利用力学模型算法对特定等级的节点进行布局，但难以展示网络整体层次关系。Palla等[3]和Jaewon等[4]认为社团是一种互联互通的全耦合网络的集合，并基于此提出了派系过滤算法（Clique Percolation Method， CPM）方法对网络的社团进行划分，但由于其算法复杂度过大难以在大规模网络中使用。Girvan和Newman提出了基于分裂的GN（GirvanNewman）算法[5]，弥补了一些传统算法上的不足，但在社团数目未定的情况下，该划分算法不能自动终止[6]。为了解决社团划分的终止问题，Newman定义了社团的模块度Q[7]，Q是社团连接强度的期望值，与社团划分数目联系紧密，可以作为社团划分的依据，是现今使用最广泛的衡量社团结构划分优劣的指标[8]。树状结构是当前解决多层次网络较为常用的方法，如TreeNetViz[9]、TreeGraph和DAViewer[10]等，但树状结构可视化多用在属性明确、属性间层次分明的网络中，如地域信息网络、协议信息网络或上下级关系网络，本文研究的是基于网络节点的联系紧密度的层次划分，目前的树状结构难以展示节点间联系紧密度。

可视化布局的相关方法广泛应用于大型网络的结构发现，经典的网络布局方法是Eades[11]提出的力导引布局算法（ForceDirected Algorithm，FDA），FDA仿真物理力学，布局结果自然，但无法展示网络的层次信息。Kamada和Kawai[12]对力导引算法进行了改进，使节点之间的距离与其最短路径距离成正比，从而确定网络节点的布局位置，但在多层次网络中容易产生混乱。胡华全 [13]提出了融合力导引布局算法（Hybrid Force Directed Layout，HFDL），通过循环方式降低布局算法对输入值的敏感度，从而得到更好的布局结果。实现大规模网络的可视化有很多困难，主要表现在：1）网络节点和连边的数目过大，直接可视化难以有效观察网络整体拓扑结构；2）网络以社团形式展开时，难以寻求合理的自动化布局；3）一般交互策略难以兼顾网络的整体结构和局部细节，分析人员的工作量太大。

针对上述问题，本文提出基于社团划分的多层次大规模网络结构可视化方法，方法利用社团划分算法将整个网络划分为多个层次的社团，并对社团集合采用改进的力导引布局算法进行布局。本文的社团划分与可视化方法主要有以下特点：1）利用社团划分应对大型网络的结构显示问题。将大规模节点转化为有限社团，宏观拓扑结构清晰。2）利用改进的力导引算法布局社团节点。基于额外电荷量的方法使布局层次分明，社团规模从内到外递增，便于区分。3）采用主副窗口协同交互，支持社团逐级展开和跳级展开，在显示上同时兼顾网络整体结构和局部细节、社团外部联系和内部结构。

1 基于社团聚类的网络结构层次划分算法

社团划分是分析网络结构和功能的有效方法。在真实网络中，每一个节点都与其他节点产生作用，根据作用的类别和强弱可将网络划分为多个聚合团，每个聚合团内节点互相作用的紧密程度显著大于团间的作用，这些聚合团被称为社团[5]。大规模网络可以认为是由若干个社团构成的，社团间的结构可以被看成网络的整体结构。通过社团划分，可以更加有效地对大规模网络的结构进行观察和分析。

由于社团是网络中联系紧密节点的集合，具有一定的特征和独立性，可以采用类似聚类的方式得到，目前社团划分算法主要包括去边法和聚点法。去边法通过循环迭代找到并删除联系较弱的边，最终将网络分成几个互不相连的社团，典型算法如Newman的GN算法[5]和Radicchi的自包含GN算法[14]，但GN算法复杂度为O（n3），耗时太大，不适合在大规模网络中使用，自包含GN算法虽然改进了算法复杂度，但该算法在社会性网络之外的其他网络中效果较差；聚点法是将联系紧密的节点聚类合并，典型算法如Newman在GN算法的基础上提出了社团快速划分法[15]，该算法是一种基于网络模块度最大化思想的聚类算法，适用于规模较大的复杂网络，算法复杂度为O（n2）。

Q的取值在0～1，大量实验表明，Q值一般不可能接近1[6]。现在学者认为，一个网络的模块度Q值大于0.3即可说明该网络具有明显的社团结构[6]。

由于网络涉及节点和边数目较大，为提高效率，本文在社团划分之前先对节点进行分簇，然后再对这些簇进行社团划分，簇划分依据为簇内节点可达，簇间无连边。合并两个无关联的簇不会改变网络模块度，只在簇内进行社团划分可以避免每次聚类都要进行全局遍历。

本文社团划分过程分为贪婪搜索、递进聚合、终止检查三个阶段，社团划分算法流程如图1所示。

其中：m由式（3）确定，∑CwiAui是节点u和节点w所在社团C中所有节点连边权值的总和，ku为节点u与整个网络其他节点连边权值的总和，∑Cwiki是社团C中所有节点与整个网络其他节点连边权值的总和。得到网络模块度的改变量ΔQuw后采用贪婪算法，找到最大的max ΔQuw，且max ΔQuw>0，删除原社团X，将节点u加入到节点w所在的社团C；如果社团X中存在多个节点，由于社团内的节点联系紧密，可认定该社团的节点具有单个节点的性质，此时将该社团的节点全部移出，加入到相邻节点j所在的社团，并计算此时的网络模块度Q的改变量QXw=∑XuΔQuw，之后采用单节点社团的方法对节点进行归类。

递进聚合阶段 将第一阶段形成的社团视为单个节点，社团节点的位置为原社团中所有节点的中心，社团节点间连边的权值为原社团间连边权值的和，并重新对式（2）中的A进行计算。然后重复贪婪搜索过程，形成更高层次的社团，逐次迭代得到不同层次的社团。

终止检查阶段 每次迭代后计算当前整个网络模块度QT，并与前一次结果作比较，当QT≤QS或达到迭代次数时停止社团划分，以前一次划分结果为最终结果。

上述社团划分流程通过计算整个网络的模块度并找到其最大值，并在得到最大值位置停止迭代；必要时也可由观察者自己交互指定社团划分迭代次数，根据分析需求确定迭代终止条件。两种划分方式分别记为终极划分和逐级划分，二者关系如图2所示。

2 多层次网络结构可视化方法

2.1 面向多层次网络改进的FDA布局算法

上述社团划分算法兼顾了网络整体结构和局部细节，但由于划分层次结构过多，还存在难以在同一界面有效显示的问题，且目前尚未发现对不同层次节点进行统一布局的有效算法。力导引布局算法是一种对同质节点布局有效的经典算法，但无法分辨不同层次节点。本文提出了一种基于额外电荷量的力导引改进算法，对不同层次进行区分布局。

算法的基本思想为：在对原有节点之间的引力和斥力不造成影响的前提下，通过额外电荷量对节点的布局位置产生影响。例如在窗口的中心固定一个单位正电荷，同时在不同社团中根据层次的高低附加额外的正电荷量，层次越高的电荷量越大，从而驱动不同层次的社团在界面中呈圆环状依次展开，越靠近中心的层次等级越低，反之越高。

按照改进的力导引算法实现的混合层次节点布局效果如图3所示。由于原始节点不受额外电荷斥力影响，展开的社团可以在中心区域按照经典FDA进行布局，其局部结构细节得以展示；单层次社团中L=Lmin，由式（4）可得社团不受电荷斥力影响；多层次社团中除了原始节点，其余不同层次的社团受到电荷斥力影响，布局呈环状结构，低层社团和高层社团从内到外依次展开。

2.2 面向多层次网络的交互设计

以社团划分和多层次布局算法为基础，本文开发了多层次网络可视化工具MSNV（Multilayer Structure Visualization of Network），针对社团可视化中社团对比、多层分解显示等需求，工具实现了基于同一数据的多视图方法，通过主窗口和一系列分窗口完成联动操作，其中主窗口主要实现社团层次操作，分窗口主要实现社团内部结构观察。主要功能包括：

1）主窗口采用形状和节点大小对社团和节点进行区分，节点为圆形，社团为正六边形，其面积与N成正比，N为该社团包含的节点数目。节点支持鼠标触动等一系列操作，通过节点标签展示该社团的核心节点和包含节点数目。

2）社团支持主窗口逐级展开和分窗口全部展开操作，有利于研究者观察社团在整个网络的外部关系信息和该社团的内部结构信息，实现了整体和局部的结合。

3）整个网络支持全局操作，可以通过网络社团布局得到网络整体结构，也可以通过全局展开观察网络的细节分布和部分节点的具体特征。

3 实验分析

为了验证本文算法，本章使用LFR（LANCICHINETIFORTUNATORADICCHI）基准网络数据集[16]对本文社团划分算法和自包含GN算法[14]进行比较验证，并使用2015年中国可视化与可视分析大会中举办的数据可视分析挑战赛的比赛数据（http：//chinavis.tju.edu.cn/sources/data）对可视化算法和工具进行测试。

3.1 数据准备

LFR基准网络数据集是当前社团研究中最常使用的模拟数据集，数据集主要包含以下重要参数：节点度分布参数N、最小社团节点数cmin、最大社团节点数cmax和混合参数mp，mp取值为0～1，参数越大表明社团发现越困难。本节参数设置如下：N=5000，cmin=5，cmax=5000，mp=0.1，0.2，0.3，0.4，0.5。

可视化竞赛网络数据由一家互联网公司提供，数据内容包括TCP流的时间、源IP、目的IP、协议类型、目的端口、上行字节数和下行字节数7个维度。数据为该公司在某段时间的正常TCP flow日志数据，该公司希望找出网络的拓扑结构，以便对网络进行改进。

对该数据进行初步统计表明，该数据集节点数目众多、网络活动频繁，以2015年4月25日8：00至12：00的数据记录为例，共175706行TCP flow记录，包含10517个不同的IP地址，是一个典型的大规模网络。

实现结构可视化的关键是IP间的关联及其关联程度，本文利用字节数定义IP之间连边的权重Auw，不同的IP作为网络节点，根据IP间的数据传输和连接情况，使用MSNV工具对整个网络的结构进行可视化。

3.2 社团算法比较验证

实验准确率为节点划分正确数与节点总数之比。由图4可以看出，本文的社团划分算法在准确率和网络模块度Q值上均优于自包含GN算法，表明该算法具有较好的划分效果。仿真实验中，该算法的社团划分时间为37～39ms，而自包含GN算法划分时间为103ms，表明该算法在运算效率上优于自包含GN算法。仿真实验机器参数如下：处理器i5 4200Hz、内存16GB、显卡NVIDIA GTX850M。

3.3 可视化方法效果分析

采用本文的基于社团划分的多层次大规模网络结构可视化方法对案例网络数据进行可视化，采用终极划分策略，实验一共迭代4次形成最终结果，得到最大模块度Q=0.5899>0.3，该网络具有明显的社团结构。

网络由22个相对独立的社团构成，最大的社团以10.59.21.10为核心，共包含9637个节点，占整个网络节点数的91.63%，该社团与标签为10.73.26.141和10.64.223.132社团有连接，是整个网络的主体社团。其他社团之间相互独立，网络整体结构是分离的，社团的规模如表1所示。

将最大的社团逐级展开可以观察到该社团主要由12个子社团构成，呈星形结构，如图5（a）所示，其中标签为10.59.21.10的子社团与所有社团都有联系，可以判定此社团包含整个网络的核心节点。将标签为10.59.21.10的子社团再次展开得到更接近星形结构的拓扑图，如图5（b）所示，标签为10.59.21.10依然是二级子社团核心，对所有二级子社团都有辐射，可以确定10.59.21.10社团是整个网络至关重要的社团。

图5（a）中，标签为10.59.212.16、10.66.206.174、10.66.148.181的子社团和10.59.21.10子社团互相连接，连线较粗表明这4个子社团之间联系较为紧密，4个子社团包含8069个节点，占主体社团的83.73%，是最大社团的主体。将这4个社团同时展开至下一级可得到如图6所示的结构（此处为了便于观察只展示关键部分），图中的7个二级子社团互相连接，其网络吞吐量在整个网络中所占比例都在8%以上，其他二级子社团都小于1.6%，可以确定这7个二级子社团是整个网络最重要的部分，对网络起支配作用。

对小社团逐个进行分窗口展开可以发现该网络除了主体部分，其他社团拓扑结构大多为星形结构，如图7所示，其中心节点是该社团的关键节点，如10.59.45.221、10.93.26.48、10.59.22.149等。

4 结语

本文针对大规模网络结构可视化问题提出了一种基于社团划分的多层次网络结构可视化方法。该方法通过基于贪婪算法的社团划分将网络划分为层次分明的若干社团；在社团的层次上对整个网络的结构进行可视化布局，并改进经典力导引算法实现了多层次节点在同一界面的有效分层布局；在可视化工具上采用了主副窗口和Overview + Detail等交互探索，兼顾网络整体结构、社团间联系以及该网络局部细节的需求。通过LFR基准网络数据集对社团划分和自包含GN算法进行仿真对比说明该方法在大规模网络社团划分上有着明显优势，最后将此方法应用在某互联网公司的计算机网络数据可视化中并取得了良好的可视化效果。

参考文献：

[1]CHAN D SM， CHUA K S， LECKIE C. Visualization of powerlaw network topologies[C]// Proceedings of the 11th IEEE International Conference on Networks. Piscataway， NJ： IEEE， 2003： 69-74.

[2]AGAPITO G， GUZZI P H， CANNATARO M. Visualization of protein interaction networks： problems and solutions[J]. BMC Bioinformatics， 2013， 14（S1）： 1-30.

[3]PALLA J， VICESEK G， VICSEK T. Uncovering the overlapping community structure of complex network in nature and society[J]. Nature， 2005， 435（7043）：814-818.

[4]JAEWON Y， JURE L. Defining and evaluating network communities based on groundtruth[J]. Knowledge and Information Systems， 2015， 42（1）： 181-213.

[5]GIVAN M， NEWMAN M E J. Community structure in social and biological networks[J]. Proceedings of the National Academy of Sciences of the United States of America， 2002， 99（12）：7821-7826.

[6]解， 汪小凡. 复杂网络中的社团结构分析算法研究综述[J]. 复杂系统与复杂性科学， 2005， 2（3）： 1-12.（XIE Z， WANG X F. An overview of algorithms for analyzing community structure in complex networks[J]. Complex Systems and Complexity Science， 2005， 2（3）： 1-12.）

[7]AARON C， NEWMAN M E J， CRISTOPHER M. Finding community structure in very large network[J]. Physical Review E， 2004， 70（6）：264-277.

[8]CAFIERI S， COSTA A， HANSEN P. Reformulation of a model for hierarchical divisive graph modularity maximization[J]. Annals of Operations Research， 2014， 222（1）： 213-226.

[9]LIANG G， LUKE X L. TreeNetViz： revealing patterns of networks over tree structures[J]. IEEE Transactions on Visualization & Computer Graphics， 2011， 17（12）：2449-2458.

[10]ZHAO J， CHEVELIER F， COLLINS C， et al. Facilitating discourse analysis with interactive visualization[J]. IEEE Transactions on Visualization & Computer Graphics， 2012， 18（12）：2639-2648.

[11]EADES P A. A heuristics for graph drawing[J]. Congressus Numerantium， 1984， 42： 149-160.

[12]KAMADA T， KAWAI S. An algorithm for drawing general undirected graphs[J]. Information Processing Letters， 1989， 31（1）：7-15.

[13]胡华全. 基于时变特征的天基网络可视化方法研究[D]. 长沙：国防科学技术大学， 2014： 48. （HU H Q. Research on visualization method of spacebased networks based on timevarying characteristic[D]. Changsha： National University of Defense Technology， 2014：48.）

[14]RADICCHI F， CASTELLANE C， CECCONI F， et al. Defining and identifying communities in network[J]. Proceedings of the National Academy of Sciences， 2004， 101（9）： 2658-2663.

[15]NEWMAN M E J. Fast algorithm for detecting community structure in network[J]. Physical Review E， 2004， 69（6）： 066133.

[16]ANDREA L， SANTO F， FILIPPO R. Benchmark graphs for testing community detection algorithms[J]. Physical Review E， 2008， 78（4）： 046110.