图是信息科学中最常用的一类抽象数据结构,能够直观的表达现实世界中对象之间的真实关系。许多重要应用都需要用图结构表示,传统应用如最优运输路线的确定、疾病爆发路径的预测、科技文献的引用关系等;新兴应用如社交网络分析、语义 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)。
在对传统的计算技术带来了挑战的同时,大数据技术的发展也促进了数据可视化的研究。作为数据最上层的展示方法,数据可视化使用图形化的手段,可以传达清晰有效的信息,促进人们对信息的理解。目前数据可视化技术可分为这几类:基于几何投影技术的方法、基于图表的方法、基于像素的方法、基于图符的方法、基于层次的方法和组合方法。作为可视化展现形式之一的网络图,是一种简单直观的图数据可视化展现形式;由于高密度数据区域的聚集特征,散点图可以更为直观的发现群体的存在;在探索大规模数据集时,网络拓扑结构的高度重叠是最严重的缺点之一,这常常会导致数据相互的关系被隐藏或很难被发现。
分布式计算框架的飞速发展极大地提高了人们对数据的处理能力,使得人们有机会可以直接研究大规模的数据集,在这方面,图数据占据了重要的位置。随着移动互联网的飞速发展,以经典的“网络”为主的图数据越来越多的出现在我们的日常生活中。在针对图数据的可视化中,提供有效的洞察力非常重要,这具体体现在以下两个方面:
面对大规模图数据的处理需求,分布式图数据布局计算往往有以下特点:
[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.