Maximum Entropy Distributions with Applications to Graph Simulation
研究了在线性约束下从乘积集中均匀采样的通用问题，包括模拟具有给定度序列的二部图、有向图和无向图，提出了两种概率分布并给出它们一致的条件，以及一种采样中等规模图的简单顺序算法。
The problem of simulating graphs (networks) subject to constraints has been studied extensively across several areas. Applications of this problem include modeling inter-bank financial networks, predator-prey ecological graphs, contingency tables, and even studying larger networks such as the Internet. In “Maximum Entropy Distributions with Applications to Graph Simulation,” P. Glasserman and E. Lelo de Larrea study the more general problem of sampling uniformly from product sets under linear constraints, which includes simulating bipartite, directed, and undirected graphs with given degree sequences. For this purpose, they consider two suitable probability distributions: one that maximizes the entropy of the system, and another that maximizes the minimum probability of hitting the desired target set. Although apparently different, the authors provide conditions under which both distributions coincide. In addition, they propose a simple sequential algorithm to sample medium-sized graphs with fixed degrees.