FC-InfoNet-Warehouse:信息网络数据仓库建模及实现

李夷洁，李川

（四川大学计算机学院，成都　610065）

FC-InfoNet-Warehouse:信息网络数据仓库建模及实现

李夷洁，李川

（四川大学计算机学院，成都610065）

数据仓库；信息网络数据仓库模型；信息维；拓扑维

0　引言

从社交网络到基因结构，越来越多的数据结构是以图结构为基础，人们试图从图数据结构中挖掘出比单一数据值更有价值的网络结构信息。例如在传统的销售主题中人们除了关心某种物品的销售量，开始更加关心销售网络，例如销售额最大的一个商品销售网络，了解这个销售网络，商家可以针对这个销售网络进行一些促销活动来实现利益最大化。信息网络是Jiawei Han，Philip S Yu等在EDBT2009和SIGMOD2010上正式提出并倡导的一种处理图数据结构的新型概念[1-2]，旨在对现实空间中的网络进行进一步的一致性抽象建模，得到一个更加一般具有普适性的模型。近年来关于信息网络的研究主要集中于拓扑维/信息维上卷下钻及其他应用型方面，例如文献[6]主要研究了信息网络中基于拓扑维异步上卷的单位间节点发现，文献[7]主要研究了信息网络中的子图发现，文献[8]主要研究了信息网络中相似性度量。这些研究方向主要集中于应用层，关于底层存储方面鲜有涉及。但是存储设计是基础，如果底层存储设计优秀，读取方便快捷，可以更高效地进行整个研究过程。本文针对信息网络进行研究，设计并构建了信息网络数据仓库模型。

传统数据仓库是面向主题的、集成的、面向数据分析处理，主要用于企业决策分析[3]。传统数据仓库所面向的主题主要是单一数据值，信息网络数据仓库结合了信息网络与数据仓库的优势，面向的主题主要是图度量方面。传统数据仓库对此场景不再适用[9-10]。

信息网络数据仓库是近年来新兴的概念，相关的研究设计鲜有涉及。文献[5]提出信息网络数据仓库模型但未给出数据仓库的具体实现方法及模型的一般实施性方案。文献[4]提出一种信息网络数据仓库模型，为了与本文所提出的信息网络数据仓库模型区分，笔者根据文献[4]提出的信息网络数据仓库模型的特点，其核心为边事实表和节点事实表，将其命名为EN信息网络数据仓库模型（Edge-Node），而根据本文所提模型结构特点将本文所提模型命名为FC信息网络数据仓库模型(Frame-Clique)，仅在本文中作以区分。

本文提出FC信息网络数据仓库模型，该模型结合传统数据仓库与信息网络优势，旨在解决信息网络数据源存储问题，提供一个一般性的信息网络数据仓库模型。该模型的一般性体现在，给定任何信息维、拓扑维、主题度量的场景，用户都可以快捷设计和构建特定的符合用户需求的信息网络数据仓库。另外，本文所提模型支持多主题建模，易于完成多主题的相互切换，具备灵活性及可扩展性，可以为信息网络上层应用研究提供高效快捷的数据读取与存储支持，提高研究效率，节省时间。

1　FC信息网络数据仓库模型

本文将传统数据仓库与信息网络相结合，期望得到一个能够处理图数据结构的一般性数据仓库模型。与传统数据仓库模型类似，本文所提出的FC信息网络数据仓库模型中所存储的也是面向主题的、集成的、不可更新、且随时间变化而不断变化的数据[11]。该模型结构包含事实表和维表，面向的主题是图。其中事实表分别为框架事实表（Frame Fact Table）和团事实表（Clique Fact Table）。框架事实表存储该模型子图的主题，团事实表存储与该主题相关的节点。但在实际存储中，因为传统关系数据库的特性，团事实表将会被拆分成两个或多个表，其中一部分表存储与主题相关的节点，另外一部分表存储主题与节点之间的联系。这种拆分需要针对不同的数据结构及需求具体确定。维表则分为存储信息维属性的信息维表，存储拓扑维属性的拓扑维表。该模型能较完整地保存信息网络研究中所需信息，并且在查询效率及存储空间方面均优于其他信息网络数据仓库模型。具体定义见定义1。结构如图1 所示。

