论文标题
具有规定程度和维度序列的超图的构建和随机生成
Construction and Random Generation of Hypergraphs with Prescribed Degree and Dimension Sequences
论文作者
论文摘要
我们提出了用于没有循环以及规定的程度和维度序列的无循环的构建和随机生成的算法。目的是为马尔可夫链蒙特卡洛（Monte Carlo）方法提供一个起点和替代方案。我们的算法利用了由零构成的矩阵和具有规定的行和柱状构成的矩阵的属性和算法的换位。当未提供初始超图时，构造算法扩展了马尔可夫链蒙特卡洛接近的适用性。随机生成算法允许开发用于超图形属性（例如平均聚类系数）的自称重要性采样估计器。我们证明了所提出算法的正确性。我们还证明，随机生成算法遵循规定的程度和尺寸序列，具有非零概率。我们通过经验和相对评估随机生成算法的有效性和效率。实验表明，随机生成算法提供了平均聚类系数的稳定，准确的估计，并且与马尔可夫链蒙特卡洛方法相比，还显示出更好的有效样本量。
We propose algorithms for construction and random generation of hypergraphs without loops and with prescribed degree and dimension sequences. The objective is to provide a starting point for as well as an alternative to Markov chain Monte Carlo approaches. Our algorithms leverage the transposition of properties and algorithms devised for matrices constituted of zeros and ones with prescribed row- and column-sums to hypergraphs. The construction algorithm extends the applicability of Markov chain Monte Carlo approaches when the initial hypergraph is not provided. The random generation algorithm allows the development of a self-normalised importance sampling estimator for hypergraph properties such as the average clustering coefficient.We prove the correctness of the proposed algorithms. We also prove that the random generation algorithm generates any hypergraph following the prescribed degree and dimension sequences with a non-zero probability. We empirically and comparatively evaluate the effectiveness and efficiency of the random generation algorithm. Experiments show that the random generation algorithm provides stable and accurate estimates of average clustering coefficient, and also demonstrates a better effective sample size in comparison with the Markov chain Monte Carlo approaches.
