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.

Cooperative greedy pursuit strategies for sparse signal representation by partitioning

Cooperative Greedy Pursuit Strategies are considered for approximating a signal partition subjected to a global constraint on sparsity. The approach aims at producing a high quality sparse approximation of the whole signal, using highly coherent redundant dictionaries. The cooperation takes place by ranking the partition units for their sequential stepwise approximation, and is realized by means of i)forward steps for the upgrading of an approximation and/or ii) backward steps for the corresponding downgrading. The advantage of the strategy is illustrated by approximation of music signals using redundant trigonometric dictionaries. In addition to rendering stunning improvements in sparsity with respect to the concomitant trigonometric basis, these dictionaries enable a fast implementation of the approach via the Fast Fourier Transform

Data partitioning and replication management in distributed geographic information system (GIS) database

This research presents several components encompassing the scope of the objective of Data Partitioning and Replication Management in Distributed GIS Database. Modern Geographic Information Systems (GIS) databases are often large and complicated. Therefore data partitioning and replication management problems need to be addresses in development of an efficient and scalable solution. ^ Part of the research is to study the patterns of geographical raster data processing and to propose the algorithms to improve availability of such data. These algorithms and approaches are targeting granularity of geographic data objects as well as data partitioning in geographic databases to achieve high data availability and Quality of Service(QoS) considering distributed data delivery and processing. To achieve this goal a dynamic, real-time approach for mosaicking digital images of different temporal and spatial characteristics into tiles is proposed. This dynamic approach reuses digital images upon demand and generates mosaicked tiles only for the required region according to user's requirements such as resolution, temporal range, and target bands to reduce redundancy in storage and to utilize available computing and storage resources more efficiently. ^ Another part of the research pursued methods for efficient acquiring of GIS data from external heterogeneous databases and Web services as well as end-user GIS data delivery enhancements, automation and 3D virtual reality presentation. ^ There are vast numbers of computing, network, and storage resources idling or not fully utilized available on the Internet. Proposed "Crawling Distributed Operating System "(CDOS) approach employs such resources and creates benefits for the hosts that lend their CPU, network, and storage resources to be used in GIS database context. ^ The results of this dissertation demonstrate effective ways to develop a highly scalable GIS database. The approach developed in this dissertation has resulted in creation of TerraFly GIS database that is used by US government, researchers, and general public to facilitate Web access to remotely-sensed imagery and GIS vector information. ^

Phosphorus cycling and partitioning in an oligotrophic Everglades wetland ecosystem: a radioisotope tracing study

1. Our goal was to quantify short-term phosphorus (P) partitioning and identify the ecosystem components important to P cycling in wetland ecosystems. To do this, we added P radiotracer to oligotrophic, P-limited Everglades marshes. 32PO4 was added to the water column in six 1-m2 enclosed mesocosms located in long-hydroperiod marshes of Shark River Slough, Everglades National Park. Ecosystem components were then repeatedly sampled over 18 days. 2. Water column particulates (>0.45 μm) incorporated radiotracer within the first minute after dosing and stored 95–99% of total water column 32P activity throughout the study. Soluble (<0.45 μm) 32P in the water column, in contrast, was always <5% of the 32P in surface water. Periphyton, both floating and attached to emergent macrophytes, had the highest specific activity of 32P (Bq g−131P) among the different ecosystem components. Fish and aquatic macroinvertebrates also had high affinity for P, whereas emergent macrophytes, soil and flocculent detrital organic matter (floc) had the lowest specific activities of radiotracer. 3. Within the calcareous, floating periphyton mats, 81% of the initial 32P uptake was associated with Ca, but most of this 32P entered and remained within the organic pool (Ca-associated = 14% of total) after 1 day. In the floc layer, 32P rapidly entered the microbial pool and the labile fraction was negligible for most of the study. 4. Budgeting of the radiotracer indicated that 32P moved from particulates in the water column to periphyton and floc and then to the floc and soil over the course of the 18 day incubations. Floc (35% of total) and soil (27%) dominated 32P storage after 18 days, with floating periphyton (12%) and surface water (10%) holding smaller proportions of total ecosystem 32P. 5. To summarise, oligotrophic Everglades marshes exhibited rapid uptake and retention of labile 32P. Components dominated by microbes appear to control short-term P cycling in this oligotrophic ecosystem.

Notes on sufficient conditions for a graph to be Hamiltonian

The first part of this paper deals with an extension of Dirac's Theorem to directed graphs. It is related to a result often referred to as the Ghouila-Houri Theorem. Here we show that the requirement of being strongly connected in the hypothesis of the Ghouila-Houri Theorem is redundant. The Second part of the paper shows that a condition on the number of edges for a graph to be hamiltonian implies Ore's condition on the degrees of the vertices.

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.^

Emergence and Fate of Siloxanes in Waste Streams: Release Mechanisms, Partitioning and Persistence in Three Environmental Compartments

