多元关系的超图可视表达与分析

刘　真，周文晖

(杭州电子科技大学计算机学院，浙江 杭州 310018)



多元关系的超图可视表达与分析

刘真，周文晖

(杭州电子科技大学计算机学院，浙江 杭州 310018)

摘要：蓬勃发展的社交网络、物联网、关系型数据库和生物医学等应用领域带来海量数据，其中数据对象之间存在错综复杂的关联.传统信息可视化领域表达二元关系的图已经不能表达这些复杂关联，越来越多研究发现表达多元关系的超图能更好地挖掘信息中隐藏的内在联系和模式.针对多元实体关系，提出两种超图可视化方法：海塞图和关联矩阵.其中超图海塞图方法通过在超图交闭半格上构建层次化海塞图进行可视化；超图矩阵可视化将超图表示成关联矩阵、超边关系矩阵和顶点关系矩阵.通过从Medline在线数据库上挖掘多元关系的肺癌超图数据分析和验证上述方法的有效性.

关键词：超图；交闭半格；海赛图；关联矩阵

0引言

基于超图的多元关系可视化研究在国际上尚处于起步阶段.现有的研究工作在表达超图时，通常都把顶点表达为平面中的顶点或者区域，例如斯坦纳树、平面中的闭曲线、细分面片和顶点等[4].超图表示方法包括文氏图、Zykov、二分图和细分画法等[4-5].文献[6]研究固定图布局的单超边嵌入方法，主要给出在避免顶点遮挡情况下，利用能量方法对超边进行路径选择和布局.Basak等研究超图可视化技术线集合(LineSet)，线集合是一个连接所有的集合元素的曲线[7].他们利用线集合分别展示在地图上显示饭店的目录和社交网络的社区.现有的超图可视化方法主要存在以下问题：第一，大多数只简单展示超边和顶点包含关系，没有展示可能存在的各种潜在信息；第二，超图规模的增加导致视觉复杂度高和易读性差；第三，普遍缺乏用户交互.本文提出了海塞图可视化和矩阵可视化两种多元关系的超图的可视设计与交互方法，并通过肺癌实例数据对方法进行验证.

1超图的海塞图可视化

已有超图可视化技术大多都参照图(Graph)可视化方法，可视化超图的拓扑性质或者几何结构，很少研究多元关系的交叉重合以及潜在关系.超图中超边之间的交集代表它们的共同顶点，这些共同顶点在超图往往起着关键作用.海塞图[8]是一种有限偏序集传递约简的表达方式.每一个有限偏序集都可以用海塞图来简洁直观的表达其中的关系.海塞图中的每个顶点代表偏序集中的一个元素，根据元素之间关系将元素排列在不同的层次上，并且仅在有直接关系的元素之间连线.所谓有直接关系是指不存在第三个元素，使得原来两个元素之间的关系可以通过第三个元素进行传递.文献[9]基于海塞图解决社交网络照片的标注、组织以及可视化问题.该方法中用海塞图作为标注过照片的结构，通过在标注的过程中直接识别新照片中的人物，将新照片拖到海塞图中找到包含相应人物的照片上完成标注.文献[10]利用海塞图非常客观和直观地实现2008年奥运会前十名国家的排名.本文超图海赛图可视化是对超图的多元关系，特别关系的交叉重叠、顶点共同出现以及关键顶点探索的有效方法.

1.1交闭半格

超边是顶点的集合，对超边两两进行求交运算可以得到新的顶点集合.对这些新产生的顶点集合和超边进行迭代求交运算，最后可以得到交闭的结构.它是一个包含关系的偏序集，称为超图的交闭半格.下文将详细介绍用海塞图来可视化超图的交闭半格.

1.2可视表达

如图1(a)所示，海塞图可视化是一种采用弧形的彩虹布局的层次化可视设计.概览视图分为超边层、新关系层和关键顶点层，其中超边层表示超图中的超边.3个层次用椭圆、棱形或者矩形表示顶点，连线表示顶点之间的直接包含关系并且根据超边规模或者连线数编码其颜色和宽度.新关系层代表交闭半格中通过求交得到的新的顶点集合.因为新关系之间也存在交集，所以新关系层一般会包含多个等级，从上到下表示越来越紧密的新关系.根据新关系的规模、等级以及关联程度进行大小或者颜色的编码，直观展示其大小、紧密程度和其在超图中的重要性.关键顶点层是指交闭半格中求交得到的单个顶点，它表示出现在超边里的重要顶点.关键顶点层位于可视化的最下方，对超图的连通性有重要影响.根据其出现的次数进行颜色或者大小的编码，以区分它们在超图中的重要性.

1.3交互设计

