基于博弈和遗传算法的网络重构算法

摘要

本发明属于复杂网络技术领域，具体公开了一种基于博弈和遗传算法的网络重构算法。其主要实现步骤包括：首先，对于节点数为N的网络，随机初始化A个0-1矩阵，初始化博弈策略；其次，已知节点实际收益值，计算A个矩阵的节点收益值，以及每个节点的总收益值；再次，根据遗传算法更新种群，迭代T代得到A个新的矩阵；最后，根据对压缩感知网络重构算法的改进，用它进行单个节点重构，直到所有节点收益值与实际收益相等，就得到了实际的网络。本发明对节点较多，度较大的网络重构也能完全正确，而且时间也非常快。

说明书

技术领域

本发明属于复杂网络技术领域，涉及复杂网络的重构和数据挖掘技术， 具体是一种基于博弈和遗传算法的网络重构算法。

背景技术

复杂网络是现实世界中复杂系统抽象出来的一种表现形式，现实世界 中存在很多这种类型的复杂网络，比如，社会网络中的朋友关系网络、电 力网、万维网、生物网络中的神经网络以及新陈代谢网络等等。在现实世 界网络中，我们把系统中的独立个体抽象成网络中的节点，系统中个体之 间按照某种规则而自然形成或人为构造的一种关系抽象成节点之间的边。

自从1998年、1999年在“Nature”和“Science”两个刊物上发表了关 于小世界网络和Scale-free网络的两篇文章以来，在世界范围内掀起了一股 复杂网络的研究热潮。此后几年来，关于复杂网络的研究取得了很多重要 的研究成果，复杂网络已经成为科学研究的一个重要领域。

由于复杂网络节点众多，结构复杂，使得其研究非常困难。在科学和 工程的许多领域，人们遇到的感兴趣的系统是由网络化的元素组成的，这 些元素称为节点，但该模式的节点与节点的相互作用或网络拓扑结构是完 全未知。其中未揭示的网络拓扑结构可以从实验或观测结果中提取若干基 于时间序列的数据来获取。

在过去几年，网络重构问题受到了越来越多的关注，大多数存在的算 法都是基于压缩感知算法，它利用网络的稀疏性，用压缩感知模型重构网 络，对于稀疏的网络效果很好，但与此同时存在的缺点就是稀疏性的约束， 对于复杂不稀疏的网络比如社区网络等就不能够重构正确，并且时间复杂 度很高，对于大网络重构很费时，针对已有算法的缺点，本算法解决的现 有算法的不足，不受稀疏性约束，并且大大降低了时间复杂度。

发明内容

本发明的目的在于根据网络节点的属性信息，重构出网络的整个拓扑 结构，提供一种基于博弈和遗传算法的网络重构算法。

本发明的技术方案是：基于博弈和遗传算法的网络重构算法，包括如 下步骤：

(1)首先随机初始化A个N*N的0-1矩阵matrix[N][N][A]，A＝100；

(2)在囚徒困境博弈下，初始化N个节点的的博弈策略state[N]，然 后计算出实际网络在博弈策略state[N]下的节点收益和总收益 payoff_real[N+1]，以及A个矩阵matrix[N][N][A]的收益 payoff[N+1][A]；

(3)遗传算法的计算过程：

(3.1)每次从A个矩阵matrix[N][N][A]中随机无重复抽取两个矩阵 matrix[N][N][a]和matrix[N][N][b]，其中a≠b，a、b分别代表随机抽取的矩 阵；

(3.2)第一个子代txt[N][N][a]的得到：

选取总收益与实际总收益差值最小的父代作为第一个子代，当 |payoff[N][a]-payoff_real[N]|≤|payoff[N][b]-payoff_real[N]|时， txt[N][N][a]＝matrix[N][N][a]；否则txt[N][N][a]＝matrix[N][N][b]；

(3.3)第二个子代txt[N][N][b]的得到：

对于txt[i][N][b]第i行的选取，也就是第i个节点的邻接向量的选取：

