Measuring graph similarity through continuous-time quantum walks and the quantum Jensen-Shannon divergence

In this paper we propose a quantum algorithm to measure the similarity between a pair of unattributed graphs. We design an experiment where the two graphs are merged by establishing a complete set of connections between their nodes and the resulting structure is probed through the evolution of continuous-time quantum walks. In order to analyze the behavior of the walks without causing wave function collapse, we base our analysis on the recently introduced quantum Jensen-Shannon divergence. In particular, we show that the divergence between the evolution of two suitably initialized quantum walks over this structure is maximum when the original pair of graphs is isomorphic. We also prove that under special conditions the divergence is minimum when the sets of eigenvalues of the Hamiltonians associated with the two original graphs have an empty intersection.

Attributed graph similarity from the quantum Jensen-Shannon divergence

One of the most fundamental problem that we face in the graph domain is that of establishing the similarity, or alternatively the distance, between graphs. In this paper, we address the problem of measuring the similarity between attributed graphs. In particular, we propose a novel way to measure the similarity through the evolution of a continuous-time quantum walk. Given a pair of graphs, we create a derived structure whose degree of symmetry is maximum when the original graphs are isomorphic, and where a subset of the edges is labeled with the similarity between the respective nodes. With this compositional structure to hand, we compute the density operators of the quantum systems representing the evolution of two suitably defined quantum walks. We define the similarity between the two original graphs as the quantum Jensen-Shannon divergence between these two density operators, and then we show how to build a novel kernel on attributed graphs based on the proposed similarity measure. We perform an extensive experimental evaluation both on synthetic and real-world data, which shows the effectiveness the proposed approach. © 2013 Springer-Verlag.

Using Covariance as a Similarity Measure for Document Language Identification in Hard Contexts

2000 Mathematics Subject Classification: C2P99.

Averaging operators and set-valued maps

MSC 2010: 54C35, 54C60.

Some Coefficient Estimates for Polynomials on the Unit Interval

2000 Mathematics Subject Classification: 26C05, 26C10, 30A12, 30D15, 42A05, 42C05.

Approximation of Univariate Set-Valued Functions - an Overview

2000 Mathematics Subject Classification: 26E25, 41A35, 41A36, 47H04, 54C65.

Interval Oscillation for Second Order Nonlinear Differential Equations with a Damping Term

2000 Mathematics Subject Classification: 34C10, 34C15.

Uniform G-Convexity for Vector-Valued Lp Spaces

2000 Mathematics Subject Classification: 46B20.

Determining the change of Brillouin frequency shift by using the similarity matching method

We have proposed a similarity matching method (SMM) to obtain the change of Brillouin frequency shift (BFS), in which the change of BFS can be determined from the frequency difference between detecting spectrum and selected reference spectrum by comparing their similarity. We have also compared three similarity measures in the simulation, which has shown that the correlation coefficient is more accurate to determine the change of BFS. Compared with the other methods of determining the change of BFS, the SMM is more suitable for complex Brillouin spectrum profiles. More precise result and much faster processing speed have been verified in our simulation and experiments. The experimental results have shown that the measurement uncertainty of the BFS has been improved to 0.72 MHz by using the SMM, which is almost one-third of that by using the curve fitting method, and the speed of deriving the BFS change by the SMM is 120 times faster than that by the curve fitting method.

The zooplankton of the Ráckeve-Soroksár Danube: Spatio-temporal changes and similarity patterns

The Ráckeve-Soroksár Danube has a great importance as it is the second largest side arm in the Hungarian section of the river Danube and many demands of exploitation are expected. The aim of this study is to analyse the spatial and temporal changes of the zooplankton (Copepoda, Cladocera) community in this river arm, moreover the similarity patterns of zooplankton communities in different Hungarian water bodies are presented in special consideration of the Ráckeve-Soroksár Danube. Basically this study is based on data from literature, however our data are also used for compiling the database for the spatio-temporal changes of the Ráckeve-Soroksár Danube. We put emphasis on the three typical sections of the side arm, as these are stressed due to hydromorphological aspects, but creating artificial borders are objectionable as well. The results show that both spatial and temporal changes are evident, what is more, the stagnant water character of the side arm should be underlined.

Indication strength of coenological similarity patterns based on genus-level taxon lists and prevalence distribution

Several methods and indicators can be used to evaluate the coenological state of a given habitat, the ones which can be created simply, quickly, standardizably and reliably and which can be used to exactly quantify the state of a given habitat in point of numbers can be of outstanding practical importance in ecology. One possible method is the examination of the genera which can be found in a given habitat in great abundance and have little number of species and various ecological characteristics. For this purpose one of the most appropriate groups is that of ground-dwelling oribatid mites (Acari: Oribatida). In our research, joining the bioindication methodological project of the “Adaptation to Climate Change” Research Group of the Hungarian Academy of Sciences, the indication strength of genus-level taxon lists and the effects of the main pattern-generating factors creating similarity patterns were analysed with the help of data series on oribatid mites collected by us and originating from literature. Our aim was to develop a method with the help of which the difference expressed with distance functions between two oribatid mite genus lists originating from any sources can correspond to spatial and temporal scales. Our results prove that these genus lists are able to express the spatial distance of the habitats. With the help of this base of comparison changes in disturbed or transformed habitats can be expressed by means of oribatid mite communities, with spatial and temporal distances.