Many real-world systems can be represented as network-graphs. Some of the networks have an inherent community structure based on interactions. The problem of identifying this grouping structure given a graph is termed as community detection problem which has certain existing algorithms. This thesis contributes by providing specific improvements to various community detection algorithms such as spectral clustering and extreme point algorithm. One of the main contributions is proposing a new sub-sampling method to make existing spectral clustering method scalable by reducing the computational complexity. Also, we have implemented extreme points algorithm for a general multiple communities detection case along with a sub-sampling based version to reduce the computational complexity. We have also developed spectral clustering algorithm for popularity-adjusted block model (PABM) model based graphs to make the algorithm exact thus improving its accuracy. / Master of Science / We live in an increasingly interconnected world, where agents constantly interact with each other. This general agent-interaction framework describes many important systems, such as social interpersonal systems, protein interaction systems, trade and financial systems, power grids, and the World Wide Web, to name a few. By denoting agents as nodes and their interconnections as links, any such system can be represented as a network. Such networks or graphs provide a powerful and universal representation for analyzing a wide variety of systems spanning a remarkable range of scientific disciplines. Networks act as conduits for many kinds of transmissions. For instance, they are influential in the dissemination of ideas, adoption of technologies, helping find jobs and spread of diseases. Thus networks play a critical role both in providing information and helping make decisions making them a crucial part of the Data and Decisions Destination Area. A well-known feature of many networks is community structure. Nodes in a network are often found to belong to groups or communities that exhibit similar behavior. The identification of this community structure, called community detection, is an important problem with many critical applications. For example, communities in a protein interaction network often correspond to functional groups. This thesis focuses on cutting-edge methods for community detection in networks. The main approach is efficient community detection via sub-sampling. This is applied to two different approaches. The first approach is optimization of a modularity function using a low-rank approximation for multiple communities. The second approach is a spectral clustering where we aim to formulate an algorithm for community detection by exploiting the eigenvectors of the network adjacency matrix.

This dissertation proposes new methods for measuring jitter of high-speed digital signals. The proposed techniques are twofold. First, a low-speed jitter measurement environment is realized by using a jitter expansion sensor. This sensor uses a low-frequency reference signal as compared to high-frequency reference signals required in standard high-speed signal jitter measurement instruments. The jitter expansion sensor generates a low-speed signal at the output, which contains jitter content of the original high-speed digital signal. The low-speed sensor output signal can be easily acquired with a low-speed digitizer and then analyzed for jitter. The proposed low-speed jitter measurement environment using the jitter expansion sensor enhances the reliability of current jitter measurement approaches since low-speed signals used as a reference signal and a sensor output signal can be generated and applied to measurement systems with reduced additive noise. The second approach is direct digitization without using a sensor, in which a high-speed digital signal with jitter is incoherently sub-sampled and then reconstructed in the discrete-time domain by using digital signal reconstruction algorithms. The core idea of this technique is to remove the hardware required in standard sampling-based jitter measurement instruments for time/phase synchronization by adopting incoherent sub-sampling as compared to coherent sub-sampling and to reduce the need for a high-speed digitizer by sub-sampling a periodic signal over its many realizations. In the proposed digitization technique, the signal reconstruction algorithms are used as a substitute for time/phase synchronization hardware. When the reconstructed signal is analyzed for jitter in digital post-processing, a self-reference signal is extracted from the reconstructed signal by using wavelet denoising methods. This digitally generated self-reference signal alleviates the need for external analog reference signals. The self-reference signal is used as a timing reference when timing dislocations of the reconstructed signal are measured in the discrete-time domain. Various types of jitter of the original high-speed reference signals can be estimated using the proposed jitter analysis algorithms.

