Page 30 - 《软件学报》2020年第11期

3346 Journal of Software 软件学报 Vol.31, No.11, November 2020

3
所有模体遍历的时间复杂度是 O(n ),n 是基因调控网的规模,即节点数.那么,若一个动态基因调控网包含 T 个快
3
照,则总的时间复杂度是 O(Tn ).由于获得的张量大小是 64×64×(T−1),由第 3.1 节数据集描述可知,现有的动态基
因调控网快照数都不大,当 T 是一个不大于 100 的数时,其张量分解和时间因式矩阵预测的时间复杂度都可以
视作常量 O(K)(无论是采用幂律分布模型还是指数分布模型),K 是张量分解的维度.进行连边预测时,需要对每
2
一个节点对进行打分,时间复杂度是 O(n ).特征提取是针对每一条边进行的提取,所以第 3 部分的时间复杂度是
O(k|E|),其中,k 是非负矩阵三因子分解的分解维度,|E|是涉及到的的边的总数.通常来说,基因调控网是及其稀疏
的,即|E|≈ξn,ξ是一个 1.5~3 左右的数.总的来说,DGNE 方法的瓶颈在于第 1 部分,算法的最大时间复杂度为
3
O(n ).
3.4 DGNE方法有效性验证
本节对 DGNE 方法的相关表现与目前已有的基础和最新方法进行对比分析,评价其在动态基因网网络演
化分析方面的表现.鉴于目前已有的相关方法无法对网络符号进行判别,因此本节首先验证在不进行符号判别
的情况下算法的表现(此时该方法退化为 MT 算法),再验证加入了符号判别算法之后 DGNE 方法的表现.
本节使用若干对比性算法,包括 4 种基准算法与 2 种最新算法与本方法进行对比,它们是:
(1) 共同邻居(CN) [16] :该方法假设在网络中,两个节点之间如果有更多的共同邻居,则它们在下一个时刻
的快照中更倾向于连边.
(2) Adamic-Adar(AA) [17] :是共同邻居算法的改良版.该方法假设两个节点如果都与一个度比较小的节点
相连,那么这两个节点在下一时刻的快照中连边的概率更大.即,度小的共同邻居节点的贡献要大于
度大的共同邻居节点.
(3) Katz [20] :是一种基于网络全局拓扑结构的链路预测算法.该方法遍历两节点间的所有路径,并假设若
这些路径中距离短的数量越多,那么这两个节点在下一时刻快照中连边的概率更大.
(4) Preferential Attachment(PA) [39] :是一种基于网络局部拓扑结构的链路预测算法.在该方法中,两节点在
下一时刻快照中相连的概率正比于两节点各自的度的乘积.
(5) ctBRM [23] :是一个基于受限玻尔兹曼机的深度学习方法,面对噪声有较好的稳定性.
(6) BCGD [24] :是一个基于隐空间的动态社会网络链路预测算法.该方法假设所有的节点都存在于某个不
可观测的隐空间中,在该空间中,距离较近的节点对更容易形成连边.
3.4.1 不进行符号判别的情况下 DGNE 方法的有效性验证
在不进行符号判别的情况下,本文的 DGNE 方法退化为 MT 算法.由于 3 个仿真数据集仅载数据规模有所
差别,故选取其中最具有代表性的 SynC 数据集与 Dro 和 Rat 分别对 DGNE 的有效性进行验证.实验结果 AUC
值见表 3,各算法准确率如图 9 所示.当 AUC 大于 0.5 时,其分数越高,表示算法在此数据集上拥有越高的预测准
确性;当 AUC 值小于等于 0.5 时,表示该算法在该数据集上的预测准确性约等于随机效果,或不如随机过程.
基于表 3 和图 9 的实验结果,可以得到以下结论.
(1) 总体来说,MT 算法效果优于其他算法.这说明 MT 算法能够正确地预测动态基因调控网的连边状况,
即,其在一定程度上对动态基因调控网网络演化机制具有正确的把握.其中,Katz 算法在 synC 数据集
上具有非常良好的表现,但在真实的数据集中其表现并不如在仿真数据集中那么优秀.这是由于本文
使用的仿真工具的数据生成模型过于强调了基因调控网的小世界特性,而小世界特性与 Katz 算法的
特点相性很好,导致结果出现异常.在以后的研究中,应适当调整仿真工具的模型和参数.
(2) 大部分基准算法的 AUC 指标表明,它们的预测效果与随机过程几乎无异.该结果说明,这些算法不适
用于对动态基因调控网进行演化分析.动态基因调控网网络演化具有其独特的特性,从结果上来看,
只有本文提出的 DGNE 方法以及 BCGD 在一定程度上可以把握其演化模式.
(3) 本文提出的 MT 算法与大部分最新算法在真实数据集上(Dro,Rat)的表现不如仿真数据集上好,这是
由于在真实的生物体内,基因调控网的演化还受到众多外部因素的干扰,如疾病、环境、食物和药物
等.小鼠作为哺乳动物其基因调控网受到的各类外部影响更甚于果蝇,因此,单纯地用模体演化解释