Multipath-Based Multicasting Strategies for Wormhole-Routed Star Graph Interconnection Networks

The star graph interconnection network has been recognized as an attractive alternative to the popular hypercube network. In this paper, we present a multipath-based multicast routing model for wormholerouted star graph networks, propose two efficient multipath routing schemes, and contrast the performance of the proposed schemes with the performance of the scheme presented in our previous work. Both of the two proposed schemes have been proven to be deadlock-free. The first scheme, simple multipath routing, uses multiple independent paths for concurrent multicasting. The second scheme, two-phase multipath routing, includes two phases: source-to-relay and relay-to-destination. For each phase, multicasting is carried out using simple multipath routing. Experimental results show that, for short and medium messages with small message startup latencies, the proposed schemes reduce multicast latency more efficiently than other schemes.     

Migration of Tasks in Interconnection Networks Based on the Star Graph

The hierarchy of the star graph allows the assignment of its special subgraphs (substars), which have the same topological features as the original graph, to a sequence of incoming tasks. The procedure for task allocation in the star graph can be done using the star code and the allocation tree constructed based on this code. In this paper, the optimal set of codes which can collectively recognize a set of distinct substars is derived. It is shown that using only (n − 1) codes, almost half of the existing substars in an n-dimensional star is recognizable for n ≤ 9. When relinquishment of tasks is considered, task migration could potentially improve the utilization of network resources by reducing/eliminating the fragmentation caused as a result of task deallocation. A deadlock-free procedure is presented to migrate a task, distributed over the nodes of one substar, to the nodes of the other substar wherein: (i) subtasks travel in parallel via disjoint paths; (ii) the adjacency among the mapped nodes is preserved. The procedure can be made distributed with a slight modification. The work can be extended to other hierarchical networks based on permutation group.     

条件变分时序图自编码器

网络表示学习(也被称为图嵌入)是链接预测、节点分类、社区发现、图可视化等图任务的基础.现有大多数的图嵌入算法主要是针对静态图开发的,难以捕捉现实世界的网络随时间进化的动态特征.目前,针对动态网络表示学习方法的研究工作仍相对不足.提出了条件变分时序图自编码器(TS-CVGAE),可以同时学习动态网络的局部结构和随时间的演化模式.该方法首先改进了传统图卷积得到时序图卷积,并在条件变分自编码器的框架下使用时序图卷积对网络节点进行编码.训练结束后,条件变分自编码器的中间层就是最终的网络嵌入结果.实验结果表明,该方法在4个现实动态网络数据集上的链接预测表现均优于相关的静、动态网络表示学习方法.     

An Efficient Tree-Based Multicasting Algorithm on Wormhole-Routed Star Graph Interconnection Networks Embedded with Hamiltonian Path

Multicasting is an important issue for numerous applications in parallel and distributed computing. In multicasting, the same message is delivered from a source node to an arbitrary number of destination nodes. The star graph interconnection network has been recognized as an attractive alternative to the popular hypercube network. In this paper, we propose an efficient and deadlock-free tree-based multi-cast routing scheme for wormhole-routed star graph networks with hamiltonian path. In our proposed routing scheme, the router is with the input-buffer-based asynchronous replication mechanism that requires extra hardware cost. Meanwhile, the router simultaneously sends incoming flits on more than one outgoing channel. We perform simulation experiments with the network latency and the network traffic. Experimental results show that the proposed scheme reduces multicast latency more efficiently than other schemes.     

一类自选网络的容错直径与容错路由算法

作为加利图的一种,自选图AGn相对于其它网络结构,在并行计算及分布式计算领域有着更好的特性,因而受到广泛的重视.ANn是由翼有虎提出的基于AGn的一类新的网络结构.这个新的网络结构在直径、容错度、容错直径和汉密尔顿连通性上都优于网络AGn.虽然该网络结构已经有了较好的非容错路由算法,但是依然没有一种针对这个结构的容错路由算法以完善其实际应用.文中通过研究ANn的性质,得出了容错直径,然后基于该容错直径,设计并实现了ANn容错路由算法,最后验证了该算法的正确性.     

Embedding Meshes on the Star Graph

We develop algorithms for mapping n-dimensional meshes on a star graph of degree n with expansion 1 and dilation 3. We show that an n-degree star graph can efficiently simulate an n-dimensional mesh.     

Graph Characterization by Counting Sink Star Subgraphs

