近年来，随着各领域学者对复杂网络理论及其应用的探究，复杂网络成为新兴研究热点。复杂网络科学是对大型复杂系统的结构与功能进行分析的有力工具，凭借其强大的建模分析能力与良好的可扩展性等优势，在现实生活中有着广泛的应用，如社会系统、生物系统、信息系统等都能在建模为复杂网络的基础上，再进行深入研究。

链路预测作为复杂网络科学中的一个研究课题，其本质是通过观测现有的链路和节点等已知信息，发现网络中缺失的链路并预测未来可能出现的链路，这对理解复杂网络的演化过程有着重要意义。同时，链路预测在不同行业中也有着广泛的应用。学者们相继在社交网络、引文分析网络、交通信息网络、生物网络、犯罪网络等方面开展了与之有关的研究工作。

传统的链路预测方法主要分为3大类：基于局部节点相似性的方法、基于路径的方法、基于随机游走的方法。其中，基于局部节点相似性的方法兼具简单和快捷的特点，主要基于如下假设：如果2个节点的相似性极高，那么它们之间拥有更多的邻居节点或者多条路径彼此更加接近，就更有可能产生连边。基于路径的方法是通过节点之间链接的路径进行计算的。基于随机游走的方法则是根据节点到其邻居节点的随机漫步转移的可能性来进行链路预测。

近年来，在基于随机游走的链路预测方法方面，许多学者开展了相关研究。García-Pérez等[1]针对异构、同构和广义异构网络中的链路预测问题，采用n链迭代算法和基于张量图的随机游走算法来度量广义异构网络中不同网络的节点相似度，提升了预测性能。Farashah等[2]提出应用于推荐系统的改进的链路预测算法，将空间聚类算法、深度神经网络算法、协同过滤模型相结合，提升了预测精度。Saxena等[3]提出了基于机器学习方法的链路预测模型，利用节点间的随机游走学习嵌入过程，并用节点的嵌入和社区信息来预测2个给定节点之间的链路，并通过实验证明了该模型的有效性。Zhou等[4]提出了改进的基于图嵌入的随机游走链路预测方法，利用网络结构的拓扑特性完成预测，提升了预测精度。这些方法在预测的准确度及速度方面都表现出良好的性能，然而大多为有监督的方法，需要提前对数据进行训练，所需成本较高。

在基于路径的方法方面，Yang等[5]提出了局部主路径度指标来预测两节点之间产生链路的概率，利用节点之间的局部路径的度分布和强度揭示节点间的相似信息，并验证了该指标的性能。Xu等[6]将路径熵应用于现实网络中的链路预测问题，考虑了节点对之间最短路径的信息熵，并提出了路径熵(PE)指标，实验证明了PE指标的良好性能。Chen等[7]考虑到链路生成机制的复杂性，联合利用显式关系和隐式关系，将二部链路预测转化为单部链路预测，提出了一种链路预测模型，提升了预测精度。这类方法时间复杂度极高，不适用于大规模网络。

考虑到复杂网络中，一些居于中心地位的节点可能有着更强的信息传播力，许多学者从这个角度出发提出了相应的链路预测方法。吕琳媛等[8]提出了结构一致性的概念，该概念能够反映网络固有链接的可预测性；除此之外，还提出了一种用于链路预测的结构扰动方法，该方法在准确性和鲁棒性方面都有所增强。陈嘉颖等[9]利用节点的度、介数、接近性等复杂网络结构信息对经典的链路预测指标进行了改进，提高了链路预测准确度。贾承丰等[10]利用word2vec模型和粒子群优化算法提取节点特征，并结合节点的度、聚类系数等特性提出了一种改进的链路预测方法，实验表明该方法在链路预测的稳定性和普适性方面有着较好表现。杨旭华等[11]提出了用二阶局部社团完成节点的高阶信息抽取，在降低算法复杂度的同时提升了链路预测算法的稳定性。

