用户需求下信息网络拓扑维上卷模型研究范文

摘要：

随着信息网络的发展，信息网络拓扑维上卷逐渐成为本领域的一个热点，同时它的应用价值也随之提升。对给定节点不上卷，其他节点上卷到指定层次的方法来满足用户的特定需求。提出满足用户需求的信息网络拓扑维上卷模型。主要贡献有：（1）首次提出有效上卷代价的概念，（2）首次实现用户的特定需求上卷，（3）设计信息网络的拓扑维上卷算法。实验证明该算法能够满足用户的特定需求，实现指定拓扑维上卷操作，具有很强的实用价值。

关键词：

信息网络；特定需求；拓扑维；上卷

引言

信息网络在日常生活中随处可见，小到数十个节点组成的科研合作者网络，大到百亿级节点的社交网络，信息网络反映现实生活中各种类型的关系，如今对信息网络的研究正日益成为一种热点和趋势。根据用户指定的需求对信息网络进行上卷操作，则可以挖掘出某些节点与其他社会团体之间的联系，有助于对这些节点进行有目的的推送或者其他操作。信息网络（InfoNetwork）是JiaweiHan和PhilipSYu等在EDBT2009和SIGMOD2010上正式提出和倡导的新概念[1-2]。它是对现实生活中问题和数据一般性的抽象，在日常生活中可以接触一些信息网络的实例，例如：蛋白质网络[3-4]、交通网络[5]、通信网络[6]、合作者网络[7]、社交网络[7-8]等，这些信息网络的规模有大有小。目前对信息网络的主要研究正越来越成为一个热门方向，主要涉及到的领域有：信息网络的可视化、在线分析处理、数据立方的构建等。例如：文献[9]提出了组件式信息网络可视化框架（InformationNetworksVi-sualizationFramework，INVF），文献[10][11]主要对信息网络数据集进行面向主题、多维、多层次的在线分析处理（OnlineAnalyticalProcessing，OLAP），在传统OLAP技术无法满足上述处理情况下，提出了面向信息网络的在线图处理（OnlineGraphicProcessing，OLGP）模型，文献[12]主要是从信息网络的底层数据库实现的角度提出了面向主题的、集成的信息网络数据组织方案，以及具有一般性的多维信息网络数据仓库模型，与本文具有较强相关性的是文献[13]和[14]，其中文献[13]的主要工作是信息网络枢纽节点的发现，提出基于拓扑维异步上卷的单位间枢纽点发现框架和算法，优化了传统算法的时间和空间复杂度较高的弱点，文献[14]是利用信息网络的拓扑维异步上卷提出基于额外窗口（AW）的信息网络Top-k接近中心度核心节点挖掘算法。前人的工作主要存在着以下问题：①主要偏向于拓扑维上卷的应用，没有涉及算法的设计与实现。在部分工作中只是简单进行暴力的剪枝操作，很多数据丢失。②只是对信息网络的出度和入度较大的节点进行上卷。只考虑了某些中心节点或者枢纽节点，没有对整个信息网络加以深入研究。③不能根据用户的特定需求进行有目的性的上卷操作，扩展性较差。只根据拓扑维进行上卷操作，而没有对用户的需求进行分析。基于前人工作的不足之处，本文的主要贡献有：①根据信息网络拓扑维上卷的性质，首次提出了有效上卷代价概念。对于不同规模的数据集，根据其拓扑结构，以及有效上卷代价可以预估其算法执行时间，提出假设。②设计并实现了基于信息网络拓扑维的上卷算法，并对算法的性能进行了优化。③根据用户特定需求有目的性的拓扑维上卷即可以对单一节点进行上卷，也可以对特定的模型进行上卷，满足用户的多重需求。

1问题定义

1.1预备知识

定义1信息网络（InfoNetwork）信息网络是基于图定义，假设G=<V，E>表示一个图结构，其中V=<V1，V2，…，Vn>代表图中所有的节点集合，E=<E1，E2，…，En>代表图中所有的边集合。信息网络分为同构信息网络和异构信息网络，节点V的类型相同并且边E代表单一属性的为同构信息网络。节点V的类型不同并且E代表不同属性的为异构信息网络。在日常生活中，信息网络随处可见，如图1所示的是一个异构的作战信息网络。每个节点代表不同的类型，有作战人员、电脑、手枪、坦克，而且节点与节点之间的边有各自不同的属性。而图2的合作者网络则是一个典型的同构信息网络，每个节点代表一个作者，而作者-作者之间的边代表者两个作者合作发表过论文。本文采用的是同构信息网络进行试验。定义2信息维（InformationDimension）设图数据库中待分析图结构为G（V，E）=G（V，θ（ID））。其中，V是图中点的集合，E表示边的集合，函数θ为图G的边信息决定函数。设变量ID={I1，I2，…，Im}是OLGP中待考察的维度集合，其中i=1，2，…，m。这m个信息属性构成的维度集合只能决定图的边集，不能改变图的拓扑结构，称ID为信息维集合。通过图3可以发现在对（1）与（2）进行信息聚集操作时，信息网络的拓扑结构并未发生改变。定义3拓扑维（TopologicalDimension）设变量TD={T1，T2，…，Tn}是刻画OLGP中图中心度量拓扑结构的一个集合。一个图可表示为G（V，E）=G（准（TD），δ（TD）），其中函数准为点拓扑决定函数，函数δ为边拓扑决定函数。这n个拓扑属性构成的拓扑维决定图的点集合和边集合，从而决定图的拓扑结构，称TD为拓扑维集合。通过图4发现在对节点进行上卷操作时，在信息网络中形成新的节点和边，从而引起信息网络的拓扑定义3有效上卷代价（Effectivecostroll-up）对信息网络G=<V，E>进行上卷操作时，面临的一个怎么进行节点的聚集和生成所需上卷后节点的问题，则定义有效上卷代价p。p=∑|v'|/∑|v|（1）其中v∈V为信息网络中所有的节点个数，v'为满足用户上卷到指定维度后的节点数，p越大则进行拓扑维上卷操作所消耗的时间越大。

