链路预测 - 版本历史

2020年5月10日 (日) 14:59 薄荷

2020-05-10T14:59:26Z

木子二月鸟：/* 参考资料 */

2020-05-10T14:50:56Z

参考资料

木子二月鸟：/* 基于机器学习的链路预测 */

2020-05-10T14:49:43Z

基于机器学习的链路预测

木子二月鸟：/* 基于机器学习的链路预测 */

2020-05-10T14:48:19Z

基于机器学习的链路预测

木子二月鸟：/* 基于似然分析的链路预测 */

2020-05-10T14:46:07Z

基于似然分析的链路预测

2020年5月10日 (日) 14:43 木子二月鸟

2020-05-10T14:43:04Z

木子二月鸟：/* 基于相似性的链路预测 */

2020-05-10T14:41:13Z

基于相似性的链路预测

2020年5月10日 (日) 14:23 木子二月鸟

2020-05-10T14:23:55Z

木子二月鸟：/* 基于相似性的链路预测 */

2020-05-10T14:21:21Z

基于相似性的链路预测

木子二月鸟：/* 基于相似性的链路预测 */

2020-05-10T14:19:54Z

基于相似性的链路预测

@@ 第238行： / 第238行： @@
 *吕琳媛,任晓龙,周涛.《网络链路预测：概念与前沿》[J].《中国计算机学会通讯》,2016年,第4期
 *Link Prediction Group 网站：http://www.linkprediction.org/
 ==编者推荐==

@@ 第237行： / 第237行： @@
 *吕琳媛,周涛.《链路预测》.北京：高等教育出版社,2013年：57-93
 *吕琳媛,任晓龙,周涛.《网络链路预测：概念与前沿》[J].《中国计算机学会通讯》,2016年,第4期
 *Link Prediction Group 网站：http://www.linkprediction.org/

@@ 第179行： / 第179行： @@
 用机器学习的思路进行链路预测，主要分为基于特征分类方法、基于概率图模型方法和基于矩阵分解方法三大类。
