《用户需求下信息网络拓扑维上卷模型研究（精品）.docx》由会员分享，可在线阅读，更多相关《用户需求下信息网络拓扑维上卷模型研究（精品）.docx（8页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、用户需求下信息网络拓扑维上卷模型研究随着信息网络的发展，信息网络拓扑维上卷逐步成为本领域的一个热门，同时它的应用价值也随之提升。对给定节点不上卷，其他节点上卷到指定层次的方法来知足用户的特定需求。提出知足用户需求的信息网络拓扑维上卷模型。主要奉献有：1初次提出有效上卷代价的概念，2初次实现用户的特定需求上卷，3设计信息网络的拓扑维上卷算法。实验证实该算法能够知足用户的特定需求，实现指定拓扑维上卷操作，具有很强的实用价值。关键词：信息网络；特定需求；拓扑维；上卷信息网络在日常生活中随处可见，小到数十个节点组成的科研合作者网络，大到百亿级节点的社交网络，信息网络反映现实生活中各种类型的关系，如今对
2、信息网络的研究正日益成为一种热门和趋势。根据用户指定的需求对信息网络进行上卷操作，则能够挖掘出某些节点与其他社会团体之间的联络，有助于对这些节点进行有目的的推送或者其他操作。信息网络InfoNetwork是JiaweiHan和PhilipSYu等在EDBT2009和SIGMOD2010上正式提出和倡导的新概念1-2。它是对现实生活中问题和数据一般性的抽象，在日常生活中能够接触一些信息网络的实例，例如：蛋白质网络3-4、交通网络5、通信网络6、合作者网络7、社交网络7-8等，这些信息网络的规模有大有小。目前对信息网络的主要研究正越来越成为一个热门方向，主要涉及到的领域有：信息网络的可视化、在线分
3、析处理、数据立方的构建等。例如：文献9提出了组件式信息网络可视化框架InformationNetworksVi-sualizationFramework，INVF，文献1011主要对信息网络数据集进行面向主题、多维、多层次的在线分析处理OnlineAnalyticalProcessing，OLAP，在传统OLAP技术无法知足上述处理情况下，提出了面向信息网络的在线图处理OnlineGraphicProcessing，OLGP模型，文献12主要是从信息网络的底层数据库实现的角度提出了面向主题的、集成的信息网络数据组织方案，以及具有一般性的多维信息网络数据仓库模型，与本文具有较强相关性的是文献13
4、和14，其中文献13的主要工作是信息网络枢纽节点的发现，提出基于拓扑维异步上卷的单位间枢纽点发现框架和算法，优化了传统算法的时间和空间复杂度较高的弱点，文献14是利用信息网络的拓扑维异步上卷提出基于额外窗口AW的信息网络Top-k接近中心度核心节点挖掘算法。前人的工作主要存在着下面问题：主要偏向于拓扑维上卷的应用，没有涉及算法的设计与实现。在部分工作中只是简单进行暴力的剪枝操作，很多数据丢失。只是对信息网络的出度和入度较大的节点进行上卷。只考虑了某些中心节点或者枢纽节点，没有对整个信息网络加以深化研究。不能根据用户的特定需求进行有目的性的上卷操作，扩展性较差。只根据拓扑维进行上卷操作，而没有对
5、用户的需求进行分析。基于前人工作的缺乏之处，本文的主要奉献有：根据信息网络拓扑维上卷的性质，初次提出了有效上卷代价概念。对于不同规模的数据集，根据其拓扑构造，以及有效上卷代价能够预估其算法执行时间，提出假设。设计并实现了基于信息网络拓扑维的上卷算法，并对算法的性能进行了优化。根据用户特定需求有目的性的拓扑维上卷即能够对单一节点进行上卷，可以以对特定的模型进行上卷，知足用户的多重需求。1问题定义1.1预备知识定义1信息网络InfoNetwork信息网络是基于图定义，假设G=V，E表示一个图构造，其中V=V1，V2，Vn代表图中所有的节点集合，E=E1，E2，En代表图中所有的边集合。信息网络分为
6、同构信息网络和异构信息网络，节点V的类型一样并且边E代表单一属性的为同构信息网络。节点V的类型不同并且E代表不同属性的为异构信息网络。在日常生活中，信息网络随处可见，如图1所示的是一个异构的作战信息网络。每个节点代表不同的类型，有作战人员、电脑、手枪、坦克，而且节点与节点之间的边有各自不同的属性。而图2的合作者网络则是一个典型的同构信息网络，每个节点代表一个作者，而作者-作者之间的边代表者两个作者合作发表过论文。本文采用的是同构信息网络进行试验。定义2信息维InformationDimension设图数据库中待分析图构造为GV，E=GV，ID。其中，V是图中点的集合，E表示边的集合，函数为图G
7、的边信息决定函数。设变量ID=I1，I2，Im是OLGP中待考察的维度集合，其中i=1，2，m。这m个信息属性构成的维度集合只能决定图的边集，不能改变图的拓扑构造，称ID为信息维集合。通过图3能够发如今对1与2进行信息聚集操作时，信息网络的拓扑构造并未发生改变。定义3拓扑维TopologicalDimension设变量TD=T1，T2，Tn是刻画OLGP中图中心度量拓扑构造的一个集合。一个图可表示为GV，E=G准TD，TD，其中函数准为点拓扑决定函数，函数为边拓扑决定函数。这n个拓扑属性构成的拓扑维决定图的点集合和边集合，进而决定图的拓扑构造，称TD为拓扑维集合。通过图4发如今对节点进行上卷操
8、作时，在信息网络中构成新的节点和边，进而引起信息网络的拓扑定义3有效上卷代价Effectivecostroll-up对信息网络G=V，E进行上卷操作时，面临的一个怎么进行节点的聚集和生成所需上卷后节点的问题，则定义有效上卷代价p。p=v/v1其中vV为信息网络中所有的节点个数，v为知足用户上卷到指定维度后的节点数，p越大则进行拓扑维上卷操作所消耗的时间越大。1.2问题定义对信息网络进行特定需求的上卷操作在对恐惧组织进行有效制裁、校企合作、进出口公司与合作国家的关系趋势预测等方面都具有极其重要的意义，对于用户指定的上卷层次，需要解决的问题：问题1.对特定节点不上卷，其他节点上卷；问题2.对特定社
9、团不上卷，其他节点上卷；问题3.对特定形式不上卷，其他节点上卷。本文主要解决问题1，下面以制裁恐惧组织为例，表1假设为每个成员的个人信息，每个人共4个维度，每个维度的取值代表该成员上卷到本维度的值，如：将恐惧组织成员谢里夫上卷到维度3，则该成员上卷后的取值为C3。图5为情报机构获取的恐惧组织关系网中部分成员之间的合作关系。当需要找到本拉登与上卷层级为3假定为公司名的联络时，则需要对信息网络图中除本拉登以外的其他所有节点进行上卷，找出它们之间的关系，如图6所示。通过它们之间的联络，反恐部门能够对这些公司进行经济等方面的制裁。2拓扑维异步算法2.1信息网络拓扑维上卷框架图7给出了信息网络拓扑维上卷
10、的框架，由信息网络拓扑图和节点信息维度的映射，得到基于用户特定需求的拓扑维上卷后的信息网络拓扑图。2.2信息网络拓扑维上卷算法设计基于对信息网络拓扑维上卷框架的理解，本文设计了信息网络拓扑维上卷算法：算法1实现了对信息网络中用户关注的节点不进行上卷操作，其他所有节点均上卷到指定的维度。在现实生活中的信息网络如：合作者网络，当查看某个节点与其他机构之间的联络时，根据文献15六度空间理论，可能只需要查看该节点在信息网络中第n跳范围内的所有机构而非查看整个信息网络，n越大所需的时间越多。本文设置n=3。算法2对算法1做出了改良：3.1数据集本文在DBLP数据集上进行实验，表1是数据集的简单概述，根据
11、数据集的详细情况，随机生成了拓扑的维度，表2具体描绘了预处理后的数据集。DBLP合作网络，两位作者之间有边则代表两个作者有合作关系。3.2实验结果目前国内外针对用户特定需求的信息网络拓扑维上卷的研究尚属空白区，大多数的研究人员都是对整个数据集进行上卷操作，不能知足用户的特点需求。本文主要做了两组试验：1信息网络不同维度的上卷操作2优化上述操作，指定跳数对于1，本文根据算法1进行实验，运用文献16和文献17提到的Java开源JUNG包，绘制的实验结果如图8所示，图中红点为用户特定查询节点，其他颜色的点分别代表数据集中除了查询节点以外其他节点上卷到指定维度的节点集，上卷到各个维度所需时间以及进行不
12、同跳数上卷效果曲线如图9所示。通过图9，发现随着维度的增大进行上卷所需断边以及生产新边的次数就越多，有效上卷代价p就越大，耗时必然越大。由于上卷整个数据集耗时过多，并且在实际生活中某个节点只要相邻的n跳范围内的其他节点具有强关联性。为了优化算法1，本文提出了算法2，详细实验的结果如图10所示，根据实验结果发现当n=3时，上卷所得的结果与遍历整个数据的结果非常的接近，耗时较之提高几个数量级，其中表3是上卷到维度1时不同跳数的耗时比拟，证实了算法2的有效性。本文主要根据信息网络的拓扑构造，本文初次提出了有效上卷代价的概念并提出了假设，实验室也很好的验证了假设。本文针对用户特定的需求，对某个特定节点不进行上卷，网络中的其他节点均上卷到指定的维度，为此本文设计了信息网络上卷算法，并在根据现实情况以及算法耗时太多的情况优化了算法，能在减少耗时的基础上很好地完成了算法，到达了预定目的。本文目前只是解决了对在节点的层次上进行上卷，进一步的工作主要会集中在对特定社团和特定形式进行上卷，并考虑更为复杂的信息网络中。