In this paper, we study the polynomial coefficients of the reduced Bartholdi zeta function for characterizing simple unweighted graphs and demonstrate how to use these coefficients for clustering graphs. The polynomial coefficients of the reduced Bartholdi zeta function are invariant to vertex order permutations and also carry information about counting the sink star subgraphs in a symmetric digraph of G. We also investigate the advantages of the reduced Bartholdi coefficients over other spectral methods such as the Ihara zeta function and Laplacian spectra. Experimental results indicate that the proposed method is more effective than the other spectral approaches, and compared to the Ihara zeta function, it has less sensitivity to structural noises such as omitting an edge.     

Conditional Term Graph Rewriting with Indirect Sharing

For reasons of efficiency, term rewriting is usually implemented by term graph rewriting. In term rewriting, expressions are represented as terms, whereas in term graph rewriting these are represented as directed graphs. Unlike terms, graphs allow a sharing of common subexpressions. In previous work, we have shown that conditional term graph rewriting is a sound and complete implementation for a certain class of CTRSs with strict equality, provided that a minimal structure sharing scheme is used. In this paper, we will show that this is also true for two different extensions of normal CTRSs. In contrast to the previous work, however, a non-minimal structure sharing scheme can be used. That is, the amount of sharing is increased.     

条件概率图产生式对抗网络

产生式对抗网络(generative adversarial networks,简称GANs)可以生成逼真的图像,因此最近被广泛研究.值得注意的是,概率图生成对抗网络(graphical-GAN)将贝叶斯网络引入产生式对抗网络框架,以无监督的方式学习到数据的隐藏结构.提出了条件概率图生成对抗网络(conditional graphical-GAN),它可以在弱监督环境下,利用粗粒度监督信息来学习到更精细而复杂的结构.条件概率图生成对抗网络的推理和学习遵循与graphical-GAN类似的方法.提出了条件概率图生成对抗网络的两个实例.条件高斯混合模型(conditional Gaussian mixture GAN,简称cGMGAN)可以在给出粗粒度标签的情况下从混合数据中学习细粒度聚类.条件状态空间模型(conditional state space GAN,简称cSSGAN)可以在给定对象标签的情况下学习具有多个对象的视频的动态过程.     

基于条件约束的胶囊生成对抗网络

生成式对抗网络(Generative adversarial networks, GAN)是主要的以无监督方式学习深度生成模型的方法之一.基于可微生成器网络的生成式建模方法, 是目前最热门的研究领域, 但由于真实样本分布的复杂性, 导致GAN生成模型在训练过程稳定性、生成质量等方面均存在不少问题.在生成式建模领域, 对网络结构的探索是重要的一个研究方向, 本文利用胶囊神经网络(Capsule networks, CapsNets)重构生成对抗网络模型结构, 在训练过程中使用了Wasserstein GAN (WGAN)中提出的基于Earth-mover距离的损失函数, 并在此基础上加以条件约束来稳定模型生成过程, 从而建立带条件约束的胶囊生成对抗网络(Conditional-CapsuleGAN, C-CapsGAN).通过在MNIST和CIFAR-10数据集上的多组实验, 结果表明将CapsNets应用到生成式建模领域是可行的, 相较于现有类似模型, C-CapsGAN不仅能在图像生成任务中稳定生成高质量图像, 同时还能更有效地抑制模式坍塌情况的发生.     

Diameter and Treewidth in Minor-Closed Graph Families

It is known that any planar graph with diameter D has treewidth O(D) , and this fact has been used as the basis for several planar graph algorithms. We investigate the extent to which similar relations hold in other graph families. We show that treewidth is bounded by a function of the diameter in a minor-closed family, if and only if some apex graph does not belong to the family. In particular, the O(D) bound above can be extended to bounded-genus graphs. As a consequence, we extend several approximation algorithms and exact subgraph isomorphism algorithms from planar graphs to other graph families.     

图神经网络在复杂图挖掘上的研究进展

图神经网络对非欧式空间数据建立了深度学习框架,相比传统网络表示学习模型,它对图结构能够实施更加深层的信息聚合操作.近年来,图神经网络完成了向复杂图结构的迁移,诞生了一系列基于复杂图的图神经网络模型.然而,现有综述文章缺乏对复杂图神经网络全面、系统的归纳和总结工作.将复杂图分为异质图、动态图和超图3种类型.将异质图神经网络按照信息聚合方式划分为关系类型感知和元路径感知两大类,在此基础上,分别介绍普通异质图和知识图谱.将动态图神经网络按照处理时序信息的方式划分成基于循环神经网络、基于自编码器以及时空图神经网络三大类.将超图神经网络按照是否将超图展开成成对图划分为展开型和非展开型两大类,进一步按照展开方式将展开型划分成星形展开、团式展开和线形展开3种类型.详细阐述了每种算法的核心思想,比较了不同算法间的优缺点,系统列举了各类复杂图神经网络的关键算法、(交叉)应用领域和常用数据集,并对未来可能的研究方向进行了展望.     