交叉：选取第i个节点收益较接近payoff_real[i]的父代的第i行，即

当|payoff[i][a]-payoff_real[i]|≤|payoff[i][b]-payoff_real[i]|时，

txt[i][N][b]＝matrix[i][N][a]并且payoff_txt[i]＝payoff[i][a]，

否则txt[i][N][b]＝matrix[i][N][b]，payoff_txt[i]＝payoff[i][b]，式中N表 示将matrix[i][N][b]第i行的N个值全部赋给txt[i][N][b]；

变异：在第i行选取之后，当txt[i][j][b]≠txt[j][i][b]时，以概率prop 选取:$\mathrm{prop}=\frac{|\mathrm{payoff}\_\mathrm{txt}[i]-\mathrm{payoff}\_\mathrm{real}[i\left]\right|}{|\mathrm{payoff}\_\mathrm{txt}[i]-\mathrm{payoff}\_\mathrm{real}[i\left]\right|+|\mathrm{payoff}\_\mathrm{txt}[j]-\mathrm{payoff}\_\mathrm{real}[j\left]\right|}$

当生成的随机数random<prop时，txt[i][j][b]＝txt[j][i][b]，更新节点 i收益值payoff_txt[i]，否则txt[j][i][b]＝txt[i][j][b]，更新节点收益值 payoff_txt[j]；

(3.4)最后更新种群，matrix[N][N][a]＝txt[N][N][a]，matrix[N][N][b]＝ txt[N][N][b]。

(3.5)重复步骤(3)50次；

(4)重复T次步骤(2)和(3)，T＝100，即种群更新迭代100次，得 到A个邻接矩阵matrix[N][N][A]；

(5)随机抽取一个矩阵matrix[N][N][m],计算节点与实际收益的差值并 按降序排列d_value[N][2]，第一列存储节点，第二列存储该节点的收益差 值；

(6)用基于压缩感知和博弈的重构算法对节点x＝d_value[1][1]重构， 得到x的邻接向量avrage[x]：

(7)把节点d_value[1][1]的邻接向量avrage[x]按照对称原则对应赋值 给步骤(4)得到的100个矩阵matrix[N][N][A]，得到100个新的初始种群， 按照步骤(3)运行一次；

(8)重复步骤(5)、(6)、(7)直到节点收益值与实际相等，得到重 构的网络。

上述步骤(2)所述的计算节点的收益是通过下面的公式计算的：

$F_{\mathrm{ij}}=S_i^{T}P{S}_j$  $G_i=\underset{j\in {\Gamma }_i}{\Sigma }{S}_i^{T}P{S}_j$

S(C)＝(1，0)^T  S(D)＝(0，1)^T

其中，P是一个2*2收益矩阵：$P=\left(\begin{array}{cc}0.95& -0.14\\ 1.56& 0.6\end{array}\right)$

F_ij表示节点i与节点j博弈后节点i获得的收益值；

G_i表示节点i和与i相连节点博弈的收益值之和；

Г_i表示与节点i有连接的节点的集合；

S_i、S_j表示节点i和节点j的策略矩阵；

公式中的T表示矩阵的转置符号；

S(C)表示为合作的策略矩阵，S(D)表示为背叛的策略矩阵。

本发明的有益效果：本发明根据节点收益值对随机产生的100个样本 邻接矩阵的交叉变异，得到较好的样本邻接矩阵，然后根据压缩感知方法 重构部分节点，最终得网络正确的邻接矩阵。本发明结合了博弈理论和遗 传算法的方法，能够快速，准确的重构出网络的真实拓扑结构。在基因调 控网络的重构、基于社会离散数据或信息揭示组织网工程科学以及国土防 卫等领域有重要的应用。本发明不仅对节点少，度小的网络实用，对于大 网络也非常实用，而且效率高，不受网络稀疏性的约束。

以下将结合附图对本发明做进一步详细说明。

附图说明

图1是本发明的流程框图；

