The Eccentric Connectivity Polynomial of some Graph Operations

The eccentric connectivity index of a graph G, ξ^C, was proposed by Sharma, Goswami and Madan. It is defined as ξ^C(G) = ∑ u ∈ V(G) degG(u)εG(u), where degG(u) denotes the degree of the vertex x in G and εG(u) = Max{d(u, x) | x ∈ V (G)}. The eccentric connectivity polynomial is a polynomial version of this topological index. In this paper, exact formulas for the eccentric connectivity polynomial of Cartesian product, symmetric difference, disjunction and join of graphs are presented.

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.

A quantum Jensen-Shannon graph kernel for unattributed graphs

In this paper, we use the quantum Jensen-Shannon divergence as a means of measuring the information theoretic dissimilarity of graphs and thus develop a novel graph kernel. In quantum mechanics, the quantum Jensen-Shannon divergence can be used to measure the dissimilarity of quantum systems specified in terms of their density matrices. We commence by computing the density matrix associated with a continuous-time quantum walk over each graph being compared. In particular, we adopt the closed form solution of the density matrix introduced in Rossi et al. (2013) [27,28] to reduce the computational complexity and to avoid the cumbersome task of simulating the quantum walk evolution explicitly. Next, we compare the mixed states represented by the density matrices using the quantum Jensen-Shannon divergence. With the quantum states for a pair of graphs described by their density matrices to hand, the quantum graph kernel between the pair of graphs is defined using the quantum Jensen-Shannon divergence between the graph density matrices. We evaluate the performance of our kernel on several standard graph datasets from both bioinformatics and computer vision. The experimental results demonstrate the effectiveness of the proposed quantum graph kernel.

A quantum Jensen-Shannon graph kernel using discrete-time quantum walks

In this paper, we develop a new graph kernel by using the quantum Jensen-Shannon divergence and the discrete-time quantum walk. To this end, we commence by performing a discrete-time quantum walk to compute a density matrix over each graph being compared. For a pair of graphs, we compare the mixed quantum states represented by their density matrices using the quantum Jensen-Shannon divergence. With the density matrices for a pair of graphs to hand, the quantum graph kernel between the pair of graphs is defined by exponentiating the negative quantum Jensen-Shannon divergence between the graph density matrices. We evaluate the performance of our kernel on several standard graph datasets, and demonstrate the effectiveness of the new kernel.

Attributed graph kernels using the Jensen-Tsallis q-differences

We propose a family of attributed graph kernels based on mutual information measures, i.e., the Jensen-Tsallis (JT) q-differences (for q  ∈ [1,2]) between probability distributions over the graphs. To this end, we first assign a probability to each vertex of the graph through a continuous-time quantum walk (CTQW). We then adopt the tree-index approach [1] to strengthen the original vertex labels, and we show how the CTQW can induce a probability distribution over these strengthened labels. We show that our JT kernel (for q  = 1) overcomes the shortcoming of discarding non-isomorphic substructures arising in the R-convolution kernels. Moreover, we prove that the proposed JT kernels generalize the Jensen-Shannon graph kernel [2] (for q = 1) and the classical subtree kernel [3] (for q = 2), respectively. Experimental evaluations demonstrate the effectiveness and efficiency of the JT kernels.

Characterizing graph symmetries through quantum Jensen-Shannon divergence

In this paper we investigate the connection between quantum walks and graph symmetries. We begin by designing an experiment that allows us to analyze the behavior of the quantum walks on the graph without causing the wave function collapse. To achieve this, we base our analysis on the recently introduced quantum Jensen-Shannon divergence. In particular, we show that the quantum Jensen-Shannon divergence between the evolution of two quantum walks with suitably defined initial states is maximum when the graph presents symmetries. Hence, we assign to each pair of nodes of the graph a value of the divergence, and we average over all pairs of nodes to characterize the degree of symmetry possessed by a graph. © 2013 American Physical Society.

A quantum Jensen-Shannon graph kernel using the continuous-time quantum walk

