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 spectral approach to learning structural variations in graphs

This paper shows how to construct a linear deformable model for graph structure by performing principal components analysis (PCA) on the vectorised adjacency matrix. We commence by using correspondence information to place the nodes of each of a set of graphs in a standard reference order. Using the correspondences order, we convert the adjacency matrices to long-vectors and compute the long-vector covariance matrix. By projecting the vectorised adjacency matrices onto the leading eigenvectors of the covariance matrix, we embed the graphs in a pattern-space. We illustrate the utility of the resulting method for shape-analysis.     

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.     

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

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

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     

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.     

Polyhedral Characteristics of Balanced and Unbalanced Bipartite Subgraph Problems

We study the polyhedral properties of three problems of constructing an optimal complete bipartite subgraph (a biclique) in a bipartite graph. In the first problem, we consider a balanced biclique with the same number of vertices in both parts and arbitrary edge weights. In the other two problems we are dealing with unbalanced subgraphs of maximum and minimum weight with non-negative edges. All three problems are established to be NP-hard. We study the polytopes and the cone decompositions of these problems and their 1-skeletons. We describe the adjacency criterion in the 1-skeleton of the polytope of the balanced complete bipartite subgraph problem. The clique number of the 1-skeleton is estimated from below by a superpolynomial function. For both unbalanced biclique problems we establish the superpolynomial lower bounds on the clique numbers of the graphs of nonnegative cone decompositions. These values characterize the time complexity in a broad class of algorithms based on linear comparisons.     

Maximal Biclique Subgraphs and Closed Pattern Pairs of the Adjacency Matrix: A One-to-One Correspondence and Mining Algorithms

Maximal biclique (also known as complete bipartite) subgraphs can model many applications in Web mining, business, and bioinformatics. Enumerating maximal biclique subgraphs from a graph is a computationally challenging problem, as the size of the output can become exponentially large with respect to the vertex number when the graph grows. In this paper, we efficiently enumerate them through the use of closed patterns of the adjacency matrix of the graph. For an undirected graph G without self-loops, we prove that 1) the number of closed patterns in the adjacency matrix of G is even, 2) the number of the closed patterns is precisely double the number of maximal biclique subgraphs of G, and 3) for every maximal biclique subgraph, there always exists a unique pair of closed patterns that matches the two vertex sets of the subgraph. Therefore, the problem of enumerating maximal bicliques can be solved by using efficient algorithms for mining closed patterns, which are algorithms extensively studied in the data mining field. However, this direct use of existing algorithms causes a duplicated enumeration. To achieve high efficiency, we propose an O(mn) time delay algorithm for a nonduplicated enumeration, in particular, for enumerating those maximal bicliques with a large size, where m and n. are the number of edges and vertices of the graph, respectively. We evaluate the high efficiency of our algorithm by comparing it to state- of-the-art algorithms on three categories of graphs: randomly generated graphs, benchmarks, and a real-life protein interaction network. In this paper, we also prove that if self-loops are allowed in a graph, then the number of closed patterns in the adjacency matrix is not necessarily even, but the maximal bicliques are exactly the same as those of the graph after removing all the self-loops.     

Hardness and approximation of minimum maximal matchings

In this paper, we consider the minimum maximal matching problem in some classes of graphs such as regular graphs. We show that the minimum maximal matching problem is NP-hard even in regular bipartite graphs, and a polynomial time exact algorithm is given for almost complete regular bipartite graphs. From the approximation point of view, it is well known that any maximal matching guarantees the approximation ratio of 2 but surprisingly very few improvements have been obtained. In this paper we give improved approximation ratios for several classes of graphs. For example any algorithm is shown to guarantee an approximation ratio of (2-o(1)) in graphs with high average degree. We also propose an algorithm guaranteeing for any graph of maximum degree Δ an approximation ratio of (2?1/Δ), which slightly improves the best known results. In addition, we analyse a natural linear-time greedy algorithm guaranteeing a ratio of (2?23/18k) in k-regular graphs admitting a perfect matching.     

Asymptotic estimates for the higher moments of the expected behavior of straight insertion sort

Perfect elimination (PE) bipartite graphs were introduced by Golumbic and Goss where they were shown to represent sparse matrices (non-symmetric) on which Gaussian elimination may be performed without fill-in. We propose an O(n³) recognition algorithm for PE bipartite graphs which improves on the O(n⁵) procedure suggested by Golumbic and Goss for this problem.     

Sum Coloring of Bipartite Graphs with Bounded Degree

We consider the Chromatic Sum Problem on bipartite graphs which appears to be much harder than the classical Chromatic Number Problem. We prove that the Chromatic Sum Problem is NP-complete on planar bipartite graphs with $\Delta \leq 5$, but polynomial on bipartite graphs with $\Delta \leq 3$, for which we construct an $O(n^{2})$-time algorithm. Hence, we tighten the borderline of intractability for this problem on bipartite graphs with bounded degree, namely: the case $\Delta =3$ is easy, $% \Delta =5$ is hard. Moreover, we construct a $27/26$-approximation algorithm for this problem thus improving the best known approximation ratio of $10/9$.     

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.     

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.

     

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.     

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.     

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

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

A note on a linear time algorithm for constructing adjacency graphs of 3D FEA data

In this paper, we present an algorithm for constructing adjacency graphs of 3D finite element analysis (FEA) data. Adjacency graphs are created to represent the connectivities of FEA data cells. They are used in most visualization methods for FEA data. We stress that in many engineering applications FEA data sets do not contain the adjacency information. This is opposite to computer-aided geometric design where, e.g., the winged edge geometrical representation is usually generated and utilized. By establishing intermediate data structures and using bin-sorting, we developed an efficient algorithm for constructing such graphs. The total time complexity of the algorithm is linear in the number of data cells.     

基于k-频繁子图聚类的二分图匿名方法

针对以二分图形式发布的社会网络隐私泄露问题,提出了一种面向敏感边识别攻击的社会网络二分图匿名方法。在已有k-安全分组的理论基础上,结合二分图的稀疏性和敏感边识别攻击形式,分别提出了正单向、逆单向以及完全（c1,c2）-安全性原则,并在此基础上,形式化地定义了一类抗敏感边识别攻击的社会网络二分图安全匿名问题;同时,还提出了一种基于k-频繁子图聚类的二分图划分算法和一种基于二分图（c1,c2）-安全性的匿名算法来保证发布二分图的安全性。实验结果表明,该算法在与已有方法相当时间开销的前提下,能产生更小的信息损失度,有效地抵制了敏感边识别攻击,实现了二分图的安全发布。     

On the complexity of signed and minus total domination in graphs

In this paper we present unified methods to solve the minus and signed total domination problems for chordal bipartite graphs and trees in O(n²) and O(n+m) time, respectively. We also prove that the decision problem for the signed total domination problem on doubly chordal graphs is NP-complete. Note that bipartite permutation graphs, biconvex bipartite graphs, and convex bipartite graphs are subclasses of chordal bipartite graphs.     

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.