虽然上述方法在链路预测方面取得了较好效果，但却难以适用于大型网络，且普遍存在对节点信息利用不够全面的问题。基于此，本文提出了一种基于聚类系数和节点中心性(clustering coefficient and node centrality)的链路预测算法，简称CCNC。通过在6个真实数据集上进行实验，并与另外10种基于相似度的指标进行比较。实验结果表明，CCNC在链路预测方面有着更高的准确性，表现出更好的性能。

定义一个无权无向的简单网络G(V, E)，其中V为网络中节点的集合，E为节点间连边的集合。N为网络节点总数，全集U为由N(N-1)/2个节点对组成的所有边集合。链路预测问题本质上是利用合适的算法，对于网络中所有不存在连边的节点对计算两节点之间可能存在连边的概率。Sxy为节点x和y间的相关性度量，值的大小与两点之间链接的概率呈正相关。将Sxy从大到小排序，排名越靠前的节点对，它们之间存在连边的可能性越大。

本文使用到的符号的含义如表 1所示, 一些经典算法的Sxy定义如表 2所示。

CN和JAC考虑了共同邻居节点的数目对相似值的影响，AA和RA以共同邻居节点的度为切入点来解决预测问题。其中，AA认为度越大的共同邻居节点其贡献度越小；RA考虑到资源分配的影响，将节点对的共同邻居节点作为传输器，起到平均分配资源的作用。PA从被预测节点对的度来考虑。NDCC引入了聚类系数这一特征，将共同邻居节点的度和聚类系数相结合，从而提升了预测效果。TDNCC定义了二层节点度，并将其与聚类系数结合进行预测。L3则依赖节点对之间长度为3的路径，通过路径上节点的度指标考虑预测问题。CN2D是一种利用网络结构预测链路间关系的链路预测算法，除了利用节点的度分布外，还利用共同邻居来根据局部信息估计网络中2个节点之间存在链路的可能性。ERA结合了AA与RA的思想，通过增加小度节点的相似性，减少大度节点的相似度，提高预测性能。

在当今数据剧增的时代，许多规模庞大的社交网络亟须处理和分析，而基于局部节点相似性的预测算法因其省时高效而备受青睐，常用于大规模网络的处理。现有的CN、AA、RA、PA、JAC这些经典的算法，只考虑了共同邻居节点的度或个数；NDCC在此基础上考虑了聚类系数。然而这些算法都没有考虑节点中心性，事实上，节点中心性计算该节点到其他节点的最短路径的平均长度，能反映节点间的接近程度，在链路预测方面有着重要作用。为此，本文提出的CCNC算法将Sxy定义为

其中：τ(x)为节点x的所有邻居节点；CC(z)为节点z的聚类系数；Dz为节点z的度，PC(x)为节点x的节点中心性；α和β为可调节参数，α+β=1。

该算法是结合局部信息和节点在网络中的重要性进行预测，其核心思想是：首先，利用节点对的共同邻居节点的度稀释链路传递的价值；其次，利用共同邻居节点的聚类系数有效地传递链路价值；最后，在度和聚类系数的基础上，加入了节点对的节点中心性弥补了缺少种子节点的特性所带来其链路价值的不足。

图 1中，节点x和y是一对被预测的节点，节点c是它们的共同邻居节点，当节点c的度值越大，对节点x与y相连可能性的贡献能力越小。而图 2中，在图 1的基础上，节点c的邻居节点之间增加了连边。此时可以看出，虽然2个网络中节点c的度相同，但是节点x和y相连的可能性明显与图 1不一样。图 2中节点x与y相连的可能性比图 1中的网络要高，图 2中节点c对应的聚类系数也大于图 1中的。由此可以看出随着被预测节点对共同邻居节点的聚类系数的增大，其节点对相连的可能性就会越高。本文使用的聚类系数CC(z)计算如下：

其中Ez表示节点z的邻居节点之间直接相连的节点对的数目。

聚类系数提取了局部社团的密集度信息，利用了局部三角形结构信息，能够很好地估计出共同邻居节点的贡献度。由于节点z的度对连接的贡献会随着其值的增大而变小，即使度相同，聚类系数不同也会导致节点对连接的可能性不同，因此本文将CC(z)/Dz引入到CCNC算法中。

