如何随机生成帕累托 - 核知识节点的图表？

Question

我已经读到，“知识”图中的节点的程度大致遵循功率定律分布，更准确地可以通过帕累托良好的分布来近似。

我在哪里可以找到一种与此分布产生随机图的算法？

例如参见论文 重新访问学位分配模型用于社交图分析 （第4页，等式1）对于我感兴趣的分布类型的数学描述（分布功能）。

Answer 1

为了从规定的度序列（无论程度序列如何）生成图，可以使用Blitzstein和DiaConis的算法：

• J. Blitzstein和P. diaconis的“用于生成规定学位的随机图的顺序重要性采样算法”

不幸的是，他们的算法可能是$ o（n^2 bar {d}）$，对于$ n $ vertices，具有平均度$ bar {d} $的$ n $顶点，因此，根据图表的大小和图形的大小，这可能还不够快。涉及的申请。

Molloy和Reed引入了“擦除的配置模型”，该模型基于与其余自由插槽成正比的度序列配对顶点。

• M. Molloy和B. Reed的“具有给定度序列的随机图的关键点”

Britton，Deijfen和Martin-Lof的论文表明，擦除的配置模型渐近接近所选择的规定度分布。虽然不能保证确切的度序列输入，但我建议使用删除的配置模型，以简化其速度和速度。

• T. Britton，M。Deijfen和A. Martin-lof的“生成具有规定度分布的简单随机图”

简而言之，擦除的配置模型图生成算法为每个顶点创建“钩子”，其中每个顶点的钩子数最初由度序列给出。首先从顶点最多的顶点开始，另一个钩子是从池中均匀地选择的，但仍未接触。为此配对建立了连接。一旦钩子耗尽了，就将自动循环删除，并将多重装饰折叠成一个。

由于允许自动循环并崩溃了多边缘，因此所产生的程度序列可能与输入序列有所不同，因此该方法不准确。如果优选精确性，则可以以更高的计算成本使用Blitzstein和Diaconus的算法。请注意，闪电战和Diaconus的算法检查规定的学位序列是否可行（或其概述中的“图形”），因此，如果不可实现，则可能需要将其再生。

可以在您想要的任何分布下选择度序列。在您的情况下，您需要根据帕累托透视分布选择它们。

我还要简要地指出，帕累托 - 孔隙式分布所说，生成具有遵循特定分布的规定度序列的图形可能不会生成您想要的“知识”图。学位分布只是图的配置文件，没有说明原始图集合中可能存在的其他功能，您将尝试建模。正如拉斐尔（Raphael）在评论中指出的那样，维基百科的页面上 无标度网络 是一些审查的好起点。