Understanding the deep biosphere is of great commercial and scientific interest and will contri-bute to increased knowledge of the environment. If environmentally relevant results are to be ob-tained the precondition to achieve genuine findings is research in pristine habitat as close as pos-sible to those encountered in-situ. Therefore benthic conditions of sediment structure and gas hydrates, temperature, pressure and bio-geochemistry have to be maintained during the sequences of sampling, retrieval, transfer, sto-rage and downstream analysis. At the Technische Universität Berlin (TUB) the Pressurized Core Sub-Sampling and Extrusion System (PRESS) was developed in the EU project HYACE/HYACINTH. It enables well-defined sectioning and transfer of drilled pressure-cores [obtained by HYACE Rotary Corer (HRC) and Fugro Pressure Corer (FPC)] into transportation and investigation chambers. Coupled with DeepIsoBUG (University Cardiff, John Parkes) it allows sub-sampling and incubation of coaxial core-sections to examine high-pressure adapted bacteria or remote biogeochemical processes in defined research conditions of the laboratory; all sterile, anaerobic and without depressurisation. Appraisals of successful PRESS deployments in the Gulf of Mexico, on IODP Expedition 311 and as part of the NGHP expedition 01 demonstrate the general concept to be feasible and useful. Aided by Deutsche Forschungsgemeinschaft (DFG) TUB is currently working on concepts to downscale the system in order to reduce logistical and financial expenses and, likewise, to enlarge its implementation by requiring less operating space. Redesigning the cutting mechanism shall simultaneously adjust the system to harder cores (e.g., ICDP). Novel transportation chambers for processed sub-samples intend to make the system more attractive for a broad spectrum of users and reduce their interdependence.

Ray tracing has for a long time been used to create photo realistic images, but due to complex calculations done per pixel and slow hardware, the time to render a frame has been counted in hours or even days and this can be drawback if a change of a scene cannot be seen instantly. When ray tracing a frame takes less than a second to render we call it “real time ray tracing” or “interactive ray tracing” and many solutions have been developed and some involves distributing the computation to different computers interconnected in a very fast network (100 Mbit or higher). There are some drawbacks with this approach because most people do not have more than one computer and if they have, the computers are most likely not connected to each other. Since the hardware of today is fast enough to render a pretty complex image within minutes it should be possible to achieve real time ray tracing by combining many different methods that has been developed and reduce the render time. This work will examine what has to be sacrificed in image quality and complexity of static scenes, in order to achieve real time frame rate with ray tracing on a single computer. Some of the methods that will be covered in this work are frame optimizations, secondary rays optimization, hierarchies, culling, shadow caching, and sub sampling.

Dans le but d’améliorer la disponibilité des services fournis par un récepteur, la conception d’un récepteur GNSS permettant de recevoir plusieurs signaux de toutes les bandes simultanément semble être la solution. Une architecture à sous échantillonnage RF optimisée de type SDR (Software Defined Radio) comportant un étage RF intégrable et reconfigurable et un étage de traitement numérique avec une implémentation logicielle du traitement en bande de base est défini pour ce récepteur GNSS, tout en répondant aux exigences des spécifications des standards GNSS : des réseaux radio cellulaires : GPS, Glonass, Galileo, Beidou. Un choix des composants discrets suite au dimensionnement system est effectué et ceci pour installer un prototype de validation expérimental. Ensuite nous nous s’intéressons à la caractérisation de la chaine RF afin d’étudier les limitations causés par la non linéarité et d’étudier la stabilité du prototype proposé. Un étage de traitement numérique des signaux IF, capturés à la sortie de l’ADC, est implémenté sous Matlab. L’acquisition de ces données permet la détermination des satellites visible à un instant donné qui nous permet éventuellement la détermination d’une position / In order to improve the availability of services provided by a receiver, designing a GNSS receiver to collect multiple signals from all bands simultaneously seems to be the solution. An optimized software-defined RF (SDR) sub-sampling architecture with an integral and reconfigurable RF stage and a digital processing stage with a software implementation of the baseband processing is defined for this GNSS receiver, while meeting the requirements GNSS standards specifications: cellular radio networks: GPS, Glonass, Galileo, Beidou. Many discrete components are selected after system dimensioning. Thus, experimental validation prototype is installed. Then we are interested in the characterization of the RF front-end in order to determine the limitations caused by the nonlinearity and to study the stability of the proposed prototype. A stage of digital processing of the IF signals, captured at the ADC output, is implemented under Matlab software. The acquisition of these data allows the determination of satellites visible at a given instant that allows us to determine a position

