基于Louvain算法的图数据三维树形可视化

林定;徐颖;黄国新;陈崇成

【摘 要】提出一种图数据的三维树形可视化方法,基于Louvain算法对图数据中的复杂的网络关系进行层次聚类,利用三维树形映射表达聚类结果,直观展示隐含于图数据中的结构关系,通过在三维场景中旋转、缩放、移动、拾取高亮等交互操作多视角地展示数据.集成开源图数据库Neo4j研发原型系统,并开展案例数据实验.实验结果表明,该方法不仅能够简洁灵活地展示图数据的总体层次结构,还能够多样化地表达数据细节,为利用虚拟现实技术探索图数据的潜在信息提供有效的技术支持.%Graph visualization as an effective technology to understand the graph structure and reveal hidden self-organi-zation is of great significance.Meanwhile,detecting hierarchical community structures in contact graph data may give reorganizational insight of complex network relationships.This paper introduces a Neo4j-based implementation of Lou-vain method to produce multi-level clusters,and a prototype system for graph visualization.In the system,the hierarchical structure data are mapped to a 3D botanical tree,and provide the flexible,intuitive operation to explore the potential infor-mation.Visual analysis of experimental results show that the proposed method not only exhibits sophisticated

hierarchical community structures clearly,but also displays the data details variously.As a result,the method which is applied virtual reality technique provides strong technical support for graph mining. 【期刊名称】《计算机工程与应用》

【年(卷),期】2018(0)007 【总页数】6页(P96-101)

【关键词】图数据;层次社区结构;三维可视化;Neo4j 【作 者】林定;徐颖;黄国新;陈崇成

【作者单位】福州大学 空间数据挖掘与信息共享教育部重点实验室,福州350116;福州大学 地理空间信息技术国家地方联合工程研究中心,福州350116;福州大学 空间数据挖掘与信息共享教育部重点实验室,福州350116;福州大学 地理空间信息技术国家地方联合工程研究中心,福州350116;福州大学 空间数据挖掘与信息共享教育部重点实验室,福州350116;福州大学 地理空间信息技术国家地方联合工程研究中心,福州350116;福州大学 空间数据挖掘与信息共享教育部重点实验室,福州350116;福州大学 地理空间信息技术国家地方联合工程研究中心,福州350116 【正文语种】中 文 【中图分类】TP391 1 引言

图将实体及其关系抽象为节点与边的集合，可以用来描述事物之间的复杂联系[1]。现实生活中与图相关的应用无处不在，例如社交网络、互联网、交通网、遗传族谱等都可以抽象为图数据。图表达的复杂网络关系不利于人们对数据总体特征的理解，于是出现了多种图聚类算法挖掘隐藏于网络关系中的社区结构[2]，即社区内部节点连接紧密、不同社区间的节点连接稀疏。其中，层次社区结构，在一定程度上反映了网络的局部规则性和全局有序性，揭示了网络系统中群体的共性规律[3]。层

次聚类作为图数据分析和可视化的关键技术，能够发现层次社区结构，通过基于节点的某种内聚性度量指标，递归地对网络进行或合并，相比扁平聚类更有助于揭示数据的内在结构与特征[4]，该方法可细分为两类：凝聚式聚类算法[5-9]和式聚类算法[2，10-11]。其中，Louvain算法[6]是一种基于模块度优化[2]的快速凝聚算法，能够准确划分出层次社团，是目前最高效的社区算法之一。Pons等[12]通过改进目标函数，定义聚类的总层次提升算法的聚合效率；吴祖峰等[13]在社区移动聚合过程中直接移除叶节点，提高Louvain算法的运行效率。Beis等[14]利用Louvain算法对图数据库存储管理的数据进行层次聚类，测试并评价图数据库在社区发现方面的性能。

