初识图数据的可视化

图数据的产生和发展

图是信息科学中最常用的一类抽象数据结构，能够直观的表达现实世界中对象之间的真实关系。许多重要应用都需要用图结构表示，传统应用如最优运输路线的确定、疾病爆发路径的预测、科技文献的引用关系等；新兴应用如社交网络分析、语义 Web 分析、生物信息网络分析等，与图相关的处理和应用几乎无所不在 [1] 。

随着技术的不断发展，网络在我们的生活中比以往任何时候都更加突出，上述一系列网络或图结构中都蕴含了越来越多的隐含信息，对这些网络的进行高效的分析和挖掘是亟待解决的一个问题，可视化技术在这一问题上具有无可比拟的优势，其视觉呈现可以给人们带来直观的对数据的理解和感知，Palmer等人在其文章中证明，图比其他可视化展现形式更适合探索数据的内部关系 [2] 。

面对飞速发展的信息社会，各式各样的数据集均迅速增长，部分原因是它们越来越多地被廉价且众多的信息传感物联网设备收集，如移动设备，航空（遥感），软件日志，照相机，麦克风，射频识别（RFID）阅读器和无线传感器网络。身处大数据时代，其对数据的分析和挖掘显得尤为重要，2016年的大数据的定义在指出大数据代表的数据信息具有 4V 特性之外，还强调了其需要特定的技术和分析方法才能转化为价值。随着技术的不断进步，各大分布式计算框架相继产生，其为大数据处理提供了有力的支撑，作为分布式计算、并行计算和网格计算的发展和延续，其对于单机串行处理性能不足的问题，给出了新的解决方案。

在万物互连的今天，我们已经拥有经典的大规模数据的处理方案，可以借助诸如 Spark 或 Hadoop 等分布式计算框架来实现大规模数据集的各种数据挖掘算法，在此趋势下越来越多的由于数据规模过大而导致的分析难题都被解决，但与此同时，在数据集规模和数据维度的极度膨胀下，我们对分析结果的准确性和可解释性的把握正在逐渐降低，追求可视化的宏观展现与细粒度的数据分析结果的一致性从来都是一个美好的愿景，前者可以对后者提供视觉上的强有力的支持和解释，在信息可视化领域，有越来越多的研究者在为此而努力。

图数据的可视化技术

从可视化技术诞生伊始，其目标就是为了帮助人们理解抽象、混乱的数据，至今这一目标依然不曾改变。现在，数据可视化已经发展成为一个广泛的研究领域领域，处于数学、计算机科学、认知和感知科学以及工程学的交叉领域。从信号理论到成像，从计算机图形学到统计学，涵盖所有与可视化原理相关的学科 [3] 。可视化的目的是通过具象的、可交互的图形，让们深入了解我们感兴趣的过程（算法流程、科学模拟或一些真实的过程）的各个方面。可视化本身有许多定义，按照 Williams 等人的观点，可视化是人类在一个空间内构建图像时所进行的认知过程。在计算机和信息科学中，它更具体地说，是使用图形、图像、动画和声音来更详细的表示目标对象的数据、结构和动态行为的空间具象表示 [4] ，这里的目标对象可以指系统、事件、过程、对象和概念的大型复杂数据集。

目前，由于互联网及物联网技术的发展，网络这一名词正在被赋予越来越多的应用场景，随之而来的是我们自身正在越来越多的网络中扮演着重要的角色：大到 Facebook 的全球社交关系网络，小到家庭智能电器组网，都成为我们日常生活中不可或缺的一部分。这些复杂的网络中往往隐含着非常有价值的信息，例如，通过分析特定的社交网络来挖掘犯罪嫌疑人的相关信息 [5] 。经典的社交网络等复杂网络，其本质可用图这一数据结构相对应，自然地，图论中的各种理论也可以被应用到网络分析中，复杂网络分析方法的发展也验证了这一结论，在本文中，将统一称研究对象为“图数据”，将对其可视化呈现称为“图数据的可视化”，这里的图数据除了包含经典的社交网络之外，还包括各种可以抽象为网络的数据，总体上可以将其称为“社会网络”。

根据 IEEE VIS [6] 的分类，可视化研究领域主要分为信息可视化（InfoVIS）、科学可视化（SCIVIS）和可视分析（VAST）三部分，其中以信息可视化最为基础，其核心目的即：将给定的数据集 D 按特定的转换（Transform）规则 T，转换为对应的带空间信息的数据集 V(D) 并显示，以此来帮助人们理解大量、复杂、抽象的原始数据。对于图数据的布局过程，这一转换 T，即数据集 D 在给定二维（或三维）空间内的一组坐标映射 V(D)。

大规模图数据可视化的重要性

