图可视化与图分析

1 前言
2 图可视化
3 图分析
- 3.1 社区发现算法 1 - Louvain
- 3.2 社区发现算法 2 - Label Propagation
4 总结

1 前言

图可视化（Graph Visualization）是一种将结构信息表示为抽象图形和网络图的方式。它在网络、生物信息学、社交网络、软件工程、数据库和网页设计、机器学习以及其他技术领域的可视界面中具有重要的应用。图可视化中的关键问题包括图布局（Layout Algorithms）和可视化交互（Visual Interactions），其目的是帮助人们从数据中获取洞察力。

图 1 佛罗里达大学稀疏矩阵数据集合的大图可视化画廊

2 图可视化

2.1 什么是图可视化

图可视化也称为网络可视化、节点 - 链接图，图可视化是将连线和实体的网络关系用可视化网络表示出来，节点表示实体，线表示连接关系。网络可视化能超越扁平数据模型，理解数据之间的关联关系。

2.2 为什么需要图可视化

图可视化是一种发现和可视化复杂关系中的结构的方法，它的优势如下：

直观性，将网络作为节点和连线的结构进行即时探索很直观。
分析快，网络可视化帮助我们快速识别趋势和异常值，有利于更快地理解数据，从而快速采取行动。
可伸缩性，网络可视化可以简化问题的复杂性，通过查看上下文理解细节。它鼓励使用数据，提出质疑，增加了发现可行性见解的可能性。
深入性，通过交互式数据分析，我们可以获得更深入的知识并理解上下文。这很难通过静态的、聚合的可视化实现。此外，不需要特定的编程技能，我们就可以与图可视化的交互，使得更多的用户能通过图可视化提出观点，增加创造价值的潜力。

下面通过一个简单的例子来说明下图可视化的优势。有一份 11 个人的数据样本，记录着他们一起工作的信息。采用两种方式展示，扁平的表格展示和图可视化。观察下图中第一个表格，很难理解这些人之间的关联，但通过图可视化我们清晰看到: 存在两个明显的组织以及一个联系两个组织的个人，具有明显的小世界网络特征。而在表中不太可能很快发现到这些信息。

图 2 样本数据表格 VS 图可视化

2.3 图布局

图布局方法是图可视化算法的核心，下面简单介绍三种经典的图布局技术：

2.3.1 The Spring Embedder（Eades 1984）

用单位自然长度的弹簧代替边；
用无限自然长度的附加弹簧连接不相邻的顶点；
弹簧在被拉伸时吸引端点，在被压缩时排斥端点；
迭代从随机初始化节点位置开始；
持续迭代，假设存在摩擦，最终达到稳定的最小能量态。

图 3 弹簧模型

图 4 Spring Embedder 布局过程示意图

2.3.2 KK（ Kamada Kawai 1989）改进弹力模型

合力放置顶点的时候，参考它们在图中的几何距离等于图距离；
对于每一对顶点 (u,v) 使用一个自然长度为 dist(u,v) 的弹簧。

2.3.3 FR（ Fruchterman Reingold 1990）
力学系统类似于原子和天体的力学系统；
采用 n-body simulation 加速。

2.4 图优化

2.4.1 Barnes–Hut Simulation Technique
图布局常采用 Barnes–Hut 模拟技术有效的模拟近程力和远程力，将直接计算斥力的的复杂度降低到，以二维空间四叉树为例：
递归对区域进行 4 分割。区域中只包含 1 个或者 0 个元素

图 5 递归区域分割

树中每一个非节点保存该区域中星体的等效值
优化斥力, s / d < 阈值（一般0.5), 满足，可以被等效；否则，计算该区域的子区域。s 表示蓝色区域宽度，d 表示 A 星体到蓝色区域距离。

图 6 近似斥力计算过程

原始的计算斥力过程，每个节点与其他节点都要计算。

图 7 原始斥力计算过程

2.4.2 Multilevel Approach

分层技术能有效解决图布局中局部最优的问题，同时也能提高布局速度，并且具有较好的布局质量，如下图所示，分层技术一般分三个阶段：

毛糙化，会得到一系列越来越粗糙的毛糙化的图 ;
初始化, 在最粗糙的毛糙化上执行布局算法；
精细化，粗糙图上的布局递归到更细的图上，并在每个级别上进一步细化。

图 8 Multilevel 技术

2.4 图交互

在许多应用领域，如社会学、生物学和软件工程，都涉及到大型复杂网络。然而，对这样的网络进行分析绝非一件简单的事，因为它通常需要多次交互才能得出结果。因此，对分析师来说，分析过程和分析得到的结果同样重要，值得保存和共享。为了应对复杂网络的分析，有必要对图交互进行分类。常见分类模型是 V2D2，其包括四个交互层次：

视图层（View Level Interactions)，用于视觉强化（如高亮显示）和视图导航（如缩放和平移），然而，它们不会改变视觉结构（如节点位置），数据的可见性和数据本身；
视觉结构层（Visual-structure Level Interactions)，改变数据的可视化映射。例如，网络布局（改变节点位置）和改变实体映射（节点颜色或者大小的改变）；
数据选择层（Data-selection Level Interactions)，改变数据的可见性，包括基于某些实体的值过滤节点；
数据变化层（Data-change Level Interactions)，操作数据值或者形成新的数据。例如，编辑一个实体数据的值和合并多个节点和边。

图 9 图交互理论