algorithm - 具有给定稀疏性的随机简单连通图生成

Question

我正在尝试寻找一种有效的算法来生成具有给定稀疏度的简单连通图。像这样的东西:

Input:
    N - size of generated graph
    S - sparseness (numer of edges actually; from N-1 to N(N-1)/2)
Output:
    simple connected graph G(v,e) with N vertices and S edges

Answer 1

高级理念

1. 生成具有 N 个节点和 N - 1 条边的(均匀选择的)随机生成树。
2. 在达到要求的边数之前，在任意两个随机节点之间添加一条边。

创建生成树

partition-based answer通过 ypnos是一个好的开始，但是总是为新边的一端选择访问节点会引入偏差。通过在每次迭代中随机选择一个访问节点，开始访问的节点有更多的迭代次数，它们有机会被选中。因此，较早选择的节点比较晚选择的节点更有可能具有高度(边数)。

偏见的例子

例如，对于 4 节点连接图而不是生成线性 path graph ，这是 75% 的可能生成树，这种偏差会导致 star graph以大于 25% 的概率生成。

偏见并不总是坏事。事实证明，这种偏差有利于生成类似于现实世界计算机网络的生成树。然而，为了创建一个真正随机的连接图，必须从可能的生成树集合中均匀地挑选初始生成树(参见维基百科的 Uniform Spanning Tree 文章)。

随机游走方法

生成均匀生成树的一种方法是通过随机游走。以下是论文 Generating Random Spanning Trees More Quickly than the Cover Time 的引述由 Wilson 描述简单 random walk算法。

Start at any vertex and do a simple random walk on the graph. Each time a vertex is first encountered, mark the edge from which it was discovered. When all the vertices are discovered, the marked edges form a random spanning tree. This algorithm is easy to code up, has small running time constants, and has a nice proof that it generates trees with the right probabilities.

这适用于简单的连通图，但是如果您需要有向图的算法，请阅读 paper进一步描述威尔逊的算法。这是 random spanning trees 的另一个资源和威尔逊算法。

实现

因为我也对这个问题感兴趣，所以我编写了各种方法的 Python 实现，包括随机游走方法。随意看看Gist of the code在 GitHub 上。

以下是随机游走方法的代码摘录:

# Create two partitions, S and T. Initially store all nodes in S.
S, T = set(nodes), set()

# Pick a random node, and mark it as visited and the current node.
current_node = random.sample(S, 1).pop()
S.remove(current_node)
T.add(current_node)

graph = Graph(nodes)

# Create a random connected graph.
while S:
    # Randomly pick the next node from the neighbors of the current node.
    # As we are generating a connected graph, we assume a complete graph.
    neighbor_node = random.sample(nodes, 1).pop()
    # If the new node hasn't been visited, add the edge from current to new.
    if neighbor_node not in T:
        edge = (current_node, neighbor_node)
        graph.add_edge(edge)
        S.remove(neighbor_node)
        T.add(neighbor_node)
    # Set the new node as the current node.
    current_node = neighbor_node

# Add random edges until the number of desired edges is reached.
graph.add_random_edges(num_edges)