（大唐国际发电股份有限公司北京高井热电厂 北京 100041）
摘要：随着互联网的快速发展和计算机应用的不断增加，大量的图数据特别是社会网络数据不断生成。多维信息网络已经成为了表示这些图数据的通用方式。但是在多维信息网络中，节点的类型多种多样，节点的属性也不尽相同。如何对于多维信息网络数据进行多角度多粒度的分析，挖掘其中的隐藏信息，成为了我们关注的焦点。图联机分析处理技术（GraphOLAP）可以对图数据进行快速的联机分析以及查询操作。借助于GraphOLAP的现有成果，针对多维信息网络的特点，我们提出了新的数据立方体框架：引入主节点的概念来指导元路径的生成，通过元路径指导网络的上卷下钻，提出属性转化和同质转化来丰富OLAP操作，讨论了优化的物化策略。最后我们使用了并行计算框架Spark来实现算法，通过多个数据集验证了框架的有效性和高效性。
关键词：GraphOLAP；数据立方体；元路径；Spark
1.背景介绍
1.1近年来随着社交网络，生物网络以及化合物网络等领域的不断发展，出现了大量的多属性图数据。研究如何对图数据进行多层次多角度的分析有着重要的意义。这些网络如DBLP合作网络，社交网络FACEBOOK，IMDB电影合作网络等，其中蕴含大量的实体信息以及实体之间的关联信息，深层次挖掘此类信息是非常有必要的。实体类型和联系的多元化是分析和挖掘此类信息网络的难点。联机分析处理技术（OLAP）能够提供用户从不同维度，不同粒度观察对象的视图，是数据仓库和数据挖掘领域的核心技术之一，近年来得到了广泛的研究应用。但是OLAP基于的传统数据立方体是同一种实体类型的多维数据模型，不能有效契合图数据分析的需求。图联机分析处理技术（GraphOLAP）结合了复杂网络分析与联机分析处理技术，将数据仓库中专门用于分析多维数据的联机分析处理技术引入到复杂网络分析当中，用来解决复杂网络中的多维度多角度分析问题，从而展示不同层次和不同粒度上的网络结构和特性。在传统信息模型中，信息存储为事实表和维度表。事实表中包含所有实体以及之间的关系，维度表中包含数据的多维属性。通过立方体来指导OLAP的维度操作，聚集函数来描述不同维度聚集时的聚集方式，度量来描述不同维度下的分析结果。
1.2对于多属性图数据来说，数据与数据之间存在关联，这些关联蕴含着许多隐藏信息有待挖掘与分析。但是传统的数据是记录的形式，数据之间没有关联。利用传统OLAP分析会丢掉这些关联关系，不能对图进行充分有效的挖掘与分析。对于多属性图的分析，除了传统图分析方法如最短路径，中介行，模式匹配等，OLAP查询来做信息发现和决策制定也有很大的发挥空间。这里根据用户可能感兴趣的点举几个简单的例子：1：获取点属性或边属性信息。这些查询往往能够通过对点属性或边属性的简单查询得到。如“用户群体中有多少中国人”或者是“电影都有哪些类型”。2：获取点和边的属性组合之后的聚集信息，这些查询需要将实体节点按照某一维度进行聚集操作之后得到结果。如“有多少男人喜欢看喜剧片”“演员国籍与电影类别之间的网络结构是什么样子的”3：查询特定实体关系的网络属性信息。这些查询需要合并实体间的关系，形成新的实体关系以及新网络。
期刊文章分类查询,尽在期刊图书馆如“男人喜欢的电影是由哪个国家的演员参演的”对于第一种查询，可以直接在节点表中进行查询，得到节点的维度属性。第二张查询需要将原图中的一些节点按照需要进行聚集操作得到新的聚集网络。第三种查询关注的是不同实体间的相互关系，根据异质网络元路径聚集进一步得到新的实体关系。传统的基于RDB的OLAP系统已经难以满足这些查询需求，除了查询1中的实体类型查询可以基于节点的维度表进行查询，其他的查询操作都要经过多表连接操作。当数据量很大时，数据库的多表连接经常会成为数据库计算的瓶颈。而且传统的数据立方体也不能很好的表现出图的结构以及图的复杂网络属性。因此设计适合大规模多维信息网络的立方体，建立多维信息网络的OLAP操作是十分有必要的。
1.3随着社交网络的兴起，网络数据的规模也在不断增加。传统的集中式计算已经不能满足需求，引入并行化计算框架是非常有意义的。目前，常用的并行计算框架有Hadoop，Spark，并行图计算框架有HAMA，GraphX，GraphLab等。这些并行图计算框架对于图类型数据的迭代操作有很好的优化，能有效的计算图的相关结构特征如pagerank，shortestpath，bipartitematching，semi-clustering等。但是对于多维信息网络的OLAP操作会导致节点数量，属性以及节点间的联系发生改变，这种改变会进一步导致网络结构改变以及网络类型改变。现有的图计算框架更适用于图遍历的迭代操作和图分隔的优化操作，对于图中节点类型以及拓扑结构发生重大变化的支持并不是很好。传统的并行计算框架Hadoop和Spark虽然不是专门为了图计算设计，但是通过建立合适的图立方体模型，也可以进行图的挖掘分析。所以我们选用Spark来完成对于立方体的相关操作。在这些需求的引导下，我们提出了一种新的数据立方体模型，引入了主节点的概念，融入异质网络特性，并基于新的数据立方体模型赋予传统的上卷下钻新的含义。针对于新的模型，我们设计了更多新的OLAP操作，为丰富查询提供了模型上的支持。为了挖掘图中的隐藏信息，我们设计了带多维层次聚类算法来进行群体划分和特征分析。为了提高查询效率，我们设计了优化的物化策略。模型是用并行化计算框架Spark完成的，支持大规模多维信息网络的分析处理。通过多个真实网络数据集实验，验证了模型的有效性和高效性。
2优化物化策略
在实体立方体上的上卷下钻操作需要将网络根据关系元路径重组网络节点，计算的复杂度很高。对于大规模网络这些操作是十分耗时的，所以我们提出了下面的一些优化算法。操作优化：二元关系元路径聚集操作将网络中的多个实体属性在二元关系元路径P𝑇1，𝑇𝑛，list=𝑇1→⋯→𝑇𝑖→⋯→𝑇𝑛的指导下，形成以起点和终点类型构成的网络。我们可以将相邻的节点做join操作，逐步合并中间路径节点，最终得到𝑇1→𝑇𝑛的网络。因此一般聚集网络的二元关系元路径不会太长，否则得到的图就没有分析的意义。二元关系元路径的聚集网络的计算可以表示𝑁′=agg2meta（N，𝑇1，𝑇𝑛，list），其中N表示多维信息网络，𝑇1表示起点类型，𝑇𝑛表示终点类型，list表示二元关系元路径序列。𝑁′为二元关系元路径聚集网络，生成算法见Algorithm1。遍历的循环可以使用spark的map函数生成对应边的RDD，利用RDD的join函数对Algorithm1进行并行。对于n元关系元路径的聚集网络计算，根据定理1可知n元关系元路径可以由n-1个二元关系元路径拼接而成，故二元关系元路径指导的网络聚集操作可以转换成n-1个二元关系元路径网络指导的聚集操作，最后将n-1个聚集网络合并。实体立方体物化：立方体的物化策略一共有三种：不物化，部分物化和完全物化。不物化策略是指在每一次的计算过程中，都直接生成所需网络再计算结果，这种策略不需要耗费很多内存空间，但是当数据量很大的时候，每一步的计算时间会显著增加，不适合大数据量的操作。完全物化策略是指在计算初期，就将数据立方体的所有网络计算出来并保存。这种方法在数据立方体的维度较多的情况下，计算初期需要花费大量时间并且占用大量的内存。部分物化策略是在计算初期，按照一定方案将数据立方体的部分网络计算出来并保存，这种方式兼顾了时间和空间效率，因此我们选择这种物化策略。
结束语
本文针对现有GraphOLAP对异质网络分析能力不足的问题，引入关系元路径的概念，提出了主节点引导元路径聚集并且设计了星型数据模型以便于在异质网络中引入关系元路径，在此基础上提出了同质转换操作和属性转换操作以丰富模型操作。针对于模型提出了优先物化二元关系元路径的物化策略和维度聚集时的维度编码算法来进行join操作的优化。最后我们引入了Spark并行计算框架，使得模型处理大规模的图数据的能力大大加强。通过真实数据与模拟数据的实验，验证了该模型框架的有效性与高效性。
参考文献：
[1]王永刚.虚拟专用网络技术在计算机网络信息安全中的应用[J].电子测试，2015年10月
论文作者:王雪飞
论文发表刊物:《电力设备》2017年第35期
论文发表时间:2018/4/28
标签：多维论文; 网络论文; 数据论文; 立方体论文; 路径论文; 操作论文; 节点论文; 《电力设备》2017年第35期论文;