基于多通道的边学习图卷积网络

通常图的边包含了图的重要信息，然而目前大多数用于图学习的深度学习模型（如图卷积网络（graph convolutional network，GCN）和图注意力网络（graph attention network，GAT））没有充分利用多维边特征的特性；另一个问题是图中可能存在噪声，影响图学习的性能。使用多层感知机对图数据进行去噪优化处理，在GCN的基础上引入了多通道学习边特征的方法，对图的多维边属性进行编码，按原始图所包含的属性分别建模为多通道，每个通道对应一种边特征属性对图节点进行约束训练，可以让算法更合理地学习图中多维边特征，在Cora、Tox21、Freesolv等数据集上的实验证明了去噪方法与多通道方法的有效性。     

(k,l)-递归极大平面图的结构

对于一个平面图G实施扩3-轮运算是指在G的某个三角形面xyz内添加一个新顶点v,使v与x, y, z均相邻,最后得到一个阶为|V(G)|+1的平面图的过程。一个递归极大平面图是指从平面图K₄出发,逐次实施扩3-轮运算而得到的极大平面图。 所谓一个(k,l)-递归极大平面图是指一个递归极大平面图,它恰好有k个度为3的顶点,并且任意两个3度顶点之间的距离均为l。该文对(k,l)-递归极大平面图的存在性问题做了探讨,刻画了(3,2)-及(2,3)-递归极大平面图的结构。     

有源网络图的一种操作算子及其应用

本文定义了有源网络图的一种操作算子,并用其推导了一种确定有源网络拓扑分析中完全树符号的新算法.用该算法确定完全树符号时,只需依次替代电流图树(或电压图树)中的有源边,并记录替换边与被替换边的关联状况便可求出完全树的符号.此方法系统性强,易于编程.     

Alternating Graph

1IntroductionInthedesignofalargemulti-processorcomputingsystem,oneoftheprimarydesigndecisionsinvolvesthetopologyofthecommunicationstructureamongesttheprocessors.Themostpopular...-t.i.'ialtopologiescurrentlyinusearetheBooleanncubetl),t2),unidirectionaln--c…     

The k-Diameter of a Kind of Circulant Graph

The diameter of a graph G is the maximal distance between pairs of vertices of G. When a network is modeled as a graph, diameter is a measurement for maximum transmission delay. The k-diameter dk(G) of a graph G, which deals with k internally disjoint paths between pairs of vertices of G, is a extension of the diameter of G. It has widely studied in graph theory and computer science. The circulant graph is a group-theoretic model of a class of symmetric interconnection network. Let Cn(i, n/2) be a circulant graph of order n whose spanning elements are i and n/2, where n4 and n is even. In this paper, the diameter, 2-diameter and 3-diameter of the Cn(i, n/2) are all obtained if gcd(n,i)=1, where the symbol gcd(n,i) denotes the maximum common divisor of n and i.     

THE MOLECULAR ALGORITHM OF CONNECTIVITY BASED ON THREE DIMENSIONAL DNA STRUCTURE

I. Introduction It was well-known that DNA computing was firstly presented in Adleman’s paper[1] in 1994, after which the field of DNA computing emerged. Henceforth, Lipton[2], in his paper, showed how a large class of Non-deterministic Polynomial (NP) complete problems could be solved by encoding the problem in DNA molecules. After this, Ouyang, et al.[3] presented a molecular biology-based ex-perimental solution to the “maximal clique” problem. Liu, et al.[4] designed a DNA model …     

A linear-time algorithm to compute the reliability of planarcube-free networks

A planar graph G=(V,E) is a cube-free graph (CF graph) if it has no subgraph homomorphic to the cube. The cube is the graph whose vertices and edges are the vertices and edges of the three dimensional geometric cube. The all-terminal reliability of a graph G whose edges can fail (with known probabilities) is the probability that G is connected. The problem of computing the all-terminal reliability of a general graph is NP-hard. An O(| V|) time algorithm for computing the all-terminal reliability of CF graphs is presented     

Geometric spanners for routing in mobile networks

