如何根据节点数和边数生成一个随机图形？

Question

我正在使用Python和igraph库:

from igraph import *
g = Graph()
g.add_vertices(4)
g.add_edges([(0,2),(1,2),(3,2)])
print g.betweenness()

我想生成一个有10000个节点和100000条边的随机图。边可以是随机的。请建议一种使用numpy.random.rand实现随机边的方法。

- Kush Jain

Answer 1

你是否必须使用 numpy.random.rand？如果不是，只需要使用Graph.Erdos_Renyi，这样就可以直接指定节点和边的数量：

g = Graph.Erdos_Renyi(n=10000, m=100000)

- Tamás

Answer 2

使用 numpy.random.rand 来实现，生成随机数组，用你想要的概率进行阈值处理，然后将其传递给 Graph.Adjacency：

adj = numpy.random.rand(edges, edges)
adj[adj > 0.999] = 1 # sets everything over 0.999 to 1
adj[adj <= 0.999] = 0 # sets everything below to 0
graph = Graph.Adjacency(adj)

这将生成一个有向图，其中adj[i,j]告诉您是否存在从i->j的边缘。如果您要代替使用无向图，则使用 Graph.Ajacency(adj,ADJ_UNDIRECTED) - 然后如果adj[i,j]==1或adj[j,i]==1，则会有一条边缘。

不能保证确切地给出100,000个边缘-您需要吗？

- babbageclunk

---

首先，不幸的是这不是他想要的。他想要给定数量的边。其次，如果图是稀疏的，则这是一种生成随机 G(n,p) 图的非常低效的方法。 - Gabor Csardi

哦，你说得对 - 我错过了边的数量。我认为我的基本方法仍然适用于他所讨论的节点数 - 邻接矩阵是浪费的（100k条边需要100M个单元格），但是你只需要它来创建图形。 - babbageclunk

numpy.random.rand(edges, edges) 应该改为 numpy.random.rand(nodes, nodes)，我认为。 - Björn Lindqvist