A perfect sampling method for exponential family random graph models

Generation of deviates from random graph models with nontrivial edge dependence is an increasingly important problem. Here, we introduce a method which allows perfect sampling from random graph models in exponential family form (“exponential family random graph” models), using a variant of Coupling From The Past. We illustrate the use of the method via an application to the Markov graphs, a family that has been the subject of considerable research. We also show how the method can be applied to a variant of the biased net models, which are not exponentially parameterized.     

Bayesian Model Selection for Exponential Random Graph Models via Adjusted Pseudolikelihoods

Models with intractable likelihood functions arise in areas including network analysis and spatial statistics, especially those involving Gibbs random fields. Posterior parameter estimation in these settings is termed a doubly intractable problem because both the likelihood function and the posterior distribution are intractable. The comparison of Bayesian models is often based on the statistical evidence, the integral of the un-normalized posterior distribution over the model parameters which is rarely available in closed form. For doubly intractable models, estimating the evidence adds another layer of difficulty. Consequently, the selection of the model that best describes an observed network among a collection of exponential random graph models for network analysis is a daunting task. Pseudolikelihoods offer a tractable approximation to the likelihood but should be treated with caution because they can lead to an unreasonable inference. This article specifies a method to adjust pseudolikelihoods to obtain a reasonable, yet tractable, approximation to the likelihood. This allows implementation of widely used computational methods for evidence estimation and pursuit of Bayesian model selection of exponential random graph models for the analysis of social networks. Empirical comparisons to existing methods show that our procedure yields similar evidence estimates, but at a lower computational cost. Supplementary material for this article is available online.     

���嵥ָ����ģ�͵����ЧӦ�����Լ���

在广义参数和非参数模型中, 虽然不存在异方差检验问题, 但是方差成分的检验问题仍是研究者们关心的对象. 本文利用P-样条的方法, 研究了广义单指标混合模型的方差成分检验问题. 得到了检验广义单指标混合模型是否存在由随机效应引起的偏大离差问题的Score检验统计量, 最后给出计算机模拟的例子, 证实了文中所提出方法的可行性和有效性, 推广和发展了先前的研究工作     

Spectral reordering of a range-dependent weighted random graph

^** Email: aas96106{at}maths.strath.ac.uk Grindrod (2002. Phys. Rev. E, 66, 0667021–0667027) posedthe problem of reordering a range-dependent random graph andshowed that it is relevant to the analysis of data sets frombioinformatics. Reordering under a random graph hypothesis canbe regarded as an extension of clustering and fits into thegeneral area of data mining. Here, we consider a generalizationof Grindrod's model and show how an existing spectral reorderingalgorithm that has arisen in a number of areas may be interpretedfrom a maximum likelihood range-dependent random graph viewpoint.Looked at this way, the spectral algorithm, which uses eigenvectorinformation from the graph Laplacian, is found to be automaticallytuned to an exponential edge density. The connection is precisefor optimal reorderings, but is weaker when approximate reorderingsare computed via relaxation. We illustrate the performance ofthe spectral algorithm in the weighted random graph contextand give experimental evidence that it can be successful forother edge densities. We conclude by applying the algorithmto a data set from the biological literature that describescortical connectivity in the cat brain.     

A Novel Simulation Method for Binary Discrete Exponential Families,With Application to Social Networks

Stochastic models for finite binary vectors are widely used in sociology, with examples ranging from social influence models on dichotomous behaviors or attitudes to models for random graphs. Exact sampling for such models is difficult in the presence of dependence, leading to the use of Markov chain Monte Carlo (MCMC) as an approximation technique. While often effective, MCMC methods have variable execution time, and the quality of the resulting draws can be difficult to assess. Here, we present a novel alternative method for approximate sampling from binary discrete exponential families having fixed execution time and well-defined quality guarantees. We demonstrate the use of this sampling procedure in the context of random graph generation, with an application to the simulation of a large-scale social network using both geographical covariates and dyadic dependence mechanisms.     

Reflection positivity, rank connectivity, and homomorphism of graphs

