• 单纯形层次化（Network Simplex Layering, AT&T,1993）
– Integer Linear Progamming(ILP) – 可以自由添加约束
• 高度约束（避免“高到不知道哪里去”） • 宽度约束
Sugiyama：层次建立(cont.)
• 同一个结构在最长路、 Coffman-Graham、单 纯形下的层次建立结果：
Sugiyama：交叉约简(cont.)
启发式算法：每次只在两层之间，锁定其中一层，对 另一层的相对位置进行调整。具体调整算法？ • 快速排序
– 先随机确定一个点p，之后对于每个点c通过最少交点的 原则确定它应当在p左侧还是右侧，之后对p两侧的节点 依此类推。
• 均值（中位数）法：
– 对于每一个点p，计算其所有邻接节点x坐标的均值（中 位数），最终对所有节点的计算结果进行排序。
Voronoi Diagram就是地图中的各个区域
• 图的简化 • 网络关系数据的交互 • 工具与应用
需要解决的问题
• 网络关系结构的图形化展示
– 和层次数据相比更加复杂 • 节点的排布 • 视图的视觉复杂度
• 与网络视图的交互
网站图

Google
图的可视化
• 节点链式显示
– 分层显示/Sugiyama – 力引导布局
• 相邻矩阵 • 基于属性的显示
• 将G中所有无出度或者无入度的节点（以及其所有连 接的边）移至G’。
– 此时图中一定有回路
• 统计所有节点出、入度之差，取差值最大的节点。
– 如果出>入，将该节点与所有出边移至G’，删去所有入边。 – 如果入>出，将该节点与所有入边移至G’，删去所有出边。
• 循环该过程。 – G’即为所求解的最大(?)无环子图。
Sugiyama类显示
• 非常适用于显示具有原生顺序的树，图的“深度” 映射到某一坐标轴上
• 这张Unix族谱的“原生顺序”是什么？ • 还有什么比较典型的有
“原生顺序”的图关系？
UNIX族谱
Sugiyama：层次建立
• 创建图的层次
– 原生顺序 – 领域知识 – 如果都没有……
• 一个好的Sugiyama布局应当满足：
• “磁场”形态
– 平行、涡旋、辐射 – 并不一定满足物理上磁场的0散度性质。
磁场力引导
• 通过磁场引入两节点间方向垂直于两节点连线
的作用力。
magnetic spring
θ
Direction of the magnetic field
Vertical magnetic field
Vertical and horizontal magnetic field
节点链接图小结
• 可理解的视觉映射 • 能够表现图的总体结构、
簇、路径 • 灵活，有许多变种 • 几乎所有直观算法的复杂
度>O(N2) • 对于密集（尤其是关系密
集）的图不是很适用
图的可视化
• 节点链式显示
– 分层显示/Sugiyama – 力引导布局
• 相邻矩阵 • 基于属性的显示
相邻矩阵
清华大学“大数据”系列课程
网络数据可视化
计算机系 胡事民
大纲
• 网络关系数据 • 网络关系数据的可视化
– 节点链接布局 – 相邻矩阵 – 混合布局
• 图的简化 • 网络关系数据的交互 • 工具与应用
回顾：树 vs. 图
有向图
无向图
加权图
非连通图
顶点的度
回路
无回路图
无回路连通图 （树）
具有根结点 的树
节点的深度
网络关系数据
• 相较于树型数据中明显的层次结构，网络数据 并不具有自底向上或自顶向下的层次结构，表 达的关系更加自由和复杂
– 社交网络 – 电话网络 – 邮件网络 – 合作网络
网络理论的应用
疾病传播分析 路由器网络的设计 搜索引擎的设计 演员的协作关系分析 科研人员的研究协作分析 社交网络
– 目标是在可视化结果中，两点欧氏距离尽可能接近 图距离。
• 在任意两节点间添加与图距离相等长度的弹簧。
– 然而通常情况下我们更关心图距离较近节点的位置 关系。
– 弹簧的弹性系数定义与图论距离反相关。
磁场力引导[Sugiyama 95]
• 基本思想
– 一些弹簧被赋予磁性 – 通过一个全局的磁场干涉弹簧的方向 – 从而我们可以影响边的方向进而影响布局
MatrixExplorer
MatLink
NodeTrix
其它布局
GMap
• GMap是一种用平面代表实体，平面的连通代 表实体的关系的一种“地图”
image courtesy of Emden Gansner, et al
Gmap生成步骤
• 先将网络图画在二维上 • 用聚类分析的方法把网络图中的节点归类 • 把各个类别中的点构造Voronoi Diagram，而
左：以相连正交的直线表达相连的节点。右：左相邻 矩阵所表达的路径在节点-链接图中的表达
识别出矩阵的模式
相邻矩阵法小结
• 完全规避边的交叉，非常适用于密集的图 • 视觉伸缩性强 • 能展示图的模式 • 可视化结果比较抽象 • 难以跟踪出路径
基于属性的图可视化
• 除了使用节点的连接关系以外，还使用各个节 点的属性
Sugiyama：层次建立(cont.)
• Coffman-Graham 层次化：
– 算法原本用于多CPU系统调度（任务依赖性由有向 无环图确认）
– 拓扑排序 – 保留拓扑排序同时满足层次化，使得每一层最多含
w个节点（限制了宽度），从汇节点开始贪心排布。 – O(n^2)
Sugiyama：层次建立(cont.)
的矩阵，代表N个节点，矩阵内的位置(i, j)表达了第i个节点和第j个节点之间的关系
– 权重 – 方向性 – 自反性
• 相关算法
– 排序 – 路径搜索
相 邻 矩 阵 法 的 排 序 示 例
《悲惨世界》人物图谱 /jheer/files/zooFra bibliotek邻矩阵路径的可视化
• 弹簧模型 （引力）
1
,
,
2
• 能量模型 （斥力）
,
迭代过程
• 从随机生成的节点排列开始 • 循环：
–为每一对节点计算排斥力 –为每一条边计算引力 –将每个节点的各个力累加到一起 –沿着合力的方向更新各个节点的位置
• 简便计算起见的抽象：
–
• 当节点的排列“足够好”时结束更新
对于“力”的理解
• “力”并没有物理意义，而是对于能量函数 （损失函数）的一种抽象。
磁场力引导
• 优点
– 非常灵活，对各种类型的图都能生成较好的显示效 果
– 能添加自定义的力 – 相对容易实现
基于能量最优的“力引导”
• 力引导布局的实质是最小化某一能量值。 • 另一则思路则是直接迭代式地由能量值求解最优
位置：
– 对于每一个节点，假设其它节点不动，求解其最优位 置。
– 迭代上述处理若干轮。
、GVA
图的其它节点链接显示方式
• 正交图
– 非常适用于显示UML图 – 算法复杂
• 环形排列
– 强调环形的拓扑结构 – 在社交网络图中广泛采用
• 嵌套排列
– 递归式地应用图排列算法 – 适用于具有层次结构的图
• 弧长链接图
弧长链接图
/jheer/files/zoo/
《悲惨世界》的人物图谱
弧长链接图
• 如果不对节点进行合理排序则易于产生交叉 • 最小化交叉数量不能在多项式时间内解决。
– 启发式算法：ILP，节点聚类
• 连线易于混淆
– 添加交互 – 过滤掉不关心的信息 – 边绑定
弧长链接图
2011年年末欧债危机时各国之间错综 复杂的借贷关系的可视化
/news/business-15748696
– 每一轮迭代后直接放大每个点到质心的距离以规避 这一情形。
• 这一力引导方法能够较大程度规避边交叉，且 最终生成的绘制面能保持较好的凸性。
Barycenter力引导(2)
• 或者可以人工锁定一些节点的位置(以确定凸多 边形的轮廓)
图距离力引导[Kamada Kawai 89]
• 两点间的图距离定义为两点之间的最短路长度。
• ILP法
Sugiyama
• 美观、可读性好、自然的自上而下排列 • 相对快速（依赖于启发式算法） • 不适用于明显不具有原生自顶向下顺序的图 • 难以实现
图的可视化
• 节点链式显示
– 分层显示/Sugiyama – 力引导布局
• 相邻矩阵 • 基于属性的显示
基于力引导的算法
• 没有原生的顺序，怎么办？ • 使用物理模型：边=弹簧；节点=互斥质点
• 基于节点的属性进行排列
–代价小 –与应用领域直接相连 –难以从多个分离视图中拼凑出总体结构 –有时候是不可行的
枢轴图(pivotGraph)
• 基于属性值“卷制”而成 • 对于二维情形能同时往两个方向进行卷制 • 通过观察边的权重能识别图的模式
词组网络
混合布局
混合布局
• 边的关系复杂——相邻矩阵 • 节点规模大——点-线图 • 二者得而兼之
力引导结果示例
High school dating network
力引导结果示例
《悲惨世界》的人物图谱 /jheer/files/zoo/
力引导布局
• 最早由Peter Eades在1984年的“启发式画图算法”一文中 提出
• 用弹簧模拟两个点之间的关系，受到弹力的作用，过近的 点会被弹开而过远的点被拉近.通过不断的迭代，最终使整 个布局达到动态平衡，趋于稳定