5次幂圈嵌套网络图的边-平衡指数集(m模3余2)

针对网络图边-平衡指数集标号问题,在等圈嵌套网络图的基础上,提出了幂圈嵌套网络图的概念,进而研究无限路5次幂圈嵌套网络图的边-平衡指数集。利用基础图、带齿套圈子图、五点扇形子图组设计新思路,大大降低了构造标号图的复杂程度,确定了当m模3余2时,无限路5次幂圈嵌套图的边-平衡指数集,并且给出了边-平衡指数集对应图形标号的设计方法。     

两类网络图的边-平衡指数集

在较小次幂圈嵌套网络图的基础上,研究了10次幂嵌套网络图的边-平衡指数集。利用基础图、带齿套圈子图、单点扇形子图设计新思路,降低了构造标号图的复杂程度。当n=10为偶数时,提出了新的变换指数方法,简化了证明过程。确定了m模6余1和余3且m大于等于2时(m为圈数)无限路10次幂圈嵌套图的边-平衡指数集,并且解决了这两类幂圈嵌套图的边-平衡指数集的存在性,给出了具体构造方法和公式证明。     

幂圈嵌套网络图C_(10)~m×P_m_(10)(m≡2,5(mod 6))的边-平衡指数集

基于网络图边-平衡指数集标号问题,在较小次幂圈嵌套网络图的基础上,研究无限路C_(10)~m×P_m_(10)网络图的边-平衡指数集。提出了单点扇形子图的新概念,利用基础图、带齿套圈子图、单点扇形子图设计新思路,再次降低了构造标号图的复杂程度。确定了当m模6余2和余5时,无限路C_(10)~m×P_m_(10)网络图边-平衡指数集,并完成全部公式证明和图形的构造。     

基于边映射表连接的匹配算法

针对面向语义网络图匹配的特殊性, 在基于状态回溯搜索算法的基础上提出一种新的称为基于边映射表连接的匹配算法, 利用语义网络图的有向性, 将图匹配问题转换为对搜索路径的规划, 并采用深度优先算法形成搜索步, 同时对目标图的所有边建立索引, 加快以边匹配为中心形成边映射表的过程, 最后对边映射表进行连接形成结果集。在真实数据集上的实验结果表明, 该算法具有较高的执行效率。     

一类链图的优美性研究

该文首先给出了四圈链图的一种新的优美标号,讨论了四圈链图与路的一个端点相粘得到的一类图的优美性和交错性,在此基础上研究了两个四圈链图与路的两个端点分别相粘得到的一类图的优美性。     

一种判定图中Hamilton圈的邻接边增长算法

一个图是否为Hamilton图在于图中是否有Hamilton圈。文中提出了变换的方法来寻找图中的Hamilton圈，即在图的顶点集中寻找满足包含给定图中所有顶点的自归邻接边增长变换的方法来寻找给定图中的Hamilton圈。由此，设计了一个在Edmonds意义下的有效算法——自归邻接边增长算法(AEG)来寻找给定图中的自归邻接边增长变换，证明了该算法能正确判断给定简单无向图中有无Hamilton圈且时间复杂度为O(n^2)。最后通过应用实例说明该算法的有效性和实用性。     

外1-平面图的均匀边染色

图[G]的[s]-均匀边[k]-染色是指用[k]种颜色对图的边进行染色,使得图[G]的每个顶点所关联的任何两种颜色的边的条数至多相差[s]。使得对于每个不小于[k]的整数[t],图[G]都具有[s]-均匀边[t]-染色的最小整数[k]称为图[G]的[s]-均匀边色数阈值。文中证明了外1-平面图的1-均匀边色数阈值最多为5,不含有相邻的3圈的外1-平面图的均匀边色数阈值最多为4,外1-平面图的2-均匀边色数阈值恰好为1。     

2r-正则图连通圈网络的Hamilton分解

互连网络是超级计算机的重要组成部分。互连网络通常模型化为一个图,图的顶点代表处理机,图的边代表通信链路。2010年师海忠提出互连网络的正则图连通圈网络模型,设计出了多种互连网络,也提出了一系列猜想。文中证明了2r -正则图连通圈网络可分解为边不交的一个Hamilton圈和一个完美对集的并,从而证明了当原图为2r-正则连通图时,这一系列猜想成立。     