It is shown that a graph parameter can be realized as the number of homomorphisms into a fixed (weighted) graph if and only if it satisfies two linear algebraic conditions: reflection positivity and exponential rank connectivity. In terms of statistical physics, this can be viewed as a characterization of partition functions of vertex coloring models.

     

Multigraph limit of the dense configuration model and the preferential attachment graph

The configuration model is the most natural model to generate a random multigraph with a given degree sequence. We use the notion of dense graph limits to characterize the special form of limit objects of convergent sequences of configuration models. We apply these results to calculate the limit object corresponding to the dense preferential attachment graph and the edge reconnecting model. Our main tools in doing so are (1) the relation between the theory of graph limits and that of partially exchangeable random arrays (2) an explicit construction of our random graphs that uses urn models.     

Condensation in preferential attachment models with location‐based choice

We introduce a model of a preferential attachment based random graph which extends the family of models in which condensation phenomena can occur. Each vertex has an associated uniform random variable which we call its location. Our model evolves in discrete time by selecting r vertices from the graph with replacement, with probabilities proportional to their degrees plus a constant α. A new vertex joins the network and attaches to one of these vertices according to a given probability associated to the ranking of their locations. We give conditions for the occurrence of condensation, showing the existence of phase transitions in α below which condensation occurs. The condensation in our model differs from that in preferential attachment models with fitness in that the condensation can occur at a random location, that it can be due to a persistent hub, and that there can be more than one point of condensation.     

Topological properties of the one dimensional exponential random geometric graph

In this article we study the one‐dimensional random geometric (random interval) graph when the location of the nodes are independent and exponentially distributed. We derive exact results and limit theorems for the connectivity and other properties associated with this random graph. We show that the asymptotic properties of a graph with a truncated exponential distribution can be obtained using the exponential random geometric graph. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

An inventory control model with stochastic review interval and special sale offer

Periodic review inventory models are widely used in practice, especially for inventory systems in which many different items are purchased from the same supplier. However, most of periodic review models have assumed a fixed length of the review periods. In practice, it is possible that the review periods are of a random (stochastic) length. This paper presents an inventory control model in the case of random review intervals and special sale offer from the supplier. The replenishment interval is assumed to obey from two different distributions, namely, exponential and uniform distributions. Also, shortages are allowed in the term of partial backordering. For this model, its convexity condition is discussed and closed form solutions are proposed.     

A Flexible Parameterization for Baseline Mean Degree in Multiple-Network ERGMs

The conventional exponential family random graph model (ERGM) parameterization leads to a baseline density that is constant in graph order (i.e., number of nodes); this is potentially problematic when modeling multiple networks of varying order. Prior work has suggested a simple alternative that results in constant expected mean degree. Here, we extend this approach by suggesting another alternative parameterization that allows for flexible modeling of scenarios in which baseline expected degree scales as an arbitrary power of order. This parameterization is easily implemented by the inclusion of an edge count/log order statistic along with the traditional edge count statistic in the model specification.     

Equality of Lifshitz and van Hove exponents on amenable Cayley graphs

We study the low energy asymptotics of periodic and random Laplace operators on Cayley graphs of amenable, finitely generated groups. For the periodic operator the asymptotics is characterised by the van Hove exponent or zeroth Novikov–Shubin invariant. The random model we consider is given in terms of an adjacency Laplacian on site or edge percolation subgraphs of the Cayley graph. The asymptotic behaviour of the spectral distribution is exponential, characterised by the Lifshitz exponent. We show that for the adjacency Laplacian the two invariants/exponents coincide. The result holds also for more general symmetric transition operators. For combinatorial Laplacians one has a different universal behaviour of the low energy asymptotics of the spectral distribution function, which can be actually established on quasi-transitive graphs without an amenability assumption. The latter result holds also for long range bond percolation models.     

随机补货间隔且需求依赖库存水平的库存控制模型

定期补货库存模型在实践中被广泛使用,尤其是在单一供应商中购买多种不同产品的库存系统中更为常见.然而,大多数定期补货库存模型都假设补货的时间间隔是恒定不变的.但在实践中,补货的时间间隔也可能是一个随机的时间长度.提出了一个随机补货时间间隔和需求依赖于当前展示库存水平的库存控制模型,且补货间隔服从指数分布和均匀分布,同时允许短缺发生并且短缺量部分延期供给,并研究了模型最优解的存在性与唯一性.最后,给出了数值算例来说明模型在实际中的应用.     

