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

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

由以上描述,本文对模体在链路预测中的影响力定义如公式(2)所示.
T − 1 T − 1
W = i θ 1 Tt− g (, )i t + ∑ θ 2 Tt− f ( , ) 1i t + ∑ (2)
t= 1 t= 1
W i 是表示第 i 个模体的影响力的分值;g(i,t)表示 t 时刻第 i 个模体中各节点连边个数;f(i,t)表示 t 时刻第 i
个模体是否闭合,即 3 个节点两两之间是否至少存在一条有向边,闭合时为 1,不闭合为 0;θ 1 ,θ 2 是控制不同时期
的历史快照对 W i 贡献的系数,距当前时刻越近,贡献越大.
由此,根据 T 到 T+1 时刻的模体转换概率矩阵 TCM T 和模体的影响力 W,可以为每一对节点对赋予一个得
分,表示 T 时刻每个边存在的概率高低,如公式(3)所示.
|tri ( , )|u v
score (, )u v = ∑ W ⋅ T ( )m (3)
m
m= 1
其中,|tri(u,v)|表示 T−1 时刻包含节点对 u,v 的模体的总数,T(m)表示包含了边(u,v)的第 m 个模体从 T 时刻到 T+1
时刻的转移概率.具体算法如算法 1 所示.
算法 1. MT.
输入:时刻 1 到时刻 2,时刻 2 到时刻 3,…,时刻 T−2 到时刻 T-1 的模体转换概率矩阵 TCM 1 ,TCM 2 ,…,TCM T−1 ,
张量分解参数 K.
输出:时刻 T+1 的基因调控网快照.
1. 构造张量 TCT=(TCM 1 ,TCM 2 ,…,TCM T−1 )对张量 TCT 进行 CP 分解,获得系数λ和大小为(T−2)×K 的矩阵
A,B,C.
2. 根据公式(3)计算模体转换似然概率矩阵 TCLM.
3. 根据公式(4)计算模体重要性得分.
4. 据公式(5)得到分数矩阵 score.
5. 取 score 矩阵中分数最高的前 L 个元素对应的节点对作为预测的连边(L 表示每个快照中包含的边的平
均数量),得到时刻 T+1 的连边邻接矩阵.
2.3 基于隐空间特征的动态基因调控网符号判别算法
在第 2.2 节研究的基础上,将动态基因调控网分为源网络和目标网络,其中,前 T−1 时刻的所有快照集合为
源网络,作为该算法的训练集,记作 G s =(G 1 ,G 2 ,…,G T−1 );由 MT 算法得到 T 时刻的快照为目标网络,记作 G t =(G T ).
在已经获得关于未来时刻基因调控网已知存在的边的情况后,对已知存在的边的符号仍所知极少,因此本文借
鉴了迁移学习的思路,寻找源网络和目标网络拓扑结构上共有的特征空间 [30] ,并通过机器学习的方法进行符号
判别.对于动态基因调控网来说,各快照都是同一网络在不同演化阶段的不同形态,因此各快照之间必定存在一
些内在的联系.本节通过寻找这种共有的特征空间,以提取其显式特征和隐空间特征,并构造一个高效的分类
器,在目标网络上对其边的符号进行判别.
与其他机器学习方法不同的是,在基因调控网编的符号判别中,没有任何“先验”的特征向量可以来对训练
集中一条边的符号来进行描述.因此,需要自己来根据源网络和目标网络的拓扑结构进行特征空间的构造.本文
构造的特征分为两类:(1) 显式特征,用以表达实例中显而易见的属性;(2) 隐空间特征,不能直接由网络拓扑结
构看出,但也表达了源网络和目标网络之间所共有的一些模式.
2.3.1 显式特征
对一个有向边(u,v),本文为其定义的显式特征包括节点的度数、中介中心性、模体个数以及共同邻居等.
这里需要注意的是,在为每一个样本定义这些特征的时候,完全不考虑这条边的符号,因为在目标网络中,对于
绝大部分边的符号都是未知的.各个特征的描述具体如下.
(1) 节点的度数.对一个有向边(u,v),通过 deg out (u)和 deg in (v)来分别指代节点 u 的出度和节点 v 的入度.节
点的度数代表着它与图中其他节点连接的紧密性.
(2) 中介中心性.对一个有向边(u,v),采用两端点的中介中心性 f bc (u)和 f bc (v)作为它的两个特征.中介中心