基于潜在组分配及对比学习增强的符号二值图神经网络

针对符号二值网络的节点异质性及三角形形式平衡理论不适用性的问题,提出一种基于潜在类分配及对比学习增强的符号二值图神经网络模型,其通过同质和异质双空间的互相补充来充分提取网络的隐式和显式信息。在同质空间,采用可学习的潜在组对节点进行分配并将节点看做多个潜在组的组合,然后通过训练来自动挖掘节点间的信息。在异质空间,对节点邻居进行有方向区分的注意力聚合,然后采用网络重建的互信息对比学习来引导聚合过程以获得表达能力更强的表示向量。在符号链接预测任务上与多种相关模型进行对比实验,实验结果显示所提出的模型在四个真实数据集上采用四种评价指标获取的16个评价结果中,12个评价结果可以取得最优值,验证了所提出模型的有效性。     

Inexact graph matching by means of estimation of distribution algorithms

Estimation of distribution algorithms (EDAs) are a quite recent topic in optimization techniques. They combine two technical disciplines of soft computing methodologies: probabilistic reasoning and evolutionary computing. Several algorithms and approaches have already been proposed by different authors, but up to now there are very few papers showing their potential and comparing them to other evolutionary computational methods and algorithms such as genetic algorithms (GAs). This paper focuses on the problem of inexact graph matching which is NP-hard and requires techniques to find an approximate acceptable solution. This problem arises when a nonbijective correspondence is searched between two graphs. A typical instance of this problem corresponds to the case where graphs are used for structural pattern recognition in images. EDA algorithms are well suited for this type of problems.

This paper proposes to use EDA algorithms as a new approach for inexact graph matching. Also, two adaptations of the EDA approach to problems with constraints are described as two techniques to control the generation of individuals, and the performance of EDAs for inexact graph matching is compared with the one of GAs.     

Properties of a hierarchical network based on the star graph

This paper introduces a new class of interconnection networks named star-pyramid. An n-level star-pyramid is formed by piling up star graphs of dimensions 1 to n in a hierarchy, connecting any node in each i-dimensional star, 1 < i ? n, to a node in the (i − 1)-dimensional star whose index is reached by removing the i symbol from the index of the former node in the i-dimensional star graph. Having extracted the properties of the new topology, featuring topological properties, a minimal routing algorithm, a simple but efficient broadcast algorithm, Hamiltonicity and pancyclicity, we then compare the network properties of the proposed topology and the well-known pyramid topology. We show that the star-pyramid has some more attractive properties than its equivalent pyramid. Finally, we propose two variants of star-pyramid, namely the generic star-pyramid and wrapped star-pyramid, as topologies with improved scalability, fault-tolerance, and diameter.     

Generalized median graph computation by means of graph embedding in vector spaces

The median graph has been presented as a useful tool to represent a set of graphs. Nevertheless its computation is very complex and the existing algorithms are restricted to use limited amount of data. In this paper we propose a new approach for the computation of the median graph based on graph embedding. Graphs are embedded into a vector space and the median is computed in the vector domain. We have designed a procedure based on the weighted mean of a pair of graphs to go from the vector domain back to the graph domain in order to obtain a final approximation of the median graph. Experiments on three different databases containing large graphs show that we succeed to compute good approximations of the median graph. We have also applied the median graph to perform some basic classification tasks achieving reasonable good results. These experiments on real data open the door to the application of the median graph to a number of more complex machine learning algorithms where a representative of a set of graphs is needed.     

Web社会网络的粗糙属性图模型及应用

针对Web环境下的社会网络具有信息粗糙性的特征,即Web数据中有大量垃圾内容和垃圾链接,同时很多信息是不完整的、缺失的,且信息有重复现象存在等,在已提出的属性图模型基础上,结合粗糙集理论解决不完备信息的优势,首先提出粗糙顶点属性图和粗糙边属性图,进而给出粗糙属性图的概念,以对Web社会网络结构进行分析,使其能够描述复杂Web社会网络中的不完整信息以及动态变化的链接。其次对粗糙属性图的粗糙特性进行分析,给出粗糙顶点精度、粗糙边精度和粗糙图精度等概念,得出粗糙属性图的精度与顶点和边集属性划分程度有关的结论,即人们对图的认知程度与图的精度密切相关。最后,在中国知网上通过对论文作者进行查询得到粗糙图,并通过不断添加顶点属性,将图顶点划分得越来越精细,挖掘出要查询的作者合作关系图,从而说明粗糙属性图在社会网络分析中符合人们的认知过程。     

Disassembly line balancing under high variety of end of life states using a joint precedence graph approach