A análise de vibrações nos sistemas estruturais e rotativos permite detectar problemas indesejáveis, como a fadiga estrutural e o desgaste excessivo, que contribuem para a redução da vida útil do sistema e seus componentes. Tradicionalmente, a medição das vibrações é realizada por sensores de contato (acelerômetros e extensômetros), que possuem como inconveniente a adição de sua massa no sistema. Como alternativa, existem os sensores de não contato (LVD e ESPI), que são equipamentos de custo elevado. Este trabalho visa o desenvolvimento de um equipamento de baixo custo que realize medições multi-pontos sem contato do comportamento vibratório de estruturas e eixos rotativos. O método proposto utiliza como base os princípios da fotogrametria em conjunto com técnicas de subamostragem, que são utilizadas em estruturas ou máquinas com frequências de vibração conhecidas (e.g máquinas rotativas). A metodologia foi inicialmente aplicada em uma viga engastada-livre, excitada periodicamente por um shaker eletrodinâmico e posteriormente em um sistema rotativo montado em um bancada de testes. A viabilidade em se utilizar o método foi verificada comparando os resultados obtidos com as medições realizadas por um vibrômetro laser Doppler, no caso do sistema estrutural, e por sensores de proximidade indutivo nas vibrações do eixo rotativo. Com base nos comparativos, conclui-se que este método, mesmo apresentando limitações de resolução, pode ser perfeitamente empregado em medições de sistemas estruturais e rotativos assim como na análise modal operacional de estruturas. / The analysis of vibrations in structural and rotating systems allows the detection of undesirable problems, such as the structural fatigue and excessive wear, which contribute to the reduction of the useful life of the systems and their components. Traditionally, the measurement of vibrations is carried out by contacting sensors (accelerometers and strain gauges), which have the inconvenience of adding mass into the system. Alternativelly, there are the non-contacting sensors (LVD and ESPI), which are high cost equipments. This work aims at developing a low cost equipment that carry out multi-point non-contact measurements of the vibratory behavior of structures and rotating shafts. The proposed method uses as a basis the principles of photogrammetry together with sub-sampling techniques, which are used in structure or machines with known vibration frequencies (e.g rotating machines). The methodology was initially applied on a cantilever beam, periodically excited by an electrodynamic shaker and later in a rotating system mounted on a test bench. The feasibility of using the method was verified comparing the results obtained with measurements from a laser Doppler vibrometer, in the case of the structural system, and with inductive proximity sensors in the rotating shaft vibration. Based on the comparison analysis, one observes that this method can be perfectly used in vibration measurements in structural and rotating systems even with limitations in resolution as well as in operational modal analysis of structures.

A análise de vibrações nos sistemas estruturais e rotativos permite detectar problemas indesejáveis, como a fadiga estrutural e o desgaste excessivo, que contribuem para a redução da vida útil do sistema e seus componentes. Tradicionalmente, a medição das vibrações é realizada por sensores de contato (acelerômetros e extensômetros), que possuem como inconveniente a adição de sua massa no sistema. Como alternativa, existem os sensores de não contato (LVD e ESPI), que são equipamentos de custo elevado. Este trabalho visa o desenvolvimento de um equipamento de baixo custo que realize medições multi-pontos sem contato do comportamento vibratório de estruturas e eixos rotativos. O método proposto utiliza como base os princípios da fotogrametria em conjunto com técnicas de subamostragem, que são utilizadas em estruturas ou máquinas com frequências de vibração conhecidas (e.g máquinas rotativas). A metodologia foi inicialmente aplicada em uma viga engastada-livre, excitada periodicamente por um shaker eletrodinâmico e posteriormente em um sistema rotativo montado em um bancada de testes. A viabilidade em se utilizar o método foi verificada comparando os resultados obtidos com as medições realizadas por um vibrômetro laser Doppler, no caso do sistema estrutural, e por sensores de proximidade indutivo nas vibrações do eixo rotativo. Com base nos comparativos, conclui-se que este método, mesmo apresentando limitações de resolução, pode ser perfeitamente empregado em medições de sistemas estruturais e rotativos assim como na análise modal operacional de estruturas. / The analysis of vibrations in structural and rotating systems allows the detection of undesirable problems, such as the structural fatigue and excessive wear, which contribute to the reduction of the useful life of the systems and their components. Traditionally, the measurement of vibrations is carried out by contacting sensors (accelerometers and strain gauges), which have the inconvenience of adding mass into the system. Alternativelly, there are the non-contacting sensors (LVD and ESPI), which are high cost equipments. This work aims at developing a low cost equipment that carry out multi-point non-contact measurements of the vibratory behavior of structures and rotating shafts. The proposed method uses as a basis the principles of photogrammetry together with sub-sampling techniques, which are used in structure or machines with known vibration frequencies (e.g rotating machines). The methodology was initially applied on a cantilever beam, periodically excited by an electrodynamic shaker and later in a rotating system mounted on a test bench. The feasibility of using the method was verified comparing the results obtained with measurements from a laser Doppler vibrometer, in the case of the structural system, and with inductive proximity sensors in the rotating shaft vibration. Based on the comparison analysis, one observes that this method can be perfectly used in vibration measurements in structural and rotating systems even with limitations in resolution as well as in operational modal analysis of structures.