图2是本发明的优化步骤；

图3是本发明实施例中一个具有34个节点的图；

图4是本发明实施例中网络的重构结果。

具体实施方式

本发明的软件运行环境是MicrosoftVisualC++6.0，实施的具体步骤参 照图1和图2，本发明基于博弈和遗传算法的网络重构算法，包括以下步骤：

(1)首先随机初始化A个N*N的0-1矩阵matrix[N][N][A]，A＝100；

(2)在囚徒困境博弈下，初始化N个节点的的博弈策略state[N]，然 后计算出实际网络在博弈策略state[N]下的节点收益和总收益 payoff_real[N+1]，以及A个矩阵matrix[N][N][A]的收益 payoff[N+1][A]；

计算节点的收益是通过下面的公式计算的：

$F_{\mathrm{ij}}=S_i^{T}P{S}_j$  $G_i=\underset{j\in {\Gamma }_i}{\Sigma }{S}_i^{T}P{S}_j$

S(C)＝(1，0)^T  S(D)＝(0，1)^T

其中，P是一个2*2收益矩阵：$P=\left(\begin{array}{cc}0.95& -0.14\\ 1.56& 0.6\end{array}\right)$

F_ij表示节点i与节点j博弈后节点i获得的收益值；

G_i表示节点i和与i相连节点博弈的收益值之和；

Г_i表示与节点i有连接的节点的集合；

S_i、S_j表示节点i和节点j的策略矩阵；

公式中的T表示矩阵的转置符号；

S(C)表示为合作的策略矩阵，S(D)表示为背叛的策略矩阵。

(3)遗传算法的计算过程：

(3.1)每次从A个矩阵matrix[N][N][A]中随机无重复抽取两个矩阵 matrix[N][N][a]和matrix[N][N][b]，其中a≠b，a、b分别代表随机抽取的矩 阵；

(3.2)第一个子代txt[N][N][a]的得到：

选取总收益与实际总收益差值最小的父代作为第一个子代，当 |payoff[N][a]-payoff_real[N]|≤|payoff[N][b]-payoff_real[N]|时， txt[N][N][a]＝matrix[N][N][a]；否则txt[N][N][a]＝matrix[N][N][b]；

(3.3)第二个子代txt[N][N][b]的得到：

对于txt[i][N][b]第i行的选取，也就是第i个节点的邻接向量的选取：

交叉：选取第i个节点收益较接近payoff_real[i]的父代的第i行，即

当|payoff[i][a]-payoff_real[i]|≤|payoff[i][b]-payoff_real[i]|时，

txt[i][N][b]＝matrix[i][N][a]并且payoff_txt[i]＝payoff[i][a]，

否则txt[i][N][b]＝matrix[i][N][b]，payoff_txt[i]＝payoff[i][b]，式中N表 示将matrix[i][N][b]第i行的N个值全部赋给txt[i][N][b]；

变异：在第i行选取之后，当txt[i][j][b]≠txt[j][i][b]时，以概率prop 选取:$\mathrm{prop}=\frac{|\mathrm{payoff}\_\mathrm{txt}[i]-\mathrm{payoff}\_\mathrm{real}[i\left]\right|}{|\mathrm{payoff}\_\mathrm{txt}[i]-\mathrm{payoff}\_\mathrm{real}[i\left]\right|+|\mathrm{payoff}\_\mathrm{txt}[j]-\mathrm{payoff}\_\mathrm{real}[j\left]\right|}$

当生成的随机数random<prop时，txt[i][j][b]＝txt[j][i][b]，更新节点 i收益值payoff_txt[i]，否则txt[j][i][b]＝txt[i][j][b]，更新节点收益值 payoff_txt[j]；

(3.4)最后更新种群，matrix[N][N][a]＝txt[N][N][a]，matrix[N][N][b]＝ txt[N][N][b]。

(3.5)重复步骤(3)50次；

(4)重复T次步骤(2)和(3)，T＝100，即种群更新迭代100次，得 到A个邻接矩阵matrix[N][N][A]；

