Strong Connectivity in Directed Hypergraphs and its Application to the Atomic Decomposition of Ontologies

Los hipergrafos dirigidos se han empleado en problemas relacionados con lógica proposicional, bases de datos relacionales, linguística computacional y aprendizaje automático. Los hipergrafos dirigidos han sido también utilizados como alternativa a los grafos (bipartitos) dirigidos para facilitar el estudio de las interacciones entre componentes de sistemas complejos que no pueden ser fácilmente modelados usando exclusivamente relaciones binarias. En este contexto, este tipo de representación es conocida como hiper-redes. Un hipergrafo dirigido es una generalización de un grafo dirigido especialmente adecuado para la representación de relaciones de muchos a muchos. Mientras que una arista en un grafo dirigido define una relación entre dos de sus nodos, una hiperarista en un hipergrafo dirigido define una relación entre dos conjuntos de sus nodos. La conexión fuerte es una relación de equivalencia que divide el conjunto de nodos de un hipergrafo dirigido en particiones y cada partición define una clase de equivalencia conocida como componente fuertemente conexo. El estudio de los componentes fuertemente conexos de un hipergrafo dirigido puede ayudar a conseguir una mejor comprensión de la estructura de este tipo de hipergrafos cuando su tamaño es considerable. En el caso de grafo dirigidos, existen algoritmos muy eficientes para el cálculo de los componentes fuertemente conexos en grafos de gran tamaño. Gracias a estos algoritmos, se ha podido averiguar que la estructura de la WWW tiene forma de “pajarita”, donde más del 70% del los nodos están distribuidos en tres grandes conjuntos y uno de ellos es un componente fuertemente conexo. Este tipo de estructura ha sido también observada en redes complejas en otras áreas como la biología. Estudios de naturaleza similar no han podido ser realizados en hipergrafos dirigidos porque no existe algoritmos capaces de calcular los componentes fuertemente conexos de este tipo de hipergrafos. En esta tesis doctoral, hemos investigado como calcular los componentes fuertemente conexos de un hipergrafo dirigido. En concreto, hemos desarrollado dos algoritmos para este problema y hemos determinado que son correctos y cuál es su complejidad computacional. Ambos algoritmos han sido evaluados empíricamente para comparar sus tiempos de ejecución. Para la evaluación, hemos producido una selección de hipergrafos dirigidos generados de forma aleatoria inspirados en modelos muy conocidos de grafos aleatorios como Erdos-Renyi, Newman-Watts-Strogatz and Barabasi-Albert. Varias optimizaciones para ambos algoritmos han sido implementadas y analizadas en la tesis. En concreto, colapsar los componentes fuertemente conexos del grafo dirigido que se puede construir eliminando ciertas hiperaristas complejas del hipergrafo dirigido original, mejora notablemente los tiempos de ejecucion de los algoritmos para varios de los hipergrafos utilizados en la evaluación. Aparte de los ejemplos de aplicación mencionados anteriormente, los hipergrafos dirigidos han sido también empleados en el área de representación de conocimiento. En concreto, este tipo de hipergrafos se han usado para el cálculo de módulos de ontologías. Una ontología puede ser definida como un conjunto de axiomas que especifican formalmente un conjunto de símbolos y sus relaciones, mientras que un modulo puede ser entendido como un subconjunto de axiomas de la ontología que recoge todo el conocimiento que almacena la ontología sobre un conjunto especifico de símbolos y sus relaciones. En la tesis nos hemos centrado solamente en módulos que han sido calculados usando la técnica de localidad sintáctica. Debido a que las ontologías pueden ser muy grandes, el cálculo de módulos puede facilitar las tareas de re-utilización y mantenimiento de dichas ontologías. Sin embargo, analizar todos los posibles módulos de una ontología es, en general, muy costoso porque el numero de módulos crece de forma exponencial con respecto al número de símbolos y de axiomas de la ontología. Afortunadamente, los axiomas de una ontología pueden ser divididos en particiones conocidas como átomos. Cada átomo representa un conjunto máximo de axiomas que siempre aparecen juntos en un modulo. La decomposición atómica de una ontología es definida como un grafo dirigido de tal forma que cada nodo del grafo corresponde con un átomo y cada arista define una dependencia entre una pareja de átomos. En esta tesis introducimos el concepto de“axiom dependency hypergraph” que generaliza el concepto de descomposición atómica de una ontología. Un modulo en una ontología correspondería con un componente conexo en este tipo de hipergrafos y un átomo de una ontología con un componente fuertemente conexo. Hemos adaptado la implementación de nuestros algoritmos para que funcionen también con axiom dependency hypergraphs y poder de esa forma calcular los átomos de una ontología. Para demostrar la viabilidad de esta idea, hemos incorporado nuestros algoritmos en una aplicación que hemos desarrollado para la extracción de módulos y la descomposición atómica de ontologías. A la aplicación la hemos llamado HyS y hemos estudiado sus tiempos de ejecución usando una selección de ontologías muy conocidas del área biomédica, la mayoría disponibles en el portal de Internet NCBO. Los resultados de la evaluación muestran que los tiempos de ejecución de HyS son mucho mejores que las aplicaciones más rápidas conocidas. ABSTRACT Directed hypergraphs are an intuitive modelling formalism that have been used in problems related to propositional logic, relational databases, computational linguistic and machine learning. Directed hypergraphs are also presented as an alternative to directed (bipartite) graphs to facilitate the study of the interactions between components of complex systems that cannot naturally be modelled as binary relations. In this context, they are known as hyper-networks. A directed hypergraph is a generalization of a directed graph suitable for representing many-to-many relationships. While an edge in a directed graph defines a relation between two nodes of the graph, a hyperedge in a directed hypergraph defines a relation between two sets of nodes. Strong-connectivity is an equivalence relation that induces a partition of the set of nodes of a directed hypergraph into strongly-connected components. These components can be collapsed into single nodes. As result, the size of the original hypergraph can significantly be reduced if the strongly-connected components have many nodes. This approach might contribute to better understand how the nodes of a hypergraph are connected, in particular when the hypergraphs are large. In the case of directed graphs, there are efficient algorithms that can be used to compute the strongly-connected components of large graphs. For instance, it has been shown that the macroscopic structure of the World Wide Web can be represented as a “bow-tie” diagram where more than 70% of the nodes are distributed into three large sets and one of these sets is a large strongly-connected component. This particular structure has been also observed in complex networks in other fields such as, e.g., biology. Similar studies cannot be conducted in a directed hypergraph because there does not exist any algorithm for computing the strongly-connected components of the hypergraph. In this thesis, we investigate ways to compute the strongly-connected components of directed hypergraphs. We present two new algorithms and we show their correctness and computational complexity. One of these algorithms is inspired by Tarjan’s algorithm for directed graphs. The second algorithm follows a simple approach to compute the stronglyconnected components. This approach is based on the fact that two nodes of a graph that are strongly-connected can also reach the same nodes. In other words, the connected component of each node is the same. Both algorithms are empirically evaluated to compare their performances. To this end, we have produced a selection of random directed hypergraphs inspired by existent and well-known random graphs models like Erd˝os-Renyi and Newman-Watts-Strogatz. Besides the application examples that we mentioned earlier, directed hypergraphs have also been employed in the field of knowledge representation. In particular, they have been used to compute the modules of an ontology. An ontology is defined as a collection of axioms that provides a formal specification of a set of terms and their relationships; and a module is a subset of an ontology that completely captures the meaning of certain terms as defined in the ontology. In particular, we focus on the modules computed using the notion of syntactic locality. As ontologies can be very large, the computation of modules facilitates the reuse and maintenance of these ontologies. Analysing all modules of an ontology, however, is in general not feasible as the number of modules grows exponentially in the number of terms and axioms of the ontology. Nevertheless, the modules can succinctly be represented using the Atomic Decomposition of an ontology. Using this representation, an ontology can be partitioned into atoms, which are maximal sets of axioms that co-occur in every module. The Atomic Decomposition is then defined as a directed graph such that each node correspond to an atom and each edge represents a dependency relation between two atoms. In this thesis, we introduce the notion of an axiom dependency hypergraph which is a generalization of the atomic decomposition of an ontology. A module in the ontology corresponds to a connected component in the hypergraph, and the atoms of the ontology to the strongly-connected components. We apply our algorithms for directed hypergraphs to axiom dependency hypergraphs and in this manner, we compute the atoms of an ontology. To demonstrate the viability of this approach, we have implemented the algorithms in the application HyS which computes the modules of ontologies and calculate their atomic decomposition. In the thesis, we provide an experimental evaluation of HyS with a selection of large and prominent biomedical ontologies, most of which are available in the NCBO Bioportal. HyS outperforms state-of-the-art implementations in the tasks of extracting modules and computing the atomic decomposition of these ontologies.

