链路预测算法在药物推荐中的应用研究∗

王秋杰 尹心明

（1.广东工业大学计算机学院 广州 510006）（2.公安部第三研究所信息安全技术部 上海 201204）

1 引言

社会网络是一种用于描述现实生活中目标、个体、组织和社区之间模型关系的拓扑结构。我们在不同区域或者不同方式上遇到的许多复杂系统可以通过社会网络实现可视化［1］。社会网络是我们了解这些复杂系统的结构、发展和关系的工具。复杂系统的网络分析能够帮助提供较多有价值的信息，同时这些信息能为后续更深层的研究提供支撑。

链路预测主要用来分析网络未来演化的状态，主要借助网络中节点的特征和已观察到的连接来预测两个节点间将来产生连接的概率［2］。其中，社交网络过去的状态是分析网络未来状态以及确定网络可能产生哪些新变化的基础。

在个体之间、社团之间和组织之间的社会关系是会随着时间的推移发生变化。因此，模拟这些现实世界关系的社交网络也会随之发生变化，并且随着这些关系的变化会产生一定程度的演化。在社会网络的动态演变中，新的链路、节点可以加入到现有的网络中，同时现有的链路、节点也可能从网络中消失。链路预测主要用于确定社交网络中各目标之间的动态关系。链路预测能够应用在不同的领域［3～6］。例如，在学术研究网络中，链路预测可以帮助找到某项学术研究的共同作者；在网购网络中，链路预测可以帮助客户推荐产品；在蛋白质作用网络中，链路预测可以帮助预测蛋白质的相互作用；另外，链路预测可以帮助预估未来文章的引用，判定人们的活动并加以归类，以及判定疾病之间的关系。

本文的首要目的是通过现有数据来创建疾病-药物网络，这些数据是从www.drugs.com上获取的，主要是关于哪些药物可以治愈哪些疾病的数据。建立好这个网络后，我们可以通过链路预测方法确定给定的药物可用于治愈哪些疾病。本文提出的内部链路方法可便于预测疾病-药物网络中的链路。为了分析提出方法的效果，我们选择四种基于相似性的链路预测算法对该网络进行预测。同时将内部链路方法的结果与四种基于相似性链路预测方法的结果进行对比。实验结果表明提出的方法在精准度、召回率和F-测度准则方面取得更好的结果。

2 链路预测问题

社交网络中的链路预测主要用来预测网络的未来结构，同时该网络被定义为一张拓扑图。用节点表示网络中的数据，用链路表示关系。判定未连接链路将来的连接状态是链路预测的主要研究内容，并通过链路预测算法为每个可能被连接的节点对分配一定的预测分数值。一对节点之间计算出来的预测分数值越高，这对节点未来连接的可能性越大。根据预测分数值的大小排列预测连边，排在前面的连边是将来最可能产生连接的链路。预测的准确性随着使用算法的变化而变化。

二分社会网络是社会网络的一种特殊形式。在二分社会网络中，节点位于两个不同的集群上。预测链路仅存在于不同集群的节点之间。同一个集群的节点中没有链路。在实际应用中，很多社会网络都有二分网络的结构［7～9］。由于大多数链路预测方法都是针对单一模式的网络结构，传统的链路预测算法很难直接应用到二分网络中。因此，基于先前的研究，本文首先将二分社会网络的链路预测转化为单一模式社会网络的链路预测。

在图1（a）表示的二分图形中，将仅包含 X节点的单一模式图表示为X-投影，同时将仅包含Y节点的单一模式图表示为Y-投影。如果二分图中的任何两个X节点与相同的Y节点建立邻域关系，那么这两个节点在 X投影中就建立一条链路。例如，由于 X1和 X2节点与图1（a）中的Y1节点连接，因此，X投影中建立了图1（b）所示的 X1和X2节点之间的链路。

把二分网络转变为单一模式的网络最简单的方法是不考虑网络的权重，即不考虑节点间的合作频率关系，直接建立未加权的网络。然而，由于单一模式的网络与二分社会网络相比包含较少的有用信息，因此图1展示的二分网络被转换成加权的单一模式的网络。本文根据合作关系的数量来给单一模式的网络赋予权重。例如在图1中，X投影上的X1和X2节点之间的权重被设为1。这是因为在二分网络中这两个节点之间有一个共同的邻居节点Y1，即Y1与 X1和 X2在原图中连接。本文将这种加权方式称为加权函数［10］，并且表示为

3 相关工作

迄今为止，提出了很多链路预测的方法。这些方法大都是基于相似性的链路预测方法［11～12］。基于相似性链路预测方法的基本理念是x节点和y节点的邻居节点交集越大，它们将来连接的可能性就越大。本文设定x和y是网络中的节点，Γ()x和Γ()

y是网络中x节点和 y节点邻居节点的集合。四个最常用的基于相似性的链路预测方法如下。

1）Common Neighbors（CN）:这种相似性指标的前提假设是两个节点将来产生连边的概率正比于这两个节点的共同邻居数［13］。由于简单，因此在链路预测问题中是应用最为广泛的相似性指标之一，其数学公式如下:

2）Jaccard Coefficient（JC）:Jaccard Coefficient是公共近邻相似性方法的一种标准化形式［14］。它指的是x和 y节点共同邻居的数量占x和 y节点邻居数量总和的比例。其中，公共近邻的数量越大，该相似性方法得到的分值越大。其数学公式如下:

3）Admic/Adar（AA）:这种方法最初是由Adamic和Adar提出的，它的主要目的是为了计算两个网页之间的相似性［15］。该方法的基本思想是度小的共同邻居节点的贡献大于度大的共同邻居节点。因此，AA指标根据共同邻居节点的度为每个节点赋予一个权重值，并且该权重等于该节点的度的对数分支一，即AA指标定义为

4）Preferential Attachment（PA）:这种相似性指标的前提假设是网络中两个节点建立新连接的概率与x节点的邻居数成正比［16］。从另一方面来说，拥有很多近邻的节点更有可能建立新的连接。纽曼［17］认为在合作网络中x节点和 y节点合作的可能性与x和y合作者的数量成正比。其数学公式如下:

4 提出的方法

在本次研究中，建立药物-疾病网络所需的数据从www.drugs.com中获得。这个网站包含的信息有针对疾病撰写的药物，偏爱这些药物的用户百分比、药物分类、怀孕类别等信息。药物-疾病网络上的节点代表了药物和疾病。在三种最普遍的治病药物之间建立连接。假设其他药物使用的百分比较低，并且对应的链路不包含在其中。表1展示了从该网站上接收数据的一个特定部分。

根据表1的疾病-药物关系，我们建立了一个以药物和疾病为节点集群的二分网络。图2是我们选择疾病和每种疾病使用率最高的前三种药物之间建立链路构造的网络范例图。本研究的目的是基于现有的药物-疾病关系，再通过相关的链路预测方法预测哪种药物可以被写成与某疾病对应的药物。

表1 使用数据的一部分

图2 药物-疾病网络范例

与传统方法不同，研究者们基于二分网络也提出了许多链路预测方法［18～20］。本文为疾病-药物二分网络中的链路预测提出了内部链路方法。在这种方法中，定义了一种称为内部链路的私有链路，并根据这些链路作出链路预测。二分网络被转化为一种加权的单模式网络后，表示原网络中内部链路的连接已被确定。在一个二分网络中，一个尚不存在连接的节点对被选择。如果这对节点之间建立的链路不造成投影图拓扑的改变，则被选节点之间的链路被称为内部链路。

本文提出的内部链路主要是指那些在二分网络中尚不存在连接的链路，并且满足当它们之间添加连接后，该二分网络的投影图不会发生变化。在我们的研究中，所有已知的链路都不能被称为内部链路。同时，为了确保重要的链路不被丢失且不必要的链路不被考虑，本文设定了一个阈值。其中，将那些权重值大于设定阀值的链路认定为内部链路。

5 实验结果

本文主要在药物-疾病网络中对提到的算法进行性能分析。另外，这类网络数据能够从www.drugs.com官网上获取。本文所选取的网络总共包含500条边。为了测试相关算法的预测准确性，本文随机选取其中100条边作为测试集，另外400条链路作为训练集。紧接着基于该疾病-药物网络，本文采用提到的算法进行链路预测。另外在尚未建立连边的节点间查找内部链路，同时将那些权重值高于预设阈值的链路定义为内部链路。紧接着，将已发现的内部链路按照权重值的大小进行排序，并选择权重排在前100的链路。本文为了对提到方法的预测效果进行对比分析，我们选择先前提到的四个基于相似性的方法进行疾病-药物二分网络的链路预测。计算出每个在训练集中不相连节点对的分数值。与先前研究类似，这个分数值代表的是节点x和y之间的相似性。预测分数值越高意味着当前缺失的链路在将来出现的可能性就越大。另外，为了进行预测效果的对比，本文将公共邻近（CN）、杰卡德系数（JC）、优先连接（PA）和Adamic/Adar（AA）等方法作为分数值的计算函数。将所有的预测链路按照预测分数值的大小进行降序排列，并且筛选出分数值较高的前100个链路作为预测结果。最后我们将本文提到的内部链路算法（IL）、共同邻居算法（CN）、杰卡德系数算法（JC）、优先连接算法（PA）和Adamic/Adar算法（AA）的预测链路与先前提取的测试集数据进行对比分析。同时，本文选择预测准确度、召回率和F-测度这三项指标作为性能评估准则。图3显示了五种不同方法在预测准确度、召回率和F-测度这三方面的性能比较结果。由图3可得，所提出的方法在三项指标中均体现出最高的预测效果。与其他四个基于相似性的链路预测算法相比，本文提出的算法具有更高的删除链路恢复效果。综上所述，根据所获得的预测结果，本文提出的算法具有较高的预测成功率，能够更方便地预测哪种药物可以用于治愈某种疾病。

6 结语

迄今为止，二分网络中的链路预测已经成为很多学术领域的研究焦点。不同领域的研究者加大了对这个课题的研究。近些年关于二分网络的链路预测大多集中在疾病-药物网络中。通常可以从网站（www.drugs.com）上获取药物推荐关系的网络数据集，该网络数据集是一个二分网络。与单一模式网络中的链路预测相比，二分网络中的预测链路是一个更难更复杂的任务。另外，基于单一模式网络的链路预测算法不能直接用于预测二分网络。因此，为了能够更好地实现二分网络的链路预测，首先需要将现有的二分网络转化为单一模式的网络。与其他经典算法相比，获得较高预测准确性的的内部链路方法能够较好地应用于疾病-药物网络中。同样，公共邻居、杰卡德系数（JC）、优先连接（PA）和Adamic/Adar（AA）等基于相似性的链路预测方法也已经被应用于二分网络中。当考虑到五种不同方法的预测效果，哪种药物可用来治疗哪种疾病已经取得了一定的突破。

图3 五种不同方法的效果对比