-*基于特征分类方法<ref name="[20]">Al Hasan, M, Chaoji, V, Salem, S (2006) [https://pattern.swarma.org/paper?id=0cae2084-710c-11ea-bbd8-0242ac1a0005 Link prediction using supervised learning].counter-terrorism and security..30.(798--805)</ref>
+*基于特征分类方法<ref name="[21]">Al Hasan, M, Chaoji, V, Salem, S (2006) [https://pattern.swarma.org/paper?id=0cae2084-710c-11ea-bbd8-0242ac1a0005 Link prediction using supervised learning].counter-terrorism and security..30.(798--805)</ref>
 网络中的链路预测问题可以看成机器学习中的分类问题，其中每个数据点对应一对节点之间关系的标记，假定两个节点之间存在连边，则数据点的值为+1，否则为-1。特征选取是分类问题中最重要的问题之一，目前研究较多的主要包括基于节点与边的属性特征和基于节点所处网络的拓扑结构特征（如CN、AA、Katz、最短路径）等。哈桑 Hasan 等人提取合著网络中科学家研究领域的关键词作为特征，用监督学习中一些常用的分类算法（如决策树、K近邻法、多层感知器、支持向量机、径向基网络）对缺失的连边进行较为精准的预测，其中以支持向量机方法表现最佳。
-*基于概率图模型<ref name="[21]">Backstrom, L, Leskovec, J (2011) [https://pattern.swarma.org/paper?id=8ccaa454-710c-11ea-9eeb-0242ac1a0005 Supervised random walks: predicting and recommending links in social networks].Proceedings of the fourth ACM international conference on Web search and data mining.(635--644)</ref>
+*基于概率图模型<ref name="[22]">Backstrom, L, Leskovec, J (2011) [https://pattern.swarma.org/paper?id=8ccaa454-710c-11ea-9eeb-0242ac1a0005 Supervised random walks: predicting and recommending links in social networks].Proceedings of the fourth ACM international conference on Web search and data mining.(635--644)</ref>
 基于概率图模型的链路预测方法使用图模型来表达节点之间的连边概率，根据模型中概率依赖关系，可分为有向无环的贝叶斯网络和无向的马尔科夫网络。随机分块模型和层次结构模型分别是典型的基于贝叶斯网络和基于马尔科夫网络的链路预测方法。基于概率图模型的链路预测方法有很多，典型的还有有监督随机游走链路预测算法，将网络结构信息与节点和连边的属性信息结合起来，给每条边分配不同的转移概率。与其他有监督的机器学习方法相比，该算法无须知道网络的特征和相关的领域知识。
@@ 第189行： / 第189行： @@
 *基于矩阵分解
-基于矩阵分解的链路预测方法是基于网络邻接矩阵的代数谱变换而得到的方法，来预测网络中链路的存在性和链路的权值<ref name="[22]">Kunegis, J, Lommatzsch, A (2009) [https://pattern.swarma.org/paper?id=2908af64-710d-11ea-b513-0242ac1a0005 Learning spectral graph transformations for link prediction].Proceedings of the 26th Annual International Conference on Machine Learning.(561--568)</ref>。相比其他几种机器学习方法，该方法要学习的参数少很多，但计算复杂度较高。链路预测问题可以视为邻接矩阵填充问题，并可以通过双线性回归模型将节点和链路的显特征和隐特征结合起来用矩阵分解方法解决<ref name="[23]">Menon A K, Elkan, C (2011) [https://pattern.swarma.org/paper?id=7f0ab830-710d-11ea-9143-0242ac1a0005 Link prediction via matrix factorization].(437--452)</ref>。边缘去噪模型将根据给定关系矩阵求未知边或丢失边的问题变成一个矩阵降噪去噪问题<ref name="[24]">Chen, Z, Zhang, W. (2014) [https://pattern.swarma.org/paper?id=d925d57a-710d-11ea-90c5-0242ac1a0005 A marginalized denoising method for link prediction in relational data].Proceedings of the 2014 SIAM International Conference on Data Mining. Society for Industrial and Applied Mathematics.(298--306)</ref>。
+基于矩阵分解的链路预测方法是基于网络邻接矩阵的代数谱变换而得到的方法，来预测网络中链路的存在性和链路的权值<ref name="[23]">Kunegis, J, Lommatzsch, A (2009) [https://pattern.swarma.org/paper?id=2908af64-710d-11ea-b513-0242ac1a0005 Learning spectral graph transformations for link prediction].Proceedings of the 26th Annual International Conference on Machine Learning.(561--568)</ref>。相比其他几种机器学习方法，该方法要学习的参数少很多，但计算复杂度较高。链路预测问题可以视为邻接矩阵填充问题，并可以通过双线性回归模型将节点和链路的显特征和隐特征结合起来用矩阵分解方法解决<ref name="[24]">Menon A K, Elkan, C (2011) [https://pattern.swarma.org/paper?id=7f0ab830-710d-11ea-9143-0242ac1a0005 Link prediction via matrix factorization].(437--452)</ref>。边缘去噪模型将根据给定关系矩阵求未知边或丢失边的问题变成一个矩阵降噪去噪问题<ref name="[25]">Chen, Z, Zhang, W. (2014) [https://pattern.swarma.org/paper?id=d925d57a-710d-11ea-90c5-0242ac1a0005 A marginalized denoising method for link prediction in relational data].Proceedings of the 2014 SIAM International Conference on Data Mining. Society for Industrial and Applied Mathematics.(298--306)</ref>。
 关于不同的链路预测研究方法的分类可以参考下表：

@@ 第179行： / 第179行： @@
 用机器学习的思路进行链路预测，主要分为基于特征分类方法、基于概率图模型方法和基于矩阵分解方法三大类。
-*基于特征分类方法
+*基于特征分类方法<ref name="[20]">Al Hasan, M, Chaoji, V, Salem, S (2006) [https://pattern.swarma.org/paper?id=0cae2084-710c-11ea-bbd8-0242ac1a0005 Link prediction using supervised learning].counter-terrorism and security..30.(798--805)</ref>
 网络中的链路预测问题可以看成机器学习中的分类问题，其中每个数据点对应一对节点之间关系的标记，假定两个节点之间存在连边，则数据点的值为+1，否则为-1。特征选取是分类问题中最重要的问题之一，目前研究较多的主要包括基于节点与边的属性特征和基于节点所处网络的拓扑结构特征（如CN、AA、Katz、最短路径）等。哈桑 Hasan 等人提取合著网络中科学家研究领域的关键词作为特征，用监督学习中一些常用的分类算法（如决策树、K近邻法、多层感知器、支持向量机、径向基网络）对缺失的连边进行较为精准的预测，其中以支持向量机方法表现最佳。
-*基于概率图模型
+*基于概率图模型<ref name="[21]">Backstrom, L, Leskovec, J (2011) [https://pattern.swarma.org/paper?id=8ccaa454-710c-11ea-9eeb-0242ac1a0005 Supervised random walks: predicting and recommending links in social networks].Proceedings of the fourth ACM international conference on Web search and data mining.(635--644)</ref>
 基于概率图模型的链路预测方法使用图模型来表达节点之间的连边概率，根据模型中概率依赖关系，可分为有向无环的贝叶斯网络和无向的马尔科夫网络。随机分块模型和层次结构模型分别是典型的基于贝叶斯网络和基于马尔科夫网络的链路预测方法。基于概率图模型的链路预测方法有很多，典型的还有有监督随机游走链路预测算法，将网络结构信息与节点和连边的属性信息结合起来，给每条边分配不同的转移概率。与其他有监督的机器学习方法相比，该算法无须知道网络的特征和相关的领域知识。
@@ 第189行： / 第189行： @@
 *基于矩阵分解
-基于矩阵分解的链路预测方法是基于网络邻接矩阵的代数谱变换而得到的方法，来预测网络中链路的存在性和链路的权值。相比其他几种机器学习方法，该方法要学习的参数少很多，但计算复杂度较高。链路预测问题可以视为邻接矩阵填充问题，并可以通过双线性回归模型将节点和链路的显特征和隐特征结合起来用矩阵分解方法解决。边缘去噪模型将根据给定关系矩阵求未知边或丢失边的问题变成一个矩阵降噪去噪问题。
+基于矩阵分解的链路预测方法是基于网络邻接矩阵的代数谱变换而得到的方法，来预测网络中链路的存在性和链路的权值<ref name="[22]">Kunegis, J, Lommatzsch, A (2009) [https://pattern.swarma.org/paper?id=2908af64-710d-11ea-b513-0242ac1a0005 Learning spectral graph transformations for link prediction].Proceedings of the 26th Annual International Conference on Machine Learning.(561--568)</ref>。相比其他几种机器学习方法，该方法要学习的参数少很多，但计算复杂度较高。链路预测问题可以视为邻接矩阵填充问题，并可以通过双线性回归模型将节点和链路的显特征和隐特征结合起来用矩阵分解方法解决<ref name="[23]">Menon A K, Elkan, C (2011) [https://pattern.swarma.org/paper?id=7f0ab830-710d-11ea-9143-0242ac1a0005 Link prediction via matrix factorization].(437--452)</ref>。边缘去噪模型将根据给定关系矩阵求未知边或丢失边的问题变成一个矩阵降噪去噪问题<ref name="[24]">Chen, Z, Zhang, W. (2014) [https://pattern.swarma.org/paper?id=d925d57a-710d-11ea-90c5-0242ac1a0005 A marginalized denoising method for link prediction in relational data].Proceedings of the 2014 SIAM International Conference on Data Mining. Society for Industrial and Applied Mathematics.(298--306)</ref>。
 关于不同的链路预测研究方法的分类可以参考下表：

@@ 第153行： / 第153行： @@
 基于似然分析的链路预测的基本思路是：根据网络结构的产生和组织方式以及目前已经观察到的链路计算网络的似然值，并认为真实的网络使得网络似然值最大，然后再根据网络似然最大化计算每一对未连接的节点产生连边的可能性。
-*层次结构模型 HSM
+*层次结构模型 HSM<ref name="[17]">Aaron Clauset,Cristopher Moore,M. E. J. Newman (2008) [https://pattern.swarma.org/paper?id=1ca0e946-70ed-11ea-82c3-0242ac1a0005 Hierarchical structure and the prediction of missing links in networks].arXiv:0811.0484.</ref>
 层次结构模型假设真实的网络都存在某种层次性，网络的连接则可看作是这种内在层次结构的反映。该方法的计算步骤如下：
@@ 第167行： / 第167行： @@
 *随机分块模型 SBM
-与层次结构模型的思想类似，随机分块模型假设网络中的节点可以被分为若干集合，两个节点间连接的概率只与相应的集合有关。换句话说，同一个群众所有节点的地位是相同的。随机分块模型特别适合刻画节点所属群的成员身份对于其连接行为有关键影响的情况，例如，著名的“角色模型”就包含了随机分块模型的理念。
+与层次结构模型的思想类似，随机分块模型假设网络中的节点可以被分为若干集合，两个节点间连接的概率只与相应的集合有关。换句话说，同一个群众所有节点的地位是相同的。随机分块模型特别适合刻画节点所属群的成员身份对于其连接行为有关键影响的情况，例如，著名的“角色模型”就包含了随机分块模型的理念。<ref name="[18]">Roger Guimerà,Marta Sales-Pardo,Luís A. N. Amaral (2006) [https://pattern.swarma.org/paper?id=aa2a88c0-7107-11ea-a3cf-0242ac1a0005 Classes of complex networks defined by role-to-role connectivity profiles].nature physics.3.1:(63-69)</ref><ref name="[19]">Joerg Reichardt,Douglas R. White (2007) [https://pattern.swarma.org/paper?id=f20b0e20-7108-11ea-9e3d-0242ac1a0005 Role models for complex networks].arXiv:0708.0958.</ref>
 随机分块模型的效果要好于层次结构模型。同时，该方法还可以剔除网络的错误连边，如纠正蛋白质相互作用网络中的错误连边。
-*闭路模型 Loop model
+*闭路模型 Loop model<ref name="[20]">吕琳媛,Xiaolong Ren,周涛 (2016) [https://pattern.swarma.org/paper?id=f5d29350-710a-11ea-9346-0242ac1a0005 网络链路预测：概念与前沿].</ref>
 似然分析的更一般的框架是：给定一个网络系统，特定网络哈密顿量的负指数被统计分配函数归一化后，就得到这个网络出现的似然，一条未被观察到的连边存在的可能性就等于添加这条连边后网络的似然值。闭路模型考虑网络结构形成中的“局部性原则”，并由此定义了网络的哈密顿量。实验表明，闭路模型的预测精度大于层次结构模型和随机分块模型。

@@ 第104行： / 第104行： @@
 <math>s_{xy}^{ACT}=\frac{1}{l^+_{xx} +l^+_{yy} - 2l^+_{xy}}</math>
-.余弦相似性指标 Cos+指标<ref name="13">Fouss F, Pirotte A, Renders J M (2007) [https://pattern.swarma.org/paper?id=f3ce12c4-70c8-11ea-8ff9-0242ac1a0005 Random-walk computation of similarities between nodes of a graph with application to collaborative recommendation].IEEE Transactions on knowledge and data engineering.19.(355-369)</ref>
+.余弦相似性指标 Cos+指标<ref name="[13]">Fouss F, Pirotte A, Renders J M (2007) [https://pattern.swarma.org/paper?id=f3ce12c4-70c8-11ea-8ff9-0242ac1a0005 Random-walk computation of similarities between nodes of a graph with application to collaborative recommendation].IEEE Transactions on knowledge and data engineering.19.(355-369)</ref>
 在由向量<math>v_x = \Lambda ^{1/2}U^{T}e_{x}</math>展开的欧式空间内，<math>L^+ </math>中的元素<math>l^{+}_{xy}</math>可表示为两向量<math>v_x</math>和<math>v_y</math>的内积，即<math> l^{+}_{xy} = v_{x}^{T} v_y</math>，其中<math>U</math>是一个标准正交矩阵，由<math>L^+</math>特征向量按照对应的特征根从大到小排列，<math>\Lambda</math>为以特征根为对角元素的对角矩阵，<math>e_{x}</math> 表示一个一维向量且只有第x个元素为1，其他都为0。由此定义余弦相似性如下：
@@ 第121行： / 第121行： @@
 <math>s_{xy}^{RWR} = q_{xy} + q_{yx} </math>
-.SimRank指标 SimR<ref name="[14]">Jeh G, Widom J. SimRank (2002) [https://pattern.swarma.org/paper?id=593e78e0-70cb-11ea-9743-0242ac1a0005 a measure of structural-context similarity].(538-543)</ref>
+.SimRank指标 SimR<ref name="[15]">Jeh G, Widom J. SimRank (2002) [https://pattern.swarma.org/paper?id=593e78e0-70cb-11ea-9743-0242ac1a0005 a measure of structural-context similarity].(538-543)</ref>
 它的基本假设是，如果两节点所连接的节点相似，那么这两个节点就相似。其自洽定义式为
@@ 第131行： / 第131行： @@
 SimR指标同时考虑了结构等价和一般等价。当节点x的邻居z同时也是节点y的邻居时，该指标考虑了结构等价；当节点x不等于节点y时，该指标概率了一般等价。可以证明，SimR指标可以用来描述两个分别从节点x和y出发的粒子平均过多久会相遇。
-.局部随机游走指标 LRW<ref name="[15]">Weiping Liu,Linyuan Lu (2010) [https://pattern.swarma.org/paper?id=98d1a08e-70eb-11ea-a520-0242ac1a0005 Link Prediction Based on Local Random Walk].arXiv:1001.2467.89.(58007)</ref>
+.局部随机游走指标 LRW<ref name="[16]">Weiping Liu,Linyuan Lu (2010) [https://pattern.swarma.org/paper?id=98d1a08e-70eb-11ea-a520-0242ac1a0005 Link Prediction Based on Local Random Walk].arXiv:1001.2467.89.(58007)</ref>
 上述4种随机游走指标是基于全局的随机游走，这类指标往往计算复杂度很高，因此很难在大规模网络上应用。刘伟平和吕琳媛提出了一种基于网络局部随机游走的相似性指标LRW，它只考虑有限步数的随机游走过程。一个粒子 t 时刻从节点x出发，定义<math>π_{xy} (t) </math>为 t+1 时刻这个粒子正好走到节点y的概率，那么可得到系统演化方程：
@@ 第141行： / 第141行： @@
 <math>s_{xy}^{LRW} = q_{xy} + q_{yx}</math>
-.叠加的局部随机游走指标 SRW<ref name="[15]">Weiping Liu,Linyuan Lu (2010) [https://pattern.swarma.org/paper?id=98d1a08e-70eb-11ea-a520-0242ac1a0005 Link Prediction Based on Local Random Walk].arXiv:1001.2467.89.(58007)</ref>
+.叠加的局部随机游走指标 SRW<ref name="[16]">Weiping Liu,Linyuan Lu (2010) [https://pattern.swarma.org/paper?id=98d1a08e-70eb-11ea-a520-0242ac1a0005 Link Prediction Based on Local Random Walk].arXiv:1001.2467.89.(58007)</ref>
 这个指标给邻近目标节点的点更多的机会与目标节点相连，充分考虑了很多真实网络连接上的局域性特点，它是在LRW的基础上，将t步及其以前的结果加总，便得到SRW的值，即：

@@ 第22行： / 第22行： @@
-第2个指标Salton指标<ref name="2">Salton G, McGill M J () [https://pattern.swarma.org/paper?id=15e10152-92c8-11ea-81db-0242ac1a0005 Introduction to Modern Information Retrieval].</ref>又称余弦相似性，其定义为 <math>s_{xy}=\frac{|Γ(x)| \cap |Γ(y)|}{\sqrt{k(x)k(y)}}</math>
+第2个指标Salton指标<ref name="[2]">Salton G, McGill M J () [https://pattern.swarma.org/paper?id=15e10152-92c8-11ea-81db-0242ac1a0005 Introduction to Modern Information Retrieval].</ref>又称余弦相似性，其定义为 <math>s_{xy}=\frac{|Γ(x)| \cap |Γ(y)|}{\sqrt{k(x)k(y)}}</math>
-第3个指标Jaccard指标<ref name="3">Jaccard P. () [https://pattern.swarma.org/paper?id=70c8a48a-92c8-11ea-9f7f-0242ac1a0005 Etude de la distribution florale dans une portion des Alpes et du Jura].</ref>是于100多年前由Jaccard提出的，其定义为 <math>s_{xy}=\frac{|Γ(x)| \cap |Γ(y)|}{|Γ(x)| \bigcup  |Γ(y)|}</math>
+第3个指标Jaccard指标<ref name="[3]">Jaccard P. () [https://pattern.swarma.org/paper?id=70c8a48a-92c8-11ea-9f7f-0242ac1a0005 Etude de la distribution florale dans une portion des Alpes et du Jura].</ref>是于100多年前由Jaccard提出的，其定义为 <math>s_{xy}=\frac{|Γ(x)| \cap |Γ(y)|}{|Γ(x)| \bigcup  |Γ(y)|}</math>
-第4个指标Sorensen指标<ref name="4">Sørensen, T, Sørensen, T A, Sørensen, T J (1948) [https://pattern.swarma.org/paper?id=ea7f2902-6e74-11ea-9db3-0242ac1a0005 A method of establishing groups of equal amplitude in plant sociology based on similarity of species content and its application to analyses of the vegetation on Danish commons].</ref>常用于生态学研究，其定义为 <math>s{xy}=\frac{2 x |Γ(x)| \cap |Γ(y)|}{kx + ky}</math>
+第4个指标Sorensen指标<ref name="[4]">Sørensen, T, Sørensen, T A, Sørensen, T J (1948) [https://pattern.swarma.org/paper?id=ea7f2902-6e74-11ea-9db3-0242ac1a0005 A method of establishing groups of equal amplitude in plant sociology based on similarity of species content and its application to analyses of the vegetation on Danish commons].</ref>常用于生态学研究，其定义为 <math>s{xy}=\frac{2 x |Γ(x)| \cap |Γ(y)|}{kx + ky}</math>
-第5个指标大度节点有利指标<ref name="5">E. Ravasz,A. L. Somera,D. A. Mongru,Z. N. Oltvai,A. -L. Barabasi (2002) [https://pattern.swarma.org/paper?id=6eb98b7e-6e91-11ea-81b9-0242ac1a0005 Hierarchical organization of modularity in metabolic networks].arXiv:0209244.</ref>（Hub promoted index，HPI）被用来定量刻画新陈代谢网络中每对反应物的拓扑相似程度，其定义为 <math>s_{xy}=\frac{2 x |Γ(x)| \cap |Γ(y)|}{min\{k_x,k_y\}}</math>，由于分母只由度较小的节点决定，在此定义下可知大度节点（hub）与其他节点之间更容易具有高的相似性。
+第5个指标大度节点有利指标<ref name="[5]">E. Ravasz,A. L. Somera,D. A. Mongru,Z. N. Oltvai,A. -L. Barabasi (2002) [https://pattern.swarma.org/paper?id=6eb98b7e-6e91-11ea-81b9-0242ac1a0005 Hierarchical organization of modularity in metabolic networks].arXiv:0209244.</ref>（Hub promoted index，HPI）被用来定量刻画新陈代谢网络中每对反应物的拓扑相似程度，其定义为 <math>s_{xy}=\frac{2 x |Γ(x)| \cap |Γ(y)|}{min\{k_x,k_y\}}</math>，由于分母只由度较小的节点决定，在此定义下可知大度节点（hub）与其他节点之间更容易具有高的相似性。
-第6个指标大度节点不利指标<ref name="6">Tao Zhou,Linyuan Lu,Yi-Cheng Zhang (2009) [https://pattern.swarma.org/paper?id=7a2b26ba-6e92-11ea-9ee2-0242ac1a0005 Predicting Missing Links via Local Information].arXiv:0901.0553.</ref>（hub depressed index, HDI）定义与HPI相似，只是分母取两端节点度的最大值，即 <math>s_{xy}=\frac{2 x |Γ(x)| \cap |Γ(y)|}{max\{k_x,k_y\}}</math>。
+第6个指标大度节点不利指标<ref name="[6]">Tao Zhou,Linyuan Lu,Yi-Cheng Zhang (2009) [https://pattern.swarma.org/paper?id=7a2b26ba-6e92-11ea-9ee2-0242ac1a0005 Predicting Missing Links via Local Information].arXiv:0901.0553.</ref>（hub depressed index, HDI）定义与HPI相似，只是分母取两端节点度的最大值，即 <math>s_{xy}=\frac{2 x |Γ(x)| \cap |Γ(y)|}{max\{k_x,k_y\}}</math>。
-第7个指标LHN-I指标<ref name="7">E. A. Leicht,Petter Holme,M. E. J. Newman (2005) [https://pattern.swarma.org/paper?id=71890c4e-6f0e-11ea-b30e-0242ac1a0005 Vertex similarity in networks].arXiv:0510143.</ref>是由Leicht，Holme和Newman提出，其定义为 <math>s_{xy}=\frac{2 x |Γ(x)| \cap |Γ(y)|}{{k_xk_y}}</math>，其中分母<math>k_xk_y</math> 正比于节点<math>v_x</math>和节点<math>v_y</math>共同邻居数的期望值，即 <math>E( |Γ(x)| \cap |Γ(y)|)</math>。在下面这篇文献中，Leicht等人同时提出了另一个基于路径的指标，为了有所区别，将此局部指标命名为LHN-I指标，将基于路径的指标命名为LHN-II指标：
+第7个指标LHN-I指标<ref name="[7]">E. A. Leicht,Petter Holme,M. E. J. Newman (2005) [https://pattern.swarma.org/paper?id=71890c4e-6f0e-11ea-b30e-0242ac1a0005 Vertex similarity in networks].arXiv:0510143.</ref>是由Leicht，Holme和Newman提出，其定义为 <math>s_{xy}=\frac{2 x |Γ(x)| \cap |Γ(y)|}{{k_xk_y}}</math>，其中分母<math>k_xk_y</math> 正比于节点<math>v_x</math>和节点<math>v_y</math>共同邻居数的期望值，即 <math>E( |Γ(x)| \cap |Γ(y)|)</math>。在下面这篇文献中，Leicht等人同时提出了另一个基于路径的指标，为了有所区别，将此局部指标命名为LHN-I指标，将基于路径的指标命名为LHN-II指标：
 第8个指标PA（preferential attachment）是基于BA无标度网络模型中新加入节点倾向于和度大的节点相连的优先连接机制而提出的，在这种机制的链路预测中，每一步首先去除一条链接，然后再添加一条链接，新链接连接节点<math>v_x</math>和<math>v_y</math>的概率就正比于两节点度的乘积，由此可以定义两节点间的优先连接相似性：<math>s_{xy}= k_xk_y</math>
-第9个指标AA（Adamic-Adar）<ref name="8">Adar, Adamic L A, E (2003) [https://pattern.swarma.org/paper?id=e4726a06-6f2d-11ea-8846-0242ac1a0005 Friends and neighbors on the web].Social networks.25.(211--230)</ref>的基本思想是度小的共同邻居节点的贡献大于度大的共同邻居节点，因此根据共同邻居节点的度为每个节点赋予一个权重值。这一点很容易理解，例如在微博中受关注较多的人往往是某个领域的专家或名人，因此共同关注他们的人之间可能并不拥有特别相似的兴趣——一个中学生和一个企业家都有可能是姚晨的粉丝。相反，如果两个人共同关注了一个粉丝很少的人（非名人），那么说明这两个人确实具有相同的兴趣爱好或者重叠的社交圈，因此有更高概率相连。又如在推荐系统中，共同购买冷门产品的两个用户往往比共同购买热门产品的用户更相似。AA指标根据共同邻居节点的度为每个节点赋予一个权重值，该权重等于该节点的度的对数分之一，即AA指标的定义为：<math>s_{xy}=\sum _{z\in \Gamma (x)\bigcap \Gamma (y)}\frac{1}{logk_z}</math>。
+第9个指标AA（Adamic-Adar）<ref name="[8]">Adar, Adamic L A, E (2003) [https://pattern.swarma.org/paper?id=e4726a06-6f2d-11ea-8846-0242ac1a0005 Friends and neighbors on the web].Social networks.25.(211--230)</ref>的基本思想是度小的共同邻居节点的贡献大于度大的共同邻居节点，因此根据共同邻居节点的度为每个节点赋予一个权重值。这一点很容易理解，例如在微博中受关注较多的人往往是某个领域的专家或名人，因此共同关注他们的人之间可能并不拥有特别相似的兴趣——一个中学生和一个企业家都有可能是姚晨的粉丝。相反，如果两个人共同关注了一个粉丝很少的人（非名人），那么说明这两个人确实具有相同的兴趣爱好或者重叠的社交圈，因此有更高概率相连。又如在推荐系统中，共同购买冷门产品的两个用户往往比共同购买热门产品的用户更相似。AA指标根据共同邻居节点的度为每个节点赋予一个权重值，该权重等于该节点的度的对数分之一，即AA指标的定义为：<math>s_{xy}=\sum _{z\in \Gamma (x)\bigcap \Gamma (y)}\frac{1}{logk_z}</math>。
 第10种指标RA是受网络资源分配过程的启发，周涛等人提出的“'''资源分配指标 Resource allocation'''”，其与AA指标有异曲同工之妙。RA和AA指标最大的区别就在于赋予共同邻居节点权重的方式不同，前者是以 1/k 的形式递减，后者是以 1/logk 的形式递减。可见，当网络的平均度较小时，RA和AA差别不大；但是当平均度较大时，就有很大的区别了。研究显示，RA指标在刻画加权网络和社区挖掘应用中的表现胜过AA指标，图灵奖得主Hopdroft的一篇论文也显示，可以利用社区等中观结构信息改进局部指标，其中RA指标改进后的效果最佳。
@@ 第238行： / 第238行： @@
 *吕琳媛,任晓龙,周涛.《网络链路预测：概念与前沿》[J].《中国计算机学会通讯》,2016年,第4期
 *Clauset A, Moore C, Newman M E J. Hierarchical structure and the prediction of missing links in networks [J]. Nature, 2008,453(7191): 98-101.
 *Link Prediction Group 网站：http://www.linkprediction.org/

@@ 第22行： / 第22行： @@
-第2个指标Salton又称余弦相似性，其定义为 <math>s_{xy}=\frac{|Γ(x)| \cap |Γ(y)|}{\sqrt{k(x)k(y)}}</math>
+第2个指标Salton指标<ref name="">Salton G, McGill M J () [https://pattern.swarma.org/paper?id=15e10152-92c8-11ea-81db-0242ac1a0005 Introduction to Modern Information Retrieval].</ref>又称余弦相似性，其定义为 <math>s_{xy}=\frac{|Γ(x)| \cap |Γ(y)|}{\sqrt{k(x)k(y)}}</math>
-第3个指标Jaccard指标是于100多年前由Jaccard提出的，其定义为 <math>s_{xy}=\frac{|Γ(x)| \cap |Γ(y)|}{|Γ(x)| \bigcup  |Γ(y)|}</math>
+第3个指标Jaccard指标<ref name="">Jaccard P. () [https://pattern.swarma.org/paper?id=70c8a48a-92c8-11ea-9f7f-0242ac1a0005 Etude de la distribution florale dans une portion des Alpes et du Jura].</ref>是于100多年前由Jaccard提出的，其定义为 <math>s_{xy}=\frac{|Γ(x)| \cap |Γ(y)|}{|Γ(x)| \bigcup  |Γ(y)|}</math>
-第4个指标Sorensen指标常用于生态学研究，其定义为 <math>s{xy}=\frac{2 x |Γ(x)| \cap |Γ(y)|}{kx + ky}</math>
+第4个指标Sorensen指标<ref name="">Sørensen, T, Sørensen, T A, Sørensen, T J (1948) [https://pattern.swarma.org/paper?id=ea7f2902-6e74-11ea-9db3-0242ac1a0005 A method of establishing groups of equal amplitude in plant sociology based on similarity of species content and its application to analyses of the vegetation on Danish commons].</ref>常用于生态学研究，其定义为 <math>s{xy}=\frac{2 x |Γ(x)| \cap |Γ(y)|}{kx + ky}</math>
-第5个指标大度节点有利指标（Hub promoted index，HPI）被用来定量刻画新陈代谢网络中每对反应物的拓扑相似程度，其定义为 <math>s_{xy}=\frac{2 x |Γ(x)| \cap |Γ(y)|}{min\{k_x,k_y\}}</math>，由于分母只由度较小的节点决定，在此定义下可知大度节点（hub）与其他节点之间更容易具有高的相似性。
+第5个指标大度节点有利指标<ref name="">E. Ravasz,A. L. Somera,D. A. Mongru,Z. N. Oltvai,A. -L. Barabasi (2002) [https://pattern.swarma.org/paper?id=6eb98b7e-6e91-11ea-81b9-0242ac1a0005 Hierarchical organization of modularity in metabolic networks].arXiv:0209244.</ref>（Hub promoted index，HPI）被用来定量刻画新陈代谢网络中每对反应物的拓扑相似程度，其定义为 <math>s_{xy}=\frac{2 x |Γ(x)| \cap |Γ(y)|}{min\{k_x,k_y\}}</math>，由于分母只由度较小的节点决定，在此定义下可知大度节点（hub）与其他节点之间更容易具有高的相似性。
-第6个指标大度节点不利指标（hub depressed index, HDI）定义与HPI相似，只是分母取两端节点度的最大值，即 <math>s_{xy}=\frac{2 x |Γ(x)| \cap |Γ(y)|}{max\{k_x,k_y\}}</math>。
+第6个指标大度节点不利指标<ref name="">Tao Zhou,Linyuan Lu,Yi-Cheng Zhang (2009) [https://pattern.swarma.org/paper?id=7a2b26ba-6e92-11ea-9ee2-0242ac1a0005 Predicting Missing Links via Local Information].arXiv:0901.0553.</ref>（hub depressed index, HDI）定义与HPI相似，只是分母取两端节点度的最大值，即 <math>s_{xy}=\frac{2 x |Γ(x)| \cap |Γ(y)|}{max\{k_x,k_y\}}</math>。
-第7个指标LHN-I指标是由Leicht，Holme和Newman提出，其定义为 <math>s_{xy}=\frac{2 x |Γ(x)| \cap |Γ(y)|}{{k_xk_y}}</math>，其中分母<math>k_xk_y</math> 正比于节点<math>v_x</math>和节点<math>v_y</math>共同邻居数的期望值，即 <math>E( |Γ(x)| \cap |Γ(y)|)</math>。在下面这篇文献中，Leicht等人同时提出了另一个基于路径的指标，为了有所区别，将此局部指标命名为LHN-I指标，将基于路径的指标命名为LHN-II指标：
+第7个指标LHN-I指标<ref name="">E. A. Leicht,Petter Holme,M. E. J. Newman (2005) [https://pattern.swarma.org/paper?id=71890c4e-6f0e-11ea-b30e-0242ac1a0005 Vertex similarity in networks].arXiv:0510143.</ref>是由Leicht，Holme和Newman提出，其定义为 <math>s_{xy}=\frac{2 x |Γ(x)| \cap |Γ(y)|}{{k_xk_y}}</math>，其中分母<math>k_xk_y</math> 正比于节点<math>v_x</math>和节点<math>v_y</math>共同邻居数的期望值，即 <math>E( |Γ(x)| \cap |Γ(y)|)</math>。在下面这篇文献中，Leicht等人同时提出了另一个基于路径的指标，为了有所区别，将此局部指标命名为LHN-I指标，将基于路径的指标命名为LHN-II指标：
 第8个指标PA（preferential attachment）是基于BA无标度网络模型中新加入节点倾向于和度大的节点相连的优先连接机制而提出的，在这种机制的链路预测中，每一步首先去除一条链接，然后再添加一条链接，新链接连接节点<math>v_x</math>和<math>v_y</math>的概率就正比于两节点度的乘积，由此可以定义两节点间的优先连接相似性：<math>s_{xy}= k_xk_y</math>
-第9个指标AA（Adamic-Adar）的基本思想是度小的共同邻居节点的贡献大于度大的共同邻居节点，因此根据共同邻居节点的度为每个节点赋予一个权重值。这一点很容易理解，例如在微博中受关注较多的人往往是某个领域的专家或名人，因此共同关注他们的人之间可能并不拥有特别相似的兴趣——一个中学生和一个企业家都有可能是姚晨的粉丝。相反，如果两个人共同关注了一个粉丝很少的人（非名人），那么说明这两个人确实具有相同的兴趣爱好或者重叠的社交圈，因此有更高概率相连。又如在推荐系统中，共同购买冷门产品的两个用户往往比共同购买热门产品的用户更相似。AA指标根据共同邻居节点的度为每个节点赋予一个权重值，该权重等于该节点的度的对数分之一，即AA指标的定义为：<math>s_{xy}=\sum _{z\in \Gamma (x)\bigcap \Gamma (y)}\frac{1}{logk_z}</math>。
+第9个指标AA（Adamic-Adar）<ref name="">Adar, Adamic L A, E (2003) [https://pattern.swarma.org/paper?id=e4726a06-6f2d-11ea-8846-0242ac1a0005 Friends and neighbors on the web].Social networks.25.(211--230)</ref>的基本思想是度小的共同邻居节点的贡献大于度大的共同邻居节点，因此根据共同邻居节点的度为每个节点赋予一个权重值。这一点很容易理解，例如在微博中受关注较多的人往往是某个领域的专家或名人，因此共同关注他们的人之间可能并不拥有特别相似的兴趣——一个中学生和一个企业家都有可能是姚晨的粉丝。相反，如果两个人共同关注了一个粉丝很少的人（非名人），那么说明这两个人确实具有相同的兴趣爱好或者重叠的社交圈，因此有更高概率相连。又如在推荐系统中，共同购买冷门产品的两个用户往往比共同购买热门产品的用户更相似。AA指标根据共同邻居节点的度为每个节点赋予一个权重值，该权重等于该节点的度的对数分之一，即AA指标的定义为：<math>s_{xy}=\sum _{z\in \Gamma (x)\bigcap \Gamma (y)}\frac{1}{logk_z}</math>。
 第10种指标RA是受网络资源分配过程的启发，周涛等人提出的“'''资源分配指标 Resource allocation'''”，其与AA指标有异曲同工之妙。RA和AA指标最大的区别就在于赋予共同邻居节点权重的方式不同，前者是以 1/k 的形式递减，后者是以 1/logk 的形式递减。可见，当网络的平均度较小时，RA和AA差别不大；但是当平均度较大时，就有很大的区别了。研究显示，RA指标在刻画加权网络和社区挖掘应用中的表现胜过AA指标，图灵奖得主Hopdroft的一篇论文也显示，可以利用社区等中观结构信息改进局部指标，其中RA指标改进后的效果最佳。