We consider the problem of the semidefinite representation of a class of non-compact basic semialgebraic sets. We introduce the conditions of pointedness and closedness at infinity of a semialgebraic set and show that under these conditions our modif
ied hierarchies of nested theta bodies and Lasserres relaxations converge to the closure of the convex hull of $S$. Moreover, if the PP-BDR property is satisfied, our theta body and Lasserres relaxation are exact when the order is large enough; if the PP-BDR property does not hold, our hierarchies convergent uniformly to the closure of the convex hull of $S$ restricted to every fixed ball centered at the origin. We illustrate through a set of examples that the conditions of pointedness and closedness are essential to ensure the convergence. Finally, we provide some strategies to deal with cases where the conditions of pointedness and closedness are violated.
We deploy numerical semidefinite programming and conversion to exact rational inequalities to certify that for a positive semidefinite input polynomial or rational function, any representation as a fraction of sums-of-squares of polynomials with real
coefficients must contain polynomials in the denominator of degree no less than a given input lower bound. By Artins solution to Hilberts 17th problems, such representations always exist for some denominator degree. Our certificates of infeasibility are based on the generalization of Farkass Lemma to semidefinite programming. The literature has many famous examples of impossibility of SOS representability including Motzkins, Robinsons, Chois and Lams polynomials, and Reznicks lower degree bounds on uniform denominators, e.g., powers of the sum-of-squares of each variable. Our work on exact certificates for positive semidefiniteness allows for non-uniform denominators, which can have lower degree and are often easier to convert to exact identities. Here we demonstrate our algorithm by computing certificates of impossibilities for an arbitrary sum-of-squares denominator of degree 2 and 4 for some symmetric sextics in 4 and 5 variables, respectively. We can also certify impossibility of base polynomials in the denominator of restricted term structure, for instance as in Landaus reduction by one less variable.
In this paper, we consider the problem of exploring structural regularities of networks by dividing the nodes of a network into groups such that the members of each group have similar patterns of connections to other groups. Specifically, we propose
a general statistical model to describe network structure. In this model, group is viewed as hidden or unobserved quantity and it is learned by fitting the observed network data using the expectation-maximization algorithm. Compared with existing models, the most prominent strength of our model is the high flexibility. This strength enables it to possess the advantages of existing models and overcomes their shortcomings in a unified way. As a result, not only broad types of structure can be detected without prior knowledge of what type of intrinsic regularities exist in the network, but also the type of identified structure can be directly learned from data. Moreover, by differentiating outgoing edges from incoming edges, our model can detect several types of structural regularities beyond competing models. Tests on a number of real world and artificial networks demonstrate that our model outperforms the state-of-the-art model at shedding light on the structural features of networks, including the overlapping community structure, multipartite structure and several other types of structure which are beyond the capability of existing models.
It has been shown that the communities of complex networks often overlap with each other. However, there is no effective method to quantify the overlapping community structure. In this paper, we propose a metric to address this problem. Instead of as
suming that one node can only belong to one community, our metric assumes that a maximal clique only belongs to one community. In this way, the overlaps between communities are allowed. To identify the overlapping community structure, we construct a maximal clique network from the original network, and prove that the optimization of our metric on the original network is equivalent to the optimization of Newmans modularity on the maximal clique network. Thus the overlapping community structure can be identified through partitioning the maximal clique network using any modularity optimization method. The effectiveness of our metric is demonstrated by extensive tests on both the artificial networks and the real world networks with known community structure. The application to the word association network also reproduces excellent results.
We propose a hierarchical Bayesian model to estimate the proportional contribution of source populations to a newly founded colony. Samples are derived from the first generation offspring in the colony, but mating may occur preferentially among migra
nts from the same source population. Genotypes of the newly founded colony and source populations are used to estimate the mixture proportions, and the mixture proportions are related to environmental and demographic factors that might affect the colonizing process. We estimate an assortative mating coefficient, mixture proportions, and regression relationships between environmental factors and the mixture proportions in a single hierarchical model. The first-stage likelihood for genotypes in the newly founded colony is a mixture multinomial distribution reflecting the colonizing process. The environmental and demographic data are incorporated into the model through a hierarchical prior structure. A simulation study is conducted to investigate the performance of the model by using different levels of population divergence and number of genetic markers included in the analysis. We use Markov chain Monte Carlo (MCMC) simulation to conduct inference for the posterior distributions of model parameters. We apply the model to a data set derived from grey seals in the Orkney Islands, Scotland. We compare our model with a similar model previously used to analyze these data. The results from both the simulation and application to real data indicate that our model provides better estimates for the covariate effects.