定义1（FC信息网络数据仓库模型）设双核星型信息网络数据仓库模型是一个四元组，信息维表IDT（Information Dimensions Table），拓扑维表TDT（Topological Dimensions Table），框架事实表FFT（Frame Fact Table）以及团事实表CFT（Clique Fact Table）。其中FFT 和CFT通过Topic_id连接，即通过主题Id连接，每个主题确定一个围绕该主题的子图。IDT与FFT通过IDT的唯一标识ID相连接，根据该主题的数据结构特征确定该主题框架由哪几种信息维属性组成。CFT与TDT通过TDT的唯一标识ID连接，根据该子图内节点的特征选定该子图内节点的拓扑维属性集合。

该模型具有如下优点：

（1）该模型解决了传统数据仓库无法对图数据结构建模的问题。提供了针对图数据结构的面向主题的数据组织模型。

（2）该模型具有一般性，给定原始数据集，通过分析主题，抽取信息维，拓扑维即可高效建立以图结构为基础的信息网络数据仓库模型。

（3）该模型可以很容易地在关系数据库上实施建立。

（4）该模型以主题为基本框架建立，具备很强的灵活性和可扩展性。用户对于主题及各个表之间的关系一目了然，极大地简化了查询分析过程。

图1　信息网络数据仓库模型

2　FC信息网络数据仓库模型相应关系表生成算法

在整个信息网络算法应用研究中，存储是基础。如何有效存储原始数据，在后续的算法实施中更加高效简洁地读取数据至关重要。根据本文所提模型，用户可以根据特定的需求抽象出主题及与主题相关的子图，通过对原始数据集结构的特点分析抽取出信息维，拓扑维。通过以下算法执行，即可简便的在关系数据库上建立FC信息网络数据仓库模型，为后续的各种图结构分析提供数据存储基础。

算法1给出在确定主题及信息维，拓扑维的条件下，通过对原始数据集的分析，构建信息网络数据仓库模型的过程。本文以xml文件为例，xml文件是以记录为单位，每条记录包含多种属性。构建相应的信息网络数据仓库时，根据主题的不同，抽取不同的子图。以记录为单位解析该xml文件，根据前期对xml文件数据结构的分析，第2，4行完成信息维，拓扑维的抽取。第3，5行完成相应维度的表插入过程。第6，7行完成topic及interest的抽取，第7，9行根据3，4行插入信息维拓扑维返回得到的相应维度的id，完成topic及interest的数据库表插入。至此，完成整个抽取构建过程。

输入：信息网络原始数据source.xml

输出：FCInfoNet-WareHouse相应关系表

3　实验

本文通过对ACM以及DBLP数据集特点的分析，进行了信息维，拓扑维及事实表抽取，设计并构建了基于ACM及DBLP数据集的FN信息网络数据仓库模型，EN信息网络数据仓库模型及ACM数据集范关系模型。基于构建完成的信息网络数据仓库模型，本文在ACM数据集上进行了时间效率方面的分析实验，在DBLP数据集上进行了存储空间方面的分析实验。

3.1查询效率试验

在查询效率方面，本文实验共进行30次，对查询时间进行平均值求取。在实验数据选取方面，首先分析数据，得到论文数量分布。分别使用论文数目最多的三年数据，论文数目平均值附近的三年数据，以及论文数目最少的三年数据作为查询条件进行实验。可以看出在实验效果方面，本文所提模型均优于其他两个模型，从而证明本文所提模型的有效性。

图3代表查询某年的所有作者的合作网络。从图中曲线可以看出，FC信息网络数据仓库模型，EN信息网络数据仓库模型均优于VRM的查询效率。而本文所提出的FC信息网络数据仓库模型在论文数较多的情况下，更加优于文献4所提出的EN信息网络数据仓库模型

3.2存储空间实验

本文使用DBLP数据集进行空间存储方面的实验。图5 给出不同论文数目时，整个模型所占空间对比图。从图中可以看出，在空间存储方面，随着论文数目的增长，本文提出的模型所占存储空间的增长趋势明显缓慢于文献4所提模型。图4 表示随着论文数目增长，EN模型和FC模型中存储关系记录数增长情况。其中EN模型存储的是作者与作者之间的合作关系，而本文是以论文为连接点，存储的是论文与作者之间的合作关系。虽然存储方式不一样，但是后期读取数据可以达到同样的效果。从图中可以看出，本文所提出模型的关系数增长明显缓慢于文献4所提模型。所以本文所提出模型在存储空间方面占据优势。

