标题： 在平均聚类系数对无特征图基于拓扑的链接预测的影响 显示英文标题

标题： On the effect of the average clustering coefficient on topology-based link prediction in featureless graphs

摘要： 链接预测是图论中的一个基本问题，具有广泛的应用，包括推荐系统、社区检测和识别虚假连接。 虽然基于特征的方法可以实现高准确性，但它们对节点属性的依赖限制了其在无特征图中的适用性。 对于此类图，通常采用基于结构的方法，包括基于共同邻居和度数依赖的方法。 然而，这些方法的有效性取决于图的密度，在密集图中基于共同邻居的算法表现良好，而度数依赖的方法更适合稀疏或树状图。 尽管如此，文献中缺乏明确的准则来区分密集图和稀疏图。 本文引入平均聚类系数作为评估图密度的准则，以帮助选择链接预测算法。 为了解决实证分析数据集不足的问题，我们提出了一种基于Barabasi-Albert模型的新型图生成方法，该方法能够在保持结构异质性的前提下控制图的密度。 通过在合成和真实世界数据集上的全面实验，我们建立了平均聚类系数的经验边界，有助于选择有效的链接预测技术。 显示英文摘要

摘要： Link prediction is a fundamental problem in graph theory with diverse applications, including recommender systems, community detection, and identifying spurious connections. While feature-based methods achieve high accuracy, their reliance on node attributes limits their applicability in featureless graphs. For such graphs, structure-based approaches, including common neighbor-based and degree-dependent methods, are commonly employed. However, the effectiveness of these methods depends on graph density, with common neighbor-based algorithms performing well in dense graphs and degree-dependent methods being more suitable for sparse or tree-like graphs. Despite this, the literature lacks a clear criterion to distinguish between dense and sparse graphs. This paper introduces the average clustering coefficient as a criterion for assessing graph density to assist with the choice of link prediction algorithms. To address the scarcity of datasets for empirical analysis, we propose a novel graph generation method based on the Barabasi-Albert model, which enables controlled variation of graph density while preserving structural heterogeneity. Through comprehensive experiments on synthetic and real-world datasets, we establish an empirical boundary for the average clustering coefficient that facilitates the selection of effective link prediction techniques.