Application of the dynamic models to the detection of imperfections in plate Structures

This paper is part of a set of publications related with the development of mathematical models aimed to simulate the dynamic input and output of experimental nondestructive tests in order to detect structural imperfections. The structures to be considered are composed by steel plates of thin thickness. The imperfections in these cases are cracks and they can penetrate either a significant part of the plate thickness or be micro cracks or superficial imperfections. The first class of cracks is related with structural safety and the second one is more connected to the structural protection to the environment, particularly if protective paintings can be deteriorated. Two mathematical groups of models have been developed. The first group tries to locate the position and extension of the imperfection of the first class of imperfections, i.e. cracks and it is the object of the present paper. Bending Kirchoff thin plate models belong to this first group and they are used to this respect. The another group of models is dealt with membrane structures under the superficial Rayleigh waves excitation. With this group of models the micro cracks detection is intended. In the application of the first group of models to the detection of cracks, it has been observed that the differences between the natural frequencies of the non cracked and the cracked structures are very small. However, geometry and crack position can be identified quite accurately if this comparison is carried out between first derivatives (mode rotations) of the natural modes are used instead. Finally, in relation with the analysis of the superficial crack existence the use of Rayleigh waves is very promising. The geometry and the penetration of the micro crack can be detected very accurately. The mathematical and numerical treatment of the generation of these Rayleigh waves present and a numerical application has been shown.

