一种恒定类间和类内连接密度的网络演化方法

摘要

本发明涉及的是一种恒定类间和类内连接密度的网络演化方法。本发明包括：（1）构造一个包含有m

说明书

技术领域

本发明涉及的是一种恒定类间和类内连接密度的网络演化方法。

背景技术

Internet、www等网络发展到现在已成为巨大网络。由于网络的复杂性，使得在真实的网 络上进行网络及网络应用的研究、测试和模拟非常困难，一种有效的研究方法是构造符合真 实网络特性的仿真网络。在复杂网络研究的早期，研究人员主要关注网络最基本的宏观特性。 例如：《Journal of Statistical Physics》杂志刊登的“Models of the Small World”一文提出的小 世界现象、网络连接的成团性质等。自从1999年Barabàsi和Albert发表于《Science》杂志 上的“Emergence of Scaling in Random Networks”一文发现真实网络的无标度性质以来（无标 度网络，Scale Free），对真实网络中各种宏观性质的微观生成机制以及网络的演化规律等一 系列问题的研究已成为科学家广泛关注的热点。BA模型首次从网络演化角度来研究网络的一 些宏观性质起源，利用BA模型构造了具有幂律度分布的无标度网络，同时指出增长和偏好 依附是BA模型无标度网络的关键要素。但刊登在《Europhys.Lett》杂志上的“Measuring  Preferential Attachment in Evolving Networks”一文发现了BA模型也存在许多局限性，如，它 只能生成度分布的标度指数固定为3的网络，而所观测到的实际网络幂指数通常在1-3的范 围内等。实验结果说明，真实网络在演化过程还受到许多其他因素的影响，而在BA模型中 并未考虑这些因素。同时，网络中节点间的连接关系和相互作用的差异对网络的性质以及动 力学性能有着很大的影响。因此，构造恒定密度的演化方法来刻画复杂网络的结构和节点间 的相互作用关系是十分必要的。

发明内容

本发明的目的在于提供一种在演化过程中依旧能够保证网络具有恒定的类间和类内密度 的方法。

本发明的目的是这样实现的：

一种恒定类间和类内连接密度的网络演化方法，包括：

（1）构造一个包含有m₀个节点的全连通网络，并设置每个节点的所属于类号：

（1.1）建立一个空的网络图，并在网络图中产生m₀个不同的节点；

（1.2）设置每个节点具有从1到m₀之间的不同类号，因此有类别数c=m₀；

（1.3）在m₀个节点中的任意两个节点间建立两条互相连接的边，共产生m₀×(m₀-1)条 有向边；

（2）引入新节点，并分配新节点的所属类号：

（2.1）产生一个新的第k个节点V_k，加入到网络中；

（2.2）在1至类数加（c+1）区间产生一个整数；

（2.3）将产生的这个整数作为类号分配给新加入节点V_k；

（3）建立新节点与已存在节点的连边：

（3.1）将新节点采用聚类性机理和偏好依附机理建立与网络中同类已存节点连边，若类 内含有的节点数目为l-1个，则建立的连边数为2l×InDensity，选择连接节点的概率与被连接 节点的出度成正比，选择被连接节点的概率与连接节点的入度成正比；

（3.2）若产生一个新的类别，即j=c+1,则需要以类间密度OutDensity为参数更新类别间 的连接：则执行以下步骤2c次

（3.2.1）随机选择两个不同的类；

（3.2.2）从两个不同的类中选择未建立连接的节点对，选择连接节点的概率与出度成正 比，选择被连接节点的概率与入度成正比；

（3.2.3）以类间连接密度OutDensity为概率在两个节点间建立连接。

本发明的有益效果在于：随着网络的演化依旧能够保证网络中的类内和类间密度的恒定 不变。

附图说明

图1为100个节点的生成网络图。

具体实施方式

下面结合附图举例对本发明做更详细地描述：

本发明的主要技术特征体现在：

随着网络的演化，网络的类内连接密度和类间连接密度保持恒定。

具体技术路线是：1.通过以一定概率追加类内的连接保证类内连接密度；2.通过以一定 次数的以一定概率追加类间的连接保证类内连接密度。

本发明包括：

1）构造一个包含有m₀个节点的全连通网络，并设置每个节点的所属于类号；

2）引入新节点，并分配该节点的所属类号；

3）建立新加入节点与已存在节点的连边；

所述的构造一个包含有m₀个节点的全连通网络，并设置每个节点的所属于类号的方法为： 1）建立一个空的网络图，并在图中产生m₀个不同的节点；2）设置每个节点具有从1到m₀之 间的不同类号，3）在任意两个节点间两条互相连接的边。

