题目：复杂网络链路挖掘和预测

现实世界中许多真实数据是由相互关联的个体组成，因此可以用复杂网络来描述和建模，其中节点和边分别表示个体及个体间的关系。链路，也即个体之间的关系，是复杂网络中最重要的信息载体，对链路的分析和挖掘是理解个体行为以及网络演化机制的基础。随着Internet和信息技术的发展，多种类型的真实复杂网络数据为开展链路挖掘和预测的研究工作提供了必要的条件，并取得了一系列重要进展。

链路挖掘主要是指利用数据挖掘的技术，为网络建立描述或预测模型，其主要任务包括节点排序、节点聚类和链路预测等。针对链路预测任务，已有来自不同领域的研究人员提出了很多的方法。然而，对于这些方法在不同数据获取方式和网络结构特性下的性能仍然缺乏系统的理解，此外，有向网络中互惠关系的分析和预测以及利用链路信息挖掘节点层次等方面尚有很多开放的问题。本文分别从链路预测指标在不同网络采样下的性能评估、网络结构特性对链路预测方法的影响、互惠关系分析和预测以及节点层次度量四个方面展开研究，论文主要贡献如下：

首先，论文对比和分析在不同采样方法获取的网络中，基于局部结构的链路预测相似性指标的性能差异。为了评价链路预测方法，已有工作中一般将网络中观测到的边随机地划分为训练集和测试集，在训练集数据上运行预测指标或方法对测试集中数据进行预测。通过采样理论可知，大部分复杂网络数据的获取方式并非完全随机的。因此，本文利用不同采样方法在真实复杂网络上生成训练和测试数据，对基于局部结构的链路预测相似性指标进行重新评估。实验结果表明，相似性指标在不同采样下的性能存在较大差异，且大多数指标在有偏采样中预测效果较差。与此同时，相似性指标在随机采样下往往会取得最好的预测效果，说明已有工作过高估计了链路预测指标的性能。

第二，论文以聚集系数为例，研究网络结构特性对已有链路预测方法的影响。基于网络结构和节点属性等信息，已有研究中提出了很多不同类型的链路预测方法。然而，这些链路预测方法在不同结构特性网络中的预测效果有何差异却少有关注。本文中，利用生成网络模型和边的随机重连方法，在不同结构特性的网络中对链路预测方法进行评估。真实网络和生成网络上的实验表明网络结构对链路预测方法的效果有着重要的影响，特别是随着网络聚集系数增加，链路预测方法可以获得更高的准确率。对比分析各种指标和方法在不同性质网络中的预测结果可以看出，基于局部结构的相似性指标在高聚集网络中有着更好的预测效果；而当网络聚集系数较低或密度较小时，基于路径的预测指标效果更好。通过预测指标在正负实例上取值分布的对比，本文对实验现象进行了进一步解释。

第三，论文在有向网络数据中分析互惠关系的性质并提出时序互惠预测框架。有向网络中对于互惠关系的研究有助于发现影响节点建立关系的关键因素，在理解节点行为和网络演化规律方面有着重要的意义。本文利用一个真实世界的信任网络数据，分析互惠关系中三种因素的影响，包括同质性、传递性和个性化。对于时序信息的进一步研究表明互惠关系中的时延服从幂率分布，而不同因素在经历短时间和长时间形成的互惠关系中发挥了不同的作用。经验分析的结果促使本文重新定义互惠预测问题，为每一个互惠申请在其建立以后的特定时间预测互惠关系是否会最终形成。此外，论文为分类算法执行基于时间窗口的训练集选择机制来解决概念漂移的问题。

最后，论文分析了有向网络中节点层次与网络结构和链路方向之间的关系。复杂网络中层次理论认为有向边是节点层次的一种外在体现，因而从观测到的网络结构中可以推断出隐含的节点层次信息。基于此设想，本文从形式上定义了层次度量问题并对问题求解的复杂度进行了分析。针对精确求解问题复杂度较高不适用于大规模网络的情况，本文提出了一种启发式层次度量算法。在真实有向网络上与已有方法进行的对比实验表明，本文算法可以取得与网络中有向链路最一致的节点层次，此外，有向边方向的预测实验也证明了算法在实际应用中的作用。