Odor space and olfactory processing: Collective algorithms and neural implementation

Several basic olfactory tasks must be solved by highly olfactory animals, including background suppression, multiple object separation, mixture separation, and source identification. The large number N of classes of olfactory receptor cells—hundreds or thousands—permits the use of computational strategies and algorithms that would not be effective in a stimulus space of low dimension. A model of the patterns of olfactory receptor responses, based on the broad distribution of olfactory thresholds, is constructed. Representing one odor from the viewpoint of another then allows a common description of the most important basic problems and shows how to solve them when N is large. One possible biological implementation of these algorithms uses action potential timing and adaptation as the “hardware” features that are responsible for effective neural computation.

Kinematic geometry of mass-triangles and reduction of Schrödinger’s equation of three-body systems to partial differential equations solely defined on triangular parameters

Schrödinger’s equation of a three-body system is a linear partial differential equation (PDE) defined on the 9-dimensional configuration space, ℝ9, naturally equipped with Jacobi’s kinematic metric and with translational and rotational symmetries. The natural invariance of Schrödinger’s equation with respect to the translational symmetry enables us to reduce the configuration space to that of a 6-dimensional one, while that of the rotational symmetry provides the quantum mechanical version of angular momentum conservation. However, the problem of maximizing the use of rotational invariance so as to enable us to reduce Schrödinger’s equation to corresponding PDEs solely defined on triangular parameters—i.e., at the level of ℝ6/SO(3)—has never been adequately treated. This article describes the results on the orbital geometry and the harmonic analysis of (SO(3),ℝ6) which enable us to obtain such a reduction of Schrödinger’s equation of three-body systems to PDEs solely defined on triangular parameters.

Three-dimensional inverse modelling of magnetic anomaly sources based on a genetic algorithm.

