第14卷第1期 智能系统学报 Vol.14 No.I 2019年1月 CAAI Transactions on Intelligent Systems Jan.2019 D0:10.11992/tis.201810025 网络出版地址：http:/kns.cnki.net/kcms/detail/23.1538.TP.20190109.1748.006html 融合朴素贝叶斯方法的复杂网络链路预测 王润芳，陈增强2，刘忠信 (1.南开大学人工智能学院，天津300350,2.天津市智能机器人重点实验室，天津300350) 摘要：近来复杂网络成为了众多学者的研究热点。但真实网络中的连边信息并不完整，不利于网络的分析研 究，链路预测可以挖掘网络中的缺失连边，为网铬重构提供基本依据。本文认为网络中链接的产生不仅受外部 因素一共同邻居的影响，还受其自身因素的影响。其中，共同邻居的影响可以通过文献中的局部朴素贝叶斯 (LNB)模型量化，节点的影响则根据其自身的度量化。本文将两者综合考虑，提出了融合朴素贝叶斯(SNB)模 型，然后用共同邻居(CN)、Adamic--Adar(AA)和资源分配(RA)指标进行推广。在美国航空网(USAi)上的实验 结果表明，该方法的预测准确度比LNB和基准方法均有所提高，从而证明了该方法的有效性。 关键词：复杂网络；融合朴素贝叶斯模型；局部朴素贝叶斯模型；贝叶斯模型；链路预测：共同邻居；节点度；网 络重构 中图分类号：TP391 文献标志码：A文章编号：1673-4785(2019)01-0099-09 中文引用格式：王润芳，陈增强，刘忠信.融合朴素贝叶斯方法的复杂网络链路预测1.智能系统学报，2019,14(1)：99-107. 英文引用格式：WANG Runfang,CHEN Zengqiang,LIU Zhongxin..Link prediction in complex networks with syncretic naive Bayes methodsJ.CAAI transactions on intelligent systems,2019,14(1):99-107. Link prediction in complex networks with syncretic naive Bayes methods WANG Runfang',CHEN Zengqiang,LIU Zhongxin'2 (1.College of Artificial Intelligence,Nankai University,Tianjin 300350,China,2.Key Laboratory of Intelligent Robotics of Tianjin, Tianjin 300350,China) Abstract:Recently,complex networks have become a research hotspot.However,edge information in the real network is incomplete,which is not conducive to the analysis and research of the network.Link prediction can provide a funda- mental basis for network reconstruction by digging out the missing edges in the network.This paper demonstrates that the generation of links in the network is not only influenced by external factors(common neighbors)but also by its own factors.Among them,the influence of common neighbors can be quantified via the local naive Bayes(LNB)model in the literature,whereas the influence of nodes can be quantified depending on their degree.Therefore,a syncretic naive Bayes(SNB)model is proposed based on comprehensive consideration of the influence of the two abovementioned as- pects.The model is then extended to common neighbors,Adamic-Adar,and Resource Allocation methods.Finally,the experimental results on USAir show that the prediction accuracy of the method is higher than that of LNB and the benchmark method,which proves the effectiveness of the SNB model. Keywords:complex network;syncretic naive Bayes model;local naive Bayes model;Bayes model;link prediction; common neighbors;the degree of node;network reconstruction 现代社会中的信息呈爆炸式增长，使得社会互信息可以通过对应的复杂网络表示，其中，网 系统极具复杂性。研究表明，各种系统之间的交 络中的节点代表系统中的个体，连边代表个体之 收稿日期：2018-10-23.网络出版日期：2019-01-10 间的关系。网络科学是专门用于研究各种复杂 基金项目：国家自然科学基金项目(61573199,61573197).天津 市自然科学基金项目(I4 JCYBJC18700). 网络系统的定性和定量规律的一门交叉学科。 通信作者：陈增强.E-mail:chenzq@nankai.edu.cn 然而，由于隐私政策和个体设置等原因，实际获
DOI: 10.11992/tis.201810025 网络出版地址: http://kns.cnki.net/kcms/detail/23.1538.TP.20190109.1748.006.html 融合朴素贝叶斯方法的复杂网络链路预测 王润芳1 ，陈增强1,2，刘忠信1,2 （1. 南开大学 人工智能学院，天津 300350; 2. 天津市智能机器人重点实验室，天津 300350） 摘 要：近来复杂网络成为了众多学者的研究热点。但真实网络中的连边信息并不完整，不利于网络的分析研 究，链路预测可以挖掘网络中的缺失连边，为网络重构提供基本依据。本文认为网络中链接的产生不仅受外部 因素——共同邻居的影响，还受其自身因素的影响。其中，共同邻居的影响可以通过文献中的局部朴素贝叶斯 (LNB) 模型量化，节点的影响则根据其自身的度量化。本文将两者综合考虑，提出了融合朴素贝叶斯 (SNB) 模 型，然后用共同邻居 (CN)、Adamic-Adar(AA) 和资源分配 (RA) 指标进行推广。在美国航空网 (USAir) 上的实验 结果表明，该方法的预测准确度比 LNB 和基准方法均有所提高，从而证明了该方法的有效性。 关键词：复杂网络；融合朴素贝叶斯模型；局部朴素贝叶斯模型；贝叶斯模型；链路预测；共同邻居；节点度；网 络重构 中图分类号：TP391 文献标志码：A 文章编号：1673−4785(2019)01−0099−09 中文引用格式：王润芳, 陈增强, 刘忠信. 融合朴素贝叶斯方法的复杂网络链路预测[J]. 智能系统学报, 2019, 14(1): 99–107. 英文引用格式：WANG Runfang, CHEN Zengqiang, LIU Zhongxin. Link prediction in complex networks with syncretic naive Bayes methods[J]. CAAI transactions on intelligent systems, 2019, 14(1): 99–107. Link prediction in complex networks with syncretic naive Bayes methods WANG Runfang1 ，CHEN Zengqiang1,2 ，LIU Zhongxin1,2 (1. College of Artificial Intelligence, Nankai University, Tianjin 300350, China; 2. Key Laboratory of Intelligent Robotics of Tianjin, Tianjin 300350, China) Abstract: Recently, complex networks have become a research hotspot. However, edge information in the real network is incomplete, which is not conducive to the analysis and research of the network. Link prediction can provide a fundamental basis for network reconstruction by digging out the missing edges in the network. This paper demonstrates that the generation of links in the network is not only influenced by external factors (common neighbors) but also by its own factors. Among them, the influence of common neighbors can be quantified via the local naive Bayes (LNB) model in the literature, whereas the influence of nodes can be quantified depending on their degree. Therefore, a syncretic naive Bayes (SNB) model is proposed based on comprehensive consideration of the influence of the two abovementioned aspects. The model is then extended to common neighbors, Adamic-Adar, and Resource Allocation methods. Finally, the experimental results on USAir show that the prediction accuracy of the method is higher than that of LNB and the benchmark method, which proves the effectiveness of the SNB model. Keywords: complex network; syncretic naive Bayes model; local naive Bayes model; Bayes model; link prediction; common neighbors; the degree of node; network reconstruction 现代社会中的信息呈爆炸式增长，使得社会 系统极具复杂性。研究表明，各种系统之间的交 互信息可以通过对应的复杂网络表示，其中，网 络中的节点代表系统中的个体，连边代表个体之 间的关系[1]。网络科学是专门用于研究各种复杂 网络系统的定性和定量规律的一门交叉学科[2]。 然而，由于隐私政策和个体设置等原因，实际获 收稿日期：2018−10−23. 网络出版日期：2019−01−10. 基金项目：国家自然科学基金项目 (61573199, 61573197). 天津 市自然科学基金项目 (14JCYBJC18700). 通信作者：陈增强. E-mail: chenzq@nankai.edu.cn. 第 14 卷第 1 期 智 能 系 统 学 报 Vol.14 No.1 2019 年 1 月 CAAI Transactions on Intelligent Systems Jan. 2019
·100· 智能系统学报 第14卷 取的网络连边信息往往是不完整的，加大了网络 率和有效性等方面均优于基准方法。然而，上述 科学研究的难度。链路预测能够对缺失信息进行 方法仅考虑了共同邻居的作用，忽略了节点自身 还原和预测，是网络科学研究的有力辅助工具， 的影响。闫玲玲等提出了一种基于度和聚类系 具有重要的理论研究和实际应用价值。一方面， 数的新指标，对中国航空网络中的节点重要性进 链路预测可以帮助人们理解各种复杂网络的演化 行分析。Pujari等1认为节点对的每个属性代表 机制，为不同演化模型的优劣比较提供统一平 不同信息，可以将所有属性对应特征进行加权整 台；另一方面，链路预测的结果可以指导生物网 合以提高预测性能。Li等剧以新浪微博为研究对 络中的实验，降低实验成本并提高准确率，还可 象，根据其自身特点提出了包含用户临近特征 以建立网络中的推荐系统。 属性特征和拓扑特征的特征集用于预测。但这 网络中的链路预测，是指如何根据网络中已 些方法仅考虑了节点自身作用，忽略了共同邻居 知的节点和结构信息，预测网络中尚未产生连边 的影响。 的两个节点之间产生连接的可能性，包括未来 为解决上述问题，本文基于局部朴素贝叶斯 链接和未知链接的预测，常用的方法可分为两大 (LNB)模型提出了融合朴素贝叶斯(syncretic na- 类：基于相似性的方法和智能方法。 ive Bayes,.SNB)模型。本文的主要贡献如下。 基于相似性方法的一个基本假设是：两个节 1)认为链接的产生受到内部和外部两方面因素的 点越相似，在未来连接的可能性越大，而节点的 影响。其中，节点对自身特点属于内部影响，可 相似程度可通过相似性指标量化，即根据相似性 以通过节点度量化；共同邻居的作用属于外部影 指标计算相似性得分，得分越高，两个节点越相 响，可以通过LNB模型量化，将两者结合提出一 似。已有相似性指标可分为三大类：基于节点局 个新模型。2)模型的优劣不仅体现在其自身的预 部信息的方法，如共同邻居(CN)I、Adamic- 测精确度上，还体现在它与其他思想的融合效果 Adar(AA)⑧I和资源分配(RA)指标等；基于全局路 上，后者可以通过其在基准指标推广后的预测精 径的方法，如Katz和局部路径(LP)例等；基于随 确度定性描述。因此，文中将SNB推广到CN、 机游走的方法o。 AA和RA形式，说明其具有普适性。 上述方法中，基于节点局部信息的方法运算 近些年，智能方法受到广泛关注。已有研究 复杂度最低，且预测准确度较高，因此常被用作 包括支持向量机、BP神经网络2)、3层隐含的 基准指标。吕琳媛等对几种基准指标的研究发 贝叶斯(3-HBP)链路预测模型221、最大熵模型2 现，无论是否加权，RA均表现最好，且无权指标 以及可变贝叶斯概率矩阵分解模型等。与直接 的性能均优于加权指标。由此得出：复杂网络中 给节点对分配相似性得分不同.这些方法都是通 的弱连接不容忽视，强调弱连接的贡献可以极大 过学习已知知识建立模型进行预测，是将来的研 提高预测准确度。此外，作者意识到这些指标存 究重点。 在共同缺点，即认为所有共同邻居对于节点对的 贡献相同。为此，Lu等假设每个共同邻居的贡 1预备知识 献不同，有些促进链接的产生，有些则抑制，因此 共同邻居数量相同的节点对产生链接的概率可能 本部分首先给出了链路预测的概念，然后介 不同。然后将朴素贝叶斯理论应用到链路预测 绍了本文的理论基础一朴素贝叶斯理论，接着 中，提出了局部朴素贝叶斯(LNB)模型。最近， 阐述了一些常用的基准指标，最后简要介绍了局 Valverde-.Rebaza等u认为每个用户可能同时属于 部朴素贝叶斯(LNB)链路预测模型。 多个社团，且扮演角色不同，预测时应充分考虑 1.1问题描述 用户所属的所有社团信息。基于此思想，Val- 一个无权无向的网络图可表示为GVE),其 verde-Rebaza在文献[l4]中提出了基于重叠组的 中V代表节点集，E≤V×V代表节点之间的连边 朴素贝叶斯(GNB)链路预测模型。此外，考虑到 集合，本文不考虑自环和重复边。假设有两个节 共同邻居之间并非完全相互独立，文献[15]使用 点x∈V,y∈V,则e=(xy)∈E表示节点x和y之 互信息量化共同邻居的相关性，对LNB进行推 间存在链接，而=x,y》生E表示节点x和y之 广，提出了广义的树增广朴素贝叶斯(TAN)概率 间不存在链接。网络中所有可能连边的集合为 模型，并扩展到了CN、AA和RA指标，在运行效 A则M=Mx-D。因此，不存在的连边集合 2
取的网络连边信息往往是不完整的，加大了网络 科学研究的难度。链路预测能够对缺失信息进行 还原和预测，是网络科学研究的有力辅助工具， 具有重要的理论研究和实际应用价值。一方面， 链路预测可以帮助人们理解各种复杂网络的演化 机制[3-4] ，为不同演化模型的优劣比较提供统一平 台；另一方面，链路预测的结果可以指导生物网 络中的实验，降低实验成本并提高准确率，还可 以建立网络中的推荐系统[5]。 网络中的链路预测，是指如何根据网络中已 知的节点和结构信息，预测网络中尚未产生连边 的两个节点之间产生连接的可能性[6] ，包括未来 链接和未知链接的预测，常用的方法可分为两大 类：基于相似性的方法和智能方法。 基于相似性方法的一个基本假设是：两个节 点越相似，在未来连接的可能性越大，而节点的 相似程度可通过相似性指标量化，即根据相似性 指标计算相似性得分，得分越高，两个节点越相 似。已有相似性指标可分为三大类：基于节点局 部信息的方法，如共同邻居 (CN)[ 7 ] 、 AdamicAdar(AA)[8]和资源分配 (RA)[9]指标等；基于全局路 径的方法，如 Katz[7]和局部路径 (LP)[9]等；基于随 机游走的方法[10]。 上述方法中，基于节点局部信息的方法运算 复杂度最低，且预测准确度较高，因此常被用作 基准指标。吕琳媛等[11]对几种基准指标的研究发 现，无论是否加权，RA 均表现最好，且无权指标 的性能均优于加权指标。由此得出：复杂网络中 的弱连接不容忽视，强调弱连接的贡献可以极大 提高预测准确度。此外，作者意识到这些指标存 在共同缺点，即认为所有共同邻居对于节点对的 贡献相同。为此，Liu 等 [12]假设每个共同邻居的贡 献不同，有些促进链接的产生，有些则抑制，因此 共同邻居数量相同的节点对产生链接的概率可能 不同。然后将朴素贝叶斯理论应用到链路预测 中，提出了局部朴素贝叶斯 (LNB) 模型。最近， Valverde-Rebaza 等 [13]认为每个用户可能同时属于 多个社团，且扮演角色不同，预测时应充分考虑 用户所属的所有社团信息。基于此思想，Valverde-Rebaza 在文献[14]中提出了基于重叠组的 朴素贝叶斯 (GNB) 链路预测模型。此外，考虑到 共同邻居之间并非完全相互独立，文献[15]使用 互信息量化共同邻居的相关性，对 LNB 进行推 广，提出了广义的树增广朴素贝叶斯 (TAN) 概率 模型，并扩展到了 CN、AA 和 RA 指标，在运行效 率和有效性等方面均优于基准方法。然而，上述 方法仅考虑了共同邻居的作用，忽略了节点自身 的影响。闫玲玲等[16]提出了一种基于度和聚类系 数的新指标，对中国航空网络中的节点重要性进 行分析。Pujari 等 [17]认为节点对的每个属性代表 不同信息，可以将所有属性对应特征进行加权整 合以提高预测性能。Li 等 [18]以新浪微博为研究对 象，根据其自身特点提出了包含用户临近特征、 属性特征和拓扑特征的特征集用于预测。但这 些方法仅考虑了节点自身作用，忽略了共同邻居 的影响。 为解决上述问题，本文基于局部朴素贝叶斯 (LNB) 模型提出了融合朴素贝叶斯 (syncretic naive Bayes，SNB) 模型。本文的主要贡献如下。 1) 认为链接的产生受到内部和外部两方面因素的 影响。其中，节点对自身特点属于内部影响，可 以通过节点度量化；共同邻居的作用属于外部影 响，可以通过 LNB 模型量化，将两者结合提出一 个新模型。2) 模型的优劣不仅体现在其自身的预 测精确度上，还体现在它与其他思想的融合效果 上，后者可以通过其在基准指标推广后的预测精 确度定性描述。因此，文中将 SNB 推广到 CN、 AA 和 RA 形式，说明其具有普适性。 近些年，智能方法受到广泛关注。已有研究 包括支持向量机[19] 、BP 神经网络[20-21] 、3 层隐含的 贝叶斯 (3-HBP) 链路预测模型[22] 、最大熵模型[23] 以及可变贝叶斯概率矩阵分解模型[24]等。与直接 给节点对分配相似性得分不同，这些方法都是通 过学习已知知识建立模型进行预测，是将来的研 究重点。 1 预备知识 本部分首先给出了链路预测的概念，然后介 绍了本文的理论基础——朴素贝叶斯理论，接着 阐述了一些常用的基准指标，最后简要介绍了局 部朴素贝叶斯 (LNB) 链路预测模型。 1.1 问题描述 G(V,E) V E ⊆ V ×V x ⊆ V, y ⊆ V exy = ⟨x, y⟩ ∈ E x y exy = ⟨x, y⟩ < E x y A |A| = |V| ×(|V| −1) 2 一个无权无向的网络图可表示为 ，其 中 代表节点集， 代表节点之间的连边 集合，本文不考虑自环和重复边。假设有两个节 点 ，则 表示节点 和 之 间存在链接，而 表示节点 和 之 间不存在链接。网络中所有可能连边的集合为 ，则 。因此，不存在的连边集合 ·100· 智 能 系 统 学 报 第 14 卷
第1期 王润芳，等：融合朴素贝叶斯方法的复杂网络链路预测 ·101· 为N=A-E。文中N(x)代表节点x的邻居集合， 它们的共同邻居集合，即节点x和y在未来连接 则节点x和节点y的共同邻居集合可以记为N(x,y)= 和未连接的概率为后验概率P(elN(x,y)和 N(x)ON() P(eN(x,y),根据贝叶斯理论有 通常，按照某种比例，将网络中所有连边划 P(e).P(N(x.y)le) P(enN(x,y))= (3) 分为训练集E和测试集E。其中，E代表已知 P(N(x,y)) 连边集合，EP代表缺失连边集合，链路预测的任 P(eW(x.y)=P(s)P(N(.) (4) P(N(x,y)) 务是根据E建立模型预测出E中的连边。 其中，ew,eg是类变量C的两个取值，分别表示节 12朴素贝叶斯理论 点x和y连接与未连接，由于各个共同邻居之间 朴素贝叶斯分类器简单易懂，受到了众多学 相互独立，则： 者的青睐。假设C为类变量，X=(X1,X2,…,X)代 P(N(x,y)le)= (5) 表n维特征向量。根据贝叶斯理论，已知特征 =EN(r.y) 向量X求类变量C取某值的概率为后验概率 P(N(x,y))= Peea (6) P(CX): EN(r.y) P(CIX)=P(CIX1,X2,....X)= 将式(5)和式(6)分别代入式(3)和式(4)，然 PC)P(X,X2,…,XlC) (1) 后两式相除，得： P(X,X2,…,Xn) P(es) P(es) P(e) (7) 朴素贝叶斯的基本假设是：当类变量C取值 P(ex) EN(xy) P(ex) :EN(t.y) P(es) 固定时，各特征变量X,(=1,2,…,m)之间相互独 constant value role of node: 立，即 式中P(e人、P(e分别表示节点x和y连接与未 连接的先验概率： PX1,X2,…,XIC)= P(XC) (2) ET P(ex)= 将式(2)代入式(1)可得 4 P(C)·ΠPXIC) P(es)=Al-IE'I A P(CIX)= PX1,X2,…,X) 显然，Pe小Pe均为常数，则s=eg= 1.3基准指标 1)共同邻居指标(CN) E也为常数，表示网络中存在边与不存在边 IAI-IETI 通常认为，共同邻居越多，节点对越相似。 的比值，可以忽略。而P(e)表示节点：的聚类 CN指标通过直接计算共同邻居数目来量化节点 系数： 对的相似性，定义如下： 2T(z) IN(x)nNO)=IN(.) Pel9）=c:=kk- (8) P(e)=1-c (9) 2)Adamic-Adar指标(AA) 式中T代表节点：的k个邻居之间真实存在的 AA指标以CN指标为基础，认为度越大的 共同邻居对于节点对的贡献越小。因此，可以通过 边数。令足=号表示：的邻居之间连接与未 惩罚度大的邻居节点提高预测准确度，其定义为 连接的比值，R值越大，说明节点z的邻居之间更 =1 倾向于相互连接，即节点z的促进作用越强。不 m logk. 同节点的R值一般不同，因此称R为节点：的角 式中k表示节点的度。 色函数。将式(8)、式(9)代入式(7)，等式两边取 3)资源分配指标(RA) 对数得： 受到资源分配动力学的启发，RA指标根据 sBaN=∑ogs+logR) 资源在节点间的传递情况，结合惩罚大度节点的 二EV{太) 思想，定义了节点对的相似性： 将其推广可得： =1 BAA=】 smon. log (logs +log.) 1.4LNB链路预侧模型 LNB模型假设节点x和y是否连接取决于 2,元0ogs+1og)
N = A− E N(x) x x y N(x, y) = N(x)∩N(y) 为 。文中 代表节点 的邻居集合， 则节点 和节点 的共同邻居集合可以记为 。 r E T E P E T E P E T E P 通常，按照某种比例 将网络中所有连边划 分为训练集 和测试集 。其中， 代表已知 连边集合， 代表缺失连边集合，链路预测的任 务是根据 建立模型预测出 中的连边。 1.2 朴素贝叶斯理论 C X = (X1,X2,··· ,Xn) n X C P(C|X) 朴素贝叶斯分类器简单易懂，受到了众多学 者的青睐。假设 为类变量， 代 表 维特征向量。根据贝叶斯理论，已知特征 向量 求类变量 取某值的概率为后验概率 ： P(C|X) = P(C|X1,X2,··· ,Xn) = P(C)· P(X1,X2,··· ,Xn|C) P(X1,X2,··· ,Xn) (1) C Xi(i = 1,2,··· ,n) 朴素贝叶斯的基本假设是：当类变量 取值 固定时，各特征变量 之间相互独 立，即 P(X1 ,X2 ,··· ,Xn |C) = ∏n i=1 P(Xi |C) (2) 将式 (2) 代入式 (1) 可得 P(C|X) = P(C)· ∏n i=1 P(Xi |C) P(X1,X2,··· ,Xn) 1.3 基准指标 1) 共同邻居指标 (CN) 通常认为，共同邻居越多，节点对越相似。 CN 指标通过直接计算共同邻居数目来量化节点 对的相似性[7] ，定义如下： s CN xy = |N(x)∩N(y)| = |N(x, y)| 2) Adamic-Adar 指标 (AA) AA 指标[8]以 CN 指标为基础，认为度越大的 共同邻居对于节点对的贡献越小。因此，可以通过 惩罚度大的邻居节点提高预测准确度，其定义为 s AA xy = ∑ z∈N(x,y) 1 logkz 式中 kz 表示节点 z 的度。 3) 资源分配指标 (RA) 受到资源分配动力学的启发，RA 指标[9]根据 资源在节点间的传递情况，结合惩罚大度节点的 思想，定义了节点对的相似性： s RA xy = ∑ z∈N(x,y) 1 kz 1.4 LNB 链路预测模型 LNB 模型 x y [11]假设节点 和 是否连接取决于 x y P(exy|N(x, y)) P(exy|N(x, y)) 它们的共同邻居集合，即节点 和 在未来连接 和未连接的概率为后验概率 和 ，根据贝叶斯理论有 P(exy|N(x, y)) = P(exy)· P(N(x, y)|exy) P(N(x, y)) (3) P(exy|N(x, y)) = P(exy)· P(N(x, y)|exy) P(N(x, y)) (4) exy, exy C x y 其中， 是类变量 的两个取值，分别表示节 点 和 连接与未连接，由于各个共同邻居之间 相互独立，则： P(N(x, y)|exy) = ∏ z∈N(x,y) P(z|exy) (5) P(N(x, y)|exy) = ∏ z∈N(x,y) P(z|exy) (6) 将式 (5) 和式 (6) 分别代入式 (3) 和式 (4)，然 后两式相除，得： r LNBCN xy = P(exy) P(exy) · ∏ z∈N(x,y) P(exy) P(exy) | {z } constant value · ∏ z∈N(x,y) P(exy|z) P(exy|z) | {z } role of node z (7) 式中 P(exy)、P(exy) 分别表示节点 x 和 y 连接与未 连接的先验概率： P(exy) = |E T | |A| P(exy) = |A| − |E T | |A| P(exy)、P(exy) s −1 = P(exy) P(exy) = |E T | |A| − |ET | P(exy|z) 显然， 均为常数，则 也为常数，表示网络中存在边与不存在边 的比值，可以忽略。而 表示节点 z 的聚类 系数： P(exy|z) = cz = 2T(z) kz ·(kz −1) (8) P(exy|z) = 1−cz (9) T(z) z kz Rz = P(exy|z) P(exy|z) Rz Rz Rz 式中 代表节点 的 个邻居之间真实存在的 边数。令 表示 z 的邻居之间连接与未 连接的比值， 值越大，说明节点 z 的邻居之间更 倾向于相互连接，即节点 z 的促进作用越强。不 同节点的 值一般不同，因此称 为节点 z 的角 色函数。将式 (8)、式 (9) 代入式 (7)，等式两边取 对数得： s LNBCN xy = ∑ z∈N(x,y) (log s+logRz) 将其推广可得： s LNBAA xy = ∑ z∈N(x,y) 1 logkz (log s+logRz) s LNBRA xy = ∑ z∈N(x,y) 1 kz (log s+logRz) 第 1 期 王润芳，等：融合朴素贝叶斯方法的复杂网络链路预测 ·101·
·102· 智能系统学报 第14卷 2融合朴素贝叶斯链路预测模型 居间链接的产生有促进作用；节点c和节点d的 共同邻居有3个，但每个共同邻居的邻居之间基 在介绍SNB模型之前，首先考虑一个问题， 本没有链接，说明这些共同邻居对其邻居间链接 节点之间链接的产生到底与什么因素有关？图1 的产生有抑制作用。综上，节点a和b在未来产 给出了3种不同的思路。 生链接的可能性更大。 实际生活中，节点间链接的产生不仅受到共 个个 同邻居的影响，与其自身的活跃程度也是密不可 分的。在共同邻居数目相等的条件下，节点倾向 于和更活跃的个体产生链接；当共同邻居数目不 。共同邻居 等时，如图1(c)中，节点a和b的共同邻居少且均 ·待预测节点对 为促进作用，但其自身的度比较小；节点c与d (a)CNs结构示意 的共同邻居多且均为抑制作用，但其自身的度比 较大。共同邻居与节点自身究竞谁的作用更大， 需要具体计算，这便是SNB模型的核心思想。 本文认为，节点x和y之间链接的产生受到 内部和外部因素的影响。其中，共同邻居的作用 属于外部影响，根据LNB的相关知识，每个共同 。共同邻居 邻居的作用不尽相同，或促进或抑制。另一方 ·待预测节点对 面，链接的产生与节点x和y自身的活跃程度密 (b)LNBs结构示意 切相关，影响大小可以通过节点的度进行量化。 这意味着，度相同的两对节点产生链接的概率会 因共同邻居贡献不同而不同，受共同邻居作用相 同的两对节点也会因其自身的度不同而产生差 异。基于此思想，本文综合考虑了共同邻居与节 点对自身的作用，提出了融合朴素贝叶斯(SNB) 链路预测模型。 。共同邻居 在SNB模型下，节点x和y产生链接的后验 ·待预测节点对 概率为： (c)SNBs结构示意 P(eIN(x,y),k.k,)= 图1CNs、LNBs、SNBs结构示意 P(eg).P(N(x,y),k:,kylex) (10) Fig.1 Structure schematic diagram of CNs,LNBs and SNBs P(N(x,y),kx.ky) 最简单的一种思路是：两节点的共同邻居数 P(@slN(x.y).kx.k,)= (11) 目越多，它们的兴趣属性等越接近，未来越有可 P(e)·PN(x,y,kx,ke) P(N(x,y),kx,k) 能产生链接，这便是图l(a)中CNs指标的主要思 由概率论相关知识，可得： 想。因此，图中节点c和d的共同邻居数目多， P(N(x.y).k.kle)= 它们产生链接的可能性大于节点a和b。 在CNs的基础上，有学者指出，每个共同邻 P(N(x.y)le)P(kleN(x.y))- (12) 居扮演角色不同，对于节点对产生链接的贡献不 P(kleN(x,y).k,) 同，因此不能通过简单计算共同邻居的数目得到 P(N(x,y),k:.kle)= 相似性，而应该累加共同邻居的贡献以得到最终 P(N(x,y))P(ke N(x,y))- (13) 的相似性分数。按照此思想，图1(b)中节点a和 P(kles.N(x,y).k,) b的共同邻居只有2个，但每个共同邻居的邻居 将式(12)和式(13)分别代入式(10)和式(11)， 之间大多存在链接，说明这两个共同邻居对其邻 可得
2 融合朴素贝叶斯链路预测模型 在介绍 SNB 模型之前，首先考虑一个问题， 节点之间链接的产生到底与什么因素有关？图 1 给出了 3 种不同的思路。 a b ? ? c d 共同邻居 待预测节点对 (a) CNs 结构示意 a b c d c ? ? 共同邻居 待预测节点对 (b) LNBs 结构示意 a b ? c ? d 共同邻居 待预测节点对 (c) SNBs 结构示意 图 1 CNs、LNBs、SNBs 结构示意 Fig. 1 Structure schematic diagram of CNs, LNBs and SNBs c d a b 最简单的一种思路是：两节点的共同邻居数 目越多，它们的兴趣属性等越接近，未来越有可 能产生链接，这便是图 1(a) 中 CNs 指标的主要思 想。因此，图中节点 和 的共同邻居数目多， 它们产生链接的可能性大于节点 和 。 a b 在 CNs 的基础上，有学者指出，每个共同邻 居扮演角色不同，对于节点对产生链接的贡献不 同，因此不能通过简单计算共同邻居的数目得到 相似性，而应该累加共同邻居的贡献以得到最终 的相似性分数。按照此思想，图 1(b) 中节点 和 的共同邻居只有 2 个，但每个共同邻居的邻居 之间大多存在链接，说明这两个共同邻居对其邻 c d a b 居间链接的产生有促进作用；节点 和节点 的 共同邻居有 3 个，但每个共同邻居的邻居之间基 本没有链接，说明这些共同邻居对其邻居间链接 的产生有抑制作用。综上，节点 和 在未来产 生链接的可能性更大。 a b c d 实际生活中，节点间链接的产生不仅受到共 同邻居的影响，与其自身的活跃程度也是密不可 分的。在共同邻居数目相等的条件下，节点倾向 于和更活跃的个体产生链接；当共同邻居数目不 等时，如图 1(c) 中，节点 和 的共同邻居少且均 为促进作用，但其自身的度比较小；节点 与 的共同邻居多且均为抑制作用，但其自身的度比 较大。共同邻居与节点自身究竟谁的作用更大， 需要具体计算，这便是 SNB 模型的核心思想。 x y x y 本文认为，节点 和 之间链接的产生受到 内部和外部因素的影响。其中，共同邻居的作用 属于外部影响，根据 LNB 的相关知识，每个共同 邻居的作用不尽相同，或促进或抑制。另一方 面，链接的产生与节点 和 自身的活跃程度密 切相关，影响大小可以通过节点的度进行量化。 这意味着，度相同的两对节点产生链接的概率会 因共同邻居贡献不同而不同，受共同邻居作用相 同的两对节点也会因其自身的度不同而产生差 异。基于此思想，本文综合考虑了共同邻居与节 点对自身的作用，提出了融合朴素贝叶斯 (SNB) 链路预测模型。 在 SNB 模型下，节点 x 和 y 产生链接的后验 概率为: P(exy|N(x, y), kx , ky) = P(exy)· P(N(x, y), kx , ky |exy) P(N(x, y), kx , ky) (10) P(exy|N(x, y), kx , ky) = P(exy)· P(N(x, y), kx , ky |exy) P(N(x, y), kx , ky) (11) 由概率论相关知识，可得： P(N(x, y), kx , ky |exy) = P(N(x, y)|exy)· P(kx |exy,N(x, y))· P(ky |exy,N(x, y), kx) (12) P(N(x, y), kx , ky |exy) = P(N(x, y)|exy)· P(kx |exy,N(x, y))· P(ky |exy,N(x, y), kx) (13) 将式 (12) 和式 (13) 分别代入式 (10) 和式 (11)， 可得: ·102· 智 能 系 统 学 报 第 14 卷
第1期 王润芳，等：融合朴素贝叶斯方法的复杂网络链路预测 ·103· P(eolN(x,y),k:,ky) 能，其中飞代表节点y不可能与节点x的邻居相 P(@N(x.y).k,k) 连，增加共同邻居数，由于节点x的邻居已经包 P(es)P(N(x,y)les)P(klesy,N(x.y)) 括y,所以节点y不可能形成自环；1表示节点y P(es)P(N(x,y)es)P(kles,N(x.y)) (14) 与x不可能形成重复边。进一步的，若想要节点 LNBCN influence of node y的度为k,则除了与之相连的它和节点x的共 P(kleN(x.y).k,) 同邻居外，还需要连接k,-n-1个节点，其中1表示 P(klex.N(x.y),kx) 节点y与x已连接。则后验概率Pk,e,N(,y),k), influence of node y 由式(14)可知，BC的值由3部分决定：共 即节点x与y已连接且两者的共同邻居数和节点 同邻居的影响，可以通过LNB模型的式(T)得到； x的度已知时，求节点y的度为k的概率，是一个 在可与y产生新链接的所有节点中选取k,-n-1 节点x的度的影响R以及节点y的度的影响R, 个节点的组合问题： 可以通过下面的分析得到。其中，节点x和y的 度的影响统称为节点度的影响，图2给出了式 P(leN(.y).k)=C (17) (14)的图解。可以看出，一个复杂的链路预测问 同理，当节点x和y未连接时，节点x的邻居 不包括y。若节点y产生新链接，则可与y形成 题可以分解为2个子问题，箭头左边相当于本文 新链接的另一个节点有m-k,-1-1种可能，其中 的SNB模型，箭头右边的第1部分相当于只考虑 第1个1表示节点y不可能形成自环，第2个 共同邻居的影响，属于外部因素；第2部分相当于 1表示节点x和y不可能连接。进一步的，若想 只考虑节点对自身的影响，属于内部因素。 要节点y的度为k,它还需要连接k,-n个节点， 则后验概率Pke,N(x,y,k),即在可与节点y产 生新链接的所有节点中选取k,-n个节点的组合 问题： Pk,ENx,,k)=C点-2 (18) ·共同邻居 将式(7)，式(15)(18)代入式(14)，可得： ·待预测节点对 P(e) Pes) 图2SNBs算法图解 Pex) P(e) EN(x.y) Fig.2 Algorithm diagram of SNBs constant value 首先考虑式(14)中的第2项，即节点x的度 Pe) (19) 的影响。假设网络中总的节点数为m=Ⅵ，已知 P(eE) x和y连接，且它们的共同邻居数为n=W(x,y训， c Rx Ry 若节点x产生新的链接，则新链接中另一个节点 P(es) 有m-n-1-1种可能，其中第1个1表示节点x 忽略常数 式(19)等号两端取对数，可 不可能形成自环，第2个1表示节点x和y不可 得其简化形式： 能存在一条以上的连边，即不考虑重复边。进一 CN (logs+logR.)+logR,+logR, 步的，若想要节点x的度为k,则除了与它和节点 EN(x.y) y的共同邻居相连接外，还需要连接k,-n-1个节 受LNB模型的启发，本文将SNBCN推广到 点，其中1表示它与节点y已连接。对于后验概 了AA和RA形式，以证明所提SNB模型的有效 率Pkle,N(x,y),即在节点x与y相连接且两者 性。可以得到： 的共同邻居已知的条件下，求节点x的度为k的 SSNBAA 1 e品，1bg -(logs+logR.)+ 概率，是一个如何在可与节点x产生新链接的所 logR,logR, 有节点中选取k-n-1个节点的组合问题。因此， logk:logk, Pkeo,Nx,y》=C点 (15) 同理可得： SSNBRA 1 -logs+log R)+ Pke,N(x,y》=C2 (16) logR logR, 然后考虑式(14)的第3项，即节点y的度的 k 影响。在式(14)中第2项已知条件的基础上，已 显然，当节点x和y相连的节点全部相同时， 知节点x的度为k。若节点y产生新链接，则可 SNB模型会退化为LNB模型，则SNBCN、SNBAA 与y形成新链接的另一个节点有m-k-1种可 和SNBRA指标会退化为相应的LNB指标
r SNBCN x,y = P(exy|N(x, y), kx , ky) P(exy|N(x, y), kx , ky) = P(exy) P(exy) · P(N(x, y)|exy) P(N(x, y)|exy) | {z } LNBCN · P(kx |exy,N(x, y)) P(kx |exy,N(x, y)) | {z } influence of node x · P(ky |exy,N(x, y), kx) P(ky |exy,N(x, y), kx) | {z } influence of node y (14) r SNBCN x,y x Rx y Ry x y 由式 (14) 可知， 的值由 3 部分决定：共 同邻居的影响，可以通过 LNB 模型的式 (7) 得到； 节点 的度的影响 以及节点 的度的影响 ， 可以通过下面的分析得到。其中，节点 和 的 度的影响统称为节点度的影响，图 2 给出了式 (14) 的图解。可以看出，一个复杂的链路预测问 题可以分解为 2 个子问题，箭头左边相当于本文 的 SNB 模型，箭头右边的第 1 部分相当于只考虑 共同邻居的影响，属于外部因素；第 2 部分相当于 只考虑节点对自身的影响，属于内部因素。 ? + 共同邻居 待预测节点对 ? ? x y x y x y 图 2 SNBs 算法图解 Fig. 2 Algorithm diagram of SNBs x m = |V| x y n = |N(x, y)| x m−n−1−1 x x y x kx y kx −n−1 y P(kx |exy,N(x, y)) x y x kx x kx −n−1 首先考虑式 (14) 中的第 2 项，即节点 的度 的影响。假设网络中总的节点数为 ，已知 和 连接，且它们的共同邻居数为 ， 若节点 产生新的链接，则新链接中另一个节点 有 种可能，其中第 1 个 1 表示节点 不可能形成自环，第 2 个 1 表示节点 和 不可 能存在一条以上的连边，即不考虑重复边。进一 步的，若想要节点 的度为 ，则除了与它和节点 的共同邻居相连接外，还需要连接 个节 点，其中 1 表示它与节点 已连接。对于后验概 率 ，即在节点 与 相连接且两者 的共同邻居已知的条件下，求节点 的度为 的 概率，是一个如何在可与节点 产生新链接的所 有节点中选取 个节点的组合问题。因此， P(kx |exy,N(x, y)) = C kx−n−1 m−n−2 (15) 同理可得： P(kx |exy,N(x, y)) = C kx−n m−n−2 (16) y x kx y y m−kx −1 然后考虑式 (14) 的第 3 项，即节点 的度的 影响。在式 (14) 中第 2 项已知条件的基础上，已 知节点 的度为 。若节点 产生新链接，则可 与 形成新链接的另一个节点有 种可 kx y x x y y y x y ky x ky −n−1 y x P(ky |exy,N(x, y), kx) x y x y ky y ky −n−1 能，其中 代表节点 不可能与节点 的邻居相 连，增加共同邻居数，由于节点 的邻居已经包 括 ，所以节点 不可能形成自环；1 表示节点 与 不可能形成重复边。进一步的，若想要节点 的度为 ，则除了与之相连的它和节点 的共 同邻居外，还需要连接 个节点，其中 1 表示 节点 与 已连接。则后验概率 ， 即节点 与 已连接且两者的共同邻居数和节点 的度已知时，求节点 的度为 的概率，是一个 在可与 产生新链接的所有节点中选取 个节点的组合问题： P(ky |exy,N(x, y), kx) = C ky−n−1 m−kx−1 (17) x y x y y y m−kx −1−1 y x y y ky ky −n P(ky |exy,N(x, y), kx) y ky −n 同理，当节点 和 未连接时，节点 的邻居 不包括 。若节点 产生新链接，则可与 形成 新链接的另一个节点有 种可能， 其中 第 1 个 1 表示节点 不可能形成自环，第 2 个 1 表示节点 和 不可能连接。进一步的，若想 要节点 的度为 ，它还需要连接 个节点， 则后验概率 ，即在可与节点 产 生新链接的所有节点中选取 个节点的组合 问题： P(ky |exy,N(x, y), kx) = C ky−n m−kx−2 (18) 将式 (7)，式 (15)~(18) 代入式 (14)，可得： r SNBCN xy = P(exy) P(exy) · ∏ z∈N(x,y) P(exy) P(exy) | {z } constant value · ∏ z∈N(x,y) P(exy|z) P(exy|z) | {z } Rz · C kx−n−1 m−n−2 C kx−n m−n−2 | {z } Rx · C ky−n−1 m−kx−1 C ky−n m−kx−2 | {z } Ry (19) P(exy) P(exy) 忽略常数 ，式 (19) 等号两端取对数，可 得其简化形式： s SNBCN xy = ∑ z∈N(x,y) (log s+logRz)+logRx +logRy 受 LNB 模型的启发，本文将 SNBCN 推广到 了 AA 和 RA 形式，以证明所提 SNB 模型的有效 性。可以得到： s SNBAA xy = ∑ z∈N(x,y) 1 logkz (log s+logRz)+ logRx logkx + logRy logky s SNBRA xy = ∑ z∈N(x,y) 1 kz (log s+logRz)+ logRx kx + logRy ky 显然，当节点 x 和 y 相连的节点全部相同时， SNB 模型会退化为 LNB 模型，则 SNBCN、SNBAA 和 SNBRA 指标会退化为相应的 LNB 指标。 第 1 期 王润芳，等：融合朴素贝叶斯方法的复杂网络链路预测 ·103·
·104· 智能系统学报 第14卷 3链路预测实验 34实验结果与分析 本部分通过两方面内容评估SNB模型的性 所提SNB模型的有效性需要实验的验证，为 能：与基准指标的预测结果比较：当训练集大小 此，本文将从以下几个方面做详细介绍。 发生变化时，预测结果的变化情况。 3.1数据集 3.4.1不同方法性能比较 本文采用的数据集为美国航空网络(USAir), 当按照9：1的比例划分训练集与测试集时，在 包含332个机场和2126条航线。网络的聚类系 USAir网络得到的预测结果如表1所示。可以看出： 数C=0.749,同配系数r=-0.208,平均度(k)=12.81, I)SNBs的AUC值最高，LNBs和CNs次之， 平均最短距离仙=2.74，度异质性H=: 说明SNBs模型整体的预测准确度最高。 )2 3.46。原网络为含权网络，文中忽略了权重信息， 2)SNBs比LNBs的AUC值高，说明与单独 将其当作无权网络处理。 考虑共同邻居相比，将共同邻居与节点自身综合 考虑效果更好。 3.2基准方法与评价指标 3)SNBs系列指标中，SNBRA的AUC值最 1)基准方法 高，SNBAA次之，之后是SNBCN,LNBs系列指 为方便评判SNB模型的性能优劣，本文采用 标也有类似规律，这与之前的认识相符，即RA指 CN、AA和RA(记为CNs)与LNBCN、LNBAA和 标预测效果优于AA指标，AA指标预测效果优 LNBRA(记为LNBs)等作为基准指标。由于CNs 于CN指标，说明惩罚大度节点确实可以提高预 和LNBs指标在前文已作介绍，此处不再赘述。 测准确度，证实了文献[11]中的结论。 2)评价指标 4)SNBCN相对于LNBCN和CN的AUC的 链路预测算法多种多样，需要统一的评价指 提高幅度最大，SNBAA次之，接着是SNBRA。究 标对其进行性能优劣比较，本文选用AUC和精确 其原因，一方面是因为预测效果越差的指标越容 度量化算法的准确度。 易提高，另一方面是因为直接计算共同邻居的贡 AUC (area under the receiver operating charac- 献时，节点自身的影响是最大的，不容忽视。且 teristic curve)表示随机从测试集EP中选择一条边 节点的度越大，越倾向于形成链接，符合优先连 的分数值比随机选择一条不存在的边分数高的概 接原则，因此考虑节点度的影响可以极大地提高 率。假设一共进行了n次独立比较，其中有n 准确度。而SNBAA和SNBRA认为，度越大的节 次测试集里的边得分高于不存在的边得分，有 点贡献越小，这与优先连接思想相悖，相当于将 次两者得分相等，则AUC值为 节点度对其自身的影响中和掉了一部分，导致 AUC=+0.5n" AUC提高的幅度变小。 5)对于精确度值，SNBs整体上与LNBs和 精确度(precision)表示前L条预测边中预测 CNs相差不大，甚至有所下降，可能是因为在预 准确的比例。计算精确度时，将所有未知连边 测的前100条边中，节点受其自身度的影响不大。 (包括测试集中的边和不存在的边)按照其相似性 表1CNs、LNBs和SNBs在USAir上的预测结果 分数降序排列，然后选择排名靠前的前L条边， Table 1 Prediction results of CNs,LNBs and SNBs on 若有m条边在测试集中，即有m条边预测准确，则 USAir Precision 模型 指标 AUC 精确度 本实验中设置L=100。 CN 0.9272 0.5790 3.3实验设置 CNs AA 0.9419 0.5975 RA 0.9511 0.6431 本实验中训练集与测试集的划分比例为9：1。 LNBCN 0.9355 0.5899 由于网络中存在数据类别不平衡问题，即已知连 LNBs LNBAA 0.9463 0.6106 边与不存在连边的数目相差很大，直接采取随机 LNBRA 0.9522 0.6249 采样方式会严重影响预测效果。为此，本实验采 SNBCN 0.9404 0.5793 用了分层采样，在保证训练集与测试集中存在边 SNBs SNBAA 0.9482 0.5945 SNBRA 0.9544 和不存在边的比例与原网络相同的条件下，随机 0.6391 划分数据集。另外，为消除随机误差的影响，实 综上，可以得到如下结论： 验中采用了10折交叉验证方法，且重复10次后 I)SNBs的AUC值较LNBs和CNs明显提 取平均值作为最终结果。 高，说明SNB模型倾向于赋予预测集中的链接更
3 链路预测实验 所提 SNB 模型的有效性需要实验的验证，为 此，本文将从以下几个方面做详细介绍。 3.1 数据集 C = 0.749 r = −0.208 ⟨k⟩ = 12.81 ⟨d⟩ = 2.74 H = ⟨ k 2 ⟩ ⟨k⟩ 2 = 本文采用的数据集为美国航空网络 (USAir)， 包含 332 个机场和 2 126 条航线。网络的聚类系 数 ，同配系数 ，平均度 ， 平均最短距离 ，度异质性 3.46。原网络为含权网络，文中忽略了权重信息， 将其当作无权网络处理。 3.2 基准方法与评价指标 1) 基准方法 为方便评判 SNB 模型的性能优劣，本文采用 CN、AA 和 RA(记为 CNs) 与 LNBCN、LNBAA 和 LNBRA(记为 LNBs) 等作为基准指标。由于 CNs 和 LNBs 指标在前文已作介绍，此处不再赘述。 2) 评价指标 链路预测算法多种多样，需要统一的评价指 标对其进行性能优劣比较，本文选用 AUC 和精确 度量化算法的准确度。 E P n n ′ n ′′ AUC (area under the receiver operating characteristic curve) 表示随机从测试集 中选择一条边 的分数值比随机选择一条不存在的边分数高的概 率 [6]。假设一共进行了 次独立比较，其中有 次测试集里的边得分高于不存在的边得分，有 次两者得分相等，则 AUC 值为 AUC = n ′ +0.5n ′′ n L m m 精确度 (precision) 表示前 条预测边中预测 准确的比例[6]。计算精确度时，将所有未知连边 (包括测试集中的边和不存在的边) 按照其相似性 分数降序排列，然后选择排名靠前的前 L 条边， 若有 条边在测试集中，即有 条边预测准确，则 Precision = m L 本实验中设置 L = 100。 3.3 实验设置 本实验中训练集与测试集的划分比例为 9∶1。 由于网络中存在数据类别不平衡问题，即已知连 边与不存在连边的数目相差很大，直接采取随机 采样方式会严重影响预测效果。为此，本实验采 用了分层采样，在保证训练集与测试集中存在边 和不存在边的比例与原网络相同的条件下，随机 划分数据集。另外，为消除随机误差的影响，实 验中采用了 10 折交叉验证方法，且重复 10 次后 取平均值作为最终结果。 3.4 实验结果与分析 本部分通过两方面内容评估 SNB 模型的性 能：与基准指标的预测结果比较；当训练集大小 发生变化时，预测结果的变化情况。 3.4.1 不同方法性能比较 当按照 9∶1 的比例划分训练集与测试集时，在 USAir 网络得到的预测结果如表 1 所示。可以看出： 1) SNBs 的 AUC 值最高，LNBs 和 CNs 次之。 说明 SNBs 模型整体的预测准确度最高。 2) SNBs 比 LNBs 的 AUC 值高，说明与单独 考虑共同邻居相比，将共同邻居与节点自身综合 考虑效果更好。 3) SNBs 系列指标中，SNBRA 的 AUC 值最 高，SNBAA 次之，之后是 SNBCN，LNBs 系列指 标也有类似规律，这与之前的认识相符，即 RA 指 标预测效果优于 AA 指标，AA 指标预测效果优 于 CN 指标，说明惩罚大度节点确实可以提高预 测准确度，证实了文献[11]中的结论。 4) SNBCN 相对于 LNBCN 和 CN 的 AUC 的 提高幅度最大，SNBAA 次之，接着是 SNBRA。究 其原因，一方面是因为预测效果越差的指标越容 易提高，另一方面是因为直接计算共同邻居的贡 献时，节点自身的影响是最大的，不容忽视。且 节点的度越大，越倾向于形成链接，符合优先连 接原则，因此考虑节点度的影响可以极大地提高 准确度。而 SNBAA 和 SNBRA 认为，度越大的节 点贡献越小，这与优先连接思想相悖，相当于将 节点度对其自身的影响中和掉了一部分，导致 AUC 提高的幅度变小。 5) 对于精确度值，SNBs 整体上与 LNBs 和 CNs 相差不大，甚至有所下降，可能是因为在预 测的前 100 条边中，节点受其自身度的影响不大。 表 1 CNs、LNBs 和 SNBs 在 USAir 上的预测结果 Table 1 Prediction results of CNs, LNBs and SNBs on USAir 模型 指标 AUC 精确度 CNs CN 0.927 2 0.579 0 AA 0.941 9 0.597 5 RA 0.951 1 0.643 1 LNBs LNBCN 0.935 5 0.589 9 LNBAA 0.946 3 0.610 6 LNBRA 0.952 2 0.624 9 SNBs SNBCN 0.940 4 0.579 3 SNBAA 0.948 2 0.594 5 SNBRA 0.954 4 0.639 1 综上，可以得到如下结论： 1) SNBs 的 AUC 值较 LNBs 和 CNs 明显提 高，说明 SNB 模型倾向于赋予预测集中的链接更 ·104· 智 能 系 统 学 报 第 14 卷
第1期 王润芳，等：融合朴素贝叶斯方法的复杂网络链路预测 ·105· 高的分数，即整体上SNBs能够更好地将测试集 0.95 LNBCN 0.90 o…CN 中的边与不存在的边区分开。 SNBCN 0.85 2)3种方法的精确度变化不明显，说明三者 0.80 对测试集中边的排序位置相差不大。 3)SNBs能够在基本保证前100条边中预测 0.70 0.65 准确率一定的条件下，将更多地测试链接识别出 0.60 来，证明了其有效性。 0.55 3.4.2预测效果随训练集大小的变化情况 0.6 0.7 0.8 0.9 训练集大小 本实验中，训练集比例从0.6开始，步长为 (a)CN、LNBCN和SNBCN的 0.1,直到比例达到0.9，得到的CNs,LNBs 精确度随训练集大小的变化情况 SNBs的AUC和精确度随训练集大小变化情况如 1.0r -◆LNBAA 图3和4所示。 …◆…AA 0.9 米-SNBAA 0.95 ◆LNBCN 0.94 w◆CN 剑08 --SNBCN 0.93 0.7 草02 0.6 0.91 0.5 0.90 .6 0.7 08 0.9 训练集大小 0.89 0.6 0.7 0.8 0.9 (b)AA、LNBAA和SNBAA的 训练集大小 精确度随训练集大小的变化情况 (a)CN、LNBCN和SNBCN的 1.00 AUC值随训练集大小的变化情况 ◆LNBRA 0.951 ◆-RA 0.95r ◆LNBAA 0.90 --SNBRA AA 0.94 -■-SNBAA 当Y0.85 0.93 0.80 兰02 梁0.75 0.70 0.91 0.65 0.90 0.60 .6 0.7 0.8 0.9 训练集大小 0.89 0.6 0.7 0.8 0.9 (C)RA、LNBRA和SNBRA的 训练集大小 精确度随训练集大小的变化情况 (b)AA、LNBAA和SNBAA的 AUC值随训练集大小的变化情况 图4 CNs、LNBs和SNBs的精确度随训练集大小的变化 情况 0.96T◆LNBRA Fig.4 Variation of Precision value of CNs,LNBs and ◆，RA -.-SNBRA SNBs with training set size 0.94 g 图3(a)中，SNBCN的AUC值始终高于 LNBCN和CN,证明了SNB模型的高效性；图 0.90 3(b)和(c)的变化趋势相似，当训练集比例较小 0.88 时，SNBRA和SNBAA的AUC值均最低，随着训 0.3866 练集的增大，SNBs与其他指标的差距逐渐减小， 0.7 0.8 0.9 训练集大小 并在训练集比例为O.9时超过其他指标，说明SNB (C)RA、LNBRA和SNBRA的 模型在训练集比例为0.9时的总体预测准确度最高。 AUC值随训练集大小的变化情况 图4(a)和图4(b)具有一致的变化趋势，即 图3CNs、LNBs和SNBs的AUC值随训练集大小的变 SNBs的精确度略低于LNBs和CNs指标，而 化情况 Fig.3 Variation of AUC value of CNs,LNBs and SNBs 图4(C)中SNBRA的精确度值一直处于或接近最 with training set size 高值，可能是因为：节点自身影响不能简单地用
高的分数，即整体上 SNBs 能够更好地将测试集 中的边与不存在的边区分开。 2) 3 种方法的精确度变化不明显，说明三者 对测试集中边的排序位置相差不大。 3) SNBs 能够在基本保证前 100 条边中预测 准确率一定的条件下，将更多地测试链接识别出 来，证明了其有效性。 3.4.2 预测效果随训练集大小的变化情况 本实验中，训练集比例从 0.6 开始，步长为 0.1，直到比例达 到 0.9，得到 的 CNs, LNBs, SNBs 的 AUC 和精确度随训练集大小变化情况如 图 3 和 4 所示。 训练集大小 0.89 0.90 0.91 0.92 0.93 0.94 0.95 AUC LNBCN CN SNBCN (a) CN、LNBCN 和 SNBCN 的 AUC 值随训练集大小的变化情况 0.89 0.90 0.91 0.92 0.93 0.94 0.95 AUC LNBAA AA SNBAA (b)AA、LNBAA 和 SNBAA 的 AUC 值随训练集大小的变化情况 0.86 0.88 0.90 0.92 0.94 0.96 AUC LNBRA RA SNBRA (c) RA、LNBRA 和 SNBRA 的 AUC 值随训练集大小的变化情况 0.6 0.7 0.8 0.9 训练集大小 0.6 0.7 0.8 0.9 训练集大小 0.6 0.7 0.8 0.9 图 3 CNs、LNBs 和 SNBs 的 AUC 值随训练集大小的变 化情况 Fig. 3 Variation of AUC value of CNs, LNBs and SNBs with training set size 训练集大小 0.70 0.65 0.60 0.55 0.75 0.80 0.85 0.90 0.95 精确度 (a) CN、LNBCN 和 SNBCN 的 精确度随训练集大小的变化情况 0.7 0.8 0.9 1.0 精确度 (b) AA、LNBAA 和 SNBAA 的 精确度随训练集大小的变化情况 0.60 0.65 0.70 0.75 0.80 0.85 0.90 0.95 1.00 精确度 (c) RA、LNBRA 和 SNBRA 的 精确度随训练集大小的变化情况 0.6 0.7 0.8 0.9 训练集大小 0.6 0.5 0.6 0.8 0.9 0.7 训练集大小 0.6 0.7 0.8 0.9 LNBCN CN SNBCN LNBAA AA SNBAA LNBRA RA SNBRA 图 4 CNs、LNBs 和 SNBs 的精确度随训练集大小的变化 情况 Fig. 4 Variation of Precision value of CNs, LNBs and SNBs with training set size 图 3(a ) 中 ， SNBCN 的 A UC 值始终高 于 LNBCN 和 CN，证明了 SNB 模型的高效性；图 3(b) 和 (c) 的变化趋势相似，当训练集比例较小 时，SNBRA 和 SNBAA 的 AUC 值均最低，随着训 练集的增大，SNBs 与其他指标的差距逐渐减小， 并在训练集比例为 0.9 时超过其他指标，说明 SNB 模型在训练集比例为 0.9 时的总体预测准确度最高。 图 4(a) 和图 4(b) 具有一致的变化趋势，即 SNBs 的精确度略低于 LNBs 和 CNs 指标，而 图 4(c) 中 SNBRA 的精确度值一直处于或接近最 高值，可能是因为：节点自身影响不能简单地用 第 1 期 王润芳，等：融合朴素贝叶斯方法的复杂网络链路预测 ·105·
·106· 智能系统学报 第14卷 度进行量化，将节点度与资源分配思想结合可以 [4]张学龙，王军进.链路预测下能源供应链网络合作演化 取得更好的预测性能。 机制研究U.智能系统学报，2017,12(2：221-228 结合图3与图4，可以得出以下结论： ZHANG Xuelong,WANG Junjin.On the evolution co- 1)随着训练集比例增大，几种指标的AUC值 operation mechanism of energy supply chain networks un- 均呈增长趋势，而精确度值均呈递减趋势，这可 der link prediction[J].CAAI transactions on Intelligent 能是由于AUC和精确度本身的侧重点不同造成 Systems..2017,12(2):221-228. 的。其中，AUC侧重于总体的预测准确率，当训 [5]ZHOU Tao,REN Jie,MEDO M,et al.Bipartite network projection and personal recommendation[J].Physical re- 练集比较大（已知信息丰富）时，预测缺失边越容 view e,2007,76(4):046115. 易，AUC值越高；精确度侧重于前L条边的预测 [6]LU Linyuan,ZHOU Tao.Link prediction in complex net- 准确率，当测试集比例较大时，前L条预测边在 works:a survey[J].Physica A:statistical mechanics and its 测试集的可能性越大，精确度越高。 applications,2011,390(6):1150-1170. 2)当SNB模型的AUC值较低时，精确度值 [7]LIBEN-NOWELL D,KLEINBERG J.The link-prediction 一般最高或接近最高；同理，当其精确度值较低 problem for social networks[].Journal of the American 时，AUC值一般最高或接近最高，说明SNB模型 society for information science and technology,2007, 的AUC和精确度一定有一个最高值，进一步从侧 58(7):1019-1031 面印证了SNB模型的有效性。 [8]ADAMIC L A,ADAR E.Friends and neighbors on the Web[J].Social networks,2003,25(3):211-230 4总结与展望 [9]ZHOU Tao,LU Linyuan,ZHANG Yicheng.Predicting 近来，有文献指出：社交网络中链接的产生受 missing links via local information[J].The European phys- 内部和外部因素的影响。受此思想的启发，本文 ical journal B.2009,71(4:623-630. 在局部朴素贝叶斯(LNB)的基础上，结合节点度 [10]LIU Weiping,LO Linyuan.Link prediction based on loc- 的自身影响，提出了融合朴素贝叶斯(NB)模 al random walk[J].EPL (europhysics letters),2010,89(5) 58007. 型。该模型易于推广到其他的基于共同邻居的指 标形式，如AA和RA具有良好的可扩展性。在 [11]LU Linyuan,ZHOU Tao.Link prediction in weighted networks:the role of weak ties[J].EPL (europhysics let- 美国航空网(USAir)上的实验结果表明：与基准 ters),2010,89(1)y18001. 方法相比，提高了链路预测性能，证实了该方法 [12]LIU Zhen,ZHANG Qianming,LU Linyuan,et al.Link 的有效性。由此得出结论：链接的产生不仅受到 prediction in complex networks:a local naive Bayes mod- 共同邻居的影响，也受到其自身度的影响，将二 el[J].EPL (europhysics letters),2011,96(4):48007 者综合考虑更加合理。 [13]VALVERDE-REBAZA J C.DE ANDRADE LOPES A. 未来，将尝试将该思想推广到智能方法做链 Link prediction in online social networks using group in- 路预测，如支持向量机、相关向量机等。另外，考 formation[C]//Proceedings of the 14th International Con- 虑到本文研究的是无权无向网络，以后可以先在 ference on Computational Science and Its Applications. 更多不同领域的网络上实现，然后再着眼于加权 Guimaraes,Portugal,2014:31-45. 网络的研究。 [14]VALVERDE-REBAZA J.VALEJO A.BERTON L.et al. A naive Bayes model based on overlapping groups for 参考文献： link prediction in online social networks[Cl//Proceedings of the 30th Annual ACM Symposium on Applied Com- [1]LIU Yangyang,ZHAO Chengli,WANG Xiaojie,et al.The puting.Salamanca,Spain,2015:1136-1141. degree-related clustering coefficient and its application to [15]WU Jiehua.A generalized tree augmented naive Bayes link prediction[J].Physica A:statistical mechanics and its link prediction model[J].Journal of computational sci- applications,2016,454:24-33 ence,2018,27:206-217. [2]何大韧，刘宗华，汪秉宏.复杂系统与复杂网络M.北京 [16]闫玲玲，陈增强，张青.基于度和聚类系数的中国航空 高等教育出版社，2009. 网络重要性节点分析.智能系统学报，2016,11(5)： [3]刘宏鲲，吕琳媛，周涛.利用链路预测推断网络演化机制 586-593. [).中国科学，2011,41(7)：816-823. YAN Lingling,CHEN Zengqiang,ZHANG Qing.Ana- LIU Hongkun,LU Linyuan,ZHOU Tao.Infer network lysis of key nodes in China's aviation network based on evolution mechanism by using link prediction[J].Chinese the degree centrality indicator and clustering coefficient science,2011.41(7):816-823 [J].CAAI transactions on intelligent systems,2016
度进行量化，将节点度与资源分配思想结合可以 取得更好的预测性能。 结合图 3 与图 4，可以得出以下结论： L L 1) 随着训练集比例增大，几种指标的 AUC 值 均呈增长趋势，而精确度值均呈递减趋势，这可 能是由于 AUC 和精确度本身的侧重点不同造成 的。其中，AUC 侧重于总体的预测准确率，当训 练集比较大 (已知信息丰富) 时，预测缺失边越容 易，AUC 值越高；精确度侧重于前 条边的预测 准确率，当测试集比例较大时，前 条预测边在 测试集的可能性越大，精确度越高。 2) 当 SNB 模型的 AUC 值较低时，精确度值 一般最高或接近最高；同理，当其精确度值较低 时，AUC 值一般最高或接近最高，说明 SNB 模型 的 AUC 和精确度一定有一个最高值，进一步从侧 面印证了 SNB 模型的有效性。 4 总结与展望 近来，有文献指出：社交网络中链接的产生受 内部和外部因素的影响。受此思想的启发，本文 在局部朴素贝叶斯 (LNB) 的基础上，结合节点度 的自身影响，提出了融合朴素贝叶斯 (SNB) 模 型。该模型易于推广到其他的基于共同邻居的指 标形式，如 AA 和 RA 具有良好的可扩展性。在 美国航空网 (USAir) 上的实验结果表明：与基准 方法相比，提高了链路预测性能，证实了该方法 的有效性。由此得出结论：链接的产生不仅受到 共同邻居的影响，也受到其自身度的影响，将二 者综合考虑更加合理。 未来，将尝试将该思想推广到智能方法做链 路预测，如支持向量机、相关向量机等。另外，考 虑到本文研究的是无权无向网络，以后可以先在 更多不同领域的网络上实现，然后再着眼于加权 网络的研究。 参考文献： LIU Yangyang, ZHAO Chengli, WANG Xiaojie, et al. The degree-related clustering coefficient and its application to link prediction[J]. Physica A: statistical mechanics and its applications, 2016, 454: 24–33. [1] 何大韧, 刘宗华, 汪秉宏. 复杂系统与复杂网络[M]. 北京: 高等教育出版社, 2009. [2] 刘宏鲲, 吕琳媛, 周涛. 利用链路预测推断网络演化机制 [J]. 中国科学, 2011, 41(7): 816–823. LIU Hongkun, LÜ Linyuan, ZHOU Tao. Infer network evolution mechanism by using link prediction[J]. Chinese science, 2011, 41(7): 816–823. [3] 张学龙, 王军进. 链路预测下能源供应链网络合作演化 机制研究[J]. 智能系统学报, 2017, 12(2): 221–228. ZHANG Xuelong, WANG Junjin. On the evolution cooperation mechanism of energy supply chain networks under link prediction[J]. CAAI transactions on Intelligent Systems, 2017, 12(2): 221–228. [4] ZHOU Tao, REN Jie, MEDO M, et al. Bipartite network projection and personal recommendation[J]. Physical review e, 2007, 76(4): 046115. [5] LÜ Linyuan, ZHOU Tao. Link prediction in complex networks: a survey[J]. Physica A: statistical mechanics and its applications, 2011, 390(6): 1150–1170. [6] LIBEN-NOWELL D, KLEINBERG J. The link-prediction problem for social networks[J]. Journal of the American society for information science and technology, 2007, 58(7): 1019–1031. [7] ADAMIC L A, ADAR E. Friends and neighbors on the Web[J]. Social networks, 2003, 25(3): 211–230. [8] ZHOU Tao, LÜ Linyuan, ZHANG Yicheng. Predicting missing links via local information[J]. The European physical journal B, 2009, 71(4): 623–630. [9] LIU Weiping, LÜ Linyuan. Link prediction based on local random walk[J]. EPL (europhysics letters), 2010, 89(5): 58007. [10] LÜ Linyuan, ZHOU Tao. Link prediction in weighted networks: the role of weak ties[J]. EPL (europhysics letters), 2010, 89(1): 18001. [11] LIU Zhen, ZHANG Qianming, LÜ Linyuan, et al. Link prediction in complex networks: a local naïve Bayes model[J]. EPL (europhysics letters), 2011, 96(4): 48007. [12] VALVERDE-REBAZA J C, DE ANDRADE LOPES A. Link prediction in online social networks using group information[C]//Proceedings of the 14th International Conference on Computational Science and Its Applications. Guimarães, Portugal, 2014: 31–45. [13] VALVERDE-REBAZA J, VALEJO A, BERTON L, et al. A naïve Bayes model based on overlapping groups for link prediction in online social networks[C]//Proceedings of the 30th Annual ACM Symposium on Applied Computing. Salamanca, Spain, 2015: 1136–1141. [14] WU Jiehua. A generalized tree augmented naive Bayes link prediction model[J]. Journal of computational science, 2018, 27: 206–217. [15] 闫玲玲, 陈增强, 张青. 基于度和聚类系数的中国航空 网络重要性节点分析[J]. 智能系统学报, 2016, 11(5): 586–593. YAN Lingling, CHEN Zengqiang, ZHANG Qing. Analysis of key nodes in China's aviation network based on the degree centrality indicator and clustering coefficient [J]. CAAI transactions on intelligent systems, 2016, [16] ·106· 智 能 系 统 学 报 第 14 卷
第1期 王润芳，等：融合朴素贝叶斯方法的复杂网络链路预测 ·107· 11(5):586-593 microblog retweet network based on maximum entropy [17]PUJARI M,KANAWATI R.Link prediction in complex model[J].Acta physica sinica,2016,65(2):31-41. networks by supervised rank aggregation[C]//Proceed- [24]WANG Yisen,LIU Fangbing,XIA Shutao,et al.Link ings of the 2012 IEEE 24th International Conference on sign prediction by variational Bayesian probabilistic mat- Tools with Artificial Intelligence.Athens,Greece,2012: rix factorization with student-t prior[J].Information sci- 782-789. ences,2017,405:175-189 [18]LI Yun,NIU Kai,TIAN Baoyu.Link prediction in Sina Microblog using comprehensive features and improved 作者简介： SVM algorithm[C]//Proceedings of the 2014 IEEE 3rd In- 王润芳，女，1994年生，硕士研究 ternational Conference on Cloud Computing and Intelli- 生，主要研究方向为智能系统预测与 gence Systems.Shenzhen,China,2014:18-22. 控制。 [19]YUAN Weiwei,HE Kangya,GUAN Donghai,et al. Graph kernel based link prediction for signed social net- works[J].Information fusion,2019,46:1-10. [20]孙诚，王志海.社会网络中基于神经网络的链路预测方 法[U.数学建模及其应用，2017,6(4)：10-17 陈增强，男，1964年生，教授，博 SUN Cheng,WANG Zhihai.The link prediction al- 士生导师，中国系统仿真学会理事，中 国人工智能学会智能空天系统专业委 gorithms based on neural networks in social networks[J]. 员会副主任，控制理论专业委员会委 Mathematical modeling and its applications,2017,6(4): 员、天津市人民政府学科评议组控制 10-17 学科组成员、天津市自动化学会理事， [21]LI Jichao,ZHAO Danling,GE Bingfeng,et al.A link pre- 担任多个期刊的编委，主要研究方向 diction method for heterogeneous networks based on BP 为智能预测控制、复杂动态网络与混沌系统。主持完成国 neural network[J].Physica A:statistical mechanics and its 家863项目和国家自然科学基金项目6项，获得省部级科技 applications,2018,495:1-17. 进步奖4次。发表学术论文300余篇。 [22]XIAO Yunpeng,LI Xixi,WANG Haohan,et al.3-HBP:a 刘忠信，男，1975年生，教授，博 three-level hidden Bayesian link prediction model in so- 士生导师，中国人工智能学会智能空 cial networks[J.IEEE transactions on computational so- 天系统专业委员会委员、中国智能物 cial systems,.2018,5(2:430-443. 联系统建模与仿真专业委员会委员、 [23]李勇军，尹超，于会，等.基于最大嫡模型的微博传播网 天津市系统工程学会理事，主要研究 络中的链路预测.物理学报，2016,65(2)：31-41 方向为群体智能与复杂动态网络、计 LI Yongjun,YIN Chao,YU Hui,et al.Link prediction in 算机控制。发表学术论文180余篇
11(5): 586–593. PUJARI M, KANAWATI R. Link prediction in complex networks by supervised rank aggregation[C]//Proceedings of the 2012 IEEE 24th International Conference on Tools with Artificial Intelligence. Athens, Greece, 2012: 782–789. [17] LI Yun, NIU Kai, TIAN Baoyu. Link prediction in Sina Microblog using comprehensive features and improved SVM algorithm[C]//Proceedings of the 2014 IEEE 3rd International Conference on Cloud Computing and Intelligence Systems. Shenzhen, China, 2014: 18–22. [18] YUAN Weiwei, HE Kangya, GUAN Donghai, et al. Graph kernel based link prediction for signed social networks[J]. Information fusion, 2019, 46: 1–10. [19] 孙诚, 王志海. 社会网络中基于神经网络的链路预测方 法[J]. 数学建模及其应用, 2017, 6(4): 10–17. SUN Cheng, WANG Zhihai. The link prediction algorithms based on neural networks in social networks[J]. Mathematical modeling and its applications, 2017, 6(4): 10–17. [20] LI Jichao, ZHAO Danling, GE Bingfeng, et al. A link prediction method for heterogeneous networks based on BP neural network[J]. Physica A: statistical mechanics and its applications, 2018, 495: 1–17. [21] XIAO Yunpeng, LI Xixi, WANG Haohan, et al. 3-HBP: a three-level hidden Bayesian link prediction model in social networks[J]. IEEE transactions on computational social systems, 2018, 5(2): 430–443. [22] 李勇军, 尹超, 于会, 等. 基于最大熵模型的微博传播网 络中的链路预测[J]. 物理学报, 2016, 65(2): 31–41. LI Yongjun, YIN Chao, YU Hui, et al. Link prediction in [23] microblog retweet network based on maximum entropy model[J]. Acta physica sinica, 2016, 65(2): 31–41. WANG Yisen, LIU Fangbing, XIA Shutao, et al. Link sign prediction by variational Bayesian probabilistic matrix factorization with student-t prior[J]. Information sciences, 2017, 405: 175–189. [24] 作者简介： 王润芳，女，1994 年生 ，硕士研究 生，主要研究方向为智能系统预测与 控制。 陈增强，男，1964 年生，教授，博 士生导师，中国系统仿真学会理事，中 国人工智能学会智能空天系统专业委 员会副主任，控制理论专业委员会委 员、天津市人民政府学科评议组控制 学科组成员、天津市自动化学会理事， 担任多个期刊的编委，主要研究方向 为智能预测控制、复杂动态网络与混沌系统。主持完成国 家 863 项目和国家自然科学基金项目 6 项，获得省部级科技 进步奖 4 次。发表学术论文 300 余篇。 刘忠信，男，1975 年生，教授，博 士生导师，中国人工智能学会智能空 天系统专业委员会委员、中国智能物 联系统建模与仿真专业委员会委员、 天津市系统工程学会理事，主要研究 方向为群体智能与复杂动态网络、计 算机控制。发表学术论文 180 余篇。 第 1 期 王润芳，等：融合朴素贝叶斯方法的复杂网络链路预测 ·107·