In this paper, we use the quantum Jensen-Shannon divergence as a means to establish the similarity between a pair of graphs and to develop a novel graph kernel. In quantum theory, the quantum Jensen-Shannon divergence is defined as a distance measure between quantum states. In order to compute the quantum Jensen-Shannon divergence between a pair of graphs, we first need to associate a density operator with each of them. Hence, we decide to simulate the evolution of a continuous-time quantum walk on each graph and we propose a way to associate a suitable quantum state with it. With the density operator of this quantum state to hand, the graph kernel is defined as a function of the quantum Jensen-Shannon divergence between the graph density operators. We evaluate the performance of our kernel on several standard graph datasets from bioinformatics. We use the Principle Component Analysis (PCA) on the kernel matrix to embed the graphs into a feature space for classification. The experimental results demonstrate the effectiveness of the proposed approach. © 2013 Springer-Verlag.

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.

A stable graph-based representation for object recognition through high-order matching

Many Object recognition techniques perform some flavour of point pattern matching between a model and a scene. Such points are usually selected through a feature detection algorithm that is robust to a class of image transformations and a suitable descriptor is computed over them in order to get a reliable matching. Moreover, some approaches take an additional step by casting the correspondence problem into a matching between graphs defined over feature points. The motivation is that the relational model would add more discriminative power, however the overall effectiveness strongly depends on the ability to build a graph that is stable with respect to both changes in the object appearance and spatial distribution of interest points. In fact, widely used graph-based representations, have shown to suffer some limitations, especially with respect to changes in the Euclidean organization of the feature points. In this paper we introduce a technique to build relational structures over corner points that does not depend on the spatial distribution of the features. © 2012 ICPR Org Committee.

Supervised learning of graph structure

Graph-based representations have been used with considerable success in computer vision in the abstraction and recognition of object shape and scene structure. Despite this, the methodology available for learning structural representations from sets of training examples is relatively limited. In this paper we take a simple yet effective Bayesian approach to attributed graph learning. We present a naïve node-observation model, where we make the important assumption that the observation of each node and each edge is independent of the others, then we propose an EM-like approach to learn a mixture of these models and a Minimum Message Length criterion for components selection. Moreover, in order to avoid the bias that could arise with a single estimation of the node correspondences, we decide to estimate the sampling probability over all the possible matches. Finally we show the utility of the proposed approach on popular computer vision tasks such as 2D and 3D shape recognition. © 2011 Springer-Verlag.

Efficient computation of decoherent quantum walks through eigenvalue perturbation

A number of recent studies have investigated the introduction of decoherence in quantum walks and the resulting transition to classical random walks. Interestingly,it has been shown that algorithmic properties of quantum walks with decoherence such as the spreading rate are sometimes better than their purely quantum counterparts. Not only quantum walks with decoherence provide a generalization of quantum walks that naturally encompasses both the quantum and classical case, but they also give rise to new and different probability distribution. The application of quantum walks with decoherence to large graphs is limited by the necessity of evolving state vector whose sizes quadratic in the number of nodes of the graph, as opposed to the linear state vector of the purely quantum (or classical) case. In this technical report,we show how to use perturbation theory to reduce the computational complexity of evolving a continuous-time quantum walk subject to decoherence. More specifically, given a graph over n nodes, we show how to approximate the eigendecomposition of the n2×n2 Lindblad super-operator from the eigendecomposition of the n×n graph Hamiltonian.

Network construction and graph theoretical analysis of functional language networks in pediatric epilepsy

This dissertation introduces a new approach for assessing the effects of pediatric epilepsy on the language connectome. Two novel data-driven network construction approaches are presented. These methods rely on connecting different brain regions using either extent or intensity of language related activations as identified by independent component analysis of fMRI data. An auditory description decision task (ADDT) paradigm was used to activate the language network for 29 patients and 30 controls recruited from three major pediatric hospitals. Empirical evaluations illustrated that pediatric epilepsy can cause, or is associated with, a network efficiency reduction. Patients showed a propensity to inefficiently employ the whole brain network to perform the ADDT language task; on the contrary, controls seemed to efficiently use smaller segregated network components to achieve the same task. To explain the causes of the decreased efficiency, graph theoretical analysis was carried out. The analysis revealed no substantial global network feature differences between the patient and control groups. It also showed that for both subject groups the language network exhibited small-world characteristics; however, the patient's extent of activation network showed a tendency towards more random networks. It was also shown that the intensity of activation network displayed ipsilateral hub reorganization on the local level. The left hemispheric hubs displayed greater centrality values for patients, whereas the right hemispheric hubs displayed greater centrality values for controls. This hub hemispheric disparity was not correlated with a right atypical language laterality found in six patients. Finally it was shown that a multi-level unsupervised clustering scheme based on self-organizing maps, a type of artificial neural network, and k-means was able to fairly and blindly separate the subjects into their respective patient or control groups. The clustering was initiated using the local nodal centrality measurements only. Compared to the extent of activation network, the intensity of activation network clustering demonstrated better precision. This outcome supports the assertion that the local centrality differences presented by the intensity of activation network can be associated with focal epilepsy.^

