随机邻接矩阵,每个节点的边数变化

Question

以下函数返回随机生成的大小邻接矩阵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

Answer 1

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

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

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