《清华大学数据可视化教程网络数据可视化562705203》由会员分享，可在线阅读，更多相关《清华大学数据可视化教程网络数据可视化562705203（92页珍藏版）》请在金锄头文库上搜索。
1、网络数据可视化网络数据可视化 计算机系胡事民 清华大学“大数据”系列课程 大纲大纲 网络关系数据网络关系数据 网络关系数据的可视化网络关系数据的可视化 节点链接布局节点链接布局 相邻矩阵相邻矩阵 混合布局混合布局 图的简化图的简化 网络关系数据的交互网络关系数据的交互 工具与应用工具与应用 有向图无向图加权图非连通图顶点的度 回路无回路图无回路连通图 （树） 具有根结点 的树 节点的深度 回顾：树回顾：树 vs. 图图 网络关系数据网络关系数据 相较于树型数据中明显的层次结构，网络数据 并不具有自底向上或自顶向下的层次结构，表 达的关系更加自由和复杂 相较于树型数据中明显的层次结构，网络数据
2、并不具有自底向上或自顶向下的层次结构，表 达的关系更加自由和复杂 社交网络社交网络 电话网络电话网络 邮件网络邮件网络 合作网络合作网络 网络理论的应用网络理论的应用 疾病传播分析 路由器网络的设计 搜索引擎的设计 演员的协作关系分析 科研人员的研究协作分析 社交网络 . . Typhoid Mary AIDS Mary 美国议会关系美国议会关系 移动专利诉讼关系移动专利诉讼关系 基于D3.js http:/bl.ocks.org/1153292 p/mobile-patent-suits-graphic-of-the-day/ 网络的重要性质网络的重要性质 关系的复杂性关系的复杂性 方向性、
3、权重方向性、权重 关系的中心性关系的中心性(centrality) Degree Closeness Betweenness 该边在图中所有最短路径中出现的总次数和该边在图中所有最短路径中出现的总次数和 Eigenvector 大纲大纲 网络关系数据网络关系数据 网络关系数据的可视化网络关系数据的可视化 节点链接布局节点链接布局 相邻矩阵相邻矩阵 混合布局混合布局 图的简化图的简化 网络关系数据的交互网络关系数据的交互 工具与应用工具与应用 需要解决的问题需要解决的问题 网络关系结构的图形化展示网络关系结构的图形化展示 和层次数据相比更加复杂和层次数据相比更加复杂 节点的排布节点的排布 视图的
4、视觉复杂度视图的视觉复杂度 与网络视图的交互与网络视图的交互 网站图网站图 Google 图的可视化图的可视化 节点链式显示节点链式显示 分层显示分层显示/Sugiyama 力引导布局力引导布局 相邻矩阵相邻矩阵 基于属性的显示基于属性的显示 Sugiyama类显示类显示 非常适用于显示具有原生顺序的树，图的“深度” 映射到某一坐标轴上 非常适用于显示具有原生顺序的树，图的“深度” 映射到某一坐标轴上 这张这张Unix族谱的“原生顺序”是什么？族谱的“原生顺序”是什么？ 还有什么比较典型的有 “原生顺序”的图关系？ 还有什么比较典型的有 “原生顺序”的图关系？ UNIX族谱 Sugiyama：
5、层次建立：层次建立 创建图的层次创建图的层次 原生顺序原生顺序 领域知识领域知识 如果都没有如果都没有 一个好的一个好的Sugiyama布局应当满足：布局应当满足： 尽量少的回边（所有边尽可能统一方向）尽量少的回边（所有边尽可能统一方向） 寻找最大无环子图（寻找最大无环子图（Minimum feedback arc set problem, 多项式时间内不可解）多项式时间内不可解） 将所有回边反向（并记录）后进行下一步处理将所有回边反向（并记录）后进行下一步处理 最终渲染时再将被反向的边恢复。最终渲染时再将被反向的边恢复。 Sugiyama：层次建立：层次建立(cont.) Eades, 19
6、93 没有入度或没有出度的节点不可能参与到任何回路 中。 没有入度或没有出度的节点不可能参与到任何回路 中。 另一方面，一张图如果所有节点都有出度有入度， 则其中一定含有环。（反证法） 另一方面，一张图如果所有节点都有出度有入度， 则其中一定含有环。（反证法） 设计贪心算法实现（并不保证得到最优解）设计贪心算法实现（并不保证得到最优解） Sugiyama：层次建立：层次建立(cont.) 对于一个图对于一个图G通过贪心法求解其最大通过贪心法求解其最大(?)无环子图无环子图 构造一个空图构造一个空图G 如果如果G不为空：不为空： 将将G中所有无出度或者无入度的节点（以及其所有连 接的边）移至 中
7、所有无出度或者无入度的节点（以及其所有连 接的边）移至G。 此时图中一定有回路此时图中一定有回路 统计所有节点出、入度之差，取差值最大的节点。统计所有节点出、入度之差，取差值最大的节点。 如果出如果出入，将该节点与所有出边移至入，将该节点与所有出边移至G，删去所有入边。，删去所有入边。 如果入如果入出，将该节点与所有入边移至出，将该节点与所有入边移至G，删去所有出边。，删去所有出边。 循环该过程。循环该过程。 G即为所求解的最大即为所求解的最大(?)无环子图。无环子图。 Sugiyama：层次建立：层次建立(cont.) 完成上一算法之后，我们得到了一张有向无环图。 之后在这张有向无环图内对每
8、个节点确定其层次， 有若干不同的方案： 完成上一算法之后，我们得到了一张有向无环图。 之后在这张有向无环图内对每个节点确定其层次， 有若干不同的方案： 最长路层次化：最长路层次化： 将所有汇节点（无出度的节点）置于底层（第将所有汇节点（无出度的节点）置于底层（第0层）层） 每个非汇节点的高度为它到汇节点集合的最长距离。每个非汇节点的高度为它到汇节点集合的最长距离。 优点：快速（线性时间）优点：快速（线性时间） 缺点：宽度控制缺点：宽度控制 Sugiyama：层次建立：层次建立(cont.) Coffman-Graham 层次化：层次化： 算法原本用于多算法原本用于多CPU系统调度（任务依赖性由
9、有向 无环图确认） 系统调度（任务依赖性由有向 无环图确认） 拓扑排序拓扑排序 保留拓扑排序同时满足层次化，使得每一层最多含保留拓扑排序同时满足层次化，使得每一层最多含 w个节点（限制了宽度），从汇节点开始贪心排布。个节点（限制了宽度），从汇节点开始贪心排布。 O(n2) Sugiyama：层次建立：层次建立(cont.) 单纯形层次化（单纯形层次化（Network Simplex Layering, AT&T,1993） Integer Linear Progamming(ILP) 可以自由添加约束可以自由添加约束 高度约束（避免“高到不知道哪里去”）高度约束（避免“高到不知道哪里去”） 宽
10、度约束宽度约束 Sugiyama：层次建立：层次建立(cont.) 同一个结构在最长路、同一个结构在最长路、 Coffman-Graham、单 纯形下的层次建立结果： 、单 纯形下的层次建立结果： 最长路 Coffman-Graham 单纯形 Sugiyama：交叉约简：交叉约简 以上仅仅从图结构上讨论了层次化问题，然而 以上述方法直接建立的图会存在交叉。 以上仅仅从图结构上讨论了层次化问题，然而 以上述方法直接建立的图会存在交叉。 交叉点的数量与实际坐标无关，而只与节点的 排序相关。 交叉点的数量与实际坐标无关，而只与节点的 排序相关。 即便是在只有两层的情形（二分图）下，寻找 交叉最少的布
11、局方案也是多项式时间内不可解 的问题。 即便是在只有两层的情形（二分图）下，寻找 交叉最少的布局方案也是多项式时间内不可解 的问题。 Sugiyama：交叉约简：交叉约简(cont.) 启发式算法：每次只在两层之间，锁定其中一层，对 另一层的相对位置进行调整。具体调整算法？ 启发式算法：每次只在两层之间，锁定其中一层，对 另一层的相对位置进行调整。具体调整算法？ 快速排序快速排序 先随机确定一个点先随机确定一个点p，之后对于每个点，之后对于每个点c通过最少交点的 原则确定它应当在 通过最少交点的 原则确定它应当在p左侧还是右侧，之后对左侧还是右侧，之后对p两侧的节点 依此类推。 两侧的节点 依
12、此类推。 均值（中位数）法：均值（中位数）法： 对于每一个点对于每一个点p，计算其所有邻接节点，计算其所有邻接节点x坐标的均值（中 位数），最终对所有节点的计算结果进行排序。 坐标的均值（中 位数），最终对所有节点的计算结果进行排序。 ILP法法 Sugiyama 美观、可读性好、自然的自上而下排列美观、可读性好、自然的自上而下排列 相对快速（依赖于启发式算法）相对快速（依赖于启发式算法） 不适用于明显不具有原生自顶向下顺序的图不适用于明显不具有原生自顶向下顺序的图 难以实现难以实现 图的可视化图的可视化 节点链式显示节点链式显示 分层显示分层显示/Sugiyama 力引导布局力引导布局 相邻
13、矩阵相邻矩阵 基于属性的显示基于属性的显示 基于力引导的算法基于力引导的算法 没有原生的顺序，怎么办？没有原生的顺序，怎么办？ 使用物理模型：边使用物理模型：边=弹簧；节点弹簧；节点=互斥质点互斥质点 力引导结果示例力引导结果示例 High school dating network 力引导结果示例力引导结果示例 悲惨世界的人物图谱 http:/hci.stanford.edu/jheer/files/zoo/ 力引导布局力引导布局 最早由最早由Peter Eades在在1984年的“启发式画图算法”一文中 提出 年的“启发式画图算法”一文中 提出 用弹簧模拟两个点之间的关系，受到弹力的作用，
14、过近的 点会被弹开而过远的点被拉近 用弹簧模拟两个点之间的关系，受到弹力的作用，过近的 点会被弹开而过远的点被拉近.通过不断的迭代，最终使整 个布局达到动态平衡，趋于稳定 通过不断的迭代，最终使整 个布局达到动态平衡，趋于稳定 弹簧模型 （引力）弹簧模型 （引力） ? ? ? 1 2 ? ?,? ? ?,? ? ? ? ? ? 能量模型（斥力）能量模型（斥力） ? ? ? ? ? ? ? ?,? ? ? ? ? ? ? 迭代过程迭代过程 从随机生成的节点排列开始从随机生成的节点排列开始 循环：循环： 为每一对节点计算排斥力为每一对节点计算排斥力 为每一条边计算引力为每一条边计算引力 将每个节点
15、的各个力累加到一起将每个节点的各个力累加到一起 沿着合力的方向更新各个节点的位置沿着合力的方向更新各个节点的位置 简便计算起见的抽象：简便计算起见的抽象： ? ? ? 当节点的排列“足够好”时结束更新当节点的排列“足够好”时结束更新 对于“力”的理解对于“力”的理解 “力”并没有物理意义，而是对于能量函数 （损失函数）的一种抽象。 “力”并没有物理意义，而是对于能量函数 （损失函数）的一种抽象。 因而在许多情况下应当被灵活处理：因而在许多情况下应当被灵活处理： 例如弹簧模型例如弹簧模型F=-k(x-d)在长距离下会施加过大的 力，使得整个布局被挤成一团，可以松弛化为 在长距离下会施加过大的 力，使得整个布局被挤成一团，可以松弛化为 F=k*log(x/d)。 Barycenter力引导力引导 Giuseppe Di Battista,1999 整张图中只对临接节点施加引力整张图中只对临接节点施加引力y=kx。 传统迭代法迭代若干轮之后整张图将趋向于坍缩在 质心处。 传统迭代法迭代若干轮之后整张图将趋向于