面向强连接网络图的无损压缩算法

幂图分析技术将所有具有相同邻居的节点集合汇聚成单个模块以大幅压缩网络图,被广泛地应用于网络图无损压缩与可视化中.然而获取最优的幂图是难点.针对此问题,提出面向强连接网络图的无损压缩算法.首先,证明了含有单个模块的最优幂图问题为NP难问题,进而扩展为一般地最优幂图问题为NP难问题;其次,在梳理现有整数线性规划模型和约束规划模型等问题的基础上,提出基于回溯策略的波束搜索算法,使有限的回溯策略提供启发信息,比已知启发式方法更快速地得到更优的结果.通过生成的随机无标度图,验证了该算法的有效性.     

一种判定图中Hamilton圈的邻接边增长算法

一个图是否为Hamilton图在于图中是否有Hamilton圈.文中提出了变换的方法来寻找图中的Hamilton圈,即在图的顶点集中寻找满足包含给定图中所有顶点的自归邻接边增长变换的方法来寻找给定图中的Hamilton圈.由此,设计了一个在Edmonds意义下的有效算法--自归邻接边增长算法(AEG)来寻找给定图中的自归邻接边增长变换,证明了该算法能正确判断给定简单无向图中有无Hamilton圈且时间复杂度为O(n2).最后通过应用实例说明该算法的有效性和实用性.     

BSP模型下基于边聚簇的大图划分与迭代处理

近年来随着互联网的普及和相关技术的日益成熟,大规模图数据处理成为新的研究热点.由于传统的如Hadoop等通用云平台不适合迭代式地处理图数据,研究人员基于BSP模型提出了新的处理方案,如Pregel,Hama,Giraph等.然而,图处理算法需要按照图的拓扑结构频繁交换中间计算结果而导致巨大的通信开销,这严重地影响了基于BSP模型的系统的处理性能.首先从降低消息通信的角度分析当前主流BSP系统的处理方案,然后提出了一种基于边聚簇的垂直混合划分策略(EC-VHP),并建立代价收益模型分析其消息通信优化的效果.在EC-VHP的基础上,提出了一个点-边计算模型,并设计了简单Hash索引和多队列并行顺序索引机制,进一步提高消息通信的处理效率.最后,在真实数据集和模拟数据集上的大量实验,验证了EC-VHP策略和索引机制的正确性和有效性.     

随机图的均匀边染色算法

图的均匀边染色是指图中任意两条相邻的边都分配到不同的颜色,且任意两个色类的颜色个数最大相差1。对图 进行均匀边染色所需的最少颜色数叫做 的均匀边色数。本文提出了一种启发式算法,能够求解图的最小均匀边色数。该算法根据均匀边染色条件,设计了两个子目标函数和一个总目标函数,借助染色矩阵的色补矩阵迭代交换,逐步寻优,直到找到最优解时结束。本文给出了详细的算法设计流程,并且进行了大量的测试和分析,实验结果表明,该算法可以高效地求出给定点数的图的最小均匀边色数,算法时间复杂度不超过 。     

大图结构特征对划分效果的影响

针对大图结构特征如何影响划分效果这一问题,提出一种通过顶点度分布特征来描述大图结构特征的方法。首先,基于真实的图数据产生若干顶点数和边数相同、但结构特征不同的仿真数据集,通过实验计算真实图与仿真图之间的相似度,证明该方法对描述真实大图结构特征的有效性。然后,通过Hash和点对交换划分算法,验证图结构特征与划分效果之间的关系。当点对交换划分算法执行到5万次时,划分一个有6301个顶点和20777条边的真实图其交叉边数比Hash划分算法降低了54.32%,划分仿真图数据集中结构特征差异明显的两个图时,交叉边数分别为6233和316。实验结果表明,点对交换划分算法能够减少交叉边数,图的顶点度分布差异越大,划分后交叉边数越少,划分效果越好,因此大图结构特征影响其划分效果,这为建立图的结构特征与划分效果之间的关系模型研究奠定了基础。     

一种基于程序DD图的无约束边生成算法

