A selected tour of the theory of identification matrices

A selected tour of the theory of identification matrices is offered here. We show that, among other things, shortest-path adjacency matrices are identification matrices for all simple graphs and adjacency matrices are identification matrices for all bipartite graphs. Additionally, we provide an improved proof that augmented adjacency matrices satisfying the circular 1's property are identification matrices. We also present a characterization of doubly convex bipartite graphs by identification matrices. Based on the theory of identification matrices, we describe an improved method for testing isomorphism between Γ circular arc graphs. The sequential algorithm can be implemented to run in O(n²) time and is optimal if the graphs are given as (augmented) adjacency matrices, so to speak.     

Spectral embedding of graphs

In this paper we explore how to embed symbolic relational graphs with unweighted edges in a pattern-space. We adopt a graph-spectral approach. We use the leading eigenvectors of the graph adjacency matrix to define eigenmodes of the adjacency matrix. For each eigenmode, we compute vectors of spectral properties. These include the eigenmode perimeter, eigenmode volume, Cheeger number, inter-mode adjacency matrices and intermode edge-distance. We embed these vectors in a pattern-space using two contrasting approaches. The first of these involves performing principal or independent components analysis on the covariance matrix for the spectral pattern vectors. The second approach involves performing multidimensional scaling on the L2 norm for pairs of pattern vectors. We illustrate the utility of the embedding methods on neighbourhood graphs representing the arrangement of corner features in 2D images of 3D polyhedral objects. Two problems are investigated. The first of these is the clustering of graphs representing distinct objects viewed from different directions. The second is the identification of characteristic views of single objects. These two studies reveal that both embedding methods result in well-structured view spaces for graph-data extracted from 2D views of 3D objects.     

On Total Unimodularity of Edge–Edge Adjacency Matrices

We consider total unimodularity for edge–edge adjacency matrices that represent adjacency relations between pairs of edges in a graph. These matrices appear in integer programming formulations of the minimum maximal matching problem, the edge dominating set problem, and so on. We investigate the problem of characterizing graphs that have totally unimodular edge–edge adjacency matrices, and give a necessary and sufficient condition for characterization. This condition is the first characterization for total unimodularity of edge–edge adjacency matrices.     

图同构的矩阵初等变换判定及算法设计

判断图同构的一种有用的方法是对图的邻接矩阵进行初等变换,变成另一个图的邻接矩阵。不幸的是,当初等变换后两个矩阵不能相等时,并不能说明两个图不同构,因为可能存在另一种变换途径,使得两个矩阵相等。另一方面,这种穷尽变换途径的方法有n!种可能(n为图的顶点个数);当n太大时,尝试每一种可能来说明两个图是否同构是不可行的,是一个NP难问题。文章提出了一个简单有效的判断图同构的方法。首先,利用邻接矩阵生成行码距异或矩阵和行码距同或矩阵;其次,寻找邻接矩阵、行码距异或矩阵、行码距同或矩阵间保持行元素一样的行-行置换;如果这种置换存在,则图同构,否则不同构。最后,根据行-行置换确定出同构函数,它给出了两个图的顶点间具有保持相邻关系的一一对应。     

Graph edit distance from spectral seriation

This paper is concerned with computing graph edit distance. One of the criticisms that can be leveled at existing methods for computing graph edit distance is that they lack some of the formality and rigor of the computation of string edit distance. Hence, our aim is to convert graphs to string sequences so that string matching techniques can be used. To do this, we use a graph spectral seriation method to convert the adjacency matrix into a string or sequence order. We show how the serial ordering can be established using the leading eigenvector of the graph adjacency matrix. We pose the problem of graph-matching as a maximum a posteriori probability (MAP) alignment of the seriation sequences for pairs of graphs. This treatment leads to an expression in which the edit cost is the negative logarithm of the a posteriori sequence alignment probability. We compute the edit distance by finding the sequence of string edit operations which minimizes the cost of the path traversing the edit lattice. The edit costs are determined by the components of the leading eigenvectors of the adjacency matrix and by the edge densities of the graphs being matched. We demonstrate the utility of the edit distance on a number of graph clustering problems.     

R-Kleene: A High-Performance Divide-and-Conquer Algorithm for the All-Pair Shortest Path for Densely Connected Networks

We propose a novel divide-and-conquer algorithm for the solution of the all-pair shortest-path problem for directed and dense graphs with no negative cycles. We propose R-Kleene, a compact and in-place recursive algorithm inspired by Kleene's algorithm. R-Kleene delivers a better performance than previous algorithms for randomly generated graphs represented by highly dense adjacency matrices, in which the matrix components can have any integer value. We show that R-Kleene, unchanged and without any machine tuning, yields consistently between 1/7 and 1/2 of the peak performance running on five very different uniprocessor systems.     