We propose a new routing graph, the restricted Delaunay graph (RDG), for mobile ad hoc networks. Combined with a node clustering algorithm, the RDG can be used as an underlying graph for geographic routing protocols. This graph has the following attractive properties: 1) it is planar; 2) between any two graph nodes there exists a path whose length, whether measured in terms of topological or Euclidean distance, is only a constant times the minimum length possible; and 3) the graph can be maintained efficiently in a distributed manner when the nodes move around. Furthermore, each node only needs constant time to make routing decisions. We show by simulation that the RDG outperforms previously proposed routing graphs in the context of the Greedy perimeter stateless routing (GPSR) protocol. Finally, we investigate theoretical bounds on the quality of paths discovered using GPSR.     

基于频繁闭图的图包含查询算法

 交通网络可利用图数据进行描述与分析,常用的方法包括挖掘、查询、分类等.提高大规模图集上查询算法效率的问题是当前图数据分析领域中一个重要的研究方向.给定图集,图包含查询返回图集中所有查询图的子图.本文提出一种基于频繁闭图的包含查询算法.算法首先通过选择比消除频繁闭图之间的冗余,然后将具有强选择性的频繁闭图通过树的结构组织起来建立索引,并在此索引基础上实现图包含查询.在文章的最后,给出了理论与实验的分析结果.结果表明,该算法不但能高效的进行索引筛选,而且能显著的减小候选集尺寸,进而大大的降低了查询图与索引模式之间以及与候选集之间的子图同构测试次数,提高了查询效率.     

Multi-domain grooming algorithm based on hierarchical integrated multi-granularity auxiliary graph in optical mesh networks

With the size of traffic demands ranges from sub-wavelength-level to wavelength-level, traffic demands need to be aggregated and carried over the network in a cost-effective manner to make sure that the resources are utilized effectively. Therefore, the technique called multi-granularity grooming is proposed to save the cost by reducing the number of switching ports in optical cross-connects. However, the existing multi-granularity grooming algorithms are mostly limited in single-domain optical networks. Since the current optical backbone keeps enlarging and is actually divided to multiple independent domains for achieving the scalability and the confidentiality, it is necessary to study the multi-granularity grooming in multi-domain optical networks. In this paper, we propose a new heuristic algorithm called hierarchical multi-domain multi-granularity grooming (HMMG) based on hierarchical integrated multi-granularity auxiliary graph (H-IMAG) to reduce the total number of optical switching ports. The H-IMAG is composed of the inter-domain virtual topology graph (VTG) and the intra-domain integrated layered auxiliary graph (ILAG), where VTG includes a wavelength virtual topology graph (WVTG) and a waveband virtual topology graph (BVTG), and ILAG includes a wavelength layered auxiliary graph (WLAG) and a waveBand layered auxiliary graph (BLAG). Then, we can groom the sub-wavelength-level demands into lightpaths based on WVTG and WLAG and groom the wavelength-level demands into high-capacity wavebands based on BVTG and BLAG. Simulation results show that performances of H-IMAG can be significantly improved compared with previous algorithm.     

基于因子图的自适应波束形成

图模型具有广泛的应用,它为许多问题提供了一种新的表达方式和研究思路。因子图作为一类重要的图模型,尤其适用于多变量的复杂统计模型。因子图的引入可以使复杂的多变量问题得到简化。因子图理论在系统建模以及信号检测和估计算法中有着重要的应用。国内外不少学者将因子图理论应用于复杂的通信信号处理,但目前很少见到将因子图理论应用在雷达信号处理中。为了将因子图理论作为一种有效的工具应用于雷达信号处理,提出了用因子图理论实现雷达信号处理中的自适应波束形成技术（ADBF）的方法,这为用图模型研究雷达信号处理提供了一个很好的思路。     

改进GCNs在指静脉特征表达中的应用

基于图模型的指静脉全局特征表达方法不仅可以降低成像质量对采集设备的依赖性,还能提高匹配效率。针对于目前指静脉图模型的研究中存在的图结构不稳定,匹配效率随图模型的变大而降低的问题,本文提出了一种基于SLIC(Simple Linear Iterative Clustering)超像素分割算法构建加权图的方法,并改进ChebyNet图卷积神经网络(Graph Convolutional Neural Networks, GCNs)提取加权图的图级(graph-level)特征。针对指静脉样本数普遍较少,而ChebyNet中卷积网络参数量较大容易造成过拟合以及其快速池化层不能自适应地选择节点的问题,本文提出了全局池化结构的改进GCNs模型SCheby-MgPool(Simplified Cheby-Multi gPool)。实验结果表明,本文提出的方法提取的指静脉特征在识别精度,匹配效率上都具有较好的性能。      

The k-Diameter of a Kind of Circulant Graph

