Random function priors for exchangeable arrays with applications to graphs and relational data

A fundamental problem in the analysis of structured relational data like graphs, networks, databases, and matrices is to extract a summary of the common structure underlying relations between individual entities. Relational data are typically encoded in the form of arrays; invariance to the ordering of rows and columns corresponds to exchangeable arrays. Results in probability theory due to Aldous, Hoover and Kallenberg show that exchangeable arrays can be represented in terms of a random measurable function which constitutes the natural model parameter in a Bayesian model. We obtain a flexible yet simple Bayesian nonparametric model by placing a Gaussian process prior on the parameter function. Efficient inference utilises elliptical slice sampling combined with a random sparse approximation to the Gaussian process. We demonstrate applications of the model to network data and clarify its relation to models in the literature, several of which emerge as special cases.

Model reductions for inference: generality of pairwise, binary, and planar factor graphs.

We offer a solution to the problem of efficiently translating algorithms between different types of discrete statistical model. We investigate the expressive power of three classes of model-those with binary variables, with pairwise factors, and with planar topology-as well as their four intersections. We formalize a notion of "simple reduction" for the problem of inferring marginal probabilities and consider whether it is possible to "simply reduce" marginal inference from general discrete factor graphs to factor graphs in each of these seven subclasses. We characterize the reducibility of each class, showing in particular that the class of binary pairwise factor graphs is able to simply reduce only positive models. We also exhibit a continuous "spectral reduction" based on polynomial interpolation, which overcomes this limitation. Experiments assess the performance of standard approximate inference algorithms on the outputs of our reductions.

Stabilization of symmetric formations to motion around convex loops

We provide a cooperative control algorithm to stabilize symmetric formations to motion around closed curves suitable for mobile sensor networks. This work extends previous results for stabilization of symmetric circular formations. We study a planar particle model with decentralized steering control subject to limited communication. Because of their unique spectral properties, the Laplacian matrices of circulant graphs play a key role. We illustrate the result for a skewed superellipse, which is a type of curve that includes circles, ellipses, and rounded parallelograms. © 2007 Elsevier B.V. All rights reserved.

Minimum maneuver time calculation using convex optimization

The problem of calculating the minimum lap or maneuver time of a nonlinear vehicle, which is linearized at each time step, is formulated as a convex optimization problem. The formulation provides an alternative to previously used quasi-steady-state analysis or nonlinear optimization. Key steps are: the use of model predictive control; expressing the minimum time problem as one of maximizing distance traveled along the track centerline; and linearizing the track and vehicle trajectories by expressing them as small displacements from a fixed reference. A consequence of linearizing the vehicle dynamics is that nonoptimal steering control action can be generated, but attention to the constraints and the cost function minimizes the effect. Optimal control actions and vehicle responses for a 90 deg bend are presented and compared to the nonconvex nonlinear programming solution. Copyright © 2013 by ASME.

Inter-simple sequence repeat (ISSR) analysis of genetic variation of Chondrus crispus populations from North Atlantic

ISSR analysis was used to investigate genetic variations of 184 haploid and diploid samples from nine North Atlantic Chondrus crispus Stackhouse populations and one outgroup Yellow Sea Chondrus ocellatus Holmes population. Twenty-two of 50 primers were selected and 163 loci were scored for genetic diversity analysis. Genetic diversity varied among populations, percentage of polymorphic bands (PPB) ranged from 27.0 to 55.8%, H(Nei's genetic diversity) ranged from 0.11 to 0.20 and I(Shannon's information index) ranged from 0.16 to 0.30. Estimators PPB, H and I had similar values in intra-population genetic diversity, regardless of calculation methods. Analysis of molecular variance (AMOVA) apportioned inter-population and intra-population variations for C crispus, showing more genetic variance (56.5%) occurred in intra-population, and 43.5% variation among nine populations. The Mantel test suggested that genetic differentiation between nine C. crispus populations was closely related with geographic distances (R = 0.78, P = 0.002). Results suggest that, on larger distance scale (ca. > 1000 km), ISSR analysis is useful for determining genetic differentiations of C crispus populations including morphologically inseparable haploid and diploid individuals. (c) 2007 Elsevier B.V. All rights reserved.