Les nouveaux besoins en communications sans fil pussent le développement de systèmes de transmission RF en termes the reconfigurabilité, multistandard et à basse consommation. Ces travaux de thèse font l’objet de la proposition d’une nouvelle architecture de réception capable d’adresser ces aspects dans le contexte des réseaux WPAN. La technique de sous échantillonnage (BPS-Bandpass Sampling) est appliquée et permet d’exploiter et certain nombre d’avantages liées au traitement du signal à Temps Discret (DT-Discrete Time signal processing), notamment le filtrage et la décimation. Si comparées à la Radio Logicielle, ces techniques permettent de relâcher les contraintes liées aux ADCs en maintenant des caractéristiques multistandard et de reconfigurabilité. Un simulateur dans le domaine fréquentiel large bande a été développé sous MATLAB pour répondre à des limitations au niveau système comme par exemple le repliement spectral et le produit gain bande. En addition avec une nouvelle méthode de conception système, cet outil permet de séparer les différentes contraintes des blocs pour la définition d’un plan de fréquence et the filtrage optimaux. La séparation des différentes contributions dans la dégradation du SNDR (notamment le bruit thermique, bruit de phase, non linéarité et le repliement), permet de relâcher de spécifications critiques liées à la consommation de puissance. L’architecture à sous échantillonnage proposée dans la thèse est résultat d’une comparaison quantitative des différentes architectures à sous échantillonnage, tout en appliquant la méthode et l’outil de conception système développés. Des aspects comme l’optimisation du filtrage entre les techniques à temps continu et temps discret et le plan de fréquence associé, permettent de trouve l’architecture qui représente le meilleur compromis entre la consommation électrique et l’agilité, dans le contexte voulu. Le bloc de filtrage à temps discret est identifié comme étant critique, et une étude sur les limitations d’implémentation circuit est menée. Des effets come les capacités parasites, l’imparité entre les capacités, le bruit du commutateur, la non linéarité, le gain finit de Ampli OP, sont évalués à travers d’une simulation comportementale en VHDL-AMS. On observe la robustesse des circuits orientés temps discret par rapport les contraintes des nouvelles technologies intégrés. Finalement, le système est spécifié en termes de bruit de phase, qui peuvent représenter jusqu’à 30% de la consommation en puissance. Dans ce but, une nouvelle méthode numérique est proposée pour être capable d’évaluer le rapport signal sur distorsion due au jitter SDjR dans le processus de sous échantillonnage. En plus, une conclusion non intuitive est survenue de cette étude, où on que réduire la fréquence d’échantillonnage n’augmente pas les contraintes en termes de jitter pour le système. L’architecture proposée issue de cette étude est sujet d’un développement circuit pour la validation du concept. / New needs on wireless communications pushes the development in terms reconfigurable, multistandards and low power radio systems. The objective of this work is to propose and design new receiver architecture capable of addressing these aspects in the context of the WPAN networks. The technique of Bandpass Sampling (BPS) is applied and permits to exploit a certain number of advantages linked to the discrete time (DT) signal processing, notably filtering and decimation. Compared to the Software-defined Radio (SDR), these techniques permit to relax the ADC constraints while keeping the multi standard and reconfigurable features. A wide band system level simulation tool is developed using MATLAB platform to overcome system level limitations such spectral aliasing and gain bandwidth product. In addition to a new system design method, the tool helps separating the blocks constraints and defining the optimum frequency plan and filtering. Separating the different contributions on the SNDR degradation (noise, phase noise, non linearity, and aliasing), critical specifications for power consumption can be relaxed. The proposed BPS architecture on the thesis is a result of a quantitative comparison of different BPS architectures, applying the system design method and tool. Aspects such filtering optimization between continuous and discrete time filtering and the associated frequency plan permitted to find the architecture which represents the best trade-off between power consumption and agility on the aimed context. The DT filtering block is therefore identified as critical block, which a study on the circuit implementation limitations is carried out. Effects such parasitic capacitances and capacitance mismatch, switch noise, non linear distortion, finite gain OTA, are evaluated through VHDL-AMS modelling. It is observed the robustness of discrete time oriented circuits. Finally, phase noise specifications are given considering that frequency synthesis circuits may represent up to 30% of the power consumption. For that goal, a new numerical method is proposed, capable of evaluating the signal to jitter distortion ratio SDjR on the BPS process. Moreover, a non intuitive conclusion is given, where reducing the sampling frequency does not increase the constraints in terms of jitter. The proposed architecture issue from this study is in stage of circuit level design in the project team of LETI for final proof of concept.

