LHL-立方体互连网络及其性质

并行计算系统一直是计算机科学中的重要研究领域,其互连网络的拓扑性质对整个网络的性能起着非常重要的作用.目前已经提出多种互连网络,其中超立方体具有对数级的直径、高连通度、对称性等很好的性质,故被用作多种并行机的处理器连接的拓扑结构.然而,超立方体并非所有性质都是最优的互连网络,且超立方体的许多变型结构具有许多比超立方体更好的性质,其中已经证明了局部扭立方体在直径、Hamilton连通性等方面都优于超立方体.给出在超立方体与局部扭立方体的顶点间的一种连接方式--超连接,从而得到一种称为LHL-立方体的新型网络,并对这种网络的以下性质进行了研究:顶点连通度、边连通度、Hamilton连通性、直径.研究结果表明,一个n维LHL-立方体是一个具有2n个顶点和n2n-1条边的n-正则图,n维LHL-立方体的顶点连通度和边连通度均为n,且是Hamilton连通的,直径上界为[n/2 ]+3.     

超级交叉立方体互连网络上的圈嵌入

作为超立方体的变型，交叉立方体同时具有一些比超立方体优越的性质，但类似于超立方体，它的升级也伴随着顶点个数的增加而成倍中增加。为了解决这一问题，一种称为超级交叉立方体（SCC）的互连网络被提了出来。有关文献已证明，SCC很好地保持了交叉立方体在顶点度数，直径和连通度方面的优越性质，而且其升级可以增加任意多个顶点。用图嵌入技术讨论了SCC模拟环网络的能力，证明了长度为4到N的任一圈都能以扩张1嵌入具有N个顶点的SCC，从而证明了SCC模拟环网络的能力与交叉立方体完全相同。     

超级扭立方体互连网络及其性质

扭立方体是超立方体的一类变体,它具有比超立方体更好的性质。但是,同超立方体一样,它也是具有2n个顶点的n-正则图,故要使一个扭立方体的维数(即顶点度数)增加1(称为升级),就必须成倍地增加扭立方体中的顶点个数。为了解决这一问题,将具有2n个顶点的扭立方体的拓扑结构加以改变,得到了包含任意多个顶点的互连网络——超级扭立方体(STN)。证明了超级扭立方体保持了扭立方体的最高连通度、对数级的直径和顶点度数、Hamilton性质、连通度级的tp-可诊断度等方面的优良性质,更进一步地,由于它包含了任意多个顶点,所以对它的升级只需增加任意多个顶点,从而克服了扭立方体的升级必须成倍增加其顶点个数的缺点。     

超级局部扭立方体互连网络及其性质

局部扭立方体是近年来提出的超立方体的一个变型,由于它的许多优越性质(如低直径),在并行处理领域越来越受到人们的重视.然而,像超立方体一样,它也有一个缺点,即要使局部扭立方体升级,就必须成倍地增加其顶点个数.为了解决这一问题,文中将顶点个数为2的次幂的局部扭立方体推广到具有任意个顶点的互连网络,提出了超级局部扭立方体(SLTC)的定义,并证明它保持了局部扭立方体的最高连通度、对数级的直径和顶点度数、Hamilton性质等方面的优良性质,从而证明了超级局部扭立方体是既保持了局部扭立方体的多种优越性质又易于升级的互连网络.     

交叉立方体中嵌入超立方体的研究

Efe提出的交叉立方体(crossedcube)是超立方体(hypercube)的一种变型。但是,交叉立方体的某些性质却优于超立方体,其直径几乎是超立方体的一半。在本文中,研究了用交叉立方体互连网络来模拟超立方体互连网络,其实质是图嵌入问题,得出了以下结论:当n≤2,2n维交叉立方体CQ2n可同构嵌入两个n 1维立方体Qn 1。当n≥3,2n维交叉立方体CQ2n可同胚嵌入n 1维超立方体Qn 1。     

超级Mbius立方体──一类最优容错的小直径互连网络

文中将具有２ｎ个顶点的Ｍｏｂｉｕｓ立方体的拓扑结构加以改变,得到了包含任意个顶点的互连网络——超级Ｍｏｂｉｕｓ立方体,并证明它保持了Ｍｏｂｉｕｓ立方体的高连通度、对数级的直径和顶点度数等优良性质,并且当顶点个数Ｎ＝２ｎ＋２ｎ－１时,０－型超级Ｍｏｂｉｕｓ立方体是一个（ｎ＋１）－正则图;更进一步地,由于它包含任意个顶点,所以其升级只需增加任意个顶点,从而克服了Ｍｏｂｉｕｓ立方体的升级必须成倍增加其顶点个数的缺点．     

超级交叉立方体互连网络及其拓扑性质