Siloxanes are widely used in personal care and industrial products due to their low surface tension, thermal stability, antimicrobial and hydrophobic properties, among other characteristics. Volatile methyl siloxanes (VMS) have been detected both in landfill gas and biogas from anaerobic digesters at wastewater treatment plants. As a result, they are released to gas phase during waste decomposition and wastewater treatment. During transformation processes of digester or landfill gas to energy, siloxanes are converted to silicon oxides, leaving abrasive deposits on engine components. These deposits cause increased maintenance costs and in some cases complete engine overhauls become necessary. The objectives of this study were to compare the VMS types and levels present in biogas generated in the anaerobic digesters and landfills and evaluate the energetics of siloxane transformations under anaerobic conditions. Siloxane emissions, resulting from disposal of silicone-based materials, are expected to increase by 29% within the next 10 years. Estimated concentrations and the risk factors of exposure to siloxanes were evaluated based on the initial concentrations, partitioning characteristics and persistence. It was determined that D4 has the highest risk factor associated to bioaccumulation in liquid and solid phase, whereas D5 was highest in gas phase. Additionally, as siloxanes are combusted, the particle size range causes them to be potentially hazardous to human health. When inhaled, they may affix onto the alveoli of the lungs and may lead to development of silicosis. Siloxane-based COD-loading was evaluated and determined to be an insignificant factor concerning COD limits in wastewater. Removal of siloxane compounds is recommended prior to land application of biosolids or combustion of biogas. A comparison of estimated costs was made between maintenance practices for removal of siloxane deposits and installation/operation of fixed-bed carbon absorption systems. In the majority of cases, the installation of fixed-bed adsorption systems would not be a feasible option for the sole purpose of siloxane removal. However they may be utilized to remove additional compounds simultaneously.

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

Phase and partitioning behavior of phenols and polycyclic aromatic hydrocarbons in offshore oil and gas produced water

Produced water constitutes the largest volume of waste from offshore oil and gas operations and is composed of a wide range of organic and inorganic compounds. Although treatment processes have to meet strict oil in water regulations, the definition of “oil” is a function of the analysis process and may include aliphatic hydrocarbons which have limited environmental impact due to degradability whilst ignoring problematic dissolved petroleum species. This thesis presents the partitioning behavior of oil in produced water as a function of temperature and salinity to identify compounds of environmental concern. Phenol, p-cresol, and 4-tert-butylphenol were studied because of their xenoestrogenic power; other compounds studied are polycyclic aromatic hydrocarbon PAHs which include naphthalene, fluorene, phenanthrene, and pyrene. Partitioning experiments were carried out in an Innova incubator for 48 hours, temperature was varied from 4ﾟC to 70ﾟC, and two salinity levels of 46.8‰ and 66.8‰ were studied. Results obtained showed that the dispersed oil concentration in the water reduces with settling time and equilibrium was attained at 48 h settling time. Polycyclic aromatic hydrocarbons (PAHs) partitions based on dispersed oil concentration whereas phenols are not significantly affected by dispersed oil concentration. Higher temperature favors partitioning of PAHs into the water phase. Salinity has negligible effect on partitioning pattern of phenols and PAHs studied. Simulation results obtained from the Aspen HYSYS model shows that temperature and oil droplet distribution greatly influences the efficiency of produced water treatment system.

The dual effect of normobaric hypoxia on heart rate variability and substrate partitioning following interval cycling

Recent studies have shown the importance of the beat-by-beat changes in heart rate influenced by the autonomic nervous system (ANS), or heart rate variability (HRV). The purpose of this study was to examine the lasting effects of hypoxic exercise on HRV, and its influences on substrate usage. Results from this study could lead an increased understanding on this topic. Eight active healthy males (age: 31±11 years; height: 180±7 cm; weight: 83±8 kg; VO₂max (maximal oxygen consumption): 4.4±0.6 L•min⁻¹) underwent normoxic and hypoxic (FᵢO₂= 0.15) conditions during high-intensity interval (HIIT) cycling (70%-high interval, 35%-rest interval). Cycling intensity was determined by a peak power output cycling test. Each experimental session consisted of a basal metabolic rate determination, up to 45-minutes of HIIT cycling, and three 30-minute post-exercise metabolic rate measurements (spanning 3 hours and 15 minutes after exercise). During exercise, RPE was higher (p<0.01) and LAC (lactate) increased (p=0.001) at each point of time in hypoxia, with no change in normoxia. After hypoxic exercise, the SNS/PNS ratio (overall ANS activity) was significantly higher (p<0.01) and significantly decreased through time in both conditions (p<0.01). In addition, a significant interaction between time and conditions (p<0.02) showed a decrease in LAC concentration through time post-hypoxic exercise. The findings showed that a single bout of hypoxic exercise alters ANS activity post-exercise along with shifting substrate partitioning from glycolytic to lipolytic energy production. The significant decrease in LAC concentration post-hypoxic exercise supports the notion that hypoxic HIIT induces a greater muscle glycogen depletion leading to increased fat oxidation to sustain glycogenesis and gluconeogenesis to maintain blood glucose level during recovery.

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.

Genome-wide association and genome partitioning reveal novel genomic regions underlying variation in gastrointestinal nematode burden in a wild bird

Acknowledgements This study was funded by a BBSRC studentship (MA Wenzel) and NERC grants NE/H00775X/1 and NE/D000602/1 (SB Piertney). The authors are grateful to Fiona Leckie, Andrew MacColl, Jesús Martínez-Padilla, François Mougeot, Steve Redpath, Pablo Vergara† and Lucy M.I. Webster for samples; Keliya Bai, Daisy Brickhill, Edward Graham, Alyson Little, Daniel Mifsud, Lizzie Molyneux and Mario Röder for fieldwork assistance; Gillian Murray-Dickson and Laura Watt for laboratory assistance; Heather Ritchie for helpful comments on manuscript drafts; and all estate owners, factors and keepers for access to field sites, most particularly Stuart Young and Derek Calder (Edinglassie), Simon Blackett, Jim Davidson and Liam Donald (Invercauld and Glas Choille), Richard Cooke and Fred Taylor† (Invermark) and T. Helps (Catterick).

A survey of graph and subgraph isomorphism problems

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.