随着计算机技术和虚拟现实技术（VR）的发展，可视化方法充分利用视觉感知补充逻辑理解的局限性，成为表达数据的整体结构与细微特征、发掘数据隐含意义的主流手段。近年来，三维交互式可视化技术能够有效缓解数据间的重叠，大大提升人们对复杂关系的认知效率[15]，是研究图数据结构与关系的重要方法之一。Cone tree[16]利用圆锥体将二维系统树图拓展为三维，通过旋转视角展示不同的兴趣节点，原理简单，是具有代表性的三维层次可视化应用；ASK-Graphview[17]通过层次聚类与多尺度交互，将大规模图转化为层次化树结构，解决可视化界面中的大量节点及边的聚集、覆盖问题；Neumann[18]引入植物学叶序算法改进多层次数据的三维空间布局；Kleiberg等[19]遵循植物学的树形特征将大规模层次数据映射为三维树木，利用简化的霍顿导管模型将抽象数据转换为几何实体，通过用户交互操作及合理的空间布局解决三维遮挡问题。

综上所述，树形映射是表达图数据中的潜在层次关系的有效方式。本文基于Louvain层次聚类算法构建了图数据三维树形可视化原型系统，集成了开源图数据库Neo4j，对图数据的复杂网络关系进行层次聚类并映射为三维树木形态，通过简洁灵活的交互操作展示数据的层次结构和局部细节，利用虚拟现实技术探索数据

的潜在信息。

2 基于Louvain算法的层次聚类

Louvain算法是一个基于模块度优化的启发式算法，能够快速地从网络中提取层次社团结构。算法的主要思想是通过计算相邻节点间的模块度增量，实现节点间的动态聚合。整个过程采用贪心迭代使社区结构不断更新完善，聚类结果具有良好的层次结构特性。模块度作为算法中社区优化的度量，定义如下：

式中，m是网络中的总边数；ki表示与节点i邻接的边权重之和；ci表示节点i所属的社区，Aij表示节点i与 j之间边的权值；若节点i和 j属于同一社区，则δ(ci,cj)=1，否则为0。

Louvain算法流程主要分为两个阶段：（1）首先对网络进行初始化，将每个节点视为各自的社区；然后按一定次序遍历整个网络，对于每个节点i，考虑将i分配到其任意邻居节点 j所在的社区后，社区中模块度的变化ΔQ，如果ΔQ＞0，将节点i移至使得ΔQ变化最大的节点的社区中，否则，保持不变。这个过程对网络中所有节点迭代执行，直到模块度增量不再发生变化为止。（2）根据第一阶段的初始划分结果，重新构造图结构，将各个社区视为新的节点，新图中节点的权重等于社区内部边的权重和，边的权重等于社区外部边的权重和。对新图重复执行第一阶段，直到整个图的模块度不再发生变化。图1描述了Louvain算法处理无向无权图的聚类过程。

图1 Louvain算法聚类过程示意图

本文研发的原型系统中对Louvain算法的实现如下：

3 图数据三维树形表达

三维数据可视化技术有效利用三维空间减少二维表达中数据重叠和杂乱的问题，避

免简化算法造成的内在信息损失，完整地表达数据的整体结构和局部细节，符合客观的视觉认知习惯，提高屏幕空间的利用效率。三维图可视化按照其映射方式可划分为：直接映射、球体映射、树形映射等，其中树形映射利用树木自然的层次结构表达图数据，有助于人们快速直观地理解复杂的网络拓扑关系，视觉效果更强。 本文在Louvain层次聚类算法的基础上，提出一种新的图数据的三维表达方式，即通过网络关联中的层次结构将数据映射为三维树形表达，如图2所示。既显式地表达了数据的聚合过程，同时，强调了数据整体与局部的关联性。其中，层次社区结构与树形拓扑结构的映射关系如下： 树叶——网络节点 枝条——网络社区 树木层级——聚类层级 分枝数量——社区数量 枝条/叶子颜色——社区类别

枝条的视觉参数有分支角度、枝条长度、枝条半径等，叶的视觉参数有方位角、大小、颜色等。枝条的分支角度很大程度上影响树木的三维空间格局，本文在植物学叶序算法基础上，考虑社区结构特征计算枝条的分支角度，即根据社区的加权容量或重要性对可用空间进行加权配置，计算公式如下：

式中θi表示社区i所对应枝条的方位角；qi×Ci(n)表示社区i的加权容量或重要性；Ci(n)表示社区i内部节点的数量；qi为权系数，根据查询频度等交互操作动态确定，初始取值为1/K；K表示聚类的总类别数，φ表示三维空间张角，本文选取360°。

枝条长度的计算与分支角度类似，由社区子集包含的节点容量或重要性决定，叶节点的数量越多，权重越大，则枝条越长。为了避免密集叶子节点间的相互遮挡，采