海塞图可视化的交互基于概览加细节的原则进行设计，并且支持不同层次可视元素的选择、拖拽、高亮等操作以及整个概览视图的缩放、平移等.超图海塞图可视化示意图如图1所示.如图1中(b)、(c)和(d)所示，可以对概览视图中的元素进行3种类型的交互.交互1是对超边ABCD的交互，概览视图高亮它关联的关系网络，图1(b)显示这个关系网络的详细信息.交互2是对超边ABCD引出的新关系BCD的进一步交互，概览视图中也会高亮出其关联的关系网络.从图1(d)可以看出，它是由超边ABCD和BCDE求交而得，BCD和其它新关系衍生出新关系BC和CD.交互3是对关键顶点C的交互.同样概览视图高亮出该顶点关联的局部海塞图结构，图1(c)详细显示局部信息.这种交互方式不仅详细展示内容信息，而且很好地展示超图中元素关系的结构信息.

2超图的关联矩阵可视化

上述超图的海塞图可视化方法要求数据规模不能太大，因此本节提出超图的矩阵可视化方法.矩阵可视化不仅能从宏观上可视化超图的关系模式，还能适合于更大规模的超图.

2.1矩阵描述

类似于图的邻接矩阵，每个超图都有一个关联矩阵.超图关联矩阵的每行代表一个超边，每列代表一个顶点(反之亦可).如果某个超边包含某个顶点，则在该超边所在行和顶点所在列交点处的数值为1，否则为0.和图的邻接矩阵不同的是，超图的关联矩阵一般情况下不是对称矩阵，并且大多数情况下都不是方阵.文献[11]提到可以对统计图表的样本和属性分别进行相关性分析.如图2所示，可以对超图关联矩阵的行向量和列向量分别两两相关性得到超边关系矩阵和顶点关系矩阵.

图1　超图海塞图可视化示意图

图2　矩阵表示

2.2可视表达

如图3所示，矩阵可视化包括3个矩阵、统计图和交互细节的展示.这3个矩阵分别是图2(a)中标出的超图关联矩阵、超边关系矩阵和顶点关系矩阵.可视化布局要保证超图关联矩阵的行和超边关系矩阵的行对齐，超图关联矩阵的列和顶点关系矩阵的列对齐.如果3个矩阵数值相差较大，使用不同的颜色库编码这3个矩阵数值.超图关联矩阵是1个二值矩阵，它展示超边和顶点之间的包含从属关系.超边关系矩阵描述的是超边之间的关系，根据颜色编码其数值大小，颜色越深代表相应超边之间的相似性越高.顶点关系矩阵描述的是顶点之间的关系.根据颜色来编码其数值大小，颜色越深代表相应顶点之间的常见性越高.超边关系矩阵和顶点关系矩阵都是对称矩阵，可以使用现有的重排算法对其进行矩阵重排[11].

图3　超图矩阵可视化示意图

2.3交互设计

超图矩阵可视化的交互主要包括概览加细节的自顶向下的交互方式，具体如下：

1)对超图关联矩阵的元素进行交互(如图3(b)、(d)交互2).超图关联矩阵高亮出该元素所关联的超边(行)和顶点(列)，并且超边关系矩阵和顶点关系矩阵也相应的高亮出相应的行和列，并且细节视图显示关注的超边和顶点信息.

2)对超边关系矩阵上元素进行交互(如图3(b)、(d)交互3).超边关系矩阵高亮出该元素所关联的行和列，超图关联矩阵中也高亮出相应的两个超边行并且细节视图显示两个超边的详细信息.

3)对顶点关系矩阵的元素进行交互(如图3(b)、(d)交互1).顶点关系矩阵高亮出该元素所关联的行和列，超图关联矩阵中也高亮出相应的两个顶点列并且细节视图显示两个顶点的信息.

4)矩阵重排交互.如图3(a)、(b)选择交互选项中的矩阵重排选项，可以分别对超边关系矩阵和顶点关系矩阵用不同的算法完成重排，超图关联矩阵的行和列会相应地同步重排.

5)统计图交互.如图3(c)选择交互选项中的统计图选项，可以分别对统计超边和顶点并且统计图会随着超图关联矩阵的重排而同步变化.

3案例分析

文献[1]介绍从Medline在线数据库上挖掘多元关系的方法，并给出关于肺癌的挖掘结果.结果包含168个三元关系，包括疾病、器官、药物、化学物质和路径等生物实体之间的关联，并且每个关系都带有权重.如果把每个三元关系当做一个超边，那么这个的挖掘结果就是一个关于肺癌的超图数据.本文对该数据进行如下可视分析：

1)为了对这些数据中的重点关系进行分析，本文过滤出了30个最重要的关系.

2)如图4(a)所示，首先使用矩阵可视化从宏观上对其进行展示.我们可以发现经过重排的超边关系矩阵和顶点关系矩阵中均存在3个明显分块.如图4(a)、(c)所示，通过对超图关联矩阵中的元素mlh1+msh2+p53: mlh1(mlh1，msh2和p53均为生物实体，mlh1+msh2+p53为三元关系，下文类似)进行交互以及统计图分析，发现顶点mlh1在这个超图中占据着比较重要的位置.

3)接着使用海塞图对数据进行可视化.如图4(a)、(b)对关键顶点mlh1以及5(d)多元关系mlh1+msh2+p53的交互，可以发现mlh1所关联的关系网络占据半个超图网络，mlh1+msh2+p53包含不出现在新关系层中的关键顶点p53等.