On the Behavior of the Homogeneous Self-Dual Model for Conic Convex Optimization

There is a natural norm associated with a starting point of the homogeneous self-dual (HSD) embedding model for conic convex optimization. In this norm two measures of the HSD model’s behavior are precisely controlled independent of the problem instance: (i) the sizes of ε-optimal solutions, and (ii) the maximum distance of ε-optimal solutions to the boundary of the cone of the HSD variables. This norm is also useful in developing a stopping-rule theory for HSD-based interior-point methods such as SeDuMi. Under mild assumptions, we show that a standard stopping rule implicitly involves the sum of the sizes of the ε-optimal primal and dual solutions, as well as the size of the initial primal and dual infeasibility residuals. This theory suggests possible criteria for developing starting points for the homogeneous self-dual model that might improve the resulting solution time in practice

Nearest-neighbor Queries in Probabilistic Graphs

Large probabilistic graphs arise in various domains spanning from social networks to biological and communication networks. An important query in these graphs is the k nearest-neighbor query, which involves finding and reporting the k closest nodes to a specific node. This query assumes the existence of a measure of the "proximity" or the "distance" between any two nodes in the graph. To that end, we propose various novel distance functions that extend well known notions of classical graph theory, such as shortest paths and random walks. We argue that many meaningful distance functions are computationally intractable to compute exactly. Thus, in order to process nearest-neighbor queries, we resort to Monte Carlo sampling and exploit novel graph-transformation ideas and pruning opportunities. In our extensive experimental analysis, we explore the trade-offs of our approximation algorithms and demonstrate that they scale well on real-world probabilistic graphs with tens of millions of edges.

Sorting under partial information (without the ellipsoid algorithm)

We revisit the well-known problem of sorting under partial information: sort a finite set given the outcomes of comparisons between some pairs of elements. The input is a partially ordered set P, and solving the problem amounts to discovering an unknown linear extension of P, using pairwise comparisons. The information-theoretic lower bound on the number of comparisons needed in the worst case is log e(P), the binary logarithm of the number of linear extensions of P. In a breakthrough paper, Jeff Kahn and Jeong Han Kim (STOC 1992) showed that there exists a polynomial-time algorithm for the problem achieving this bound up to a constant factor. Their algorithm invokes the ellipsoid algorithm at each iteration for determining the next comparison, making it impractical. We develop efficient algorithms for sorting under partial information. Like Kahn and Kim, our approach relies on graph entropy. However, our algorithms differ in essential ways from theirs. Rather than resorting to convex programming for computing the entropy, we approximate the entropy, or make sure it is computed only once in a restricted class of graphs, permitting the use of a simpler algorithm. Specifically, we present: an O(n2) algorithm performing O(log n·log e(P)) comparisons; an O(n2.5) algorithm performing at most (1+ε) log e(P) + Oε(n) comparisons; an O(n2.5) algorithm performing O(log e(P)) comparisons. All our algorithms are simple to implement. © 2010 ACM.

Comparing large graphs efficiently by margins of feature vectors

Measuring the structural similarity of graphs is a challenging and outstanding problem. Most of the classical approaches of the so-called exact graph matching methods are based on graph or subgraph isomorphic relations of the underlying graphs. In contrast to these methods in this paper we introduce a novel approach to measure the structural similarity of directed and undirected graphs that is mainly based on margins of feature vectors representing graphs. We introduce novel graph similarity and dissimilarity measures, provide some properties and analyze their algorithmic complexity. We find that the computational complexity of our measures is polynomial in the graph size and, hence, significantly better than classical methods from, e.g. exact graph matching which are NP-complete. Numerically, we provide some examples of our measure and compare the results with the well-known graph edit distance. (c) 2006 Elsevier Inc. All rights reserved.