We present a modelling method to estimate the 3-D geometry and location of homogeneously magnetized sources from magnetic anomaly data. As input information, the procedure needs the parameters defining the magnetization vector (intensity, inclination and declination) and the Earth's magnetic field direction. When these two vectors are expected to be different in direction, we propose to estimate the magnetization direction from the magnetic map. Then, using this information, we apply an inversion approach based on a genetic algorithm which finds the geometry of the sources by seeking the optimum solution from an initial population of models in successive iterations through an evolutionary process. The evolution consists of three genetic operators (selection, crossover and mutation), which act on each generation, and a smoothing operator, which looks for the best fit to the observed data and a solution consisting of plausible compact sources. The method allows the use of non-gridded, non-planar and inaccurate anomaly data and non-regular subsurface partitions. In addition, neither constraints for the depth to the top of the sources nor an initial model are necessary, although previous models can be incorporated into the process. We show the results of a test using two complex synthetic anomalies to demonstrate the efficiency of our inversion method. The application to real data is illustrated with aeromagnetic data of the volcanic island of Gran Canaria (Canary Islands).

Análise quantitativa de dispersão de vazamentos de substâncias inflamáveis e/ou tóxicas em ambientes com barreiras ou semi confinados.

Com o atual desenvolvimento industrial e tecnológico da sociedade, a presença de substâncias inflamáveis e/ou tóxicas aumentou significativamente em um grande número de atividades. A possível dispersão de gases perigosos em instalações de armazenamento ou em operações de transporte representam uma grande ameaça à saúde e ao meio ambiente. Portanto, a caracterização de uma nuvem inflamável e/ou tóxica é um ponto crítico na análise quantitativa de riscos. O objetivo principal desta tese foi fornecer novas perspectivas que pudessem auxiliar analistas de risco envolvidos na análise de dispersões em cenários complexos, por exemplo, cenários com barreiras ou semi-confinados. A revisão bibliográfica mostrou que, tradicionalmente, modelos empíricos e integrais são usados na análise de dispersão de substâncias tóxicas / inflamáveis, fornecendo estimativas rápidas e geralmente confiáveis ao descrever cenários simples (por exemplo, dispersão em ambientes sem obstruções sobre terreno plano). No entanto, recentemente, o uso de ferramentas de CFD para simular dispersões aumentou de forma significativa. Estas ferramentas permitem modelar cenários mais complexos, como os que ocorrem em espaços semi-confinados ou com a presença de barreiras físicas. Entre todas as ferramentas CFD disponíveis, consta na bibliografia que o software FLACS® tem bom desempenho na simulação destes cenários. Porém, como outras ferramentas similares, ainda precisa ser totalmente validado. Após a revisão bibliográfica sobre testes de campo já executados ao longo dos anos, alguns testes foram selecionados para realização de um exame preliminar de desempenho da ferramenta CFD utilizado neste estudo. Foram investigadas as possíveis fontes de incertezas em termos de capacidade de reprodutibilidade, de dependência de malha e análise de sensibilidade das variáveis de entrada e parâmetros de simulação. Os principais resultados desta fase foram moldados como princípios práticos a serem utilizados por analistas de risco ao realizar análise de dispersão com a presença de barreiras utilizando ferramentas CFD. Embora a revisão bibliográfica tenha mostrado alguns dados experimentais disponíveis na literatura, nenhuma das fontes encontradas incluem estudos detalhados sobre como realizar simulações de CFD precisas nem fornecem indicadores precisos de desempenho. Portanto, novos testes de campo foram realizados a fim de oferecer novos dados para estudos de validação mais abrangentes. Testes de campo de dispersão de nuvem de propano (com e sem a presença de barreiras obstruindo o fluxo) foram realizados no campo de treinamento da empresa Can Padró Segurança e Proteção (em Barcelona). Quatro testes foram realizados, consistindo em liberações de propano com vazões de até 0,5 kg/s, com duração de 40 segundos em uma área de descarga de 700 m2. Os testes de campo contribuíram para a reavaliação dos pontos críticos mapeados durante as primeiras fases deste estudo e forneceram dados experimentais para serem utilizados pela comunidade internacional no estudo de dispersão e validação de modelos. Simulações feitas utilizando-se a ferramenta CFD foram comparadas com os dados experimentais obtidos nos testes de campo. Em termos gerais, o simulador mostrou bom desempenho em relação às taxas de concentração da nuvem. O simulador reproduziu com sucesso a geometria complexa e seus efeitos sobre a dispersão da nuvem, mostrando claramente o efeito da barreira na distribuição das concentrações. No entanto, as simulações não foram capazes de representar toda a dinâmica da dispersão no que concerne aos efeitos da variação do vento, uma vez que as nuvens simuladas diluíram mais rapidamente do que nuvens experimentais.

