logo标签列表

给定稀疏度的随机简单连通图生成

algorithmrandomgraph
22

我正在尝试寻找一种高效的算法来生成一个给定稀疏度的简单连通图。类似于：

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
这篇论文声称提供了一种有效的算法来生成随机连通图。我还没有仔细阅读细节，但他们声称在大型网络中表现更好。http://complexnetworks.fr/wp-content/uploads/2011/01/random.pdf - Harsh
4个回答
47

总体思路

  1. 生成一个有N个节点和N-1条边的（均匀选择的）随机生成树。
  2. 直到达到所需的边数，添加连接任意两个随机节点的边。

创建生成树

ypnos在这里给出了基于分区的答案，但是在每次选择新边的一个端点时，总会选择一个已访问过的节点，从而引入偏差。通过在每次迭代中随机选择一个已访问过的节点，可以使被访问得更早的节点具有更多的迭代机会，因此，先前的节点比后面选择的节点更有可能具有高度（边数）。

偏差的例子

例如，在一个由4个节点组成的连通图中，不要生成线性的路径图（占所有可能生成树的75%），这种偏差将导致星形图的生成概率大于它应该有的25%。

the possible spanning trees for a graph of size 2, 3, and 4 nodes

偏差并不总是一件坏事。事实证明，这种偏差对于生成类似于真实计算机网络的生成树是有好处的。但是，为了创建一个真正随机的连通图，必须从可能的生成树集中均匀选择初始生成树（请参见维基百科的均匀生成树文章）。

随机游走方法

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

从任何一个顶点开始，在图上进行简单的随机游走。每次首次遇到一个顶点时，标记发现它的边。当所有顶点都被发现时，标记的边就形成了一棵随机生成树。此算法易于编码，运行时间常数小，并且有一个很好的证明，证明它能生成具有正确概率的树。

这对于简单的连通图很有效，但如果您需要针对有向图的算法，请进一步阅读此文，因为它描述了Wilson算法。这里还有另一个关于随机生成生成树和Wilson算法的资源。

实现

由于我也对这个问题感兴趣，所以编写了Python实现各种方法，包括随机漫步方法。请随意查看GitHub上代码Gist of the code。

以下是随机漫步方法代码的摘录：

# 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)
2
随机游走方法的复杂度是什么？“随机选择一个节点；如果已经使用过则忽略它”的模式是否会导致潜在的无限运行时间？ - Jules Olléon
1
正如Wilson的论文所讨论的那样，Andrei Broder算法在无向图的覆盖时间内运行，对于最坏的图形，它受到O(n^3)的限制，但对于几乎所有图形来说，它只有O(n lg n)那么小---其中n是顶点数。 - Wesley Baugh
graph.add_random_edges(num_edges) 的作用是什么？因为边已经在 graph.add_edge(edge) 中添加了。 - want_to_be_calm
@want_to_be_calm：早期的代码通过创建一个具有N-1条边的图来处理高级别想法的第一部分。原问题的第二部分询问如何创建一个特定数量边的稀疏图。如果 |E| < (|N| - 1)，则需要添加额外的边（高级别想法的第二点）。在示例代码中，num_edges 的值本身是不明确的。这取决于 add_random_edged() 的实现方式，它是指定所请求的总边数还是应该添加的新边数。 - Wesley Baugh
23
每个节点至少需要一个边。
从一个节点开始。在每次迭代中，创建一个新节点和一条新边。该边用于将新节点与前一个节点集中的随机节点连接起来。
创建所有节点后，创建随机边直到满足S。确保不创建重复边（可以使用邻接矩阵实现）。
随机图的生成时间为O（S）。
刚用Java做了这样的东西。此外，在创建最小连通图时最好添加随机节点。否则，您将始终获得仅覆盖最后一个节点的垂直线，不超过两个垂直线覆盖前一个节点，依此类推。或者，您可以通过邻接矩阵操作获取所生成图的同构图。 - Eugene
1
这很好而且简单，但如果图是密集的，它就不是O(S)，因为需要检查双重边缘。我的意思是，最坏情况几乎从来不是O(S)，但如果图是密集的，即使期望的时间复杂度也不是O(S)。 - Gabor Csardi
4
很遗憾，这个图并不是在所有具有n个节点和m条边的图中均匀随机选择的。它将生成一种特定类型的图形。由于某些节点早先出现在图形中，这些节点倾向于具有更高的度数。 - cglacet
4

根据 Wesley Baugh 的回答，我使用 cytoscape.js 实现了以下javascript代码来处理图表：

function generateRandomGraph(cy, numNode, avgDegree, weightMin, weightMax) {
  // create nodes
  for (var i = 0; i < numNode; i++) {
    cy.add({
      group: "nodes",
      data: {
        id: "n" + i
      }
    });
  }

  // perform random walks to connect edges
  var nodes = cy.nodes(),
    S = nodes.toArray(),
    T = []; // visited

  var currNodeIdx = randomIntBetween(0, S.length);
  var currNode = S[currNodeIdx];
  S.splice(currNodeIdx, 1);
  T.push(currNode);

  while (S.length > 0) {
    var neighbourNodeIdx = randomIntBetween(0, S.length);
    var neighbourNode = S[neighbourNodeIdx];
    cy.add({
      group: "edges",
      data: {
        weight: randomIntBetweenInclusive(weightMin, weightMax),
        source: currNode.id(),
        target: neighbourNode.id()
      }
    });
    S.splice(neighbourNodeIdx, 1);
    T.push(neighbourNode);
    currNode = neighbourNode;
  }

  // add random edges until avgDegree is satisfied
  while (nodes.totalDegree() / nodes.length < avgDegree) {
    var temp = sampleInPlace(nodes, 2);
    if (temp[0].edgesWith(temp[1]).length === 0) {
      cy.add({
        group: "edges",
        data: {
          weight: randomIntBetweenInclusive(weightMin, weightMax),
          source: temp[0].id(),
          target: temp[1].id()
        }
      })
    }
  }
}

generateRandomGraph(cy, 20, 2.8, 1, 20);

如果需要完整的示例源代码，请访问我的GitHub资料库 :)

1
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接