基于Motif 聚集系数与时序划分的高阶链接预测方法∗

康驻关,金福生,王国仁

(北京理工大学 计算机学院,北京 100081)

网络中的链接预测[1]指通过已知的网络结构信息,预测网络中尚未产生链接的节点间产生新链接的可能性.如果给定网络的当前状态,则链接预测将重点放在评估未来状态中存在边的可能性.可以理解为预测社交网络中两个人未来相互认识,计算机网络中的通信或生物网络中的生物分子相互作用的可能性.一个好的链接预测算法不仅可以用来挖掘网络中节点与结构间的关系,而且可以进一步帮助研究者探索网络结构的演化规律.目前,链接预测不仅在理论研究上取得了较好的成果,而且在一些特定的场景下也具有广泛的应用价值,例如预测社交网络中的友谊发现、推断基因与疾病之间的新关系、发现学术界的合作关系等[2,3,4]具体应用.常见的链接预测算法一次只需要预测一条边,然而在分析复杂网络结构演化时往往需要考虑所有的边,这些算法则不能进行很好的扩展.本文提出的高阶链接预测任务将探测更大的特征集,这也要求算法能够捕获数据集中更多潜在的可表示性特征.原则上,好的链接预测模型可以适用于网络中任意结构的预测,具体表示为预测网络中任意高阶的交互.毋庸置疑,链接预测是复杂的网络分析中一个有重要实用价值的研究问题,在交互事件发生之前对其进行预测,是深入探索网络结构演化的一项重要能力.

目……