在对传统的计算技术带来了挑战的同时，大数据技术的发展也促进了数据可视化的研究。作为数据最上层的展示方法，数据可视化使用图形化的手段，可以传达清晰有效的信息，促进人们对信息的理解。目前数据可视化技术可分为这几类：基于几何投影技术的方法、基于图表的方法、基于像素的方法、基于图符的方法、基于层次的方法和组合方法。作为可视化展现形式之一的网络图，是一种简单直观的图数据可视化展现形式；由于高密度数据区域的聚集特征，散点图可以更为直观的发现群体的存在；在探索大规模数据集时，网络拓扑结构的高度重叠是最严重的缺点之一，这常常会导致数据相互的关系被隐藏或很难被发现。

分布式计算框架的飞速发展极大地提高了人们对数据的处理能力，使得人们有机会可以直接研究大规模的数据集，在这方面，图数据占据了重要的位置。随着移动互联网的飞速发展，以经典的“网络”为主的图数据越来越多的出现在我们的日常生活中。在针对图数据的可视化中，提供有效的洞察力非常重要，这具体体现在以下两个方面：

• 通过布局来展现图数据的具体特征
  在这方面可以回答用户关于图数据本身的定量问题，例如在数据中拥有邻居最多的节点的信息、数据可以被划分为几个聚簇等等。这类问题的特点，是有明确的“问题驱动”，往往在没有可视化结果的帮助下用户也能得到准确的结果，但对于图数据而言，诸如想聚簇等特征，只有通过具体的布局呈现，才能更直观的得到一些运行结果的评价，像划分的聚簇间有无重叠这一问题，既需要数值上的（重叠度）准确度量，也同样需要布局上的清晰的边界划分。

• 为产生布局结果的过程提供信息
  这部分内容并不针对具体问题，但对布局过程的尽可能详细的展现，使用户能够更容易的针对布局结果呈现的状态来反推出一些非常规问题的答案，例如在两方对立的意见网络中，中间（中立）节点对整个布局质量的影响（更紧密或更清晰），对于这个列子，研究者可能在一开始只发现了布局混乱这一现象，而并不知道中间节点对布局的影响，在经过对布局过程的可视化过程研究以后才得到最终结论。这类问题即 Telea 所说的“研究者对一种现象感兴趣，是为了发现数据新的特性并建立意想不到的关联”[3] ，这对于进一步理解数据中的信息起到了至关重要的作用.

<< 更多精彩尽在『程序萌部落』>>
<< https://www.cxmoe.com >>

分布式大图布局计算的特点和挑战

面对大规模图数据的处理需求，分布式图数据布局计算往往有以下特点：

• 需要进行计算的数据量巨大。节点规模在百万以上，单机甚至无法将全部顶图数据加载到内存中，虽然使用 Spark 等基于内存的分布式框架可以完成对此规模数据的处理，但如此规模的数据量仍然对集群的 IO 性能、网络传输性能提出了很高的要求；

• 需要完成逻辑上的多次迭代。应用广播等方式可以避免显式的循环使用，但布局计算的完成仍然离不开动辄几百次的迭代步骤，这对于传统 MapReduce计算框架来说是一个灾难，Spark 的 RDD 有效的避免了中间结果的 IO 操作，但上百次的迭代仍需要研究者十分小心的处理 RDD 的各种转换；

• 必须重写已有布局算法。显而易见，在布局算法的运行机制和环境发生改变后，布局算法也需要重新进行设计以适应不同的计算框架，虽然这和原有布局算法有着相同的算法思想，但在特定分布式计算框架上设计出完全适合且能够高效运行的算法，往往考验着研究人员对特定分布式计算框架的理解程度；

• 布局结果难以查看。单机布局算法往往能够轻松的对每次迭代的结果进行展示，像可视化布局工具 Gephi [7] 可以通过显示每次布局的结果来呈现动态的布局过程，但在分布式计算框架中这一操作往往很难实现，因为在此环境下数据会分片发往不同的工作节点进行计算，如果每次迭代完成都要汇总一次来展现
  当前布局结果，这将直接导使用基于内存的计算框架的优点的丧失。

参考文献

[1] 于戈, 谷峪, 鲍玉斌, 等. 云计算环境下的大规模图数据处理技术[J]. 计算机学报, 2011,34(10): 1753-1767.
[2] PALMER S, ROCK I. Rethinking perceptual organization: The role of uniform connectedness[J]. Psychonomic bulletin & review, 1994, 1(1): 29-55.
[3] C T A. Data visualization: principles and practice[M]. AK Peters/CRC Press, 2007.
[4] WILLIAMS M. Visualization.[J]. Annual Review of Information Science and Technology(ARIST), 1995(30): 161-207.
[5] JOHNSON J, REITZEL J D, NORWOOD B, et al. Social network analysis: A systematic approach for investigating[J]. FBI Law Enforcement Bulletin., 2013, 350.
[6] IEEE VIS[EB/OL]. 2019. http://ieeevis.org/year/2019/welcome.
[7] BASTIAN M, HEYMANN S, JACOMY M. Gephi: an open source software for exploring and manipulating networks[C]//Third international AAAI conference on weblogs and social media.
2009.