7

以下函数返回一个随机生成的大小为 的邻接矩阵nxn，表示一个图。

import random

def random_adjacency_matrix(n):   
    matrix = [[random.randint(0, 1) for i in range(n)] for j in range(n)]

    # No vertex connects to itself
    for i in range(n):
        matrix[i][i] = 0

    # If i is connected to j, j is connected to i
    for i in range(n):
        for j in range(n):
            matrix[j][i] = matrix[i][j]

    return matrix

这是一个非常幼稚的解决方案，我希望它满足两个额外的要求。

  1. 矩阵表示的图必须是全连接的，换句话说，不能有任何节点在一定数量的步骤中无法从任何其他节点到达。

  2. 每个节点都有许多边。现在它是完全随机的，因此一个节点有多少边相当一致，当n它很大时，所有图的平均边数往往也很大。我希望每个节点的平均边数变化更大，与图的大小无关，这样一些图的连接很少，而另一些则有很多。

编辑：使用 networkx 包，这似乎是我想要的，只有上面的第 1 点也满足：

import networkx, random
G = networkx.binomial_graph(50, random.random()) # 50 nodes, random probability of an edge
4

4 回答 4

3

首先，让我们推荐networkx图形库。它非常易于使用，并且已经包含了一个很好的算法工具箱。例如，您可以轻松地测试一个图的连通性或在图中请求一组连接的组件。

其次，有多种命名的统计分布是经典的。如果你能找到你想要的那个，那将对你和任何愿意提供帮助的人都有帮助。从您给出的粗略描述来看，听起来您可能正在寻找幂律分布（又名“长尾”分布，另请参见“无标度网络”）。您在（例如）社交网络中经常看到这类分布，在这种情况下，连接性非常高的节点相对较少（即流行的节点），然后是连接性非常低的许多节点。在少数高度连接和许多稀疏连接之间，中间存在一种指数衰减。这似乎是描述随机生成的社交网络的论文：社交网络的随机图模型。

给定 networkx 和适当的统计分布，您应该能够构建您的梦想图。祝你的项目好运，编码愉快。

于 2012-05-11T17:17:05.117 回答
2

没有提供足够的信息来完全指定您想要的图表类型。然而，由于图通常是某种物理结构的抽象，所以对随机图的常见要求是无标度的。这些图具有度分布渐近服从幂律的性质。人口动态、Facebook 好友、引文网络和互联网流量都对某些领域具有幂律依赖性。生成无标度网络的规范方法是Barabási-Albert 方法。下面转载（来自维基百科）是创建这样一个网络的动画。它保证连接任何 N 并且泛化允许您设置连接。

在此处输入图像描述

networkx可以轻松生成这些随机图：

import networkx

node_number = 20
initial_nodes = 2
G = networkx.barabasi_albert_graph(node_number, initial_nodes)
于 2012-05-11T17:40:21.750 回答
1

问题1：

首先创建一个将所有节点连接在一起的随机生成树，然后添加其他边。

问题2：

创建一个所有(i,j)for1 ≤ i < j ≤ n的列表，打乱列表并获取前 k 个边。然后，您的图形将具有n顶点和k±n边。

于 2012-05-11T17:09:33.843 回答
1

(1) 这很简单——只需先创建一棵树，并且只有在确保连通性之后——开始添加更多边。
这可以通过迭代地增加一组连接的顶点来轻松完成。
伪代码：

source <- select random vertex
set <- {source}
while set != V:
   chose a random vertex v from set, and u from V\set
   add (v,u),(u,v) as an edge
   add u to set

(2)
我会使用正态分布来选择每个节点的边数。每个节点都会得到一个不同的随机变量——因此会有不同数量的节点。

  • 我认为这是一个很好的方法，因为现实生活中事物往往呈正态分布（由于中心极限定理）。
  • 您可以通过修改用于确定每个顶点的边数的随机变量的均值和方差来控制连通性。
  • 您也可以使用任何其他分布来选择每个节点的边数，但我相信正态分布最适合。
于 2012-05-11T17:12:22.650 回答