随机图划分

Question

我正在尝试测试一些图分区的模型(这些模型来自现实世界，在现实世界中，图缓慢地自我分区)。要做到这一点，我需要能够统一地随机地将该图划分为连续的组件(我们也可以在给定该图的初始连接的情况下)。如果不需要邻接性标准，我相信这将是随机划分集合的问题，可以进行组合分析。有谁知道将图随机划分为子图的方法(即随机采样一个分区)，或者，如果不知道这样的方法，则随机采样一组元素？将分区数量随机化，然后将成员身份随机化的方法将不起作用，因为每个分区大小都有不同数量的可能分区。

Answer 1

您必须区分edge-cut partitioning和vertex-cut partitioning，在这种情况下，您可以沿着边或顶点划分图形。这会显著影响您的问题，因为不同顶点切割的数量比边切割的数量多得多。这是因为在vertex-cut中，您只将边分配给分区-而在边切割中，您将顶点分配给分区-并且边比顶点多得多(例如，对于n个顶点，O(n^2)条边)。因此，组合上较大的顶点切割导致必须检查连通性的更多子图。一种简单的随机化方法是枚举所有分区，迭代地选择一个分区，并检查所选分区中所有子图的连通性。然后你只需要取第一个。在这种情况下，所有的解决方案都具有相同的概率(均匀随机)。