摘要
链接预测是图论中的一个基础性问题，广泛应用于推荐系统、社区发现以及虚假连接识别等领域。尽管基于特征的方法能够实现较高的预测精度，但其对节点属性的依赖性限制了其在无特征图（featureless graphs）中的适用性。对于此类图，通常采用基于结构的方法，如基于共同邻居和度依赖性的算法。然而，这些方法的有效性依赖于图的密度：基于共同邻居的算法在密集图中表现良好，而度依赖性方法则更适合稀疏或树状结构的图。然而，现有文献中尚缺乏明确的判别标准来区分密集图与稀疏图。本文提出以平均聚类系数（average clustering coefficient）作为评估图密度的指标，以辅助选择合适的链接预测算法。为解决实证分析中数据集稀缺的问题，本文提出一种基于Barabasi-Albert模型的新型图生成方法，可在保持图结构异质性的前提下，对图的密度进行可控调节。通过在合成数据集与真实世界数据集上的系统性实验，本文确立了平均聚类系数的一个经验性边界，为高效链接预测技术的选择提供了依据。