Disassembly is an important aspect of end of life product treatment, as well as having products disassembled in an efficient and responsible manner. Disassembly line balancing is a technique that enables a product to be disassembled as efficiently and economically viable as possible; however, considering all possible end of life (EOL) states of a product makes disassembly line balancing very difficult. The EOL state and the possibility of multiple recovery options of a product can alter both disassembly tasks and task times for the disassembly of the EOL product. This paper shows how generating a joint precedence graph based on the different EOL states of a product is beneficial to achieving an optimal line balance where traditional line balancing approaches are used. We use a simple example of a pen from the literature to show how a joint disassembly precedence graph is created and a laptop example for joint precedence graph generation and balancing. We run multiple scenarios where the EOL conditions have different probabilities and compare results for the case of deterministic task times. We also consider the possibility where some disassembly task times are normally distributed and show how a stochastic joint precedence graph can be created and used in a stochastic line balancing formulation.     

基于图论的PMU最优配置方法及比较

首先阐述了电力系统状态估计模型和进行PMU最优配置的准则,随后以系统的完全可观测为目标,介绍了基于图论的深度优先搜索法、GTP算法和最小生成树算法。应用上述算法分别对IEEE标准节点系统进行PMU最优配置仿真。仿真结果表明几种方法在解的多样性,计算时间等方面各具特色,适用于不同的配置需要。     

基于介度相关性的无标度网络抗毁性研究

复杂网络主要面临随机攻击和选择性攻击,在不同的攻击方式下复杂网络的抗毁性有很大差异。综合考虑复杂网络的抗毁性参数,以节点的度和介数中心性为度量参数,通过5种不同攻击方式对无标度网络的抗毁性进行测试,得到度和介数的实时测量值,动态分析攻击下无标度网络的介度相关性。实验结果表明,无标度网络在ID、RD攻击下介度满足幂律关系,而在IB、RB和随机攻击下不严格满足幂律关系。     

Bounded synchronisation of a time-varying dynamical network with nonidentical nodes

This paper investigates the global bounded synchronisation problem of complex dynamical networks of coupled nonidentical nodes with general time-varying topology through the Lyapunov function and graph theory. Several sufficient conditions in form of scalar inequalities are established so that the global bounded synchronisation of the general dynamical network can be evaluated by the stability of a linear time-varying system and the boundedness of a nonlinear function, both associated with the dynamics of nonidentical nodes. These analytical results are simple yet generic, without assuming the symmetry coupling configuration matrix or calculating their eigenvalues. They can be used to explore synchronisation issues of various complex networks. Numerical simulations show their effectiveness.     

面向图神经网络的对抗攻击与防御综述

面向已有的图神经网络的攻击与防御方法,较全面地综述了图神经网络对抗攻防技术与鲁棒性分析.首先,综述了图神经网络在不同任务下的对抗攻击与基于不同策略的防御方法,并全面介绍了鲁棒性分析技术;随后,介绍了常用的基准数据集与评价指标;最后,提出了未来可能的研究方向和发展趋势.     

Neural network model for the efficient calculation of Green's functions in layered media

In this article, neural networks are employed for fast and efficient calculation of Green's functions in a layered medium. Radial basis function networks (RBFNs) are effectively trained to estimate the coefficients and the exponents that represent a Green's function in the discrete complex image method (DCIM). Results show very good agreement with the DCIM, and the trained RBFNs are very fast compared with the corresponding DCIM. © 2003 Wiley Periodicals, Inc. Int J RF and Microwave CAE 13: 128–135, 2003.     

The generation of animated motion by means of a recurrent neural network

The possibility to use neural networks to guide animated motion sequences is investigated. The performance of two recurrent architectures, both derived from the cascade-correlation network, is compared. These architectures only differ in the objective function used to train the hidden units. Small differences in performance were observed, but both networks could successfully produce simple motion sequences. An animation environment was created to display arm movement and walking sequences.     

Analysis of a two-layered network by means of the power-series algorithm

We consider an extension of the classical machine-repair model, also known as the computer-terminal model or time-sharing model. As opposed to the classical model, we assume that the machines, apart from receiving service from the repairman, supply service themselves to queues of products. The extended model can be viewed as a two-layered queueing network, of which the first layer consists of two separate queues of products. Each of these queues is served by its own machine. The marginal and joint queue length distributions of the first-layer queues are hard to analyse in an exact fashion. Therefore, we apply the power-series algorithm to this model to obtain the light-traffic behaviour of the queue lengths symbolically. This leads to two accurate approximations for the marginal mean queue length. The first approximation, based on the light-traffic behaviour, is in closed form. The second approximation is based on an interpolation between the light-traffic behaviour and heavy-traffic results for the mean queue length. The obtained approximations are shown to work well for arbitrary loaded systems. The proposed numerical algorithm and approximations may prove to be very useful for system design and optimisation purposes in application areas such as manufacturing, computer systems and telecommunications.     

