1. 网络数据1.1. 树型结构表达了层次结构关系而不具备层次结构的关系数据可统称为网络Network数据1.2. 网络数据并不具有自底向上或自顶向下的层次结构表达的关系更加自由和复杂1.3. 若路径中顶点没有重复出现则称这条路径为简单路径1.4. 现代人类社会和虚拟网络社会的方方面面都存在网络型数据1.4.1. 人与人之间的电话通信、邮件往来构成了通信网络1.4.2. 人人、推特、新浪微博等社交网站中的好友关系构成了社交网络1.4.3. 多个学者或机构合作发表论文的关系构成了学术合作网络1.4.4. 人体内的基因与基因共同作用形成人的不同外观、性格这种基因协作关系构成了生物基因网络1.4.5. 出租车的出发地与目的地构成了城市交通网络1.4.6. 证券市场中的股票买入卖出关系构成了金融交易网络词组网络1.4.7. 文本的单词与单词之间按照指定的关系构成了词组网2. 网络数据可视化2.1. 图的绘制Graph Drawing是一个历史悠久的研究方向2.2. 三个方面网络布局、网络属性可视化和用户交互其中布局确定图的结构关系是最核心要素2.3. 节点-链接法2.3.1. 用节点表示对象用线或边表示关系的节点-链接布局Node-link是最自然的可视化布局表达2.3.2. 关系型数据库的模式表达、地铁线路图的表达因而是网络数据可视化的首要选择2.3.3. 针对不同的数据特性可采用不同的节点-链接布局法2.4. 力引导布局2.4.1. Force-directed Layout2.4.2. 力引导布局方法最早由Peter Eades在1984年的“启发式画图算法”一文中提出 目的是减少布局中边的交叉尽量保持边的长度一致2.4.3. ​“力引导”的概念被提出演化成力引导布局算法2.4.3.1. 丰富了两个点之间的物理模型加入点之间的静电力通过计算系统的总能量并使得能量最小化从而达到布局的目的2.4.3.2. 这种改进的模型称为能量模型可看成弹簧模型的一般化2.4.4. 无论是弹簧模型还是能量模型其算法的本质都是要解一个能量优化问题区别在于优化函数的组成不同2.4.5. 优化对象包括引力和斥力部分不同算法对引力和斥力的表达方式不同2.4.6. 力引导布局可广泛地应用于各类无方向图很多可视化工具包都实现了这个算法只要在调用工具包中的布局之前定义好点、边和权重就能快速地实现一个力引导布局2.4.7. Tulip2.4.8. Prefuse2.4.9. Gephi2.4.10. Protovis2.4.11. 力引导布局易于理解、容易实现可以用于大多数网络数据集而且实现的效果具有较好的对称性和局部聚合性因此比较美观2.4.12. 力引导布局只能达到局部优化而不能达到全局优化并且初始位置对最后优化结果的影响较大2.4.13. 力引导布局的众多改进算法主要针对效率的优化优化思路也大致分减少迭代次数和降低每次迭代的时间复杂度两种2.5. 多维尺度分析布局2.5.1. MDS Layout2.5.2. MDS布局的出现正是为了弥补力引导布局的局限性2.5.3. 针对高维数据用降维方法将数据从高维空间降到低维空间力求保持数据之间的相对位置不变同时也保持布局效果的美观性2.5.4. 力引导布局方法的局部优化使得在局部点与点之间的距离能够比较忠实地表达内部关系但却难以保持局部与局部之间的关系2.5.5. MDS是一种全局控制目标是要保持整体的偏离最小这使得MDS的输出结果更加符合原始数据的特性2.5.6. 古典尺度分析基于矩阵近似和基本欧式几何理论计算伪内积空间B与内积空间中点的相异性2.5.7. 基于距离的尺度分析方法的思想是使两点的距离尽量等价地表达它们的相异性也就是求解一个优化问题使高维距离和相异性差的误差函数Stress最小2.5.8. 算法的另一个输入就是降维的维度取决于可视化结果的呈现维度空间一维、二维或三维​而输出是每个节点在低维空间的坐标2.5.9. MDS布局因为能保持全局优化而保证了布局的质量同时具有较好的可扩展性能够处理节点和关系非常多的数据2.5.10. 古典尺度分析因为其时间复杂度和空间复杂度较大而不能处理大数据图pivotMDS用基于采样的方法获得近似古典尺度分析的效果不但能降低算法的复杂度还能通过调整采样频率渐进式地细化布局的效果2.6. 弧长链接图2.6.1. 节点-链接法的一个变种是*弧长链接图Arc Diagram​2.6.2. 采用一维布局方式即节点沿某个线性轴或环状排列圆弧表达节点之间的链接关系2.6.3. 对节点的排序优化问题又称为序列化Serialization​在可视化、统计等领域有广泛的应用2.7. 相邻矩阵布局2.7.1. 相邻矩阵Adjacency Matrix指代表N个节点之间关系的N×N的矩阵矩阵内的位置i,j表达了第i个节点和第j个节点之间的关系2.7.2. 对于无权重的关系网络用零壹矩阵Binary Matrix来表达两个节点之间的关系是否存在2.7.3. 对于带权重的关系网络相邻矩阵则可用i,j位置上的值代表其关系紧密程度2.7.4. 对于无向关系网络相邻矩阵是一个对角线对称矩阵2.7.5. 对于有向关系网络相邻矩阵不具对称性2.7.6. 相邻矩阵的对角线表达节点与自己的关系2.7.7. 与节点-链接法相比相邻矩阵能很好地表达一个两两关联的网络数据即完全图​而节点-链接图不可避免地会造成极大的边交叉造成视觉混乱2.7.8. 相邻矩阵的表达简单易用可以用数值矩阵也可以将数值映射到色彩空间表达2.7.9. 针对稀疏矩阵的排序算法主要有高维嵌入方法High-dimensional Embedding和最近邻旅行商问题估计方法*Nearest-neighbor TSP Approximation2.7.10. 相邻矩阵法可显著表达节点之间的直接关系而对间接关系也就是关系传递性的可视表达比较薄弱2.7.11. 相邻矩阵的改进在于排序技术的改进在显示上可以将用户关心的矩阵行列放大类似于焦点上下文方法2.8. 混合布局方法2.8.1. 节点-链接布局适用于节点规模大但边关系较为简单并且能从布局中看出图的拓扑结构的网络数据2.8.2. 相邻矩阵恰恰相反适用于节点规模较小但边关系复杂甚至是两两节点之间都存在关系的数据2.8.3. 两种数据的特点是用户选择布局的首要区分原则3. 网络数据的地图隐喻可视化3.1. 地图是人们最熟悉的图形形式将数据以及数据的分类表示成地图的形式可以让人们容易理解数据的集合关系3.2. 将网络图用地图形式表达的方法称为GMap3.2.1. GMap是一种用平面代表集合平面划分代表数据聚类的“地图”可视化策略地图上的国家、国家之间的关系作为可视化隐喻表达了数据的分类和类别之间的相邻度关系3.3. GMap的实现分4步3.3.1. 将网络数据布置于二维空间3.3.2. 用聚类分析的方法将网络图中的节点归类3.3.3. 根据各个类别中点的分类情况构造Voronoi 图3.3.3.1. 一个Voronoi图代表地图的一个区域3.3.4. 给地图的每个Voronoi区域上色3.4. GMap由于其与地图的相似性受到了广泛的接受人们用它来表达事物与事物、类与类之间的抽象关系使可视化结果非常生动有趣4. 超图及其可视化4.1. 超图Hypergraph起源于离散数学中的集簇即集合的集合4.2. 超图在信息科学的许多领域都得到了广泛应用4.3. 超图除了可以直接表示多元关系还能从集合的子系统这个概念引申出聚类的概念一个子系统是一些数据的聚类4.4. 超图并没有一种标准的画法在不同的领域有不同的表示4.4.1. 特别是超边的可视化方法各异如斯坦纳树、平面中的闭曲线、细分面片以及节点等4.4.2. 一般数学研究和工业应用中常见的是文氏图法、海塞图法、细分法以及正交法4.4.3. 超图的正交法是工业界比较常见的画法尤其在大规模集成电路设计中4.4.4. 超图的海塞图是对超图集合偏序中按传递关系约简的结果4.5. 随着超图规模的增加视觉复杂度高和易读性差的问题是面临的挑战4.6. 超图的应用领域广泛如何赋予超图在应用领域的实际意义也是一个值得进一步研究的问题5. 动态网络数据可视化5.1. 动态网络数据是流数据的一种其中“动态”一词可以理解为节点的增减、关系的增减、节点/关系权重的变化三种5.2. 动态网络数据可视化的典型案例是力引导布局5.3. 动画是一种直观的可视化技术它主要基于点边图Node Link Diagram来表示5.4. 时间轴技术不那么直观但它更侧重于分析时变特性6. 图可视化的视觉效果6.1. 随着网络数据规模的不断扩大人们逐渐发现在使用传统方法绘制的结果中节点和边经常出现互相遮挡形成极高的视觉混杂度Visual Clutter​甚至会阻碍我们对真实数据的认知6.2. 根据信息可视化的信息分级Level of Detail原则对大规模图进行层次化简化6.3. 在尽量不减少原图信息量包括边和节点的数目的前提下对图进行基于骨架的聚类6.4. 无论采取哪种思路其目的都是为了应对大规模图对有限可视化空间的挑战降低网络数据可视化的视觉混杂度挖掘和展示数据背后隐藏的信息6.5. 图的拓扑简化6.5.1. 图的拓扑结构包括两个部分节点和边。对应的对图的拓扑进行简化也存在两种方法即分别对节点和边进行层次化简化6.5.2. 产生最小生成树的算法有很多比较著名的有反向删除算法Reverse-delete Algorithm和Prim算法Prims Algorithm等6.5.3. 另一种方法是将强连通的节点进行聚类并把聚类后的节点集作为一个新的超级节点绘制到可视化结果中6.6. 图的边绑定6.6.1. 边绑定Edge Bundling6.6.2. 所谓边绑定是针对节点-链接图中关系过多造成的边互相交错、重叠难以看清的问题而设计的一类可视化压缩算法其核心思想就是在保持信息量即不减少边和节点总数的情况下将图上互相靠近的边捆绑成束从而达到去繁就简的效果6.6.3. 绑定后由于相似形状的连接线集中在一起构成线束使得视觉复杂度大大降低从而使节点间的连接关系也显得更加清楚明了6.6.4. 边绑定可以被看作是沿着若干特定的方向对边进行捆绑从而减少边之间的交叉凸显网络拓扑结构的方法6.7. 图的拓扑简化和边绑定的目的是解决规模较大的图存在的视觉混杂问题7. 图可视化中的交互7.1. 基于视点的交互7.1.1. 基于视点的交互是指用交互手段来预测和帮助用户在图中切换视点7.1.2. 视点交互中比较常规的方法包括界面的平移、缩放、旋转等操作而近年来随着人眼和体感跟踪技术的发展更是出现了一些跟踪人眼和身体移动轨迹的硬件支持这类交互7.1.3. 大规模网络可视化常用的交互操作是Link Sliding和Bring Go技术7.1.4. Bring Go交互操作的目的也是帮助用户将关注焦点从一个节点转移到它的邻居节点7.2. 基于图元的交互7.2.1. 基于图元的交互是指对于一个可视化映射元素的交互如节点的选择、高亮、删除、移动、展开获取细节与收缩7.2.2. 节点的展开与收缩在大规模网络节点-链接图中应用广泛7.2.3. 节点的收缩可以降低整个布局的视觉复杂度使布局更加美观7.2.4. 节点的展开配合视点交互可以使用户的注意力聚焦到感兴趣的局部数据7.3. 基于图结构的交互7.3.1. 大规模网络数据可视化中的图元交互可能会带来不确定性7.3.2. 核心思想是“*焦点上下文”​FocusContext技术7.3.3. 鱼眼是一种极端的广角镜头技术它使用一种焦距极短并且视角接近于180°的镜头7.3.4. 受到鱼眼镜头的启发研究者提出在图的探索过程中根据用户关注的焦点进行有针对性的放大而其他区域则相应的缩小8. 网络数据可视化的挑战8.1. 网络和层次数据可视化方法所面临的挑战主要来自图的规模8.2. 一种可视化方法可能在处理几百个顶点的时候有比较好的效果但仍然无法处理成千上万甚至上百万的规模评价一种可视化方法对数据规模的适应能力相当于考察方法在数据规模上的可扩展性8.3. 用户对数据的认知能力和感知能力也不尽相同构成了可视化的另一大挑战8.4. 一般大众观看交通网络可视化的目的是粗略查看城市中的拥堵位置用于指导开车的路线选择8.5. 城市规划设计师对数据和地理信息已有基本了解可视化可辅助深入挖掘造成城市拥堵的原因协助城市的重规划8.6. 具有不同文化、专业背景的人对不同的视觉元素的感知能力更是可视化能否有效传递信息的一个重要因素8.7. 网络和层次数据可视化面临的挑战也是衡量一个可视化好坏的评价标准8.8. 有些布局需要达到实时交互级别就对算法的时间复杂度要求较高8.9. 布局效果的一致性是指对于相同结构的数据布局相似使用户能保持对布局的印象 提高用户对流数据或动态数据的感知8.10. 一种好的可视化设计往往是用户一部分需求的最大化满足带有强烈的目的性它不仅要考虑到数据的特殊性质还要兼顾用户对数据的认知水平以及用户对数据的可视化需求8.11. 并没有一种可视化方法能够满足所有用户对所有数据的所有可视化需求