用叶序角公式绕枝螺旋式确定叶的生长位置点，于是形成图2左侧所示的三维树木模型，具有清晰的层次拓扑关系。 4 集成Neo4j的图数据三维可视化原型系统

Neo4j是基于Java实现的高性能的开源NoSQL数据库，以图结构作为数据库的底层存储模型，完全支持ACID事务性，具有高可用性与丰富的开发资源。它集成了Traversal数据遍历接口及Lucene数据索引功能，具备免索引邻接（Index-Free Adjacency）特性和于数据规模的查询性能而被广泛使用。本文利用Neo4j图数据库存储和管理数据，充分发挥其高效的查询和响应效率实现聚类过程中快速的网络数据遍历，基于Louvain算法研发图数据的三维树形可视化原型系统，并广泛应用于社会网络实验的示例数据集对系统进行初步测试。 4.1 系统的总体架构

系统的开发环境为普通PC机（CPU-i7/8 G/Eclipse/WebGL1.0），采用浏览器-服务器（B/S）模式实现系统框架。浏览器端通过HTTP请求访问服务器，服务器根据请求运行Louvain算法对图数据进行层次聚类并返回聚类结果，浏览器端接收聚类生成的层次结构数据，并采用WebGL+HTML5+JavaScript技术实时渲染，系统的主体框架如图3所示。 4.2 案例数据的三维树形展示 （1）数据来源

案例数据采用广泛应用于社会网络实验的示例数据，分别为：空手道俱乐部（Zachary’s Karate Club）网络数据[20]和美国大学生足球（American College Football）网络数据[2]。Zachary网络数据包括34个节点，7边，其中节点代表俱乐部成员，边代表成员之间存在交流关系。Football网络数据包括115个节点，613条边，该网络中的节点代表各个学校的参赛队伍，边则表示对应的两只队伍之间至少有过一场比赛。

（2）交互式三维树形展示与结果分析 图2 树形拓扑映射关系 图3 系统主体架构

本文通过空手道俱乐部网络说明Louvain层次聚类与三维树木逆向建模的映射过程，利用美国大学生足球网络展示三维数据树的交互式操作。空手道俱乐部网络的聚类过程如图4所示。聚类的第①阶段生成4个社区结构，第②阶段将4个初始社区视为虚节点重新构造网络结构，最终生成2个鲜明的社区结构。其中，图4（b）是聚类过程对应的系统树图（dendrogram）；（c）、（d）是基于节点链接关系使用Gephi[21]实现的二维聚类结果图；（e）是三维树形映射表达的层次聚类过程，主干对应整个层次社区结构和网络中的所有叶子节点，4个二级枝条代表第①阶段生成的初始社区结构，2个一级枝条代表最终划分的社区结构。 图4 空手道俱乐部网络聚类结果图

类似地，美国大学生足球网络数据的聚类过程也形成相应的三维树木模型，如图5所示，树形映射除了能够表达层次聚类的中间社区合并过程，还提供了多视图的数据展示及简单灵活的交互操作。首先，通过对三维场景中的缩放、平移、旋转等全局操作能够实现对数据总体特征的多视角展示，利用有限的屏幕空间充分表达数据的属性信息。此外，为了有效地表达数据在三维场景的局部细节，还实现了基于用户兴趣的局部细节展示。数据的局部细节展示包括：模型的旋转，改善三维空间中数据遮挡问题；模型的缩放，放大用户兴趣细节。通过交互式地选取用户的兴趣域，改变兴趣域内枝条和叶节点的大小及布局，突出焦点信息。如图5中（d）、（f）所示，当用户指定感兴趣的社区结构时，当前社区所映射的枝条高亮显示，利用轨迹球交互式地调整枝条的空间布局；当用户指定感兴趣的叶节点，当前叶节点高亮显示，利用局部坐标轴更改节点所占的屏幕像素大小，效果直观，操作灵活。三维树形可视化利用树木先天的层次结构表达层次聚类后的图数据，有助于人们理解复

杂的图数据模式和拓扑关系，视觉效果更强。不仅有效提高了屏幕空间的利用效率，同时，交互地表达了用户的兴趣域信息，为探索三维图可视化提供一种新的有效途径。