基于图谱分解的人脸特征描述

文章探索用图谱方法嵌入且分析人脸几何特征,以图的邻接矩阵的主要特征向量来定义邻接矩阵的特征模。对每个特征模,计算谱特征向量,包括主分量特征值,模间邻接矩阵。用局部线性嵌入方法(LLE)方法嵌入这些向量到一个模式空间。另外,用人脸特征点来表示邻接图,并以几何平均图和模式特征向量的平均图两种方法对比描述不同嵌入方法的人脸特征。实验结果表明,谱向量特征平均方法能够较好地描述人脸。     

Laplacian matrices of weighted digraphs represented as quantum states

Representing graphs as quantum states is becoming an increasingly important approach to study entanglement of mixed states, alternate to the standard linear algebraic density matrix-based approach of study. In this paper, we propose a general weighted directed graph framework for investigating properties of a large class of quantum states which are defined by three types of Laplacian matrices associated with such graphs. We generalize the standard framework of defining density matrices from simple connected graphs to density matrices using both combinatorial and signless Laplacian matrices associated with weighted directed graphs with complex edge weights and with/without self-loops. We also introduce a new notion of Laplacian matrix, which we call signed Laplacian matrix associated with such graphs. We produce necessary and/or sufficient conditions for such graphs to correspond to pure and mixed quantum states. Using these criteria, we finally determine the graphs whose corresponding density matrices represent entangled pure states which are well known and important for quantum computation applications. We observe that all these entangled pure states share a common combinatorial structure.     

Adjacency matrix generation from the image of graphs: a morphological approach

This paper presents a system for automatic generation of the adjacency matrix from the image of graphs. The graph, we assume, is printed or hand printed and available as a part of a document either separately or along with text and picture. A morphology-based approach is used here to separate components of the graphs: vertices, edges and labels. A novel technique is proposed to traverse the nonplanar edges joining the vertices. The proposed method may be used for logical compression of the information contained in the graph image in the form of an adjacency matrix. It may also be used to replace the cumbersome, error-prone and time-consuming manual method of generation of the adjacency matrix for graphs with large number of vertices and complex interconnections.     

TreeMatrix: A Hybrid Visualization of Compound Graphs

We present a hybrid visualization technique for compound graphs (i.e. networks with a hierarchical clustering defined on the nodes) that combines the use of adjacency matrices, node‐link and arc diagrams to show the graph, and also combines the use of nested inclusion and icicle diagrams to show the hierarchical clustering. The graph visualized with our technique may have edges that are weighted and/or directed. We first explore the design space of visualizations of compound graphs and present a taxonomy of hybrid visualization techniques. We then present our prototype, which allows clusters (i.e. subtrees) of nodes to be grouped into matrices or split apart using a radial menu. We also demonstrate how our prototype can be used in the software engineering domain, and compare it to the commercial matrix‐based visualization tool Lattix using a qualitative user study.     

基于竞争性协同表示的局部判别投影特征提取

特征提取算法中利用样本间的协同表示关系构造邻接图只考虑所有训练样本的协同能力,而忽视了每一类训练样本的内在竞争能力。为此,本文提出一种基于竞争性协同表示的局部判别投影特征提取算法（competitive collaborative repesentation-based local discrininant projection for feature extraction,CCRLDP）,该算法利用基于具有竞争性协同表示的方法构造类间图和类内图,考虑到邻接图中各类型系数的影响,引入保留正表示系数的思想稀疏化邻接图,通过计算类内散度矩阵和类间散度矩阵来刻画图像的局部结构并得其最优投影矩阵。在一些数据集上的实验结果表明,相比同类基于局部判别投影的特征提取算法,该算法具有很高的识别率,并在噪声和遮挡上具有良好的鲁棒性,该算法能有效地提高图像的识别效率。     

An eigendecomposition approach to weighted graph matching problems

An approximate solution to the weighted-graph-matching problem is discussed for both undirected and directed graphs. The weighted-graph-matching problem is that of finding the optimum matching between two weighted graphs, which are graphs with weights at each arc. The proposed method uses an analytic instead of a combinatorial or iterative approach to the optimum matching problem. Using the eigendecompositions of the adjacency matrices (in the case of the undirected-graph-matching problem) or Hermitian matrices derived from the adjacency matrices (in the case of the directed-graph-matching problem), a matching close to the optimum can be found efficiently when the graphs are sufficiently close to each other. Simulation results are given to evaluate the performance of the proposed method     

EvoArch: An evolutionary algorithm for architectural layout design

