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.

A bidding strategy for minimizing the imbalances costs for renewable generators in Spanish power markets

The aim of this paper is to suggest a simple methodology to be used by renewable power generators to bid in Spanish markets in order to minimize the cost of their imbalances. As it is known, the optimal bid depends on the probability distribution function of the energy to produce, of the probability distribution function of the future system imbalance and of its expected cost. We assume simple methods for estimating any of these parameters and, using actual data of 2014, we test the potential economic benefit for a wind generator from using our optimal bid instead of just the expected power generation. We find evidence that Spanish wind generators savings would be from 7% to 26%.

A survey of graph and subgraph isomorphism problems

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

Direct power control with common mode voltage elimination for open-winding brushless doubly-fed wind power generators

In this paper, a new open-winding control strategy is proposed for a brushless doubly-fed reluctance generator (BDFRG) applicable for wind turbines. The BDFRG control winding is fed via a dual two-level three-phase converter using a single dc bus. Direct power control based on maximum power point tracking with common mode voltage elimination is designed, which not only the active and reactive power is decoupled, but the reliability and redundancy are all improved greatly by increasing the switching modes of operation, while DC-link voltage and rating of power devices decreased by 50% comparing to the traditional three-level converter systems. Consequently its effectiveness is evaluated by simulation tests based on a 42-kW prototype generator.

A survey of graph and subgraph isomorphism problems

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

A Scalable General Purpose System for Large-Scale Graph Processing

Graph analytics is an important and computationally demanding class of data analytics. It is essential to balance scalability, ease-of-use and high performance in large scale graph analytics. As such, it is necessary to hide the complexity of parallelism, data distribution and memory locality behind an abstract interface. The aim of this work is to build a scalable graph analytics framework that does not demand significant parallel programming experience based on NUMA-awareness.
The realization of such a system faces two key problems:
(i)~how to develop a scale-free parallel programming framework that scales efficiently across NUMA domains; (ii)~how to efficiently apply graph partitioning in order to create separate and largely independent work items that can be distributed among threads.

Generic wind estimation and compensation based on residual generators and higher-order sliding mode schemes

This master thesis proposes a solution to the approach problem in case of unknown severe microburst wind shear for a fixed-wing aircraft, accounting for both longitudinal and lateral dynamics. The adaptive controller design for wind rejection is also addressed, exploiting the wind estimation provided by suitable estimators. It is able to successfully complete the final approach phase even in presence of wind shear, and at the same time aerodynamic envelope protection is retained. The adaptive controller for wind compensation has been designed by a backstepping approach and feedback linearization for time-varying systems. The wind shear components have been estimated by higher-order sliding mode schemes. At the end of this work the results are provided, an autonomous final approach in presence of microburst is discussed, performances are analyzed, and estimation of the microburst characteristics from telemetry data is examined.

Graph analysis of verbal fluency test discriminate between patients with Alzheimer’s disease, Mild Cognitive Impairment and normal elderly controls

Verbal fluency is the ability to produce a satisfying sequence of spoken words during a given time interval. The core of verbal fluency lies in the capacity to manage the executive aspects of language. The standard scores of the semantic verbal fluency test are broadly used in the neuropsychological assessment of the elderly, and different analytical methods are likely to extract even more information from the data generated in this test. Graph theory, a mathematical approach to analyze relations between items, represents a promising tool to understand a variety of neuropsychological states. This study reports a graph analysis of data generated by the semantic verbal fluency test by cognitively healthy elderly (NC), patients with Mild Cognitive Impairment – subtypes amnestic(aMCI) and amnestic multiple domain (a+mdMCI) - and patients with Alzheimer’s disease (AD). Sequences of words were represented as a speech graph in which every word corresponded to a node and temporal links between words were represented by directed edges. To characterize the structure of the data we calculated 13 speech graph attributes (SGAs). The individuals were compared when divided in three (NC – MCI – AD) and four (NC – aMCI – a+mdMCI – AD) groups. When the three groups were compared, significant differences were found in the standard measure of correct words produced, and three SGA: diameter, average shortest path, and network density. SGA sorted the elderly groups with good specificity and sensitivity. When the four groups were compared, the groups differed significantly in network density, except between the two MCI subtypes and NC and aMCI. The diameter of the network and the average shortest path were significantly different between the NC and AD, and between aMCI and AD. SGA sorted the elderly in their groups with good specificity and sensitivity, performing better than the standard score of the task. These findings provide support for a new methodological frame to assess the strength of semantic memory through the verbal fluency task, with potential to amplify the predictive power of this test. Graph analysis is likely to become clinically relevant in neurology and psychiatry, and may be particularly useful for the differential diagnosis of the elderly.

