主权项 |
一种基于分组遗传算法的链路预测方法,其特征在于:包括如下步骤:(1)参数的初始化:根据需要预测的具体网络确定网络的节点个数N、种群大小M=100及种群迭代次数P=200、移除的边的比例Pr,其中Pr取(0,1)中的任何一个值;(2)确定训练集E<sup>T</sup>和测试集E<sup>P</sup>,得到观测矩阵A<sup>0</sup>:载入网络的连边数据集,计算出整个网络的连边数n,从网络的连边数据集中随机抽取[n×Pr+0.5]条边,其中[]表示取整数,这些边所组成的集合即为测试集E<sup>P</sup>,网络的连边数据集除去测试集E<sup>P</sup>之外作为训练集E<sup>T</sup>;先初始化观测矩阵A<sup>0</sup>为一个N×N的全零矩阵,依次遍历训练集E<sup>T</sup>中的所有边,并将这些边在观测矩阵A<sup>0</sup>中对应的元素改成1;(3)用分组遗传算法在不同分辨率λ的情况下对观测网络进行社区划分,其中λ依次取{0.1,0.2,0.3,0.4,0.5,0.6,0.7,0.8,0.9}中的一个,该分组遗传算法的具体步骤包括:1)随机生成M种初始的社区划分结构作为初始种群的染色体,依次遍历每一个染色体中的每一个社区,若社区内有节点与其它节点不全连接,那么将这个节点移入一个新的社区内,直到所有的社区内的节点之间都互相连接为止;2)计算初始种群中各个染色体的模块度密度函数值D<sub>λ</sub>,按D<sub>λ</sub>值的大小对染色体进行排序,并选择D<sub>λ</sub>值最大的那个染色体作为最优染 色体:<img file="FDA0001151082970000021.GIF" wi="758" he="195" />其中V<sub>i</sub>表示第i个社区内的所有节点的集合,<img file="FDA0001151082970000022.GIF" wi="37" he="65" />表示不在第i个社区内的节点的集合,L(V<sub>i</sub>,V<sub>i</sub>)表示第i个社区内所含边数的2倍,<img file="FDA0001151082970000023.GIF" wi="150" he="68" />表示第i个社区与其他社区的连接边数,|V<sub>i</sub>|为第i个社区内的节点个数,K表示网络中所含有的社区的个数;3)根据轮盘赌的方法随机选择两个染色体作为父代1和父代2;4)在所选择的父代1的染色体的小组部分随机选择两个社区,将这两个社区标号内的所有社区标号取出,将这些社区内的节点对应的分组情况遗传给子代,子代中其它还未分组的节点的分组情况与这些节点在父代2中的节点的分组情况相同;5)调整分组情况:找出社区内节点个数小于k最小值的那些社区内的节点,并将这些节点分别移入与其连接边数最多的社区内部;6)重复步骤3)至步骤5)直到生成M个子带;7)重复步骤2)至步骤6)直到迭代P代为止;8)保存最优染色体的社区划分情况作为计算出来的社区划分情况;(4)根据步骤(3)中最后得到的划分结果,计算测试集E<sup>P</sup>以及原始网络中不存在连边的节点对之间连接的可能性大小,记为R值;(5)从步骤(4)中计算R值的那些边中,按照R值从大到小的顺序排列,挑选前m个R值大对应的边作为我们算法预测出来的边;(6)计算这种预测算法的准确度。 |