One-Pot, High-Yield Synthesis of Convex Au Octahedra by H2O2 - Mediated Process In Solution Phase

A simple, non-seeding and high-yield synthesis of convex gold octahedra with size of ca. 50 nm in aqueous solution is described. The octahedral nanoparticles were systematically prepared by reduction of HAuCl4 using ascorbic acid (AA) in the presence of cetyltrimethylammonium bromide (CTAB) as the stabilizing surfactant while concentrations of Au3+ were fixed. The synthesizing process is especially different to other wet synthesis of metallic nanoparticles because it is mediated by H2O2. Mechanism of the H2O2 – mediated process will be described in details. The gold octahedra were shown to be single crystals with all 8 faces belonging to {111} family. Moreover, the single crystalline particles also showed attractive optical properties towards LSPR that should find uses as labels for microscopic imaging, materials for colorimetric biosensings, or nanosensor developments.

A simple inhibition coefficient for quantifying potency of biocontrol agents against plant-pathogenic fungi

Microbial interactions depend on a range of biotic and environmental variables, and are both dynamic and unpredictable. For some purposes, and under defined conditions, it is nevertheless imperative to evaluate the inhibitory efficacy of microbes, such as those with potential as biocontrol agents. We selected six, phylogenetically diverse microbes to determine their ability to inhibit the ascomycete Fusarium
coeruleum, a soil-dwelling pathogen of potato tubers that causes the storage disease dry rot. Interaction assays, where colony development was quantified (for both fungal pathogen and potential control agents), were therefore carried out on solid media. The key parameters that contributed to, and were indicative of, inhibitory efficacy were identified as: fungal growth-rates (i) prior to contact with the biocontrol
agent and (ii) if/once contact with the biocontrol agent was established (i.e. in the zone of mixed
culture), and (iii) the ultimate distance traveled by the fungal mycelium. It was clear that there was no correlation between zones of fungal inhibition and the overall reduction in the extent of fungal colony development. An inhibition coefficient was devised which incorporated the potential contributions of distal inhibition of fungal growth-rate; prevention of mycelium development in the vicinity of the biocontrol
agent; and ability to inhibit plant-pathogen growth-rate in the zone of mixed culture (in a ratio of 2:2:1). The values derived were 84.2 for Bacillus subtilis (QST 713), 74.0 for Bacillus sp. (JC12GB42), 30.7 for Pichia anomala (J121), 19.3 for Pantoea agglomerans (JC12GB34), 13.9 for Pantoea sp. (S09:T:12), and
21.9 (indicating a promotion of fungal growth) for bacterial strain (JC12GB54). This inhibition coefficient, with a theoretical maximum of 100, was consistent with the extent of F. coeruleum-colony development (i.e. area, in cm2) and assays of these biocontrol agents carried out previously against Fusarium
spp., and other fungi. These findings are discussed in relation to the dynamics and inherent complexity of natural ecosystems, and the need to adapt models for use under specific sets of conditions.

A proposed simple method for measurement in the anterior chamber angle: biometric gonioscopy

OBJECTIVE:

To design a system of gonioscopy that will allow greater interobserver reliability and more clearly defined screening cutoffs for angle closure than current systems while being simple to teach and technologically appropriate for use in rural Asia, where the prevalence of angle-closure glaucoma is highest.

DESIGN:

Clinic-based validation and interobserver reliability trial.

PARTICIPANTS:

Study 1: 21 patients 18 years of age and older recruited from a university-based specialty glaucoma clinic; study 2: 32 patients 18 years of age and older recruited from the same clinic.

INTERVENTION:

In study 1, all participants underwent conventional gonioscopy by an experienced observer (GLS) using the Spaeth system and in the same eye also underwent Scheimpflug photography, ultrasonographic measurement of anterior chamber depth and axial length, automatic refraction, and biometric gonioscopy with measurement of the distance from iris insertion to Schwalbe's line using a reticule based in the slit-lamp ocular. In study 2, all participants underwent both conventional gonioscopy and biometric gonioscopy by an experienced gonioscopist (NGC) and a medical student with no previous training in gonioscopy (JK).

