自然界中存在大量的复杂系统,这些系统都可通过网络加以描述。在自然生物科学、社会科学与工程技术等领域中的真实系统,都可以抽象化为结构清晰的网络模型进行表达。典型的网络由两类元素构成,分别是节点与节点间的连边,其中节点表示系统中的个体,节点间的连边表示个体间的特定关系。复杂网络中的链路预测非常具有研究意义和实际应用价值,也是颇受关注的数据挖掘领域的延伸课题之一,在社会网络、技术网络和生物网络等领域都有链路预测应用的实例。近几年来,错边识别问题也渐渐引起人们的注意,与链路预测问题一样,两者在数据处理等方面都发挥着至关重要的作用。它们的核心思想类似,都是根据已知的连边和节点属性去评估节点间连边存在的可能性。在实际应用中,人们往往不加区分地将针对于链路预测所提出来的算法直接应用于错边识别中,这样的做法未考虑算法在两个不同问题中所呈现的性能差异。本文重点研究了 18种算法应用于链路预测和错边识别时存在的性能差异与鲁棒性差异。本文分别从定性与定量的角度,对比了算法在链路预测与错边识别问题中的性能差异;模拟真实数据,考虑了网络中存在噪声连边的情况,对比算法的鲁棒性差异。所取得的主要科研成果如下:(1)本文对比了算法在链路预测和错边识别问题中性能的差异,并提出量化算法性能差异性的指标。现有的相似性算法都是针对链路预测所提出来的,而对于错边识别仍然缺乏行之有效的算法。实际应用中,人们往往直接将链路预测算法应用到错边识别中,而我们对算法在两个问题中的性能差异仍缺乏全面的认知。适用于链路预测的算法是否同样适用于错边识别?本文通过对比18个算法的链路预测AUCl和错边识别AUCs等指标的表现情况进而反映算法性能差异。实验结果表明,部分算法在链路预测中准确度较高,而在错边识别中AUCs值却较低,且算法在错边识别中性能更稳定。此外,量化性能差异性的指标τ(AUCl,AUCs)与网络的统计特征平均最短路径长度〈d〉间为正相关关系。(2)上述实验是在理想无噪的条件下进行的,而实际网络数据中往往存在着噪声,因此算法的鲁棒性也是衡量算法性能的重要指标。本文在考察算法准确度AUC的基础上,考虑了网络中存在噪声连边的情况,对比算法在链路预测与错边识别中的鲁棒性差异。网络中的噪声对算法预测或识别错误边准确度的影响是本文考察的重点。本文通过改变噪声比例r,探究算法准确度AUCl与AUCs的变化趋势,进而体现算法鲁棒性的差异。实验结果表明,算法在链路预测中对噪声较敏感,而在错边识别中表现出较强的鲁棒性。本文针对已知的网络数据较稀疏或其中存在噪声连边的情况,系统地对比了 18个相似性度量指标在链路预测与错边识别中的准确度与鲁棒性等性能的差异。实验结果表明,部分算法在链路预测中准确度较高,而在错边识别中准确度却较低。此外,本文根据算法AUCl与AUCs曲线变化行为将算法分为三类,对实际应用中算法的选择具有指导意义。本文关于算法在错边识别问题中性能的分析,有助于我们对错边识别问题建立更全面的认知。