Generalization-oriented road line segmentation by means of an artificial neural network applied over a moving window

In line generalization, results depend very much on the characteristics of the line. For this reason it would be useful to obtain an automatic segmentation and enrichment of lines in order to apply to each section the best algorithm and the appropriate parameter. In this paper we present a methodology for applying a line-classifying backpropagation artificial neural network (BANN) for a line segmentation task. The procedure is based on the use of a moving window along the line to detect changes in the sinuosity and directionality of the line. A summary of the BANN design is presented, and a test is performed over a set of roads from a 1:25k scale map with a recommendation of the value of the parameters of the moving window. Segmentation results were assessed by an independent group of experts; a summary of the evaluation procedure is shown.     

Inexact graph matching for model-based recognition: Evaluation and comparison of optimization algorithms

A method for segmentation and recognition of image structures based on graph homomorphisms is presented in this paper. It is a model-based recognition method where the input image is over-segmented and the obtained regions are represented by an attributed relational graph (ARG). This graph is then matched against a model graph thus accomplishing the model-based recognition task. This type of problem calls for inexact graph matching through a homomorphism between the graphs since no bijective correspondence can be expected, because of the over-segmentation of the image with respect to the model. The search for the best homomorphism is carried out by optimizing an objective function based on similarities between object and relational attributes defined on the graphs. The following optimization procedures are compared and discussed: deterministic tree search, for which new algorithms are detailed, genetic algorithms and estimation of distribution algorithms. In order to assess the performance of these algorithms using real data, experimental results on supervised classification of facial features using face images from public databases are presented.     

Internet资源属性关系的新拓扑模型——时变半边图

引入半边概念描述Internet资源的特征属性，为网络环境下各类资源特征属性建立一个统一描述框架；扩展一般情况下的资源关系表示图，提出了资源属性关系的时变半边图模型；以网络的无尺度特性作为资源关联关系的演化规律的理论依据，给出时变半边图的一个具体生成算法。时变半边图能更方便地反映资源属性之间的动态拓扑关系，具有很好的可扩充性，可望再现真实网络的无尺度特性。     

On simultaneous straight-line grid embedding of a planar graph and its dual

Simultaneous representations of planar graphs and their duals normally require that the dual vertices to be placed inside their corresponding primal faces, and the edges of the dual graph to cross only their corresponding primal edges. Erten and Kobourov [C. Erten, S.G. Kobourov, Simultaneous embedding of a planar graph and its dual on the grid, Theory Computer Systems 38 (2005) 313-327] provided a linear time algorithm on simultaneous straight-line grid embedding of a 3-connected planar graph and its dual such that all the vertices are placed on grid points and each edge is drawn as one straight-line segment except for one which is drawn using two segments. Their drawing size is (2n−2)×(2n−2), where n is the total number of vertices in the graph and its dual. They raised an open question on whether there is a large class of planar graphs that allows this simultaneous straight-line grid embedding on a smaller grid. We answer this open question by giving a linear time simultaneous straight-line grid embedding algorithm for a 3-connected planar graph and its dual on a grid of size (n−1)×n.     

An application of a discrete wavelet transform and a back-propagation neural network algorithm for fault diagnosis on single-circuit transmission line

This article proposes an application of the discrete wavelet transform (DWT) and back-propagation neural networks (BPNN) for fault diagnosis on single-circuit transmission line. ATP/EMTP is used to simulate fault signals. The mother wavelet daubechies4 (db4) is used to decompose the high-frequency component of these signals. In addition, characteristics of the fault current at various fault inception angles, fault locations and faulty phases are detailed. The DWT is employed in extracting the high frequency component contained in the fault currents, and the coefficients of the first scale from the DWT that can detect fault are investigated, and the decision algorithm is constructed based on the BPNN. The results show that the proposed technique provides satisfactory results.     

Towards a framework for multiple artificial neural network topologies validation by means of statistics

Artificial neural networks (ANNs) are flexible computing tools that have been applied to a wide range of domains with a notable level of accuracy. However, there are multiple choices of ANNs classifiers in the literature that produce dissimilar results. As a consequence of this, the selection of this classifier is crucial for the overall performance of the system. In this work, an integral framework is proposed for the optimization of different ANN classifiers based on statistical hypothesis testing. The framework is tested in a real ballistic scenario. The new quality measures introduced, based on the Student t‐test, and employed throughout the framework, ensure the validity of results from a statistical standpoint; they reduce the appearance of experimental errors or the appearance of possible randomness. Results show the relevance of this framework, proving that its application improves the performance and efficiency of multiple classifiers.