Interpolation solution in generalized stochastic exponential population growth model

In this paper, first we consider model of exponential population growth, then we assume that the growth rate at time t is not completely definite and it depends on some random environment effects. For this case the stochastic exponential population growth model is introduced. Also we assume that the growth rate at time t depends on many different random environment effect, for this case the generalized stochastic exponential population growth model is introduced. The expectations and variances of solutions are obtained. For a case study, we consider the population growth of Iran and obtain the output of models for this data and predict the population individuals in each year.     

Optimal deteriorating items production inventory models with random machine breakdown and stochastic repair time

This study develops deteriorating items production inventory models with random machine breakdown and stochastic repair time. The model assumes the machine repair time is independent of the machine breakdown rate. The classical optimization technique is used to derive an optimal solution. A numerical example and sensitivity analysis are shown to illustrate the models. The stochastic repair models with uniformly distributed repair time tends to have a larger optimal total cost than the fixed repair time model, however the production up time is less than the fixed repair time model. Production and demand rate are the most sensitive parameters for the optimal production up time, and demand rate is the most sensitive parameter to the optimal total cost for the stochastic model with exponential distribution repair time.     

Hitting Times,Cover Cost,and the Wiener Index of a Tree

We exhibit a close connection between hitting times of the simple random walk on a graph, the Wiener index, and related graph invariants. In the case of trees, we obtain a simple identity relating hitting times to the Wiener index. It is well known that the vertices of any graph can be put in a linear preorder so that vertices appearing earlier in the preorder are “easier to reach” by a random walk, but “more difficult to get out of.” We define various other natural preorders and study their relationships. These preorders coincide when the graph is a tree, but not necessarily otherwise. Our treatise is self‐contained, and puts some known results relating the behavior or random walk on a graph to its eigenvalues in a new perspective.     

Duality in inhomogeneous random graphs,and the cut metric

The classical random graph model G(n, c/n) satisfies a “duality principle”, in that removing the giant component from a supercritical instance of the model leaves (essentially) a subcritical instance. Such principles have been proved for various models; they are useful since it is often much easier to study the subcritical model than to directly study small components in the supercritical model. Here we prove a duality principle of this type for a very general class of random graphs with independence between the edges, defined by convergence of the matrices of edge probabilities in the cut metric. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 39, 399–411, 2011     

The admissible parameter space for exponential smoothing models

We discuss the admissible parameter space for some state space models, including the models that underly exponential smoothing methods. We find that the usual parameter restrictions (requiring all smoothing parameters to lie between 0 and 1) do not always lead to stable models. We also find that all seasonal exponential smoothing methods are unstable as the underlying state space models are neither reachable nor observable. This instability does not affect the forecasts, but does corrupt the state estimates. The problem can be overcome with a simple normalizing procedure. Finally we show that the admissible parameter space of a seasonal exponential smoothing model is much larger than that for a basic structural model, leading to better forecasts from the exponential smoothing model when there is a rapidly changing seasonal pattern.     

Network structure,perception level,and participants' welfares

Based on a market consisting of one monopoly and several customers who are embedded in an economic network, we study how the different perception levels about the network structure affect the two kinds of participants' welfares, and then provide some good strategies for the monopoly to mine the information of the network structure. The above question is the embodiment of the “complex structure and its corresponding functions” question often mentioned in the field of complexity science. We apply a two‐stage game to solve for the optimal pricing and consumption at different perception levels of the monopoly and further utilize simulation analysis to explore the influence patterns. We also discuss how this theoretic model can be applied to a real world problem by introducing the statistical exponential random graph model and its estimation method. Further, the main findings have specific policy implications on uncovering network information and demonstrate that it is possible for the policy‐maker to design some win–win mechanisms for uplifting both the monopoly's profit and the whole customers' welfare at the same time. © 2014 Wiley Periodicals, Inc. Complexity 21: 349–362, 2015