论文标题
关于给定直方图的图形数
On the Number of Graphs with a Given Histogram
论文作者
论文摘要
让$ g $成为$ n $顶点上的大型（简单，未标记的）密集图。假设我们只知道或可以估计，对于某些固定的小图$ f $，每个顶点的子图$ f $的经验分布都参与其中。我们的其他图表对我们来说基本相同，即具有相似的本地结构？在本文中，我们在经验分布的图表数量上得出了上限和下限，其经验分布位于$ g $的图形（在Kolmogorov-Smirnov距离中）。我们的界限作为解决方案作为解决方案的最大熵问题，在固定尺寸$ k $的随机图上不取决于$ n $，在$ d $ d $ d $全球密度约束下。边界渐近地接近，差距以$ d $消失，速度取决于Kolmogorov-Smirnov球中心的浓度函数。
Let $G$ be a large (simple, unlabeled) dense graph on $n$ vertices. Suppose that we only know, or can estimate, the empirical distribution of the number of subgraphs $F$ that each vertex in $G$ participates in, for some fixed small graph $F$. How many other graphs would look essentially the same to us, i.e., would have a similar local structure? In this paper, we derive upper and lower bounds on the number of graphs whose empirical distribution lies close (in the Kolmogorov-Smirnov distance) to that of $G$. Our bounds are given as solutions to a maximum entropy problem on random graphs of a fixed size $k$ that does not depend on $n$, under $d$ global density constraints. The bounds are asymptotically close, with a gap that vanishes with $d$ at a rate that depends on the concentration function of the center of the Kolmogorov-Smirnov ball.