Modelling of entrainment in industrial flotation cells: Water recovery and degree of entrainment

Entrainment in flotation can be considered as a two-step process, including the transfer of the suspended solids in the top of the pulp region just below the pulp-froth interface to the froth phase and the transfer of the entrained particles in the froth phase to the concentrate. Both steps have a strong classification characteristic. The degree of entrainment describes the classification effect of the drainage process in the froth phase. This paper briefly reviews two existing models of degree of entrainment. Experimental data were collected from an Outokumpu 3 m(3) tank cell in the Xstrata Mt. Isa Mines copper concentrator. The data are fitted to the models and the effect of cell operating conditions including air rate and froth height on the degree of entrainment is examined on a size-by-size basis. It is found that there is a strong correlation between the entrainment and the water recovery, which is close to lineal. for the fines. The degree of entrainment decreases with increase in particle size. Within the normal range of cell operating conditions, few particles coarser than 50 mu m are recovered by entrainment. In general, the degree of entrainment increases with increase in the ail rate and decreases with increase in the froth height. Air rate and froth height strongly interact with each other and affect the entrainment process mainly via changes in the froth retention time, the froth structure and froth properties. As a result, other mechanisms such as entrapment may become important in recovering the coarse entrained particles. (c) 2005 Elsevier Ltd. All rights reserved.

Construction of an Intraplate Fault System Model of South Australia, and Simulation Tool for the iSERVO Institute Seed Project