交叉立方体是近年提出的超立方体的一种变种。由于它的许多优越性质（如直径、嵌入性等）,在并行处理领域越来越受到人们的重视。然而,像超立方体一样,它也有一个缺点,即要使交叉立方体升级,就必须成倍地增加其顶点个数。为了解决这一问题,本文将顶点个数的２的次幂的交叉立方体推广到具有任意个顶点的互连网络,提出了超级交叉立方体的定义,并证明它保持了交叉立方体在高速通度、对数级的直径和顶点度数等方面的优良性质,从     

Mbius立方体互连网络上的圈嵌入算法

图嵌入技术是研究多处理器互连网络模拟其它网络的能力的重要技术．文中讨论了近年提出的一类互连网络——Ｍｏｂｉｕｓ立方体上的圈嵌入性质．Ｍｏｂｉｕｓ立方体是超立方体的变型，它们具有一些比超立方体更优越的性质，如ｎ维Ｍｏｂｉｕｓ立方体Ｍｎ的直径大约是ｎ维超立方体的一半，其期望距离大约是ｎ维超立方体的２３等．文中证明了Ｍｏｂｉｕｓ立方体另一个比超方体优越的性质，即任一长度为ｌ（４≤ｌ≤２ｎ）的圈能以扩张ｌ嵌入ｎ维Ｍｏｂｉｕｓ立方体Ｍｎ（ｎ≥２），并给出了构造过程，从而也证明Ｍｎ对环网络的模拟能力比超立方体的高（超立方体不含奇长圈）．     

交叉扭立方体互联网络及其性质

扭N立方体是近年来提出的一种新型变体网络结构.通过X-变换操作使得存在2n个顶点的超立方体的网络直径从N减少到N-1,减少了网络规模增大时所需要的网络开销,从而受到了广泛的欢迎.与超立方体一样,扭N立方体也存在缺点,如果增加扭N立方体的维数,会成倍增加扭N立方体的顶点个数.为了解决这一问题,本文通过扭N立方体的结构,提出了交叉扭立方体的定义,并给出了相应的拓扑结构网络图,证明了交叉扭立方体的部分子网与超立方体网络同构,同时研究了交叉扭立方体的网络直径、连通度等问题.通过上述拓扑结构的基本性质的研究,得到了交叉扭立方体的性能优于扭N立方体的重要结论.     

交叉立方体环的Hamilton连通性和Pancyclicity性

交叉立方体是超立方体互连网络的一种变型,它的某些性质优于超立方体。例如,其直径几乎是超立方体的一半;当n≥3,交叉立方体CQn具有Hamilton连通性;当n≥2,所有长度在4到2n之间的圈都能够以扩张1嵌入CQn,即交叉立方体具有Pancyclity性。但是,交叉立方体同超立方体一样,当需要升级时,必须成倍增加结点。交叉立方体环互连网络CRN作为层次环互连网络HRN[8]的一种,可以有效地克服这个缺点,当需要升级时,只需在环上增加一个交叉立方体。在文中,证明了交叉立方体环互连网络仍然保持了交叉立方体具有的Hamilton连通性和Pancyclity性。     

Graph OLAPing 的建模、设计与实现

提出了一系列Graph的OLAP模型和算法,实现了以Graph数据为中心度量的OLAP操作.主要贡献包括:(1)提出了面向Graph的数据仓库概念模型——双星模型;(2)提出了Graph的数据立方概念和创建过程;(3)设计了信息维聚集算法I-OLAPing;(4)设计了拓扑维聚集算法T-OLAPing;(5)实现了Graph OLAP的原型系统Graph OLAPer1.0.实验结果表明,设计和实现的Graph OLAPing算法及原型系统Graph OLAPer1.0能够有效地进行科研合作网分析.     

基于图结构描述的几何约束模型的研究与建立

本文提出了一种基于图结构描述的二维图形几何约束模型的建立及存储方法。该方法利用图论的概念和原理,提出用无向图的结构描述一个几何约束系统,用约束图表示图形的约束信息,规则图则用来表达几何推理的过程,同时利用面向对象的技术建立一种扩展的图的领接表的数据结构来存储约束模型。这种方法对约束的分类及表达清晰、直观,能够处理各种约束信息,效率及可靠性较高。     

基于社交网络的图数据挖掘应用研究

社交网络数据的高度复杂性给数据挖掘研究带来了巨大的挑战,而社交网络数据挖掘更注重实体之间相互关联的特点,使得图数据挖掘技术的研究与应用逐渐成为该领域的热点。传统数据挖掘,如聚类、分类、频繁模式挖掘等技术逐渐拓展到图数据挖掘领域。文中首先介绍了现阶段图数据挖掘算法（其中包括图查询、图聚类、图分类和图的频繁子图挖掘）的研究内容和存在的问题;其次介绍了图形数据库研究现状,以及对比了主流图形数据库管理系统的优劣;最后介绍了图挖掘技术在社交网络中的应用。     

基于图划分抽样算法的图表示学习

