图的条件着色的两个上界

通过构造一个可行算法——条件图算法,给出了一般图的条件边集合,并由此得到条件图,对条件图应用正常着色已有性质,证明了两个条件着色色数上界表达式.     

Modelling a disease-relevant contact network of people who inject drugs

This study uses social network analysis to model a contact network of people who inject drugs (PWID) relevant for investigating the spread of an infectious disease (hepatitis C). Using snowball sample data, parameters for an exponential random graph model (ERGM) including social circuit dependence and four attributes (location, age, injecting frequency, gender) are estimated using a conditional estimation approach that respects the structure of snowball sample designs. Those network parameter estimates are then used to create a novel, model-dependent estimate of network size. Simulated PWID contact networks are created and compared with Bernoulli graphs. Location, age and injecting frequency are shown to be statistically significant attribute parameters in the ERGM. Simulated ERGM networks are shown to fit the collected data very well across a number of metrics. In comparison with Bernoulli graphs, simulated networks are shown to have longer paths and more clustering. Results from this study make possible simulation of realistic networks for investigating treatment and intervention strategies for reducing hepatitis C prevalence.     

What makes a network go round? Exploring the structure of a strong component with exponential random graph models

A strong component is a subgraph in a directed network where, following the direction of ties, all nodes in the graph are reachable from one another. Mutual reachability implies that every node in the graph is theoretically able to send materials to and/or influence every other node suggesting that strong components are amongst the more egalitarian network structures. Despite this intriguing feature, they remain understudied. Using exponential random graph models (ERGM) for directed networks, we investigate the social and structural processes underlying the generation of strong components. We illustrate our argument using a network of 301 nodes and 703 personal lending ties from Renaissance Florence. ERGM shows that our strong component arises from triadic clustering alongside an absence of higher-order star structures. We contend that these processes produce a strong component with a hierarchical, rather than an egalitarian structure: while some nodes are deeply embedded in a dense network of exchange, the involvement of others is more tenuous. More generally, we argue that such tiered core-periphery strong components will predominate in networks where the social context creates conditions for an absence of preferential attachment alongside the presence of localized closure. Although disparate social processes can give rise to hierarchical strong components linked to these two structural mechanisms, in Florence they are associated with the presence of multiple dimensions of social status and the connectedness of participants across disparate network domains.     

Bayesian analysis for partially observed network data,missing ties,attributes and actors

We consider partially observed network data as defined in Handcock and Gile (2010). More specifically we introduce an elaboration of the Bayesian data augmentation scheme of Koskinen et al. (2010) that uses the exchange algorithm (Caimo and Friel, 2011) for inference for the exponential random graph model (ERGM) where tie variables are partly observed. We illustrate the generating of posteriors and unobserved tie-variables with empirical network data where 74% of the tie variables are unobserved under the assumption that some standard assumptions hold true. One of these assumptions is that covariates are fixed and completely observed. A likely scenario is that also covariates might only be partially observed and we propose a further extension of the data augmentation algorithm for missing attributes. We provide an illustrative example of parameter inference with nearly 30% of dyads affected by missing attributes (e.g. homophily effects). The assumption that all actors are known is another assumption that is liable to be violated so that there are “covert actors”. We briefly discuss various aspects of this problem with reference to the Sageman (2004) data set on suspected terrorists. We conclude by identifying some areas in need of further research.     

关于0类图的一个注记

在图G的顶点上放置一些Pebble,图G的一个Pebbling移动是从一个顶点移走两个Pebble而把其中的一个移到与其相邻的一个顶点上.连通图G的Pebbling数f(G)是最小的正整数n,使得不管n个Pebble如何放置在G的顶点上,总可以通过一系列的Pebbling移动把一个Pebble移到图G的任意一个顶点上.Graham猜测:对于任意的连通图G和H,有f(G×H)≤f(G)f(H).若f(G)=|V(G)|,称G是0类的(Class 0).证明了有关0类图的一个结果.作为推论,得到了P×C5和P×P都是0类图,其中P是Petersen图.     

Probability inheritance algorithm and its implementation

An algorithm for functional evaluation of the likelihood of paternal and maternal recombination fractions for pedigree data is proposed. The idea behind the algorithm is that the probability of affected status and certain marker genotypes of ancestors is inherited by their descendants along with the inheritance of certain haplotypes. In this algorithm, the likelihood is evaluated by a single recursive call for each terminal sibling set along with the inheritance flow. The advantage of the algorithm is not only the simplicity of its implementation, but also its functional form of evaluation. The likelihood is obtained as a polynomial of the recombination fractions, making it easier to validate the likelihood more carefully, resulting in a more accurate localization of the disease locus. We report an experimental implementation of this algorithm in R, together with several practical applications.     

β-Skeleton depth functions and medians

We define the β-skeleton depth based on the probability that a point is contained within the β-skeleton influence region of two i.i.d. random vectors. The proposed family of depth functions satisfies the four desirable properties of statistical depth function. We also define and examine the sample β-skeleton depth functions and show that they share well-behaved asymptotic properties, including uniform consistency and asymptotic normality. Finally, we explore the β-skeleton multidimensional medians as location estimators of the center of multivariate distributions, discuss its asymptotic properties, and study its breakdown point. A Monte Carlo study compares the β-skeleton medians with the random Tukey median and the sample mean.     

b-Tree Facets for the Simple Graph Partitioning Polytope

The simple graph partitioning problem is to partition an edge-weighted graph into mutually disjoint subgraphs, each consisting of no more than b nodes, such that the sum of the weights of all edges in the subgraphs is maximal. In this paper we introduce a large class of facet defining inequalities for the simple graph partitioning polytopes _n (b), b 3, associated with the complete graph on n nodes. These inequalities are induced by a graph configuration which is built upon trees of cardinality b. We provide a closed-form theorem that states all necessary and sufficient conditions for the facet defining property of the inequalities.     

简析婉约的语言风格

婉约和豪放是一组对立的语言表现风格,具有音律柔和、词语清新秀丽、句式松散舒缓、辞格新颖委婉的特点.     

An Improved Randomized Approximation Algorithm for Max TSP

We present an O(n³)-time randomized approximation algorithm for the maximum traveling salesman problem whose expected approximation ratio is asymptotically , where n is the number of vertices in the input (undirected) graph. This improves the previous best.Part of work done while visiting City University of Hong Kong.