MAIN OUTCOME MEASURES:

Study 1: The association between biometric gonioscopy and conventional gonioscopy, Scheimpflug photography, and other factors known to correlate with the configuration of the angle. Study 2: Interobserver agreement using biometric gonioscopy compared to that obtained with conventional gonioscopy.

RESULTS:

In study 1, there was an independent, monotonic, statistically significant relationship between biometric gonioscopy and both Spaeth angle (P = 0.001, t test) and Spaeth insertion (P = 0.008, t test) grades. Biometric gonioscopy correctly identified six of six patients with occludable angles according to Spaeth criteria. Biometric gonioscopic grade was also significantly associated with the anterior chamber angle as measured by Scheimpflug photography (P = 0.005, t test). In study 2, the intraclass correlation coefficient between graders for biometric gonioscopy (0.97) was higher than for Spaeth angle grade (0.72) or Spaeth insertion grade (0.84).

CONCLUSION:

Biometric gonioscopy correlates well with other measures of the anterior chamber angle, shows a higher degree of interobserver reliability than conventional gonioscopy, and can readily be learned by an inexperienced observer.

Convex Quadratic Programming Approach to the Maximum Matching Problem

The problem of determining a maximum matching or whether there exists a perfect matching, is very common in a large variety of applications and as been extensively studied in graph theory. In this paper we start to introduce a characterisation of a family of graphs for which its stability number is determined by convex quadratic programming. The main results connected with the recognition of this family of graphs are also introduced. It follows a necessary and sufficient condition which characterise a graph with a perfect matching and an algorithmic strategy, based on the determination of the stability number of line graphs, by convex quadratic programming, applied to the determination of a perfect matching. A numerical example for the recognition of graphs with a perfect matching is described. Finally, the above algorithmic strategy is extended to the determination of a maximum matching of an arbitrary graph and some related results are presented.

Preconditioning 2D Integer Data for Fast Convex Hull Computations

In order to accelerate computing the convex hull on a set of n points, a heuristic procedure is often applied to reduce the number of points to a set of s points, s ≤ n, which also contains the same hull. We present an algorithm to precondition 2D data with integer coordinates bounded by a box of size p × q before building a 2D convex hull, with three distinct advantages. First, we prove that under the condition min(p, q) ≤ n the algorithm executes in time within O(n); second, no explicit sorting of data is required; and third, the reduced set of s points forms a simple polygonal chain and thus can be directly pipelined into an O(n) time convex hull algorithm. This paper empirically evaluates and quantifies the speed up gained by preconditioning a set of points by a method based on the proposed algorithm before using common convex hull algorithms to build the final hull. A speedup factor of at least four is consistently found from experiments on various datasets when the condition min(p, q) ≤ n holds; the smaller the ratio min(p, q)/n is in the dataset, the greater the speedup factor achieved.

Properties and algorithms of the (n, k)-arrangement graphs

The (n, k)-arrangement interconnection topology was first introduced in 1992. The (n, k )-arrangement graph is a class of generalized star graphs. Compared with the well known n-star, the (n, k )-arrangement graph is more flexible in degree and diameter. However, there are few algorithms designed for the (n, k)-arrangement graph up to present. In this thesis, we will focus on finding graph theoretical properties of the (n, k)- arrangement graph and developing parallel algorithms that run on this network. The topological properties of the arrangement graph are first studied. They include the cyclic properties. We then study the problems of communication: broadcasting and routing. Embedding problems are also studied later on. These are very useful to develop efficient algorithms on this network. We then study the (n, k )-arrangement network from the algorithmic point of view. Specifically, we will investigate both fundamental and application algorithms such as prefix sums computation, sorting, merging and basic geometry computation: finding convex hull on the (n, k )-arrangement graph. A literature review of the state-of-the-art in relation to the (n, k)-arrangement network is also provided, as well as some open problems in this area.