所述的引入新节点，并分配该节点的所属类号方法是：1）产生一个新的节点，并将其加 入到网络中；2）从1到当前类别数加1的区间内随机生成一个数字，并将其作为新节点的类 号。

所述的建立新加入节点与已存在节点的连边的方法是：1）若新加入节点分配的类中节点 数大于1，则根据设定的参数建立新加入节点与类内节点的连边；2）若新加入节点的类号中 节点数为1，则跟军设定的参数建立网络中类之间的连边。

实施例：

1）构造一个包含有m₀个节点的全连通网络，并设置每个节点的所属于类号；

与无标度网络的生成方法一样，网络的初始阶段需要构造一个具有m₀个节点的全连通网 络，具体的步骤如下：

建立一个空的网络图，并在图中产生m₀个不同的节点；

设置每个节点具有从1到m₀之间的不同类号，因此有类别数c=m₀；

在m₀个节点中的任意两个节点间建立两条互相连接的边，因此共产生m₀×(m₀-1)条有向 边

2）引入新节点，并分配该节点的所属类号；

具体步骤如下：

产生一个新的节点V_k（第k个节点)，并将其加入到网络中；

在1至类数加（c+1）区间产生一个随机的整数：

将产生的这个随机整数作为类号分配给新加入节点V_k：

3）建立新加入节点与已存在节点的连边；

节点加入以后产生网络中的新边是保证网络中类内和类间密度恒定的关键。具体实现如 下：

新引入的节点首先采用聚类性机理和偏好依附机理建立与网络中同类已存节点连边，若 类内含有的节点数目为l-1个，则建立的连边数为2l×InDensity,选择连接节点的概率与被连 接节点的出度成正比，选择被连接节点的概率与连接节点的入度成正比。

如果产生一个新的类别，即j=c+1,则需要以类间密度OutDensity为参数更新类别间的连 接。则执行以下过程2c次。a)首先，随机选择两个不同的类；b)从两个不同的类中选择未建立 连接的节点对，选择连接节点的概率与其出度成正比，选择被连接节点的概率与其入度成正 比；c)以类间连接密度OutDensity为概率在两个节点间建立连接。

按照以上网络演化方法生成的含有100个节点的网络如图1所示。

4）保证类内和类间密度恒定的相关引理、推论以及证明过程

引理1：如果网络初始包含有m₀个节点，且网络演化过程中增加c₀个类别时，那么增加的 节点数均值为类内节点的平均个数为

证明：初始包含有m₀个节点，增加一个节点产生一个新的类别，即类数为m₀+1的概率 为

因此增加这个类别平均需要添加m₀+1个新节点。如果网络演化过程中增加了c₀个类别， 那么平均增加的节点数为$(m_0+1),+...,(m_0+c_0)=\frac{(m_0+c_0+m_0+1)\times (m_0+c_0-m_0-1+1)}{2}=\frac{(2m_0+c_0+1)\times c_0}{2}.$

网络演化增加c₀个类别时，共平均包含节点数为个，其包含的类数为 m₀+c₀，因此类内平均节点数为化简后得证毕。

引理2：有向网络包含类别数为c个，且类间密度为OutDensity时，当类别数增加1个时， 寻找2c个未建立连接的节点并以OutDensity为概率建立连接，则生成后的网络类间密度依旧为 OutDensity。

证明：假设类别数增加前共有节点x个，有

那么类别数增加后共添加边数为2c×OutDensity个，那么，此时含有的边数为：

$x+2c\times \mathrm{OutDensity}=x+\frac{2\mathrm{cx}}{c(c-1)},$

生成后的网络间密度为：$(x+\frac{2\mathrm{cx}}{c(c-1)})/c(c+1)=\frac{x}{c(c-1)}=\mathrm{OutDensity}.$

因此生成后的网络与生成前的网络密度相同。证毕。

推论1：如果网络初始是节点数为0，网络演化过程中增加c₀个类别时，那么网络中节点 数均值为类内节点的平均个数为

推论1由引理1中将m₀=0即可。

以上规则中借鉴了无标度网络模型中的偏好依附机理，同时也引入了聚类性和信息传播 的驱动模式。从以上引理和推论可知：按照本发明的网络演化方法保证了演化过程中增加的 节点数与增加的类数的平方成正比。类内节点数量的均值与增加的类数成正比；以及网络中 连接的增加的策略能够保证连接密度值稳定的性质。在连接权重分布生成阶段，通过规则模 拟了电子邮件在用户之间进行发送、回复和转发的过程，更加接近真实的通信情况。