对于图 3来说，如果节点x与f相连，节点y与g相连，与图 2相比，节点之间的平均最短路径缩短，从而节点间的距离就会越近。相比图 2，图 3中从节点x通往节点y的路径多出2条，故节点x与y相连的可能性就会更高。经过以上分析可以看出，被预测节点与其他节点的平均最短路径对节点之间相连的可能性具有较为直接的影响。

节点中心性PC(x)考虑的就是节点x到其他所有节点的最短路径的平均距离。对于任意一个节点来说，该节点到其他节点的最短路径越近，它的节点中心性就越高，原本与其无链接的节点就越有可能与之相连。网络中的节点连通度越高，各节点间的连接也愈加紧密，节点之间的平均最短路径长度也会越短，还未相连的节点之间产生连边的可能性也越高。如果一对节点的节点中心性都很高，那么这对节点在网络中的中心地位就很高，从而它们之间更有可能产生链接。因此，节点对的节点中心性更能反映与其他节点之间相连的能力。

在网络G中，任意一个节点x到其他节点的平均最短路径距离表示为

其中：dxj表示节点x和j的最短路径距离。dx的值越小，节点x离网络中其他节点的距离就越近。节点x的节点中心性为

由于CCNC算法是以被预测节点对的共同邻居节点为基础，将节点对的节点中心性相乘，同样其邻居节点的度对连接的贡献会随着度的取值增大而变小，因此算法就在节点中心性乘积PC(x)PC(y) 的基础上除以度的取值Dz即$ \frac{{{\rm{PC}}\left( x \right){\rm{PC}}\left( y \right)}}{{{D_z}}}$。

综上所述，在共同邻居节点上，度和聚类系数能反映出共同邻居节点对链路预测所带来的价值；在节点对上，节点中心性能反映节点对的链接特征和在网络中的中心地位。CCNC算法对上述指标进行合理结合，更充分地利用网络的局部特征，提高了链路预测的准确性。

CN的时间复杂度与节点的度有关，假设网络节点数为n，边数为e，整个网络的平均度为k，则计算共同邻居的时间复杂度为o(k)，则CN算法的时间复杂度为o(n2k)。基于共同邻居的AA、RA算法与CN算法有类似的计算过程，因此它们具有相同的时间复杂度。PA和JAC两个算法较为简单，其时间复杂度为o(n2)。NDCC算法在计算所有节点对之间的相似度之前，首先计算网络中每个节点的聚类系数其时间复杂度为o(n2)，这部分计算过程在数据预处理阶段完成，因此其时间复杂度为o(n2k)。TDNCC和L3与二阶共同邻居有关，它们的时间复杂度为o(n2k)。CN2D算法需要计算共同邻居的度和个数，其时间复杂度为o(n2k)。ERA算法也是基于了AA算法的思想，因此时间复杂度为o(n2k)。CCNC算法需要计算每个节点的节点中心性和聚类系数，因此时间复杂度为o(n2(e+k))。

在算法的实验和评估阶段，对网络中所有的连边集合E，每次从中随机抽取90%的连边作为训练集ET，将剩余10%的连边作为测试集EP，来评判算法的精确度。显然，E=ET∪EP，ET∩EP=ø。

