超图环境下链路预测问题的探究

作者：佘美富; 王逸伟; 张建章; 詹秀秀; 刘闯^*

来源：西南大学学报(自然科学版), 2023, 45(08): 61-75.

DOI：10.13718/j.cnki.xdzk.2023.08.006

• 超图
• 链路预测
• 超链路预测
• 带重启的随机游走
• 有限集合
• 算法

超图作为图的扩展，可以表示多种实体间的关系，使得其表达能力大大强于图，该优势吸引人们的关注并日益成为研究热点.链路预测作为图数据挖掘中的常见任务，也在超图上扩展为超链路预测.超链路预测通过已知超边或节点的属性来估计新超边出现的可能性，但是由于超边内节点数量的任意性，其可能的超边由O(n2)暴增至O(2n),这大大增加了算法的复杂度.本文使用下采样方法以减少候选超边集的大小，将图上的带重启的随机游走算法扩展到超图上.还将图上的其他指标，如CN、 CE、 Jaccard等，扩展到超图进行比较.结果表明，带重启的随机游走指标在精确率和召回率上要明显优于其他指标，并且观察到演化良好的超图其超边内部的联系强度随节点数的增加而增加，由此可知超链路预测的主要难点在于对小尺寸超边的预测.

• 单位
  杭州师范大学