5 结论与展望

图5 足球网络数据交互式多视角展示

本文基于Louvain层次聚类算法，利用Neo4j在数据查询与更新方面的优势，结合本地缓存技术实现了网络数据的快速层次划分，研发了图数据三维树形可视化原型系统，利用三维树形映射展示了经典社会网络数据集。结果表明，本文提出的方法不仅能够简洁灵活地展示图数据的总体层次结构，还能够多样化地表达数据细节，突出用户的兴趣域，为利用虚拟现实技术探索图数据的潜在信息提供有效的技术支持。

三维树模型清晰地表达了图数据的层次结构，揭示了节点逐步聚合为社区的过程。但受限于基于节点相似性的聚类算法的共同缺陷，聚类结果中丢失了图节点之间的邻接关系。在后续的研究中将根据三维场景的视角及用户兴趣域，在树模型上叠加显示社区内部及单个节点的邻接关系细节。

[1]Jerrik B S.Graph database[M].Sebastopol：O’Reilly Media，2015. [2]Girvan 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.

[3]李建华，汪晓锋，吴鹏.基于局部优化的社区发现方法研究现状[J].中国科学院院刊，2015，30（2）：238-247.

[4]Schaeffer S E.Graph clustering[J].Computer Science Review，2007，1（1）：27-.

[5]Newman M E J.Fast algorithm for detecting community structure in

networks[J].Physical Review E，2004，69（6）.

[6]Clauset A，Newman M E，Moore C.Finding community structure in very large networks[J].Physical Review E Statistical Nonlinear&Soft Matter Physics，2004，70（2）：2-277.

[7]Low K L，Tan T S.Model simplification using

vertexclustering[C]//Proceedings of Symposium on Interactive 3D Graphics，Providence，Ri，USA，1997：75-81.

[8]Blondel V D，Guillaume J L，Lambiotte R，et al.Fast unfolding of communities in large networks[J].Journal of Statistical Mechanics Theory&Experiment，2008，30（2）：155-168.

[9]Rosvall M，Bergstrom C T.Maps of random walks on complex networks reveal community structure[J].Proceedings of the National Academy of Sciences，2008，105（4）：1118-1123.

[10]van Dongen S.Graph clustering by flow simulation[D].Utrecht：University of Utrecht，2000.

[11]Flake G W，Lawrence S，Giles C L，et al.Self-organization and identification of Web communities[J].Computer，2002，35（3）：66-71. [12]Pons P，Latapy M.Post-processing hierarchical community structures：Quality improvements and multi-scale view[J].Theoretical Computer Science，2011，412（8/10）：2-900.

[13]吴祖峰，王鹏飞，秦志光，等.改进的Louvain社团划分算法[J].电子科技大学学报，2013，1（1）：105-108.

[14]Beis S，Papadopoulos S，Kompatsiaris Y.Benchmarking graph databases on the problem of community detection[M]//New Trends in

Database and Information Systems II.Switzerland：Springer International Publishing，2015：3-14.

[15]Ware C，Mitchell P.Visualizing graphs in three dimensions[J].ACM Transactionson AppliedPerception，2008，5（1）.

[16]Robertson G G，Mackinlay J D，Card S K.Cone trees：Animated 3D visualizations of hierarchical information[C]//Proceedings of the SIGCHI Conference on Human Factors in Computing Systems，1991：1-194. [17]Abello J，Van H F，Krishnan N.ASK-GraphView：A large scale graph visualization system[J].IEEE Transactions on Visualization&Computer Graphics，2006，12（5）：669-676.

[18]Neumann P，Carpendale S，Agarawala A.PhylloTrees：Phyllotactic patterns for tree layout[C]//Proceedings of Eurovis’06，2006：59-66. [19]Kleiberg E，Wetering H V D，Wijk J J V.Botanical visualization of huge hierarchies[C]//Proceedings of IEEE Symposium on Information Visualization，2001：87-94.

[20]Zachary W W.An information flow model for conflict and fission in small groups[J].Journal of Anthropological Research，1977，33（5）：452-473.

[21]Jacomy M，Bastian M，Heymann S.Gephi：An open source software for exploring and manipulating networks[C]//Proceedings of International Conference on Weblogs and Social Media，2009：361-362.