1.2问题定义

对信息网络进行特定需求的上卷操作在对恐怖组织进行有效制裁、校企合作、进出口公司与合作国家的关系趋势预测等方面都具有极其重要的意义，对于用户指定的上卷层次，需要解决的问题：问题1.对特定节点不上卷，其他节点上卷；问题2.对特定社团不上卷，其他节点上卷；问题3.对特定模式不上卷，其他节点上卷。本文主要解决问题1，下面以制裁恐怖组织为例，表1假设为每个成员的个人信息，每个人共4个维度，每个维度的取值代表该成员上卷到本维度的值，如：将恐怖组织成员谢里夫上卷到维度3，则该成员上卷后的取值为C3。图5为情报机构获取的恐怖组织关系网中部分成员之间的合作关系。当需要找到本•拉登与上卷层级为3（假定为公司名）的联系时，则需要对信息网络图中除本拉登以外的其他所有节点进行上卷，找出它们之间的关系，如图6所示。通过它们之间的联系，反恐部门可以对这些公司进行经济等方面的制裁。

2拓扑维异步算法

2.1信息网络拓扑维上卷框架

图7给出了信息网络拓扑维上卷的框架，由信息网络拓扑图和节点信息维度的映射，得到基于用户特定需求的拓扑维上卷后的信息网络拓扑图。

2.2信息网络拓扑维上卷算法设计

基于对信息网络拓扑维上卷框架的理解，本文设计了信息网络拓扑维上卷算法：算法1实现了对信息网络中用户关注的节点不进行上卷操作，其他所有节点均上卷到指定的维度。在现实生活中的信息网络（如：合作者网络），当查看某个节点与其他机构之间的联系时，根据文献[15]六度空间理论，可能只需要查看该节点在信息网络中第n跳范围内的所有机构而非查看整个信息网络，n越大所需的时间越多。本文设置n=3。算法2对算法1做出了改进：

3实验

3.1数据集

本文在DBLP数据集上进行实验，表1是数据集的简单概述，根据数据集的具体情况，随机生成了拓扑的维度，表2详细描述了预处理后的数据集。DBLP合作网络，两位作者之间有边则代表两个作者有合作关系。

3.2实验结果

目前国内外针对用户特定需求的信息网络拓扑维上卷的研究尚属空白区，大多数的研究人员都是对整个数据集进行上卷操作，不能满足用户的特点需求。本文主要做了两组试验：（1）信息网络不同维度的上卷操作（2）优化上述操作，指定跳数对于（1），本文根据算法1进行实验，运用文献[16]和文献[17]提到的Java开源JUNG包，绘制的实验结果如图8所示，图中红点为用户特定查询节点，其他颜色的点分别代表数据集中除了查询节点以外其他节点上卷到指定维度的节点集，上卷到各个维度所需时间以及进行不同跳数上卷效果曲线如图9所示。通过图9，发现随着维度的增大进行上卷所需断边以及生产新边的次数就越多，有效上卷代价p就越大，耗时必然越大。由于上卷整个数据集耗时太多，并且在实际生活中某个节点只要相邻的n跳范围内的其他节点具有强关联性。为了优化算法1，本文提出了算法2，具体实验的结果如图10所示，根据实验结果发现当n=3时，上卷所得的结果与遍历整个数据的结果非常的接近，耗时较之提高几个数量级，其中表3是上卷到维度1时不同跳数的耗时比较，证明了算法2的有效性。

4结语

本文主要根据信息网络的拓扑结构，本文首次提出了有效上卷代价的概念并提出了假设，实验室也很好的验证了假设。本文针对用户特定的需求，对某个特定节点不进行上卷，网络中的其他节点均上卷到指定的维度，为此本文设计了信息网络上卷算法，并在根据现实情况以及算法耗时过多的情况优化了算法，能在减少耗时的基础上很好地完成了算法，达到了预定目的。本文目前只是解决了对在节点的层次上进行上卷，进一步的工作主要会集中在对特定社团和特定模式进行上卷，并考虑更为复杂的信息网络中。

参考文献：

[9]李洋涛，李川，吴诗极，等.INVF：面向信息网络的可视化框架与算法[J].计算机科学与探索，2013，7（12）：1104-1114.

[10]李川，赵磊，唐常杰，等.GraphOLAPing的建模、设计与实现[J].软件学报，2011，22（2）:258-268.

[11]徐洪宇，李川，唐常杰.在线图处理：面向信息网络的在线分析处理[J].计算机科学与探索，2012，6（9）:97-110

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

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

[14]曾卫，李川，唐常杰，等.复杂空航信息网络枢纽节点的高效发现[J].华中科技大学学报:自然科学版，2012（S1）:280-283

[16]王柏，吴巍，徐超群，等.复杂网络可视化研究综述[J].计算机科学，2007:17-2.

作者：刘松 李川 单位：四川大学计算机学院