The terminology and notion in this paper are similar to Ref.[1], all graphs discussed here are finite and simple. The diameter d(G) of a graph G is the maximal distance between pairs of vertices of G. The connectivity of G is the minimum number of vertices needed to be removed in order to disconnect the graph. When a network is modeled as a graph,a vertex represents a node of processor (or a station) and an edge between two vertices is the link (or connection) between those two processors. I…     

关于无重复分解产生树的定理

本文定义了一种二分图,称之为互补划分图。利用此图容易证明有关互补划分的定理,并可得到一个判别是否是本性互补划分的较弱的条件。     

Properties and Algorithms for Unfolding of Probabilistic Data-Flow Graphs

It is known that any selection statement (e.g. if and switch-case statements) in an application is associated with a probability which could either be predetermined by user input or chosen at runtime. Such a statement can be regarded as a computation node whose computation time is represented by a random variable. This paper focuses on iterative applications (containing loops) reflecting those uncertainties. Such an application can then be transformed to a probabilistic data-flow graph.Two timing models, the time-invariant and time-variant models, are introduced to characterize the nature of these applications. Since there can be many unfolding factors associated with each of the possible graph outcomes, for the time-invariant model, we propose a means of selecting a constant minimum rate-optimal unfolding factor for unfolding the probabilistic graph. We demonstrate that this factor guarantees the best schedule length.We also suggest a good estimate for choosing an unfolding factor for a graph under the time-variant model. Experiments show that using our selection scheme results in an iteration period close to the theoretical iteration bound of the experimental graph. Furthermore, this paper discusses an alternative approach which selects a few optimal schedules (with respect to the graph outcomes) to be stored in the system. The other possibilities will be represented by a modified template graph.     

Grid Colorings in Steganography

A proper vertex coloring of a graph is called rainbow if, for each vertex v, all neighbors of v receive distinct colors. A k-regular graph G is called rainbow (or domatically full) if it admits a rainbow (k+1)-coloring. The d-dimensional grid graph G_d is the graph whose vertices are the points of Zopf^d and two vertices are adjacent if and only if their l₁-distance is 1. We use a simple construction to prove that G_d is rainbow for all d ges 1. We discuss an important application of this result in steganography     

基于笛卡尔乘积图上Sobolev平滑的时变图信号分布式批量重构

针对大规模网络数据的重构问题,该文以图信号处理(GSP)理论为基础,提出一种基于笛卡尔乘积图上Sobolev平滑的分布式批量重构算法(DBR-SSC)。该算法首先按时间顺序将时变图信号划分为多个信号段,并利用笛卡尔积将每一段内各时刻的图建模为乘积图;然后利用笛卡尔乘积图上的Sobolev差分平滑,将每一段的信号重构问题归结为优化问题;最后设计具有高收敛速度的分布式算法求解该优化问题。采用两种现实世界的数据集进行仿真实验,实验结果表明所提算法重构误差低并具有高收敛速度。     

The L(2,1)-labeling and operations of graphs

Motivated by a variation of the channel assignment problem, a graph labeling analogous to the graph vertex coloring has been presented and is called an L(2,1)-labeling. More precisely, an L(2,1)-labeling of a graph G is a function f from the vertex set V(G) to the set of all nonnegative integers such that |f(x)-f(y)| /spl ges/ 2 if d(x,y)=1 and |f(x)-f(y)| /spl ges/ 1 if d(x,y) = 2. The L(2,1)-labeling number /spl lambda/(G) of G is the smallest number k such that G has an L(2,1)-labeling with max{f(v):v/spl isin/V(G)}=k. A conjecture states that /spl lambda/(G) /spl les/ /spl Delta//sup 2/ for any simple graph with the maximum degree /spl Delta//spl ges/2. This paper considers the graphs formed by the Cartesian product and the composition of two graphs. The new graph satisfies the conjecture above in both cases(with minor exceptions).     

一种求解最小割的警示传播算法

最小割问题（minimum cut problem）是NP（Non-deterministic Polynomial）难问题,警示传播算法（warning propagation）是一种基于因子图的消息传递算法,可用于求解组合优化问题.首先,本文借助隐马尔可夫模型将无向图转换为因子图,将求解最小割映射为求解因子图的相应问题.进而设计一种求解最小割的警示传播算法.最后,选取了几组随机无向图实例进行数值实验,实验结果表明,该算法在求解速度上优于同类算法.