文献[12]将多元关系抽象为顶点，对异构够的顶点数据进行整体力引导，将顶点分散到整个布局平面上减少交叉重叠.它还通过一系列交互操作探索骨生物数据之间的直接和潜在关系.与其利用顶点链接法表示超图的镜像点探索方式相对比，本文能够通过不断的交互和可视感知，用户对超图数据中的各种关系有一个清晰全面的认识.实验结果证明海塞图和矩阵方法相结合的方法不但挖掘出更多生物实体之间的关联，而且可以发现其中的关键顶点.因此该方法可以很好地帮助生物学家分析这些关系，并对假设进行直观的检验.

4总结与展望

本文对表达多元关系的超图数据可视化和分析进行探索.但是随着超图规模的增加，视觉复杂度和易读性较差问题是面临的挑战.超图的应用领域广泛，如何赋予超图在应用领域的实际意义也是一个值得进一步研究的问题.无论是实体—数据关系的变换还是映射方式，或者结点—超边的布局算法，亦或者是超图的图简化算法和交互，以及超图数据的可视分析都是将来超图的研究方向.将来的工作中本文作者将面向我国的发展需求，提出在此方面继续开展深入研究.通过提供有效的大规模超图数据可视化方法，能够面向领域应用提供强大的可视分析工具，提高人民对数据的理解和分析能力，对相关科学研究、工程实践和社会生活都有积极的意义.

参考文献

[1]MUKHOPADHYAY S, PALAKAL M, MADDU K. Multi-way association extraction and visualization from biological text documents using hyper-graphs: applications to genetic association studies for diseases[J]. Artificial intelligence in medicine,2010,49(3):145-154.

[2]范伟,李晓明.物联网数据特性对建模和数据挖掘的挑战[J].中国计算机学会通讯,2010,6(9):38-43.

[3]BERGE C. Hypergraphs [M]. Amsterdam: North Holland,1989:1-2.

[4]KAUFAMNN M, KREVELD M V, SPECKMANN B. Subdivision Drawings of Hypergraphs[M]// Graph Drawing. Berlin: Springer Berlin Heidelberg,2008:396-407.

[5]BRANDES U, CORNELSEN S, PAMPEL B, et al. Path-based Supports for Hypergraphs [J]. Journal of Discrete Algorithms,2012,14:248-261.

[6]JUNGHANS M.Visualization of Hyperedges in Fixed Graph Layouts[D].Cottbus: Brandenburg University of Technology Cottbus,2008:29-54.

[7]ALPER B, RICHE N H, RAMOS G, et al. Design study of linesets, a novel set visualization technique[J]. Visualization and Computer Graphics, IEEE Transactions on,2011,17(12):2259-2267.

[8]GANTER B, WILLE R. Formal Concept Analysis：Mathematical Foundations[M]. Berlin: Springer,1999:1-10.

[9]CRAMPES M, OLIVEIRA-KUMAR D, RANEZ S, et al. Visualizing social photos on a hasse diagram for eliciting relations and indexing new photos[J]. Visualization and Computer Graphics, IEEE Transactions on,2009,15(6):985-992.

[10]SIMON T. Hasse diagram of the 2008 Olympic medal table [EB/OL]. [2015-12-04]. http://tartarus.org/simon/2008-olympics-hasse/.

[11]CHEN C H.Generalized association plots: information visualization via iteratively generated correlation matrices [J]. Statistica Sinica,2002,12(1):7-29.

[12]夏菁,刘真,胡越琦,等.基于超图的骨生物数据可视化[J].计算机辅助设计与图形学学报,2011,23(12):2040-2045.

DOI：10.13954/j.cnki.hdu.2016.03.012

收稿日期：2016-02-19

基金项目：浙江省自然科学基金资助项目(LQ12F02003)

作者简介：刘真(1977-)，女，山东泰安人，讲师，信息可视化与可视分析.

中图分类号：TP391

文献标识码：A

文章编号：1001-9146(2016)03-0057-06

Visualizing and Analyzing Multivariate Data Relationship Based on Hypergraph

LIU Zhen, ZHOU Wenhui

(SchoolofComputer,HangzhouDianziUniversity,HangzhouZhejiang310018,China)

Abstract：The vigorous development of social network, internet of things, relational database and biomedical application field has brought huge amounts of data, which has complex relationship with each other. Traditional information visualization can’t express these complex relationships through binary relation graph. More and more research has found that multi-relational hypergraph expression can mine information hidden in the inherent relation and model better. For multivariate entity relationship, this paper presents mainly two hypergraph visualization methods: Hasse diagram and matrix. We construct and visualize hierarchical Hasse diagram based on intersection closure semi lattice of hypergraph. Moreover, we extend hypergraph incidence matrix to hyperedge relation matrix and node relation matrix to visualize various relations in a moderate size hypergraph. Finally experiment results demonstrate that our method is efficient through analyzing the multivariate relation of the lung cancer hypergraph data from Medline online database.

Key words：hypergraph; intersection closure semi lattice; Hasse diagram; incidence matrix