在基于神经网络的图表示算法中,当节点属性维度过高、图的规模过大时,从内存到显存的数据传输会成为训练性能的瓶颈。针对这类问题,该方法将图划分算法应用于图表示学习中,降低了内存访问的I/O开销。该方法根据图节点的度数,将图划分成若干个块,使用显存缓存池存储若干个特征矩阵块。每一轮训练,使用缓存池中的特征矩阵块,以此来减少内存到显存的数据拷贝。针对这一思想,该方法使用基于图划分的抽样算法,设计显存的缓存池来降低内存的访问,运用多级负采样算法,降低训练中负样本采样的时间复杂度。在多个数据集上,与现有方法对比发现,该方法的下游机器学习准确率与原算法基本一致,训练效率可以提高2~ 7倍。实验结果表明,基于图划分的图表示学习能高效训练模型,同时保证节点表示向量的测试效果。今后的课题可以使用严谨的理论证明,阐明图划分模型与原模型的理论误差。     

关于互连网络的几个猜想

n-立方体是著名的互连网络,星图、煎饼图和冒泡排序图是由凯莱图模型设计出来的重要的互连网络。对换树（transposition tree）的凯莱图是一类特殊的凯莱图,星图和冒泡排序图分别是对换树为星和路的凯莱图。给出了关于n-立方体、星图、煎饼图、冒泡排序图和对换树的凯莱图的各一个猜想;提出了对换图的凯莱图的概念,进而由这一概念设计出了两个互连网络——圈图和轮图,并证明冒泡排序图和星图分别可嵌入圈图和轮图。     

图数据库发展综述

随着数据关联关系的发现、管理和应用的深入,图数据库快速发展.归纳总结了图数据库概念、图模型、组成架构图和数据库的特点;详细阐述了图数据库的关键技术;分析比较了当前主流图数据库产品,归纳了当前图数据库主要应用场景;最后提出图数据库未来发展的趋势.     

一个大规模股市图交互式可视化分析系统

随着物联网、移动互联网、云计算以及各种数据自动采集技术的迅猛发展,许多领域迅速积累了大量具有图结构的可用数据。其中一个重要的图应用是股市图。如何分析股市图达到合理充分的投资决策支持一直是一个重要的课题。其中极大团(Maximal Clique)分析是分析股市图的一个重要方法。股市图的规模庞大,传统的极大团枚举算法仅仅罗列图中所有的极大团。但一个图中可以有指数级数量的极大团,而一支股票对应的点可以参与到任意多的极大团中。因此,传统的极大团枚举算法不能直接有效支持股市图分析。本文提出一个支持快速选择、自动分组及导航浏览三种股市图交互式可视化操作的大规模股市图分析系统。根据用户感兴趣的股市图节点,这三种股市图交互式可视化操作从股市图中快速枚举出与这些特定股票相关的极大团、查看这些特定股票之间的组合关系以及显示与这些特定股票相关的其他股票,是有效支持股市图分析的必要手段。同时基于对某些特定顶点或边相关的极大团枚举的需求,本文提出了从图中枚举出与特定顶点或边相关的极大团算法。我们使用真实数据验证了本文提出的算法的优越性。     

基于邻域的大规模图数据动态分割算法

随着图数据的规模日益增大,出现大量以动态图数据为基础的分布式处理需求,划分问题在动态图数据分布式处理领域尤为重要. 对大规模动态图数据上的划分问题进行研究,根据图结构性质及动态图特点,提出并实现基于邻域的动态图分割算法. 算法分为静态切分和动态调整两个阶段,其中基于割边算法整合现有最优化策略提出了大规模图数据的静态切割算法. 在优化后的静态切割算法的基础上,根据图数据的动态扩张的特性提出动态分割算法. 根据迁移顶点所达到的最小负载值进行顶点迁移,并在此基础上进行性能及割边控制优化操作. 最后,改进算法在各类图数据集上进行了验证,验证的结果显示在平衡度和割边等指标上优化后的算法效果显著,提高了划分的合理性,并且在保证割边不增加的情况下提高了图分割的平衡度.     

VB5.0中图形控件的应用分析

本文介绍了在ＶＢ应用程序中设计动态统计图表的两种方法,一是利用图形控件Ｐｉｎｎａｃｌｃｅ－ＢＰＳ Ｃｒａｐｈ Ｃｏｎｔｒｏｌ,一是利用ＯＬＥ技术链接嵌入电子表格Ｅｘｃｅｌ图表。     

知识图谱平台综述

近年来,知识图谱被广泛研究和应用。为了能够更加准确、高效地维护知识图谱的全生命周期,以及对知识图谱进行更多复杂的操作,大量知识图谱平台被设计、开发和应用。而开发者通常是基于他们所拥有的知识图谱而进行设计和开发的,缺少对知识图谱平台整体上的认识以及对应用场景特殊性需求的理解。通过调研当前主流的43个知识图谱平台,分别从知识图谱平台的功能、架构和应用三个角度对其进行系统性地分析和研究,旨在使平台开发和使用人员对知识图谱平台有更深入的认识,进而促进知识图谱平台被高效地开发和使用。