Belief propagation for minimum weight many-to-one matchings in the random complete graph

In a complete bipartite graph with vertex sets of cardinalities n and n', assign random weights from exponential distribution with mean 1, independently to each edge. We show that, as n -> infinity, with n' = n/alpha] for any fixed alpha > 1, the minimum weight of many-to-one matchings converges to a constant (depending on alpha). Many-to-one matching arises as an optimization step in an algorithm for genome sequencing and as a measure of distance between finite sets. We prove that a belief propagation (BP) algorithm converges asymptotically to the optimal solution. We use the objective method of Aldous to prove our results. We build on previous works on minimum weight matching and minimum weight edge cover problems to extend the objective method and to further the applicability of belief propagation to random combinatorial optimization problems.

Investigations on Optimal Pulse-Width Modulation to Minimize Total Harmonic Distortion in the Line Current

PWM waveforms with positive voltage transition at the positive zero crossing of the fundamental voltage (type-A) are generally considered for PWM waveform with even number of switching angles per quarter whereas, waveforms with negative voltage transition at the positive zero crossing (type-B) are considered for odd number of switching angles per quarter. Optimal PWM, for minimization of total harmonic distortion of line to line (VWTHD), is generally solved with the aforementioned criteria. This paper establishes that a combination of both types of waveforms gives better performance than any individual type in terms of minimum VWTHD for complete range of modulation index (M). Optimal PWM for minimum VWTHD is solved for PWM waveforms with pulse numbers (P) of 5 and 7. Both type-A and type-B waveforms are found to be better in different ranges of M. The theoretical findings are confirmed through simulation and experimental results on a 3.7 kW squirrel cage induction motor in an open-loop V/f drive. Further, the optimal PWM is analysed from a space vector point of view.

PERCOLATION ON THE INFORMATION-THEORETICALLY SECURE SIGNAL TO INTERFERENCE RATIO GRAPH

We consider a continuum percolation model consisting of two types of nodes, namely legitimate and eavesdropper nodes, distributed according to independent Poisson point processes in R-2 of intensities lambda and lambda(E), respectively. A directed edge from one legitimate node A to another legitimate node B exists provided that the strength of the signal transmitted from node A that is received at node B is higher than that received at any eavesdropper node. The strength of the signal received at a node from a legitimate node depends not only on the distance between these nodes, but also on the location of the other legitimate nodes and an interference suppression parameter gamma. The graph is said to percolate when there exists an infinitely connected component. We show that for any finite intensity lambda(E) of eavesdropper nodes, there exists a critical intensity lambda(c) < infinity such that for all lambda > lambda(c) the graph percolates for sufficiently small values of the interference parameter. Furthermore, for the subcritical regime, we show that there exists a lambda(0) such that for all lambda < lambda(0) <= lambda(c) a suitable graph defined over eavesdropper node connections percolates that precludes percolation in the graphs formed by the legitimate nodes.

Lateralisation abnormalities in obsessive-compulsive disorder: a line bisection study

Objective Asymmetry in brain structure and function is implicated in the pathogenesis of psychiatric disorders. Although right hemisphere abnormality has been documented in obsessive-compulsive disorder (OCD), cerebral asymmetry is rarely examined. Therefore, in this study, we examined anomalous cerebral asymmetry in OCD patients using the line bisection task. Methods A total of 30 patients with OCD and 30 matched healthy controls were examined using a reliable and valid two-hand line bisection (LBS) task. The comparative profiles of LBS scores were analysed using analysis of covariance. Results Patients with OCD bisected significantly less number of lines to the left and had significant rightward deviation than controls, indicating right hemisphere dysfunction. The correlations observed in this study suggest that those with impaired laterality had more severe illness at baseline. Conclusions The findings of this study indicate abnormal cerebral lateralisation and right hemisphere dysfunction in OCD patients.

A Physical Model for Inception and Propagation of Upward Lightning Leader from a 1200 kV AC Power Transmission Line

UHV power transmission lines have high probability of shielding failure due to their higher height, larger exposure area and high operating voltage. Lightning upward leader inception and propagation is an integral part of lightning shielding failure analysis and need to be studied in detail. In this paper a model for lightning attachment has been proposed based on the present knowledge of lightning physics. Leader inception is modeled based on the corona charge present near the conductor region and the propagation model is based on the correlation between the lightning induced voltage on the conductor and the drop along the upward leader channel. The inception model developed is compared with previous inception models and the results obtained using the present and previous models are comparable. Lightning striking distances (final jump) for various return stroke current were computed for different conductor heights. The computed striking distance values showed good correlation with the values calculated using the equation proposed by the IEEE working group for the applicable conductor heights of up to 8 m. The model is applied to a 1200 kV AC power transmission line and inception of the upward leader is analyzed for this configuration.

Divide and Conquer: Efficient Large-Scale Structure from Motion Using Graph Partitioning

