马吴迪， 胡学钢， 何 伟

（合肥工业大学 计算机与信息学院，安徽 合肥 230009）

0 引 言

复杂网络是由数量巨大的节点和节点之间错综复杂的关系共同构成的网络结构。复杂网络中节点之间关系会随时间的流逝不断变化，这种动态特性，使网络整体的拓扑结构不断进行着演化。链路预测［1］是利用网络的拓扑结构来预测网络中节点对之间缺失［2－4］或可能产生的链接，是探索和分析网络结构演化的重要手段。如在社交网络中好友关系链路预测利用已存在的好友关系预测将来哪些用户会成为好友；会员参与互动话题的关系网络［5］通过目前会员参与话题的情况预测会员未来会参与哪些话题等。

根据目标网络中的节点类型，已有的复杂网络研究可以分为单分网络和二分网络2类。如果一个网络中包含2类节点，并且网络中的边只存在于不同类型的节点间，称为二分网络［6］，其抽象的拓扑图为二部图。现实世界中二分网络的普遍性，使得针对二分网络不同类型节点间的链路预测具有广泛的应用价值。单分网络中的链路预测算法往往是基于节点对的结构相似度来进行预测的［7］。二部图中产生链接的节点对属于不同类别，其邻居节点也分别属于不同类别，这使得单分网络的链路预测算法无法直接应用在二分网络中。

ILP［8］是一种有效的二分网络链路预测方法，但是由于其采用单向的投影策略即底部投影，容易导致信息丢失。本文在内部链路预测算法ILP的基础上，提出一种改进的链路预测算法ILPExt，采用底部和顶部双向投影策略，避免了丢失信息，从而提高了链路预测的精度。……