基于图神经网络的多维度池化图分类

目前很多处理图数据的图神经网络方法被提出,然而大多数研究侧重于对特征聚合的卷积层的研究而不是进行下采样的池化层.此外,形成聚类簇的池化方式需要额外计算分配矩阵;节点得分的池化方式排名方式单一.为解决上述问题,提高图分类任务的准确性,本文提出了一种新的基于多维度信息的图池化算子MDPool.该模型使用节点特征信息以及图拓扑结构信息,获取不同维度下的节点得分.使用注意力机制归纳不同维度下的得分权重,生成更为健壮的节点排名,基于节点排名自适应选择节点集合生成诱导子图.提出的MDPool可以集成到多种的图神经网络结构,将MDPool池化算子与图神经网络卷积层堆叠形成编码解码模型EDMDPool.在4个公开数据集的图分类任务中, EDMDPool均高于现有基线模型.     

基于条件化有向图的工作流过程优化

为改善工作流的性能和效率,一个智能化的工作流管理系统应该具有分析和优化工作流过程定义的能力,该文首先给出影响工作流过程性能的主要因素,借助于定量分析的方法,讨论了这些因素对工作流性能和效率的影响,以此为基础,基于条件化有向图这种过程定义模型提出了一组对工作流过程进行优化的方法。     

Substar Reliability Analysis in Star Networks

In this paper, we derive an upper bound on the (n − 1)-star reliability in an S_n using the probability fault model. Approximate (n − 1)-star reliability results are also obtained using the fixed partitioning. The numerical results show that the (n − 1)-star reliabilities under the probability fault model and the fixed partitioning are in good agreement especially for the low value of the node reliability. The numerical results are also shown to be consistent with and close to the simulation results. Conservative comparisons are made where possible between the reliability of similar size star graphs and hypercubes.     

基于有向图和贝叶斯网络融合的飞机系统故障诊断研究

针对民用飞机系统的故障复杂性和特殊性,提出了一种基于有向图和贝叶斯网络融合的故障诊断方法.首先分析增压系统的组成,总结各组件之间的功能逻辑;接着以有向图理论为基础,将有向图中的节点赋值为系统各组件功能,进而推导出系统的功能模型,提高了故障诊断的直观性和有效性;最后利用贝叶斯网络快速的概率推理能力,缩小故障点集,实现故障定位,提高了诊断的快速性和精确性.通过实例验证,所研究的故障诊断方法对排故效率有了提升,同时对飞机其他系统的故障诊断有一定的参考价值.     

一种基于Hadoop的大规模图直径算法

为提高具有百万个节点以上的大规模图处理效率,通过研究大规模图和分布式框架Hadoop,提出了GDH大规模图直径算法。算法通过每次计算出半径相同的图节点,直到最后一次迭代求出所有节点的半径,然后用节点半径之和除以节点数算出大规模图直径。算法的时空复杂度不大,并且与经典的直径算法相比,GDH算法的效率高些。经测试雅虎网站和脸谱网站的网页数据,发现该算法可清晰地分析Web图的网页节点和社交图的人际关系。     

Study of General Incomplete Star Interconnection Networks

IIntroduct1OllThe star graph【1]proposed as a particular case ofC叫ley graphs[ZJ Is vertex－and edge－symmetric．strongly hlerarchlcal,maximally tault－tolerant,strongly resilient and has diameter and node degreethat are superior to those of a slmll。－slied hypercube(which Is also a Cnyley graph)IOr parallelcomputers[3]．MNor references can be found In studying the star graph regarding its propertiesllJ,e毗edding cwabllity[4],communication c叩劝ility[5－71,andfanfaut－toierm尬 cap劝ility…     

Conditional Edge-Fault Hamiltonicity of Matching Composition Networks

A graph G is called Hamiltonian if there is a Hamiltonian cycle in G. The conditional edge-fault Hamiltonicity of a Hamiltonian graph G is the largest k such that after removing k faulty edges from G, provided that each node is incident to at least two fault-free edges, the resulting graph contains a Hamiltonian cycle. In this paper, we sketch common properties of a class of networks, called matching composition networks (MCNs), such that the conditional edge-fault hamiltonicity of MCNs can be determined from the found properties. We then apply our technical theorems to determine conditional edge-fault hamiltonicities of several multiprocessor systems, including n-dimensional crossed cubes, n-dimensional twisted cubes, n-dimensional locally twisted cubes, n-dimensional generalized twisted cubes, and n-dimensional hyper Petersen networks. Moreover, we also demonstrate that our technical theorems can be applied to network construction.