随机邻接列表生成器

本文关键字:列表 随机 | 更新日期: 2024-09-17 03:36:56

我目前正在开发一个应用程序,为我最后一年的项目在图中找到最大团。我已经完成了大部分项目,并且刚刚开始测试应用程序。

该应用程序目前使用邻接列表作为输入,我想知道是否有人知道邻接列表随机生成器,所以我可以测试我的应用程序?

非常感谢

随机邻接列表生成器

如果你从邻接矩阵而不是邻接列表的角度来考虑图,这个问题会更容易解决。具有m顶点的图可以由mm矩阵表示,其中每条边如果不存在则为0,如果存在则为1。

对于有向图,所有元素都是必需的,但对于无向图,则需要一个上三角矩阵。

一旦你得到了邻接矩阵,你就可以很容易地将其转换为邻接列表。

这取决于您的随机图模型。最简单的模型是Erdõs–Rényi模型,其中指定节点的数量和任何给定对之间链接的概率。这很容易生成,但生成的图不会很有趣,因为它们与现实世界中观察到的大多数网络根本不相似。真实世界的网络通常具有幂律度分布和较高的聚类系数。你可能对其他一些标准型号感兴趣,可以解决这个问题(Watts Strogatz或Barabási–Albert)。我还使用了本文中描述的LFR模型,该模型的源代码在这里可用。