以上两组实验表明，本文所提出模型在查询效率方面及存储空间方面均优于文献4所提信息网络数据仓库模型及传统的泛关系表模型。

4　结语

本文提出FC信息网络数据仓库模型，并给出该模型的形式化概念及一般性实现算法，以期能够结合信息网络与数据仓库的优势，解决原始数据集结构内容混乱导致数据分析过程效率低的问题，具有查询灵活、高效、存储空间小等优点。基于本文提出的FC信息网络数据仓库模型，可以方便的对现实生活中的各种信息网络数据进行建模及构建实施。

图2　按年份论文数量分布

图3　按年份查询合作者网络时间对比

图4　核心边数量对比

图5　存储空间对比

[1]Han Jiawei,Yan Xifeng,Yu P S.Scalable OLAP and Miningof Information Network[C].Proceedings of the 12th International Conference on Extending Database Technology:Advances in Database Technology(EDBT'09).New York,NY,USA:ACM,2009:1159.

[2]Han Jiawei,Sun Yizhou,Yu P S,et al.Mining Knowledgefrom Databases:an Information Network Analysis Approach[C].Proceedings of the 2010International Conference on Management of Data(SIGMOD'10).New York,NY,USA:ACM,2010:1251-1252.

[3]王珊,李翠平,李盛恩等.数据仓库与数据分析教程[M].高等教育出版社,2012:6-13.

[4]聂章艳,李川,唐常杰,等.面向OLGP的多维信息网络数据仓库模型设计[J].计算机科学与探索,2014,8(1):51-60.

[5]Li C,Yu P S,Zhao L,et al.Infonetolaper:Integrating Infonetwarehouse and Infonetcube with Infonetolap[C].Proc of VLDB.2011,4.

[6]杨尚乾,李川,唐常杰,等.基于拓扑维上卷的空航信息网络枢纽节点发现[J].华中科技大学学报:自然科学版,2012(S1):280-283.

[7]Gupta M,Gao J,Yan X,et al.Top-k Interesting Subgraph Discovery in Information Networks[C].Data Engineering(ICDE),2014 IEEE 30th International Conference on.IEEE,2014:820-831.

[8]Pei-xiang Zhao,Jia-wei Han,Yi-zhou Sun.P-Rank:A Comprehensive Structural Similarity Measure over Information Networks.Proc. 2009 ACM Conf.on Information and Knowledge Management(CIKM'09),Hong Kong,China,Nov.2009.

[9]Jia-wei Han,Yi-zhou Sun,etc.Minning Heterogeneous Information Networks.Tutorial at the 2010 ACM SIGKDD Conf.on Knowledge Discovery and Data Mining(KDD'10),Washington,D.C.,July 2010.

[10]Jim Gray,SurajitChaudhuri,Adam Bosworth,Andrew Layman,Don Reichart,MuraliVenkatrao,Frank Pellow,Hamid Pirahesh.Data cube:A Relational Aggregation Operator Generalizing Group-by,Cross-Tab,and Sub Totals.Data Min.Knowl.Discov.,1(1):29-53, 1997.

[11]Inmon W H.Building the Data Warehouse[M].John Wiley&Sons,2005.

Information Network;Database Warehouse;Information Network Warehouse;Information Dimension;Topological Dimension

FC-InfoNet-Warehouse：Modeling and Implementation of Information Network Warehouse

LI Yi-jie，Li Chuan
(College of Computer Science,Sichuan University,Chengdu 610065)

李夷洁（1991-），女，河南新乡人，硕士，研究方向为信息网络数据仓库

2015-12-10

2015-12-30

信息网络是一种对复杂网络进行高度一致性抽象、用于处理图数据的新型概念。为了更加灵活高效地读取数据，提升研究效率，提出一种以图为主题结合信息网络与数据仓库优势的FC信息网络数据仓库模型。实验表明该模型在查询效率，存储空间及查询灵活性等方面较前人所提EN信息网络数据仓库模型均具有明显优势。

李川（1977-），男，河南郑州人，博士，副教授，研究方向为数据库、数据挖掘

The information network is a new concept and model aims to modeling and abstracting complex network in a unified way.Presents the information network data warehouse model to combine the information network and the advantages of data warehouse,the theme of this model is graph,it is named FC-information network data warehouse model.The experimental results show that the model in the query time,storage space and flexible and efficient query than previous proposed EN-information network data warehouse model has obvious advantages.