To foster ongoing international cooperation beyond ACES (APEC Cooperation for Earthquake Simulation) on the simulation of solid earth phenomena, agreement was reached to work towards establishment of a frontier international research institute for simulating the solid earth: iSERVO = International Solid Earth Research Virtual Observatory institute (http://www.iservo.edu.au). This paper outlines a key Australian contribution towards the iSERVO institute seed project, this is the construction of: (1) a typical intraplate fault system model using practical fault system data of South Australia (i.e., SA interacting fault model), which includes data management and editing, geometrical modeling and mesh generation; and (2) a finite-element based software tool, which is built on our long-term and ongoing effort to develop the R-minimum strategy based finite-element computational algorithm and software tool for modelling three-dimensional nonlinear frictional contact behavior between multiple deformable bodies with the arbitrarily-shaped contact element strategy. A numerical simulation of the SA fault system is carried out using this software tool to demonstrate its capability and our efforts towards seeding the iSERVO Institute.

Theoretical foundations of neural networks

Neural networks have often been motivated by superficial analogy with biological nervous systems. Recently, however, it has become widely recognised that the effective application of neural networks requires instead a deeper understanding of the theoretical foundations of these models. Insight into neural networks comes from a number of fields including statistical pattern recognition, computational learning theory, statistics, information geometry and statistical mechanics. As an illustration of the importance of understanding the theoretical basis for neural network models, we consider their application to the solution of multi-valued inverse problems. We show how a naive application of the standard least-squares approach can lead to very poor results, and how an appreciation of the underlying statistical goals of the modelling process allows the development of a more general and more powerful formalism which can tackle the problem of multi-modality.

The detection and identification of extraneous metals in material conveyance systems

The aim of this work was to design and build an equipment which can detect ferrous and non-ferrous objects in conveyed commodities, discriminate between them and locate the object along the belt and on the width of the belt. The magnetic induction mechanism was used as a means of achieving the objectives of this research. In order to choose the appropriate geometry and size of the induction field source, the field distributions of different source geometries and sizes were studied in detail. From these investigations it was found the square loop geometry is the most appropriate as a field generating source for the purpose of this project. The phenomena of field distribution in the conductors was also investigated. An equipment was designed and built at the preliminary stages of thework based on a flux-gate magnetometer with the ability to detect only ferrous objects.The instrument was designed such that it could be used to detect ferrous objects in the coal conveyors of power stations. The advantages of employing this detector in the power industry over the present ferrous metal electromagnetic separators were also considered. The objectives of this project culminated in the design and construction of a ferrous and non-ferrous detector with the ability to discriminate between ferrous and non-ferrous metals and to locate the objects on the conveying system. An experimental study was carried out to test the performance of the equipment in the detection of ferrous and non-ferrous objects of a given size carried on the conveyor belt. The ability of the equipment to discriminate between the types of metals and to locate the object on the belt was also evaluated experimentally. The benefits which can be gained from the industrial implementations of the equipment were considered. Further topics which may be investigated as an extension of this work are given.

Flow field analysis of some mixing and conveying screw element regions, within a closely intermeshing, co-rotating twin-screw extruder.

Grafting of antioxidants and other modifiers onto polymers by reactive extrusion, has been performed successfully by the Polymer Processing and Performance Group at Aston University. Traditionally the optimum conditions for the grafting process have been established within a Brabender internal mixer. Transfer of this batch process to a continuous processor, such as an extruder, has, typically, been empirical. To have more confidence in the success of direct transfer of the process requires knowledge of, and comparison between, residence times, mixing intensities, shear rates and flow regimes in the internal mixer and in the continuous processor.The continuous processor chosen for the current work in the closely intermeshing, co-rotating twin-screw extruder (CICo-TSE). CICo-TSEs contain screw elements that convey material with a self-wiping action and are widely used for polymer compounding and blending. Of the different mixing modules contained within the CICo-TSE, the trilobal elements, which impose intensive mixing, and the mixing discs, which impose extensive mixing, are of importance when establishing the intensity of mixing. In this thesis, the flow patterns within the various regions of the single-flighted conveying screw elements and within both the trilobal element and mixing disc zones of a Betol BTS40 CICo-TSE, have been modelled using the computational fluid dynamics package Polyflow. A major obstacle encountered when solving the flow problem within all of these sets of elements, arises from both the complex geometry and the time-dependent flow boundaries as the elements rotate about their fixed axes. Simulation of the time dependent boundaries was overcome by selecting a number of sequential 2D and 3D geometries, used to represent partial mixing cycles. The flow fields were simulated using the ideal rheological properties of polypropylene and characterised in terms of velocity vectors, shear stresses generated and a parameter known as the mixing efficiency. The majority of the large 3D simulations were performed on the Cray J90 supercomputer situated at the Rutherford-Appleton laboratories, with pre- and postprocessing operations achieved via a Silicon Graphics Indy workstation. A mechanical model was constructed consisting of various CICo-TSE elements rotating within a transparent outer barrel. A technique has been developed using coloured viscous clays whereby the flow patterns and mixing characteristics within the CICo-TSE may be visualised. In order to test and verify the simulated predictions, the patterns observed within the mechanical model were compared with the flow patterns predicted by the computational model. The flow patterns within the single-flighted conveying screw elements in particular, showed good agreement between the experimental and simulated results.

A computational model of prosody for Yorùbá text-to-speech synthesis

This work examines prosody modelling for the Standard Yorùbá (SY) language in the context of computer text-to-speech synthesis applications. The thesis of this research is that it is possible to develop a practical prosody model by using appropriate computational tools and techniques which combines acoustic data with an encoding of the phonological and phonetic knowledge provided by experts. Our prosody model is conceptualised around a modular holistic framework. The framework is implemented using the Relational Tree (R-Tree) techniques (Ehrich and Foith, 1976). R-Tree is a sophisticated data structure that provides a multi-dimensional description of a waveform. A Skeletal Tree (S-Tree) is first generated using algorithms based on the tone phonological rules of SY. Subsequent steps update the S-Tree by computing the numerical values of the prosody dimensions. To implement the intonation dimension, fuzzy control rules where developed based on data from native speakers of Yorùbá. The Classification And Regression Tree (CART) and the Fuzzy Decision Tree (FDT) techniques were tested in modelling the duration dimension. The FDT was selected based on its better performance. An important feature of our R-Tree framework is its flexibility in that it facilitates the independent implementation of the different dimensions of prosody, i.e. duration and intonation, using different techniques and their subsequent integration. Our approach provides us with a flexible and extendible model that can also be used to implement, study and explain the theory behind aspects of the phenomena observed in speech prosody.