2020, Vol. 41
网络科学的研究不仅是在宏观上挖掘不同复杂网络之间的共性以及它们所遵循的普适性规律，从中观层面对网络群组结构和层次结构进行研究，而且在微观层面也提出节点的度及其度分布、最短距离等来表示网络的测度.然而根据已有的信息构建网络模型时，所得到的观测数据并不一定真实有效，或部分缺失、或掺杂错误数据等，有时还会因时间因素导致不能够获得潜在的网络信息，在仿真实验时得不到准确的数据和理想的研究结论.因此，链路预测成为网络信息挖掘的一个研究热点[1].
链路预测(link prediction)是通过对已知的网络拓扑结构进行分析，构建预测算法以发现网络中尚未存在连边的节点对之间产生连边的概率[2]，本质上是从网络链路的微观层面解释网络结构形成的原因.链路预测解决的是网络中缺失信息的还原与预测问题.所谓还原，指的是对网络中实际存在的但尚未被探测到的链路的发现，这种链路也被称为未知链接(unknown links)；所谓预测，指的是对网络中目前不存在但是未来很可能存在的链路的预测，这种链路也被称为未来链接(future links).
复杂网络中的链路预测算法主要是基于网络静态图，即网络规模以及节点间相互作用不变，然后分析其拓扑结构，推断网络的真实情况.然而现实网络是动态变化的，网络结构随时间推移不断变化，时态网络(temporal networks)[3]中节点间产生连边的时间信息对预测将来产生新链接的概率有重要的意义.Tang[4]将时态网络切片，提出了时态距离、可达性等概念研究时态网络.Paranjape等[5]定义δ-motif小子图作为分析时态网络的工具，大大提高了算法的时间效率.Lei等[6]提出了一种非线性模型(GCN-GAN)来解决加权的时态网络链路预测问题.该模型利用GCN计算各个时间切片的局部特征，然后将计算结果输入到LSTM模型，刻画网络的动态变化情况，再利用GAN生成预测结果.由于该方法的训练过程较为复杂，因此还需要进一步优化以实现大规模网络上的链路预测.Yasami等[7]利用随机多层网络模型解决网络中的链路缺失和未来链路的预测问题，并在仿真数据集和真实的DBLP数据集中表现出众.然而，算法仅限于有向网络，其他类型的网络中缺少通用性.此外，一些统计学方法，如整合移动自回归模型，即ARIMA[8]也可以用于时态网络链路预测研究，但受限于网络数据的平稳性检验，因此对于网络结构随时间变化较大的预测效果并不是十分理想.因此，时态网络链路预测问题还有很大的研究空间.
1 问题描述定义一个无权网络，G={V, E, T}，V={v1, v2, …, vn}是网络中所有节点的集合，T是网络的时间跨度.假设节点产生连边没有时间的延迟，即事件是在一瞬间发生的，那么可以用exyt=(vx, vy, t)表示在第t时刻节点vx和节点vy之间产生了连边，则E={e1, e2, …, et|t=1, 2, 3, …}是所有时态网络中的连边的集合.将网络按照时间间隔切分成m个时间切片，设每个时间窗口长度为L，则这一系列的网络状态可以描述为
|
(1) |
其中，Gt表示网络在t时刻的拓扑结构.
时态网络中的链路预测问题可以描述为：已知0~T时刻的网络拓扑结构变化情况，预测第T+1时刻的网络中节点的连边情况，简单来说，就是根据网络历史信息预测下一时刻网络中的连边情况.以数学形式表示为
|
(2) |
链路的存在与当前网络的拓扑结构有着密不可分的关系，如果在每一层的网络时间快照中计算节点对的相似性值，则会得到对应的一系列按时间顺序排列的节点对之间的相似性值，记为
|
(3) |
其中，St(vx, vy)表示在第t时刻的网络结构中节点对(vx, vy)的相似性值.在第t时刻，网络可以视为静态网络，则可以利用静态网络中的相似性指标计算相似性.
基于共同邻居的JC指标[9]、AA指标[10]等在实验中都有很好的表现，而且算法复杂度低且适用于大型网络.尽管表现良好，但是由于所使用的网络信息有限，因此预测准确度不够理想.该方法的另一个劣势在于，链路预测指标对于连边的刻画粒度比较粗糙.当网络中子图结构相似时，只利用共同邻居这一信息会忽略邻居节点间的连边关系这一重要信息，具有不同结构的节点对之间的相似性指标值区分度不大.图 1所示为具有相同共同邻居信息的网络A和B，有两对未连接的种子节点(A, a)和(B, b)都只有3个共同邻居节点.
|
图 1 具有相同共同邻居信息的网络示意图 Fig.1 Two networks with the same common neighbor information (a)—网络A; (b)—网络B. |
分别计算图 1所示网络中两个种子节点的连接概率，如果以Jaccard指标值表示Score分数值，那么在网络A中S(vA, va)=3/7，在网络B中S(vB, vb)=3/7.显然，JC指标赋予了它们相同的值，然而网络B中的两个种子节点显然比网络A中的两个种子节点有更紧密的关系，局部相似性更高.因此可知，所利用的局部信息不能轻易地区分这两对节点，也不足以完整地表示节点之间的相似性.
为了更加完备地利用网络的结构信息，本文利用邻居节点的局部聚类信息来表达链路的结构信息，这样的优势在于可以表达与目标链路具有相同结构的一些其他重要链路的结构信息.如何利用节点的聚集特性来描述种子节点之间产生连边的可能性，提出以下两种假设思路：
1) 假设种子节点间产生链接的概率(或分值)等于节点间的相似性值，而相似性可以用种子节点的共同邻居节点的聚类性表示.
2) 如果种子节点间产生链接的概率(或分值)等于节点间的相似性值，假设邻居节点的聚类性可以增强种子节点间原有的相似性.
在网络中，连边关系的局部聚集特性表现形式为所有的连边都比较紧密，聚集成一个簇，也可以称之为社区结构，而节点的局部聚集特性可以由聚类系数(clustering coefficient)[11]来表示.用数学公式表达，其定义如下：
|
(4) |
其中:Ci为节点的聚类系数；Ti是{ejk:vj, vk∈L(i), ejk∈E}中边的数目，节点vj, vk是节点vi的邻居节点，L(i)是节点vi的邻居节点集合，ejk是节点vi的邻居节点之间的连边；ki表示节点vi的度.节点的聚类系数反映了节点的邻居节点之间相互连接的概率.Ci取值在0与1之间，Ci越接近1，说明节点vi的邻居们抱成一团，节点vi的局部越紧密；Ci越接近0，说明节点vi的邻居比较稀疏，整个结构接近树状.
定义1(NCC相似性指标) 用SxyNCC表示节点为vx和vy的NCC(node clustering coefficient)相似性指标，定义为
|
(5) |
其中：Γ(z)表示节点vx与vy的共同邻居，z∈Γ(x)∩Γ(y)；kz是节点vz的度，节点vj是节点vz的邻居节点，其邻接矩阵记为aj.SxyNCC的值越大，说明两节点越相似，则它们之间越有可能产生连边.
定义2(NCCP相似性指标) 用SxyNCCP表示节点为vx和vy的NCCP(node clustering coefficient plus)相似性指标，定义为
|
(6) |
其中，|Θcn|表示对CN指标归一化处理，保证每个相似值平等对待，避免相似值过大，与事实相悖.由CN指标计算公式Sxy=|Γ(x)∩Γ(y)|，其中Γ(x)是节点vx的邻居节点的集合，z∈Γ(x)∩Γ(y).由此可知，CN指标的相似性分值S∈[0, ∞)，需要采用函数将S∈R(R为实数)映射到[0, 1]，本文采用具有较好归一化效果的Logistic函数.结合式(5)和式(6)，可以得到适用于时态网络的节点相似性计算公式：
|
(7) |
|
(8) |
其中：z表示节点对的邻居节点，z∈Γ(x)∩Γ(y)；t表示时刻，t=1表示第一个时刻，t=1, 2, …, m；StNCC(vx, vy)表示在第t时刻的网络结构中利用NCC指标计算节点对(vx, vy)的相似性值；StNCCP(vx, vy)表示在第t时刻的网络结构中利用NCCP指标计算节点对(vx, vy)的相似性值.
本文将网络时间快照计算得到的相似性值序列S={St(vx, vy)|t=1, 2, …, m}看作是一组动态数列，为了使模型简单易于计算，降低算法的计算复杂度，采用线性回归(linear regression，LR)预测模型[12]作为基本的回归预测模型，该模型计算效率高、性能良好，且模型的预测范围较小，预测值在[0, 1]之间.在文献[13]中作者将科学家合作网络划分成网络时间序列，然后利用有监督和无监督两种方法进行链路预测实验，结果表明在同等指标下，无监督预测的线性回归模型(LR)表现较好.
将前m-1层网络时间快照中节点对之间的相似性序列S={St(vx, vy)|t=1, 2, …, m-1}作为训练集数据，Sm(vx, vy)作为预测目标，建立与时间t之间的函数.假设
|
(9) |
结合式(7)和式(8)，利用一元线性回归分析法可以计算最佳参数a和b的值，最终得到在第t时刻的相似性计算公式为
|
(10) |
|
(11) |
本算法的核心思想是：将网络划分为多个时间快照，然后利用所有快照的历史信息来预测未来时刻的网络状态.时态网络链路预测算法过程为
输入：时态网络G(V, E, T)
输出：算法评价指标值
1) 读取网络G(V, E, T)，获取网络中所有可能出现的边.
2) 将时态网络划分为m个单层网络，构建一系列网络时间快照{Gt|t=1, 2, …, m}.
3) 根据式(7)、式(8)分别计算前m-1个时刻的节点对之间的相似性值，构建相似性值时间序列.
4) 选择对比度量指标[NCC, NCCP, CN, JC, AA, RA]，计算在其他相似性指标下的节点对的相似性值.
5) 根据得到的前m-1个时刻的分数值序列训练得到预测模型，采用式(10)、式(11)计算第m时刻节点间的相似性值.
6) 计算衡量算法的多个评价指标，如AUC(接受者操作特性曲线下方的面积)、精确度P、召回率R和F1指标等.
2.3 复杂度分析CN指标[14]的时间复杂度与节点的度有关，假设网络节点数为N, 整个网络的平均度为k，则计算共同邻居的时间复杂度为O(k)，则CN算法的时间复杂度为O(N2k).基于共同邻居的JC，AA，RA算法[15]与CN算法有类似的计算过程，因此它们有相同的时间复杂度.基于随机游走的SimRank算法[16]的时间复杂度为O(Nkl)，其中l是随机游走的步数.本文所提出的两种相似性度量方法NCC和NCCP需要计算节点的聚类系数，进行链路预测过程的时间复杂度为O(N2k).以上算法的时间复杂度比较如表 1所示.
|
表 1 经典算法的时间复杂度比较 Table 1 Time complexity comparison of theclassic algorithms |
由表 1可以看出，SR算法时间复杂度最低，是O(Nk)，因此效率最高.但由于其属于全局迭代算法，包含随机游走过程，因此实验结果并不稳定.本文提出算法的时间复杂度与其他同类算法相同，都是O(N2k)，虽然略高于SR算法，但因为其不存在随机过程，保证了结果的稳定性，因此具有更好的适用性.
3 实验分析 3.1 相似性度量方法对比实验本文选取不同领域的6个真实网络数据集:空手道俱乐部网络(Karate)、海豚社会关系网络(Dolphins)、911恐怖袭击网络(911data)、美国政治书籍网络(Polbooks)、美国大学生足球俱乐部(Footballs)和科学家合作网络(Scientists).6个真实网络数据集的统计特征见表 2.
|
|
表 2 网络的统计特征 Table 2 Statistic characteristics of networks |
本文采用随机抽样法划分网络数据集，测试集的比例默认设定为10%.选择传统的4个链路预测方法作为对比算法，分别是基于共同邻居的CN指标、Jaccard指标(JC)、AA指标、RA指标.循环重复实验多次，采用评价指标AUC的平均值作为算法的评估结果，如表 3所示.
|
|
表 3 不同网络数据集的AUC值 Table 3 AUC for different network datasets |
由表 3可知，对于Karate，Dolphins和911data这3个较小规模的网络，AA和RA指标具有较高的预测精确度，所提出的NCC和NCCP指标表现也比较优异.在Polbooks网络数据集中，NCCP和RA指标表现显著，且平均AUC值达到了0.873.在Scientists网络中AUC值达到了0.931，预测精确度高，NCCP指标预测效果最好.实验结果表明，网络邻居节点的聚类系数可以提高预测精确度.
为了更加清晰地展现NCC和NCCP指标的性能，做了以下显著性检验：本文采用皮尔逊相关系数进行检验，首先将NCC和NCCP指标与CN，JC，AA，RA指标进行对比计算，分别得到相应指标的假设机率(p)，然后把分别得到的p加和取平均得到NCC指标的p为0.000 6, NCCP指标的p为0.000 8，均远小于0.05.所以本实验效果较显著.
为了验证NCCP相似性指标对CN指标的增强效果，本文利用AUC值的对比情况来刻画，实验得到如表 4所示数据.由后两列计算结果可以看出，在添加邻居节点的聚类系数后构建的NCCP指标比CN指标预测效果有了普遍的提高，说明NCCP有一定的增强效果.
|
|
表 4 NCCP指标的增强效果 Table 4 Enhancement effect of NCCP index |
根据表 4结果可知，NCC指标与NCCP指标在整体上优于CN指标.
3.2 时态网络链路预测实验为了验证时态网络的链路预测算法的效果，本文使用Email-Eu-core temporal network时态网络数据集[5].该网络是根据欧洲某大型研究机构内部成员的电子邮件往来关系所构建的，对所有接收和发出的邮件信息内容作匿名处理.数据集不包含成员和其他地方地区的通信邮件，仅限于机构内部核心成员之间的通信，完整的数据集包含了来自4个部门成员之间的所有电子邮件，时间跨度为802天.本文所使用的网络数据集来自第三个部门(Dept3)，该数据集有89个节点、12 216条时态边，转化为静态网络则有1 506条边，时间跨度为802天.节点代表机构内部的部门成员，每条连边代表他们之间有一次邮件往来，数据集中每条数据(u, v, t)表示在时间t从用户u向用户v发送了电子邮件.
利用精确度P、召回率R和F1指标对预测结果进行评价，如果按天划分时态网络，那么每日的邮件数量即代表每层网络的连边数目，得到如表 5所示结果.
|
|
表 5 按日划分时态网络预测结果的评价指标值 Table 5 Evaluation indicators of temporal networkprediction results by dividing days |
由表 5可知，NCC指标的预测结果明显优于其他指标，说明基于邻居节点聚类的度量指标可以提高链路预测精确度.表 5中的P值都普遍偏低，究其原因，一方面时态网络数据集本身较小，另一方面网络划分的层数过多.按天划分时态网络导致每层的连边都特别稀疏，信息很零散，使所有指标的预测效果都偏低.
如果按月划分时态网络, 得到如表 6所示结果，NCC指标预测结果仍然优于其他指标，显示其有效性；且3个评价指标值比按天划分的网络的评价指标值都有所提高，说明时态网络链路预测的精确度还与网络划分的层数有关系，当网络划分过细时，网络分辨率很高，则预测效果不理想.
|
|
表 6 按月划分时态网络预测结果的评价指标值 Table 6 Evaluation indicators of temporal networkprediction results by dividing months |
选取目前公认的比较好的RA指标结合ARIMA模型作为基线算法，与本文提出的NCC指标结合线性回归模型进行比较，使用按月划分的网络数据集，随着层数的增加得到的AUC结果如图 2所示.
|
图 2 本文提出的方法与基线方法的对比 Fig.2 Comparison of the proposed methodwith the baseline method |
由图 2可看出，除了层数为4和13的时候本文提出的方法低于ARIMA_RA方法，其他情况均好于ARIMA_RA方法.
综合以上实验结果，本文所提出的NCC指标在对时态网络的链路进行预测时优于其他相似性指标，说明在考虑邻居节点的聚集情况后，更贴近真实网络中人们交流协作的过程，因此预测效果更好.并且，从以上两种划分形式可以看出，时态网络的预测效率还与时间的划分和时态网络模型有密切关系.
将网络划分为m个时间快照，然后利用所有快照的历史信息来预测未来时刻的网络状态是本文方法的研究思路.然而，在现实网络中，不同时刻网络状态对预测未来时刻网络状态所贡献的重要性是不同的，例如信息传播过程中，最近时间节点的信息最重要，历史时间中的过时信息的影响力不大.为了在本次时态网络链路预测中验证该思想，选择预测时刻(即第m层)的前n层网络信息进行预测.实验中n取1, 2, 4, 7, 9, 10，得到如表 7，表 8所示的预测结果.
|
|
表 7 预测结果精确度评价指标值 Table 7 Evaluation indicators of precision ofprediction results |
|
|
表 8 预测结果F1值评价指标值 Table 8 Evaluation indicators of F1-value results |
由表 7和表 8中数据可知，n=1时所有预测算法的精确度都相同；当n=2时，两个评价指标在所有算法中的值都开始减小，此时AA指标预测效果最好；当n逐渐增大时，两个评价指标都普遍呈减小的趋势，这说明越贴近预测时间的网络结构对最终结果的影响越大.而且，在n增大的过程中，本文所提出的NCC和NCCP指标对时态网络的链路预测效果逐渐开始显示其优越性.
4 结语本文将时态网络划分为一系列时间快照序列，利用所提出的度量指标计算每一层网络中的节点对相似性，构建节点对相似性时间序列，然后，结合时间序列回归模型预测节点对未来的相似性.实验结果表明，利用邻居节点的聚类信息可以提高预测精度，利用真实邮件网络数据集验证了所提出的指标的预测效果优越性，并且实验结果证明越接近预测时间的网络结构对预测结果影响越大.
| [1] |
Das K, Sinha S K.Identification and analysis of future user interactions using some link prediction methods in social networks[C]//Data, Engineering and Applications.Singapore: Springer, 2019: 83-94. http://link.springer.com/chapter/10.1007/978-981-13-6347-4_8
|
| [2] |
Liu Z, Zhang Q M, Lyu L Y, et al. Link prediction in complex networks:a local naïve Bayes model[J]. Europhysics Letters, 2011, 96(4): 48007. DOI:10.1209/0295-5075/96/48007 |
| [3] |
Holme P. Modern temporal network theory:a colloquium[J]. European Physical Journal B, 2015, 88(9): 1-30. |
| [4] |
Tang J K.Temporal network metrics and their application to real world networks[D].Cambridge: University of Cambridge, 2012. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.310.742
|
| [5] |
Paranjape A, Benson A R, Leskovec J.Motifs in temporal networks[C]//Proceedings of the 10th ACM International Conference on Web Search and Data Mining.New York, 2017: 601-610.
|
| [6] |
Lei K, Qin M, Bai B, et al.GCN-GAN: a non-linear temporal link prediction model for weighted dynamic networks[C]//IEEE INFOCOM 2019—IEEE Conference on Computer Communications.Paris, 2019: 388-396. http://www.researchgate.net/publication/330700427_GCN-GAN_A_Non-linear_Temporal_Link_Prediction_Model_for_Weighted_Dynamic_Networks
|
| [7] |
Yasami Y, Safaei F. A novel multilayer model for missing link prediction and future link forecasting in dynamic complex networks[J]. Physica A:Statistical Mechanics and Its Applications, 2018, 492: 2166-2197. DOI:10.1016/j.physa.2017.11.134 |
| [8] |
Hyndman R J, Athanasopoulos G. Forecasting:principles and practice[M]. Melbourne: OTexts, 2018.
|
| [9] |
Jaccard P. Etude comparative de la distribution florale dans une portion des Alpes et des Jura[J]. Bulletin del la Société Vaudoise des Sciences Naturelles, 1901, 37: 547-579. |
| [10] |
Adamic L A, Adar E. Friends and neighbors on the web[J]. Social Networks, 2003, 25(3): 211-230. DOI:10.1016/S0378-8733(03)00009-1 |
| [11] |
Holland P W, Leinhardt S. Transitivity in structural models of small groups[J]. Social Networks, 1977, 2(2): 49-66. |
| [12] |
Cohen J. Applied multiple regression/correlation analysis for the behavioral sciences[M]. Mahwah: Lawrence Erlbaum Associates, 2003.
|
| [13] |
Ricardo P, Soares S, Prudencio R.Time series based link prediction[C]//International Joint Conference on Neural Networks.Brisbane, 2012: 1-7. http://www.researchgate.net/publication/237091637_Time_Series_Based_Link_Prediction
|
| [14] |
Xu M, Yin Y C.A similarity index algorithm for link prediction[C]//2017 12th International Conference on Intelligent Systems and Knowledge Engineering(ISKE).Nanjing, 2017: 1-6. http://www.researchgate.net/publication/322516879_A_similarity_index_algorithm_for_link_prediction
|
| [15] |
Zhou T, Lyu L Y, Zhang Y C. Predicting missing links via local information[J]. European Physical Journal B, 2009, 71(4): 623-630. DOI:10.1140/epjb/e2009-00335-8 |
| [16] |
Jeh G, Widom J.SimRank: a measure of structural-context similarity[C]//Proceedings of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining—KDD′02.Edmonton: ACM Press, 2002: 538-543. http://www.researchgate.net/publication/2558295_SimRank_A_Measure_of_Structural-Context_Similarity
|