(5)随机抽取一个矩阵matrix[N][N][m],计算节点与实际收益的差值并 按降序排列d_value[N][2]，第一列存储节点，第二列存储该节点的收益差 值；

(6)用基于压缩感知和博弈的重构算法对节点x＝d_value[1][1]重构， 得到x的邻接向量avrage[x]：

根据压缩感知模型G_x＝Φ_x·Y_x，其中G_x为节点x的实际收益，本算法的 已知条件；Φ_x为节点x与其余N-1个节点博弈的收益值，通过博弈求得； Y_x为节点x的邻接向量，是我们要求的解。由G_x、Φ_x已知，通过矩阵的 逆运算，得到节点x的邻接向量Y_x，即avrage[x]。

(7)把节点d_value[1][1]的邻接向量avrage[x]按照对称原则对应赋值 给步骤(4)得到的100个矩阵matrix[N][N][A]：matrix[x][N][A]＝avrage[x]， matrix[N][x][A]＝avrage[x]，得到100个新的初始种群，按照步骤(3)运行 一次；

(8)重复步骤(5)、(6)、(7)直到节点收益值与实际相等，得到重 构的网络。

综上，本发明根据节点收益值对随机产生的100个样本邻接矩阵的交 叉变异，得到较好的样本邻接矩阵，然后根据压缩感知方法重构部分节点， 最终得网络正确的邻接矩阵。本发明结合了博弈理论和遗传算法的方法， 能够快速，准确的重构出网络的真实拓扑结构。在基因调控网络的重构、 基于社会离散数据或信息揭示组织网工程科学以及国土防卫等领域有重要 的应用。本发明不仅对节点少，度小的网络实用，对于大网络也非常实用， 而且效率高，不受网络稀疏性的约束。

本发明的效果可以通过以下实验进一步说明：

1.仿真条件：

在CPU为core22.4GHZ、内存4G、WINDOWS7系统上使用Microsoft  VisualC++6.0进行了仿真。

2.仿真内容：

选取一个具有34个节点，78条边的空手道俱乐部网络，节点度最小为 1，最大为17。实验中，随机生成100个样本邻接矩阵，经过100代的进化 交叉后，得到100个较好的样本邻接矩阵，然后结合压缩感知重构算法， 每重构一个节点，更新种群，迭代一代，当抽取种群的节点收益值与实际 收益值相等时终止，即得到网络网络，实验中我们重构了17个节点后收益 值就相等了。

实验中，图3是空手道俱乐部网络的真实连接，图4是通过我们的方 法重构的正确情况。由实验结果可知，采用本发明中提出的网络重构方法， 可以很好的重构出网络的拓扑结构。

上述实施方式仅是本发明的一个实例，不构成对本发明的任何限制， 例如用本发明方法还可以应用到其他网络的重构，如62个节点，159条边 的海豚网络，计算机随机产生的100个节点，301条边的EA网络等。

3.实验结果

在图4是相应实验的仿真结果，横坐标表示重构的节点数，纵坐标表 示错误边数，可以看出当重构18个节点后重构的错误边数即达到0，网络 重构正确。

综上，本发明根据节点收益值对随机产生的100个样本邻接矩阵的交 叉变异，得到较好的样本邻接矩阵，然后根据压缩感知方法重构部分节点， 最终得网络正确的邻接矩阵。本发明结合了博弈理论和遗传算法的方法， 能够快速，准确的重构出网络的真实拓扑结构。在基因调控网络的重构、 基于社会离散数据或信息揭示组织网工程科学以及国土防卫等领域有重要 的应用。本发明不仅对节点少，度小的网络使用，对于大网络也非常实用， 而且效率高。

本实施例没有详细叙述的部分属本行业的公知的常用手段，这里不一 一叙述。以上例举仅仅是对本发明的举例说明，并不构成对本发明的保护 范围的限制，凡是与本发明相同或相似的设计均属于本发明的保护范围之 内。