The architectural layout design problem, which is concerned with the finding of the best adjacencies between functional spaces among many possible ones under given constraints, can be formulated as a combinatorial optimization problem and can be solved with an Evolutionary Algorithm (EA). We present functional spaces and their adjacencies in form of graphs and propose an EA called EvoArch that works with a graph-encoding scheme. EvoArch encodes topological configuration in the adjacency matrices of the graphs that they represent and its reproduction operators operate on these adjacency matrices. In order to explore the large search space of graph topologies, these reproduction operators are designed to be unbiased so that all nodes in a graph have equal chances of being selected to be swapped or mutated. To evaluate the fitness of a graph, EvoArch makes use of a fitness function that takes into consideration preferences for adjacencies between different functional spaces, budget and other design constraints. By means of different experiments, we show that EvoArch can be a very useful tool for architectural layout design tasks.     

Laplacian versus adjacency matrix in quantum walk search

A quantum particle evolving by Schrödinger’s equation contains, from the kinetic energy of the particle, a term in its Hamiltonian proportional to Laplace’s operator. In discrete space, this is replaced by the discrete or graph Laplacian, which gives rise to a continuous-time quantum walk. Besides this natural definition, some quantum walk algorithms instead use the adjacency matrix to effect the walk. While this is equivalent to the Laplacian for regular graphs, it is different for non-regular graphs and is thus an inequivalent quantum walk. We algorithmically explore this distinction by analyzing search on the complete bipartite graph with multiple marked vertices, using both the Laplacian and adjacency matrix. The two walks differ qualitatively and quantitatively in their required jumping rate, runtime, sampling of marked vertices, and in what constitutes a natural initial state. Thus the choice of the Laplacian or adjacency matrix to effect the walk has important algorithmic consequences.     

Volume-based large dynamic graph analysis supported by evolution provenance

We present an approach for the visualization and interactive analysis of dynamic graphs that contain a large number of time steps. A specific focus is put on the support of analyzing temporal aspects in the data. Central to our approach is a static, volumetric representation of the dynamic graph based on the concept of space-time cubes that we create by stacking the adjacency matrices of all time steps. The use of GPU-accelerated volume rendering techniques allows us to render this representation interactively. We identified four classes of analytics methods as being important for the analysis of large and complex graph data, which we discuss in detail: data views, aggregation and filtering, comparison, and evolution provenance. Implementations of the respective methods are presented in an integrated application, enabling interactive exploration and analysis of large graphs. We demonstrate the applicability, usefulness, and scalability of our approach by presenting two examples for analyzing dynamic graphs. Furthermore, we let visualization experts evaluate our analytics approach.

     

Graph isomorphism and identification matrices: parallel algorithms

In this paper, we explore some properties of identification matrices and exhibit some uses of identification matrices in studying the graph isomorphism problem, a famous open problem. We show that, given two graphs in the form of a certain identification matrix, isomorphism can be tested efficiently in parallel if at least one matrix satisfies the circular 1s property, and more efficiently in parallel if at least one matrix satisfies the consecutive 1s property. Graphs which have identification matrices satisfying the consecutive 1s property include, among others, proper interval graphs and doubly convex bipartite graphs. The result presented here substantially broadens the class of graphs for which there are known efficient parallel isomorphism testing algorithms     

A SimpleO(log N) Time Parallel Algorithm for Testing Isomorphism of Maximal Outerplanar Graphs

Maximal outerplanar graphs constitute an important class of graphs, often encountered in various applications, e.g., computational geometry, robotics, etc. In this paper, we propose a parallel algorithm for testing the isomorphism of maximal outerplanar graphs. Given the ordered adjacency lists of the two graphs, the proposed algorithm tests their isomorphism inO(log N) time usingNprocessors, for graphs withNnodes on an EREW shared memory model, as well as on a hypercube arhitecture. When the adjacency matrices of the graphs are given, this algorithm can be redesigned onN²processors to run inO(log N) time.     

Structure Indicators for Transportation Graph Analysis I: Planar Connected Simple Graphs

The paper deals with the representation of a transportation infrastructure by a planar connected simple graph and aims at studying its features through the analysis of graph properties. All planar and connected graphs with 4 up to 7 edges are analysed and compared to extract the most suitable parameters to investigate some network features. Then, a set of 41 graphs representing some actual underground networks are also analysed. Besides, as a third scenario, the underground network of Milan, along its development in years, is proposed in order to apply the proposed methodology. Many parameters are taken into consideration. Some of them are already discussed in literature, such as the eigenvalues and gaps of adjacency matrix or such as the “classical” parameters α, β, γ. Others, such as the first two Betti numbers, are new for these applications. In order to overcome the problem of comparing features of graphs with different size, the normalisation of these parameters is considered. Some relationships between Betti numbers, eigenvalues, and classical parameters are also investigated. Results show that the eigenvalues and gaps of the adjacency matrix well represent some features of the graphs while combining them with the Betti numbers, a more significant interpretation can be achieved. Particularly, their normalised values are able to describe the increasing complexity of a graph.