Intracranial Volume Estimation and Graph Theoretical Analysis of Brain Functional Connectivity Networks

Understanding pathways of neurological disorders requires extensive research on both functional and structural characteristics of the brain. This dissertation introduced two interrelated research endeavors, describing (1) a novel integrated approach for constructing functional connectivity networks (FCNs) of brain using non-invasive scalp EEG recordings; and (2) a decision aid for estimating intracranial volume (ICV). The approach in (1) was developed to study the alterations of networks in patients with pediatric epilepsy. Results demonstrated the existence of statistically significant (p

Opportunistic Contact Graph Routing

L'ambiente di questa tesi è quello del Delay and Disruption Tolerant Networks (DTN), un'architettura di rete di telecomunicazioni avente come obiettivo le comunicazioni tra nodi di reti dette “challenged”, le quali devono affrontare problemi come tempi di propagazione elevati, alto tasso di errore e periodi di perdita delle connessioni. Il Bunde layer, un nuovo livello inserito tra trasporto e applicazione nell’architettura ISO/OSI, ed il protocollo ad esso associato, il Bundle Protocol (BP), sono stati progettati per rendere possibili le comunicazioni in queste reti. A volte fra la ricezione e l’invio può trascorrere un lungo periodo di tempo, a causa della indisponibilità del collegamento successivo; in questo periodo il bundle resta memorizzato in un database locale. Esistono varie implementazioni dell'architettura DTN come DTN2, implementazione di riferimento, e ION (Interplanetary Overlay Network), sviluppata da NASA JPL, per utilizzo in applicazioni spaziali; in esse i contatti tra i nodi sono deterministici, a differenza delle reti terrestri nelle quali i contatti sono generalmente opportunistici (non noti a priori). Per questo motivo all’interno di ION è presente un algoritmo di routing, detto CGR (Contact Graph Routing), progettato per operare in ambienti con connettività deterministica. È in fase di ricerca un algoritmo che opera in ambienti non deterministici, OCGR (Opportunistic Contact Graph Routing), che estende CGR. L’obiettivo di questa tesi è quello di fornire una descrizione dettagliata del funzionamento di OCGR, partendo necessariamente da CGR sul quale è basato, eseguire dei test preliminari, richiesti da NASA JPL, ed analizzarne i risultati per verificare la possibilità di utilizzo e miglioramento dell’algoritmo. Sarà inoltre descritto l’ambiente DTN e i principali algoritmi di routing per ambienti opportunistici. Nella parte conclusiva sarà presentato il simulatore DTN “The ONE” e l’integrazione di CGR e OCGR al suo interno.

Coupled symplectic maps as models for subdiffusive processes in disordered Hamiltonian lattices

Acknowledgements One of us (T. B.) acknowledges many interesting discussions on coupled maps with Professor C. Tsallis. We are also grateful to the anonymous referees for their constructive feedback that helped us improve the manuscript and to the HPCS Laboratory of the TEI of Western Greece for providing the computer facilities where all our simulations were performed. C. G. A. was partially supported by the “EPSRC EP/I032606/1” grant of the University of Aberdeen. This research has been co-financed by the European Union (European Social Fund - ESF) and Greek national funds through the Operational Program “Education and Lifelong Learning” of the National Strategic Reference Framework (NSRF) - Research Funding Program: THALES - Investing in knowledge society through the European Social Fund.