基于相似路径集进行软件故障定位是众多有效故障定位方法中的一种,该方法利用测试技术、程序切片和削片技术给出具体的软件故障定位报告.在实现上述方法时,求出程序DD图(Decision-to-Decision Graph)的无约束边就是关键步骤.目前,针对这一关键步骤的研究中,虽然取得了一定进展,但如何基于程序DD图生成无约束边,尚需要进一步研究.首先选用十字链表结构存储程序的DD图,进而计算出该程序DD图中各边对应的主宰树和蕴含树,在此基础上求出程序DD图中无约束边.通过实验验证,提出的无约束边生成算法是一种有效的方法.     

论图Pn3的优美性

定义了图Pn3.给出了.图Pn3的优美标号,从而证明了图Pn3是优美图,并且是平衡二分图,也是交错图.     

基于节点相似性分组与图压缩的图摘要算法

方法压缩率较高，图压缩算法无法直接被用于下游任务分析的问题，提出一种图摘要与图压缩的融合算法，即基于节点相似性分组与图压缩的图摘要算法（GSNSC）。首先，初始化节点为超节点，并根据相似度对超节点分组；其次，将每个组的超节点合并，直到达到指定次数或指定节点数；再次，在超节点之间添加超边和校正边以恢复原始图；最后，对于图压缩部分，判断对每个超节点的邻接边压缩和摘要的代价，并选择二者中代价较小的执行。在Web-NotreDame、Web-Google和Web-Berkstan等6个数据集上进行了图压缩率和图查询实验。实验结果表明，在6个数据集上，与SLUGGER(Scalable Lossless sUmmarization of Graphs with HiERarchy)算法相比，所提算法的压缩率至少降低了23个百分点；与SWeG(Summarization of Web-scale Graphs)算法相比，所提算法的压缩率至少降低了13个百分点；在Web-NotreDame数据集上，所提算法的度误差比SWeG降低了41.6%。以上验证了所提算法具有更好的图压缩率和图查询准确度。     

关于互连网络的几个猜想

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

面向复杂网络的图稀疏算法综述

大规模数据下复杂网络的算法分析面临复杂度高的挑战,为此引入图稀疏的思想,在保持原始图性质的情况下以一定的精度在稀疏图上实现了高效的算法分析。图稀疏算法是一种保留顶点、对边稀疏采样的方法。按照相应算法分析所需要的原始图性质,提出图稀疏的边度量方式。文中系统回顾了4种边度量下的图稀疏采样方法:生成图稀疏、边连通图稀疏、聚类图稀疏、边传播性图稀疏,归纳了不同边度量方式下图稀疏的优缺点和适应性,并进一步讨论了动态图流稀疏化的最新研究进展。最后,总结了图稀疏领域有待解决的问题并展望了未来的研究方向。     

基于边膨胀图的压缩感知理论

膨胀图(Expander graphs, EG) 理论与压缩感知(Compressive sensing, CS)理论相结合是近几年发展起来的一个新方向, 其优点在于能设计出具有确定结构的0-1测量矩阵, 且可根据膨胀图的结构协同设计重建算法, 相当于在重建算法中引入了先验知识, 能更快更准确地重构出稀疏信号. 本文从非均匀采样的必要性和合理性分析出发, 在已有的膨胀图压缩感知理论基础上, 将膨胀图的定义拓展到左顶点度数不相等的边膨胀图, 并建立起边膨胀图邻接矩阵与有限等距性质 (Restricted isometry property, RIP)条件之间的联系, 又进一步给出了边膨胀图邻接矩阵的列相关系数的上限值. 同时根据边膨胀图的特性, 协同设计了两种压缩感知重建算法. 通过仿真实验对比边膨胀图代表的非均匀采样模式与现有膨胀图代表的均匀采样模式, 以及本文设计的算法与传统算法在重建稀疏信号上的性能, 实验结果验证了边膨胀图压缩感知理论的有效性.     

一个求解层次图边交叉数最小化问题的遗传算法

最小化边交叉数是层次图绘制过程中的一个关键步骤,直接影响着层次图的可读性。提出了一个基于 遗传算法的层次图边交叉数最小化算法,详细地给出了编码表示方法以及遗传算子的设计。与常用的启发算法 相比,该算法得到了更好的计算结果,此外算法简单且易于实现。