为了验证本文所提算法的有效性与准确性，本文采用了6个结构、大小各不相同的真实网络进行实验，分别为：爵士音乐家合作网络Jazz (https://deim.urv.cat/~alexandre.arenas/data/welcome. htm)、美国航空网络USAir(http://vlado.fmf.uni-lj.si/pub/networks/pajek/data/gphs.htm)、PolBooks网络POL (http://vlado.fmf.uni-lj.si/pub/networks/data/mix/mixed.htm)、Dolphins网络DOL (http://vlado.fmf.uni-lj.si/pub/networks/data/mix/mixed.htm)、食物链网络FWFW(http://vlado.fmf.unilj.si/pub/networks/data/bio/foodweb/foodweb.htm)和政治博客网络PB(http://vlado.fmf.uni-lj.si/pub/networks/data/mix/mixed.htm)。各数据集的拓扑特征如表 3所示，其中：M为网络的连边数；$ C = \frac{{\sum\limits_{i = 1}^N {{\rm{CC}}\left( i \right)} }}{N}$为网络平均聚类系数；$ K = \frac{{\sum\limits_{i \in \left\{ {1 \cdots N} \right\}} {{D_i}} }}{N}$为网络平均度；$ D = \frac{{2M}}{{N\left( {N - 1} \right)}}$为网络密度。

曲线下面积(AUC)[24]用来从整体上衡量算法的精确度，可以描述为在EP中随机选择一条存在的连边的概率高于随机从不存在边的集合E中选择一条不存在的连边的概率。如果独立重复比较T次，有T1次在EP中选择存在连边的概率大于不存在连边的概率，有T2次在EP中选择存在连边的概率等于不存在连边的概率，则AUC可以定义为

精确度(Precision)[25]用来预测前几个概率最大的预测结果的准确率。如果从EP和不存在边的集合E中随机抽取L条边，其中有l条边来自EP，则Precision定义为

对于小于200条链路的网络，本文选择L为10；对于小于1 000且大于或等于200条链路的网络，本文选择L为20；对于大于或等于1 000条链路的网络，本文取L为100。Precision的取值越高，则预测结果的精度也越高。

1) 对实验数据进行预处理，得到对应网络下每个节点的度、聚类系数和节点中心性；

2) 获取网络中每一节点对的一阶共同邻居节点，计算并保存它们的节点中心性；

3) 根据式(1)计算每一对节点之间的相似度，相似度越高则节点对相连可能性越大；

4) 在已有连边的集合中按比例随机抽取测试集，分别抽取50次，通过评价指标计算结果并求50次实验结果的平均值，衡量算法的优越性。

在CCNC算法中，α和β是2个可调节参数，并且α+β=1。为了确定α和β取何值时预测效果最佳，将α从0.1开始，每次增加0.1，一直取到0.9。对6个不同网络进行了链路预测，分别以AUC和Precision为评价指标，结果如图 4和5所示。

可以看出，当α取0.4、β取0.6时，CCNC算法整体预测效果最为精确。因此，本文采用α为0.4、β为0.6的CCNC算法，分别在上述6个网络中与其他常见的10个算法进行实验比较。同样使用了AUC和Precision指标进行评价对比，结果如表 4和5所示。

由表 4可知：在Jazz、USAir、POL、DOL和PB这5个网络中，CCNC算法与其他10个算法相比，都取得了AUC的最大值。特别是在POL和DOL网络中，CCNC的AUC比其他算法有着大幅度的提升。然而在密度很高的FWFW网络中，由于大部分节点的节点中心性都很高，并且相差不大，使得CCNC算法此时的预测结果没有达到最好的效果。整体来看CCNC算法的预测效果与其他10个算法相比是不错的。

由表 5可知：同样在Jazz、USAir、POL和DOL这4个网络中，CCNC的预测效果均优于其他算法。值得注意的是在PB网络中，JAC的Precision为0，原因是PB网络十分庞大而且网络密度很小，而JAC算法使用共同邻居节点数量的占比来进行预测，故效果很差。CCNC则在度指标和聚类系数的基础上，添加了节点中心性这一指标，在网络密度小的情况下，极大地提高了预测的准确性。

从实验结果可以看出，在6个不同大小的网络中，CCNC几乎都取得了AUC和Precision的最大值，预测结果优于其他算法。

本文提出了一种基于聚类系数和节点中心性的链路预测算法CCNC。与传统的基于局部节点的链路预测算法不同，该算法不仅引入了共同邻居节点的聚类系数和度这2个局部特征，而且还考虑了节点在整个网络中的中心地位，对相应节点对本身的特征进行分析，根据中心地位越高的节点越可能与其他节点相关联这一规律，引入了节点对的节点中心性特征来完成链路预测。在6个不同拓扑特征的网络中，与10种基于局部节点相似性的链路预测算法进行实验对比，本文算法取得了较好的效果。