Parallel dynamic graph-partitioning for unstructured meshes

A parallel method for the dynamic partitioning of unstructured meshes is described. The method introduces a new iterative optimisation technique known as relative gain optimisation which both balances the workload and attempts to minimise the interprocessor communications overhead. Experiments on a series of adaptively refined meshes indicate that the algorithm provides partitions of an equivalent or higher quality to static partitioners (which do not reuse the existing partition) and much more rapidly. Perhaps more importantly, the algorithm results in only a small fraction of the amount of data migration compared to the static partitioners.

Large eddy simulation of shock boundary layer interaction control using micro-vortex generators

The performance of supersonic engine inlets and external aerodynamic surfaces can be critically affected by shock wave / boundary layer interactions (SBLIs), whose severe adverse pressure gradients can cause boundary layer separation. Currently such problems are avoided primarily through the use of boundary layer bleed/suction which can be a source of significant performance degradation. This study investigates a novel type of flow control device called micro-vortex generators (µVGs) which may offer similar control benefits without the bleed penalties. µVGs have the ability to alter the near-wall structure of compressible turbulent boundary layers to provide increased mixing of high speed fluid which improves the boundary layer health when subjected to flow disturbance. Due to their small size,µVGs are embedded in the boundary layer which provide reduced drag compared to the traditional vortex generators while they are cost-effective, physically robust and do not require a power source. To examine the potential of µVGs, a detailed experimental and computational study of micro-ramps in a supersonic boundary layer at Mach 3 subjected to an oblique shock was undertaken. The experiments employed a flat plate boundary layer with an impinging oblique shock with downstream total pressure measurements. The moderate Reynolds number of 3,800 based on displacement thickness allowed the computations to use Large Eddy Simulations without the subgrid stress model (LES-nSGS). The LES predictions indicated that the shock changes the structure of the turbulent eddies and the primary vortices generated from the micro-ramp. Furthermore, they generally reproduced the experimentally obtained mean velocity profiles, unlike similarly-resolved RANS computations. The experiments and the LES results indicate that the micro-ramps, whose height is h≈0.5δ, can significantly reduce boundary layer thickness and improve downstream boundary layer health as measured by the incompressible shape factor, H. Regions directly behind the ramp centerline tended to have increased boundary layer thickness indicating the significant three-dimensionality of the flow field. Compared to baseline sizes, smaller micro-ramps yielded improved total pressure recovery. Moving the smaller ramps closer to the shock interaction also reduced the displacement thickness and the separated area. This effect is attributed to decreased wave drag and the closer proximity of the vortex pairs to the wall. In the second part of the study, various types of µVGs are investigated including micro-ramps and micro-vanes. The results showed that vortices generated from µVGs can partially eliminate shock induced flow separation and can continue to entrain high momentum flux for boundary layer recovery downstream. The micro-ramps resulted in thinner downstream displacement thickness in comparison to the micro-vanes. However, the strength of the streamwise vorticity for the micro-ramps decayed faster due to dissipation especially after the shock interaction. In addition, the close spanwise distance between each vortex for the ramp geometry causes the vortex cores to move upwards from the wall due to induced upwash effects. Micro-vanes, on the other hand, yielded an increased spanwise spacing of the streamwise vortices at the point of formation. This resulted in streamwise vortices staying closer to the wall with less circulation decay, and the reduction in overall flow separation is attributed to these effects. Two hybrid concepts, named “thick-vane” and “split-ramp”, were also studied where the former is a vane with side supports and the latter has a uniform spacing along the centerline of the baseline ramp. These geometries behaved similar to the micro-vanes in terms of the streamwise vorticity and the ability to reduce flow separation, but are more physically robust than the thin vanes. Next, Mach number effect on flow past the micro-ramps (h~0.5δ) are examined in a supersonic boundary layer at M=1.4, 2.2 and 3.0, but with no shock waves present. The LES results indicate that micro-ramps have a greater impact at lower Mach number near the device but its influence decays faster than that for the higher Mach number cases. This may be due to the additional dissipation caused by the primary vortices with smaller effective diameter at the lower Mach number such that their coherency is easily lost causing the streamwise vorticity and the turbulent kinetic energy to decay quickly. The normal distance between the vortex core and the wall had similar growth indicating weak correlation with the Mach number; however, the spanwise distance between the two counter-rotating cores further increases with lower Mach number. Finally, various µVGs which include micro-ramp, split-ramp and a new hybrid concept “ramped-vane” are investigated under normal shock conditions at Mach number of 1.3. In particular, the ramped-vane was studied extensively by varying its size, interior spacing of the device and streamwise position respect to the shock. The ramped-vane provided increased vorticity compared to the micro-ramp and the split-ramp. This significantly reduced the separation length downstream of the device centerline where a larger ramped-vane with increased trailing edge gap yielded a fully attached flow at the centerline of separation region. The results from coarse-resolution LES studies show that the larger ramped-vane provided the most reductions in the turbulent kinetic energy and pressure fluctuation compared to other devices downstream of the shock. Additional benefits include negligible drag while the reductions in displacement thickness and shape factor were seen compared to other devices. Increased wall shear stress and pressure recovery were found with the larger ramped-vane in the baseline resolution LES studies which also gave decreased amplitudes of the pressure fluctuations downstream of the shock.