Despite significant advances in recent years, structure-from-motion (SfM) pipelines suffer from two important drawbacks. Apart from requiring significant computational power to solve the large-scale computations involved, such pipelines sometimes fail to correctly reconstruct when the accumulated error in incremental reconstruction is large or when the number of 3D to 2D correspondences are insufficient. In this paper we present a novel approach to mitigate the above-mentioned drawbacks. Using an image match graph based on matching features we partition the image data set into smaller sets or components which are reconstructed independently. Following such reconstructions we utilise the available epipolar relationships that connect images across components to correctly align the individual reconstructions in a global frame of reference. This results in both a significant speed up of at least one order of magnitude and also mitigates the problems of reconstruction failures with a marginal loss in accuracy. The effectiveness of our approach is demonstrated on some large-scale real world data sets.

Graph Modification Problems: A Modern Perspective

We give an overview of recent results and techniques in parameterized algorithms for graph modification problems.

Query Click and Text Similarity Graph for Query Suggestions

Query suggestion is an important feature of the search engine with the explosive and diverse growth of web contents. Different kind of suggestions like query, image, movies, music and book etc. are used every day. Various types of data sources are used for the suggestions. If we model the data into various kinds of graphs then we can build a general method for any suggestions. In this paper, we have proposed a general method for query suggestion by combining two graphs: (1) query click graph which captures the relationship between queries frequently clicked on common URLs and (2) query text similarity graph which finds the similarity between two queries using Jaccard similarity. The proposed method provides literally as well as semantically relevant queries for users' need. Simulation results show that the proposed algorithm outperforms heat diffusion method by providing more number of relevant queries. It can be used for recommendation tasks like query, image, and product suggestion.

Kinematics and dynamics of Jansen leg mechanism: A bond graph approach

The Jansen mechanism is a one degree-of-freedom, planar, 12-link, leg mechanism that can be used in mobile robotic applications and in gait analysis. This paper presents the kinematics and dynamics of the Jansen leg mechanism. The forward kinematics, accomplished using circle intersection method, determines the trajectories of various points on the mechanism in the chassis (stationary link) reference frame. From the foot point trajectory, the step length is shown to vary linearly while step height varies non-linearly with change in crank radius. A dynamic model for the Jansen leg mechanism is proposed using bond graph approach with modulated multiport transformers. For given ground reaction force pattern and crank angular speed, this model helps determine the motor torque profile as well as the link and joint stresses. The model can therefore be used to rate the actuator torque and in design of the hardware and controller for such a system. The kinematics of the mechanism can also be obtained from this dynamic model. The proposed model is thus a useful tool for analysis and design of systems based on the Jansen leg mechanism. (C) 2015 Elsevier B.V. All rights reserved.

Ultrasonic Guided Wave Sensor Network Optimization for Monitoring Rivet Line

Guided waves using piezo-electric wafer active sensors (PWAS) is one of the useful techniques of damage detection. Sensor network optimization with minimal network hardware footprint and maximal area of coverage remains a challenging problem. PWAS sensors are placed at discrete locations in order to inspect damages in plates and the idea has the potential to be extended to assembled structures. Various actuator-sensor configurations are possible within the network in order to identify and locate damages. In this paper we present a correlation based approach to monitor cracks emanating from rivet line using a simulated guided wave signal whose sensor is operating in pulse echo mode. Discussions regarding the identification of phase change due to reflections from the crack are also discussed in this paper.

Falcon: A Graph Manipulation Language for Heterogeneous Systems

Graph algorithms have been shown to possess enough parallelism to keep several computing resources busy-even hundreds of cores on a GPU. Unfortunately, tuning their implementation for efficient execution on a particular hardware configuration of heterogeneous systems consisting of multicore CPUs and GPUs is challenging, time consuming, and error prone. To address these issues, we propose a domain-specific language (DSL), Falcon, for implementing graph algorithms that (i) abstracts the hardware, (ii) provides constructs to write explicitly parallel programs at a higher level, and (iii) can work with general algorithms that may change the graph structure (morph algorithms). We illustrate the usage of our DSL to implement local computation algorithms (that do not change the graph structure) and morph algorithms such as Delaunay mesh refinement, survey propagation, and dynamic SSSP on GPU and multicore CPUs. Using a set of benchmark graphs, we illustrate that the generated code performs close to the state-of-the-art hand-tuned implementations.

Theoretical insights on the electro-thermal transport properties of monolayer MoS2 with line defects

Two dimensional (2D) materials demonstrate several novel electrical, mechanical, and thermal properties which are quite distinctive to those of their bulk form. Among many others, one important potential application of the 2D material is its use in the field of energy harvesting. Owing to that, here we present a detailed study on electrical as well as thermal transport of monolayer MoS2, in quasi ballistic regime. Besides the perfect monolayer in its pristine form, we also consider various line defects which have been experimentally observed in mechanically exfoliated MoS2 samples. For calculating various parameters related to the electrical transmission, we employ the non-equilibrium Green's function-density functional theory combination. However, to obtain the phonon transmission, we take help of the parametrized Stillinger-Weber potential which can accurately delineate the inter-atomic interactions for the monolayer MoS2. Due to the presence of line defects, we observed significant reductions in both the charge carrier and the phonon transmissions through a monolayer MoS2 flake. Moreover, we also report a comparative analysis showing the temperature dependency of the thermoelectric figure of merit values, as obtained for the perfect as well as the other defective 2D samples. (C) 2016 AIP Publishing LLC.