Archive 2019 年 7 月 5 日

NetworkX中四种网络模型的生成函数

1、规则图 random_graphs.random_regular_graph(d, n) 含有n个节点,每个节点有d个邻居节点的规则图。 2、ER图 random_graphs.erdos_renyi_graph(n,p) 生成一个含有n个节点,以概率p来连接N个节点中的每一对节点 3、WS小世界模型 random_graphs.watts_strogatz_graph(n, k, p) 生成一个含有n个节点、每个节点有k个邻居、以概率p随机化重连边的WS小世界网络。 简单说,小世界网络外圈是是一个环形,然后每个环形上的节点随机连接到其它节点。 这种结构的网络模型是一类具有较短的平均路径长度又具有较高的聚类系数的网络的总称。 通过调节一个参数可以从规则网络向随机网络过渡,该模型成为WS小世界模型。 从一个环状的规则网络开始:网络含有N个结点,每个节点向与它最临近的K个节点连出K条边,并满足N>>K>>ln(N)>>1。 以概率p随机地重新连接网络中的每个边,即将边的一个端点保持不变,而另一个端点取为网络中随机选择的一个节点。其中规定,任意两个不同的节点之间至多只能有一条边,并且每一个节点都不能有边与自身相连。 这样就会产生pNK/2条长程的边把一个节点和远处的结点联系起来。改变p值可以实现从规则网络(p=0)向随机网络(p=1)转变。 注意WS小世界模型构造算法中的随机化过程有可能破坏网络的连通性,更佳的模型需要考虑:NW小世界网络模型。 4、BA图(无标度) andom_graphs.barabasi_albert_graph(n, m) 生成一个含有n个节点、每次加入m条边的BA无标度网络。 无标度网络的特征是具有严重的异质性,其各节点之间的连接度数具有严重的不均匀分布性。 典型的如的路由器,网络中少数称之为Hub点的节点拥有极其多的连接,而大多数节点只有很少量的连接。 又比如呼叫中心、发电厂等,由少数Hub点对无标度网络的运行起着主导的作用。 无标度网络的无标度性,是描述大量复杂系统整体上严重不均匀分布的一种内在性质。 在无标度网络中,如果中心节点受到攻击,那么会引起大规模瘫痪。

Read More