Comparing large-scale graphs based on quantum probability theory

DOI10.1016/J.AMC.2019.03.061MaRDI QIDQ2279341zbMATH OpenOpenAlexWikidataFDO

Authors Hayoung Choi, Yifei Shen, Yuanming Shi, Hosoo Lee

Publication date 12 December 2019

Published in Applied Mathematics and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1807.00252

zbMATH Keywords

quantum probabilitymoment matrixlarge-scale datasetscomparing graphs

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Quantum information, communication, networks (quantum-theoretic aspects) (81P45)

Abstract: In this paper, a new measurement to compare two large-scale graphs based on the theory of quantum probability is proposed. An explicit form for the spectral distribution of the corresponding adjacency matrix of a graph is established. Our proposed distance between two graphs is defined as the distance between the corresponding moment matrices of their spectral distributions. It is shown that the spectral distributions of their adjacency matrices in a vector state includes information not only about their eigenvalues, but also about the corresponding eigenvectors. Moreover, we prove that such distance is graph invariant and sub-structure invariant. Examples with various graphs are given, and distances between graphs with few vertices are checked. Computational results for real large-scale networks show that its accuracy is better than any existing methods and time cost is extensively cheap.

Recommendations

• Comparing large graphs efficiently by margins of feature vectors
• Attributed graph similarity from the quantum Jensen-Shannon divergence
• Spectral classes of regular, random, and empirical graphs
• A quantum Jensen-Shannon graph kernel for unattributed graphs
• A new dissimilarity measure for comparing labeled graphs

Cites work

• scientific article; zbMATH DE number 3150484 (Why is no real title available?)
• A DNA-based graph encoding scheme with its applications to graph isomorphism problems
• A comparative analysis of the Tanimoto index and graph edit distance for measuring the topological similarity of trees
• A determinant characterization of moment sequences with finitely many mass points
• A new dissimilarity measure for comparing labeled graphs
• A note about cospectral graphs for the adjacency and normalized Laplacian matrices
• A similarity measure for graphs with low computational complexity
• A study of graph spectra for comparing graphs and trees
• A survey of graph edit distance
• Bounds on the number of closed walks in a graph and its applications
• Comparing large graphs efficiently by margins of feature vectors
• Cospectral graphs and the generalized adjacency matrix
• Distance between distance spectra of graphs
• Distance between spectra of graphs
• Distance between the normalized Laplacian spectra of two graphs
• Enumeration of cospectral graphs.
• Fifty years of graph matching, network alignment and network comparison
• Global similarity tests of physical designs of circuits: a complex network approach
• Graph distance measures based on topological indices revisited
• Inequalities for the number of walks in graphs
• Isospectral graphs and isoperimetric constants
• Measures of distance between probability distributions
• Number of walks and degree powers in a graph
• On Information and Sufficiency
• Spectral analysis of growing graphs. A quantum probability point of view
• Spectral distances of graphs
• Spectral distances on graphs

Cited in

(4)

• Cospectrality of multipartite graphs
• Graph comparison via nonlinear quantum search
• Fast computation of von Neumann entropy for large-scale graphs via quadratic approximations
• A distance measure for large graphs based on prime graphs

This page was built for publication: Comparing large-scale graphs based on quantum probability theory

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2279341)