This thesis addresses the problem of gas distribution modelling for gas monitoring and gas detection. The presented research is particularly focused on the methods that are suitable for uncontrolled environments. In such environments, gas source locations and the physical properties of the environment, such as humidity and temperature may be unknown or only sparse noisy local measurements are available. Example applications include air pollution monitoring, leakage detection, and search and rescue operations. This thesis addresses how to efficiently obtain and compute predictive models that accurately represent spatio-temporal gas distribution. Most statistical gas distribution modelling methods assume that gas dispersion can be modelled as a time-constant random process. While this assumption may hold in some situations, it is necessary to model variations over time in order to enable applications of gas distribution modelling for a wider range of realistic scenarios. This thesis proposes two time-dependent gas distribution modelling methods. In the first method, a temporal (sub-)sampling strategy is introduced. In the second method, a time-dependent gas distribution modelling approach is presented, which introduces a recency weight that relates measurement to prediction time. These contributions are presented and evaluated as an extension of a previously proposed method called Kernel DM+V using several simulation and real-world experiments. The results of comparing the proposed time-dependent gas distribution modelling approaches to the time-independent version Kernel DM+V indicate a consistent improvement in the prediction of unseen measurements, particularly in dynamic scenarios under the condition that there is a sufficient spatial coverage. Dynamic scenarios are often defined as environments where strong fluctuations and gas plume development are present. For mobile robot olfaction, we are interested in sampling strategies that provide accurate gas distribution models given a small number of samples in a limited time span. Correspondingly, this thesis addresses the problem of selecting the most informative locations to acquire the next samples. As a further contribution, this thesis proposes a novel adaptive sensor planning method. This method is based on a modified artificial potential field, which selects the next sampling location based on the currently predicted gas distribution and the spatial distribution of previously collected samples. In particular, three objectives are used that direct the sensor towards areas of (1) high predictive mean and (2) high predictive variance, while (3) maximising the coverage area. The relative weight of these objectives corresponds to a trade-off between exploration and exploitation in the sampling strategy. This thesis discusses the weights or importance factors and evaluates the performance of the proposed sampling strategy. The results of the simulation experiments indicate an improved quality of the gas distribution models when using the proposed sensor planning method compared to commonly used methods, such as random sampling and sampling along a predefined sweeping trajectory. In this thesis, we show that applying a locality constraint on the proposed sampling method decreases the travelling distance, which makes the proposed sensor planning approach suitable for real-world applications where limited resources and time are available. As a real-world use-case, we applied the proposed sensor planning approach on a micro-drone in outdoor experiments. Finally, this thesis discusses the potential of using gas distribution modelling and sensor planning in large-scale outdoor real-world applications. We integrated the proposed methods in a framework for decision-making in hazardous inncidents where gas leakage is involved and applied the gas distribution modelling in two real-world use-cases. Our investigation indicates that the proposed sensor planning and gas distribution modelling approaches can be used to inform experts both about the gas plume and the distribution of gas in order to improve the assessment of an incident.

No description available.