Comparing large-scale graphs based on quantum probability theory

DOI10.1016/J.AMC.2019.03.061zbMATH Open1428.05186arXiv1807.00252OpenAlexW2962973811WikidataQ128008276 ScholiaQ128008276MaRDI QIDQ2279341FDOQ2279341

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)

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.

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

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

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)

Cites Work

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

Cited In (4)

• Graph comparison via nonlinear quantum search
• A distance measure for large graphs based on prime graphs
• Fast computation of von Neumann entropy for large-scale graphs via quadratic approximations
• Cospectrality of multipartite 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)