Probabilistic Models for Scalable Knowledge Graph Construction

In the past decade, systems that extract information from millions of Internet documents have become commonplace. Knowledge graphs -- structured knowledge bases that describe entities, their attributes and the relationships between them -- are a powerful tool for understanding and organizing this vast amount of information. However, a significant obstacle to knowledge graph construction is the unreliability of the extracted information, due to noise and ambiguity in the underlying data or errors made by the extraction system and the complexity of reasoning about the dependencies between these noisy extractions. My dissertation addresses these challenges by exploiting the interdependencies between facts to improve the quality of the knowledge graph in a scalable framework. I introduce a new approach called knowledge graph identification (KGI), which resolves the entities, attributes and relationships in the knowledge graph by incorporating uncertain extractions from multiple sources, entity co-references, and ontological constraints. I define a probability distribution over possible knowledge graphs and infer the most probable knowledge graph using a combination of probabilistic and logical reasoning. Such probabilistic models are frequently dismissed due to scalability concerns, but my implementation of KGI maintains tractable performance on large problems through the use of hinge-loss Markov random fields, which have a convex inference objective. This allows the inference of large knowledge graphs using 4M facts and 20M ground constraints in 2 hours. To further scale the solution, I develop a distributed approach to the KGI problem which runs in parallel across multiple machines, reducing inference time by 90%. Finally, I extend my model to the streaming setting, where a knowledge graph is continuously updated by incorporating newly extracted facts. I devise a general approach for approximately updating inference in convex probabilistic models, and quantify the approximation error by defining and bounding inference regret for online models. Together, my work retains the attractive features of probabilistic models while providing the scalability necessary for large-scale knowledge graph construction. These models have been applied on a number of real-world knowledge graph projects, including the NELL project at Carnegie Mellon and the Google Knowledge Graph.

A graph-based hyper heuristic for timetabling problems

This paper presents an investigation of a simple generic hyper-heuristic approach upon a set of widely used constructive heuristics (graph coloring heuristics) in timetabling. Within the hyperheuristic framework, a Tabu Search approach is employed to search for permutations of graph heuristics which are used for constructing timetables in exam and course timetabling problems. This underpins a multi-stage hyper-heuristic where the Tabu Search employs permutations upon a different number of graph heuristics in two stages. We study this graph-based hyper-heuristic approach within the context of exploring fundamental issues concerning the search space of the hyper-heuristic (the heuristic space) and the solution space. Such issues have not been addressed in other hyper-heuristic research. These approaches are tested on both exam and course benchmark timetabling problems and are compared with the fine-tuned bespoke state-of-the-art approaches. The results are within the range of the best results reported in the literature. The approach described here represents a significantly more generally applicable approach than the current state of the art in the literature. Future work will extend this hyper-heuristic framework by employing methodologies which are applicable on a wider range of timetabling and scheduling problems.

Hybrid Graph Heuristics within a Hyper-heuristic Approach to Exam Timetabling Problems

This paper is concerned with the hybridization of two graph coloring heuristics (Saturation Degree and Largest Degree), and their application within a hyperheuristic for exam timetabling problems. Hyper-heuristics can be seen as algorithms which intelligently select appropriate algorithms/heuristics for solving a problem. We developed a Tabu Search based hyper-heuristic to search for heuristic lists (of graph heuristics) for solving problems and investigated the heuristic lists found by employing knowledge discovery techniques. Two hybrid approaches (involving Saturation Degree and Largest Degree) including one which employs Case Based Reasoning are presented and discussed. Both the Tabu Search based hyper-heuristic and the hybrid approaches are tested on random and real-world exam timetabling problems. Experimental results are comparable with the best state-of-the-art approaches (as measured against established benchmark problems). The results also demonstrate an increased level of generality in our approach.