复杂网络链路预测

第３９卷第５期　２０１０年９月　电子科技大学学报　Ｊｏｕｒｎａｌ　ｏｆ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｅｌｅｃｔｒｏｎｉｃ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｙ　ｏｆ　Ｃｈｉｎａ　Ｖｌｏ１．３９　ＮＯ．５　Ｓｅｐ．２０１０　复杂网络链路预测　吕琳媛　（弗里堡大学物理系瑞士弗里堡　ＣＨ－１７００）　【摘要】网络中的链路预测是指如何通过已知的网络结构等信息预测网络中尚未产生连边的两个节点之间产生连接的可　能性。预测那些已经存在但尚未被发现的连接实际上是一种数据挖掘的过程，而对于未来可能产生的连边的预测则与网络的　演化相关。传统的方法是基于马尔科夫链或者机器学习的，往往考虑节点的属性特征。该类方法虽然能够得到较高的预测精　度，但是由于计算的复杂度以及非普适性的参数使其应用范围受到限制。另一类方法是基于网络结构的最大似然估计，该类　方法也有计算复杂度高的问题。相比上述两种方法，基于网络结构相似性的方法更加简单。通过在多个实际网络中的实验发　现，基于相似性的方法能够得到很好的预测效果，并且网络的拓扑结构性质能够帮助选择合适的相似性指标。该文综述并比　较了若干有代表性的链路预测方法，展望了若干重要的开放性问题。　关键词复杂网络；链路预测；最大似然估计；概率模型；相似性指标　中图分类号ＴＰ３９１　文献标识码Ａ　ｄｏｉ：１０．３９６９￣．ｉｓｓｎ．１００１．０５４８．２０１０．０５．００２　Ｌｉｎｋ　Ｐｒｅｄｉｃｔｉｏｎ　ｏｎ　Ｃｏｍｐｌｅｘ　Ｎｅｔｗｏｒｋｓ　ＬＵ　Ｌｉｎ—ｙｕａｎ　（Ｄｅｐａｒｔｍｅｎｔ　ｏｆＰｈｙｓｉｃｓ，Ｕｎｉｖｅｒｓｉｔｙ　ｏｆＦｒｉｂｏｕｒｇ　Ｆｒｉｂｏｕｒｇ　Ｓｗｉｔｚｅｒｌａｎｄ　ＣＨ－１７００）　Ａｂｓｔｒａｃｔ　Ｌｉｎｋ　ｐｒｅｄｉｃｔｉｏｎ　ａｉｍｓ　ａｔ　ｅｓｔｉｍａｔｉｎｇ　ｔｈｅ　ｌｉｋｅｌｉｈｐｏｄ　ｏｆ　ｔｈｅ　ｅｘｉｓｔｅｎｃｅ　ｏｆ　ｌｉｎｋｓ　ｂｅｔｗｅｅｎ　ｎｏｄｅｓ．Ｔｈｅ　ｐｒｅｄｉｃｔｉｎｇ　ｏｆ　ｅｘｉｓｔｅｎｔ　ｙｅｔ　ｕｎｋｎｏｗｎ　ｌｉｎｋｓ　ｉＳ　ｓｉｍｉｌａｒ　ｔｏ　ｈｅ　ｄａｔｔａ　ｍｉｎｉｎｇ　ｐｒｏｃｅｓｓ．ｗｈｉｌｅ　ｔｈｅ　ｐｒｅｄｉｃｔｉｎｇ　ｏｆ　ｆｕｔｕｒｅ　Ｉｉｎｋｓ　ｒｅｌａｔｅｓ　ｔｏ　ｈｅ　ｔｎｅｔｗｏｒｋ　ｅｖｏｌｕｔｉｏｎ．Ｔｈｅ　ｔｒａｄｉｔｉｏｎａｌ　ｍｅｔｈｏｄｓ　ａｒｅ　ｂａｓｅｄ　ｏｎ　Ｍａｒｋｏｖ　Ｃｈａｉｎｓ　ａｎｄ　ｍａｃｈｉｎｅ　ｌｅａｒｎｉｎｇ　ｗｈｉｃｈ　ｕｓｕａｌｌｙ　ｉｎｖｏｌｖｅ　ｔｈｅ　ｎｏｄｅ　ａｔｔｒｉｂｕｔｅｓ　ｉｎｆｏｒｍａｔｉｏｎ。Ａ１ｔｈｏｕｇｈ　ｔｈｅｓｅ　ｍｅｔｈｏｄｓ　Ｃａｎ　ｇｉｖｅ　ｇｏｏｄ　ｐｒｅｄｉｃｔｉｏｎ．ｔｈｅ　ｈｉｇｈ　ｃｏｍｐｕｔａｔｉｏｎａｌ　ｃｏｍｐｌｅｘｉｔｙ　ｌｉｍｉｔｓ　ｔｈｅｉｒ　ａｐｐｌｉｃａｔｉｏｎｓ　ｉｎ　ｌａｒｇｅ—ｓｃａｌｅ　ｓｙｓｔｅｍｓ．Ｔｈｅ　ａｐｐｒｏａｃｈｅｓ　ｂａｓｅｄ　ｏｎ　ｍａｘｉｍｕｍ　ｌｉｋｅｌｉｈｏｏｄ　ａｐｐｒｏｘｉｍａｔｉｏｎ　ａｌｓｏ　ＳＵｆｆｅｒ　ｔｈｉｓ　ｓｈｏｒｔｃｏｍｉｎｇ．Ａｎｏｔｈｅｒ　ｇｒｏｕｐ　ｏｆ　ｍｅｔｈｏｄｓ　ｉＳ　ｂａｓｅｄ　ｏｎ　ｔｈｅ　ｎｏｄｅ　ｓｉｍｉｌａｒｉＷ　ｔｈａｔ　ｉｓ　ｄｅｆｎｅｄ　ｉｓｏｌｅｌｙ　ｂａｓｅｄ　ｏｎ　ｔｈｅ　ｎｅｔｗｏｒｋ　ｓｔｒｕｃｔｕｒｅ．Ｅｘｔｅｎｓｉｖｅ　ｅｘｐｅｒｉｍｅｎｔｓ　ｏｎ　ｍａｎｙ　ｒｅａｌ　ｎｅｔｗｏｒｋｓ　ｓｈｏｗ　ｔｈａｔ　ｔｈｅ　ｓｉｍｉｌａｒｉｙ—ｔｂａｓｅｄ　ｍｅｔｈｏｄｓ　Ｃａｎ　ｇｉｖｅ　ｇｏｏｄ　ｐｒｅｄｉｃｔｉｏｎ　ｗｈｉｌｅ　ｗｉｔｈ】ｏｗｅｒ　ｃｏｍｐｕｔａｔｉｏｎａｌ　ｃｏｍｐｌｅｘｉｙ　ｃｏｍｐａｒｔｎｇ　ｗｊｉｔｈ　ｔｈｅ　ａｂｏｖｅ　ｔｗｏ　ｋｉｎｄｓ　ｏｆ　ｍｅｔｈｏｄｓ．Ｔｈｉｓ　ａｒｔｉｃｌｅ　ｉｎｔｒｏｄｕｃｅｓ　ａｎｄ　ｃｏｍｐａｒｅｓ　ｍａｎｙ　ｒｅｐｒｅｓｅｎｔａｔｉｖｅ　ｌｉｎｋ　ｐｒｅｄｉｃｔｉｏｎ　ｍｅｔｈｏｄｓ　ｎｄ　ａｏｕｔｌｎｅｓ　ｉｓｏｍｅ　ｍｐｏｒｉｔａｎｔ　ｏｐｅｎ　ｐｒｏｂｌｅｍｓ，ｗｈｉｃｈ　ｍａｙ　ｂｅ　ｖａｌｕａｂｌｅ　ｆｏｒ　ｒｅｌａｔｅｄ　ｒｅｓｅａｒｃｈ　ｄｏｍａｉｎｓ．　Ｋｅｙ　ｗｏｒｄｓ　ｃｏｍｐｌｅｘ　ｎｅｔｗｏｒｋｓ：ｌｎｋ　ｐｒｅｄｉｉｃｔｉｏｎ；ｍａｘｉｍｕｍ　ｌｉｋｅｌｉｈｐｏｄ　ａｐｐｒｏｘｉｍａｔｉｏｎ；ｐｒｏｂａｂｉｌｉｓｔｉｃ　ｍｏｄｅｌ；　ｓｉｍｉｌａｒｉｔｙ　ｎｄｅｘ　ｉ网络中的链路预Ｎ（１ｉｋ　ｎｐｒｅｄｉｃｔｉｏｎ），既包含了对　方法还有很多，如文献［５］利用网络的拓扑结构信息　以及节点的属性，建立了一个局部的条件概率模型　进行预测。文献［６】基于节点的属性定义了节点间的　未知链接（ｅｘｉｓｔｅｎｔ　ｙｅｔ　ｕｎｋｎｏｗｎ　ｌｉｎｋｓ）的预测，也包含　了对未来链接（ｆｕｔｕｒｅ　ｌｉｋｓ）的预测。链路预测作为数　ｎ据挖掘领域的研究方向之一在计算机领域已有较深　入的研究，研究的思路和方法主要基于马尔科夫链　相似性，可以直接用于进行链路预测。虽然应用节　点属性等外部信息的确可以得到很好的预测效果，　但是很多情况下，信息的获得是非常困难的，甚至　和机器学习。文献［２】应用马尔科夫链进行网络的链　路预测和路径分析。之后，文献［３］将基于马尔科夫　链的预测方法扩展到自适应性网站（ａｄａｐｔｉｖｅ　ｗｅｂ　是不可能的，如很多在线系统的用户信息都是保密　的。另外，即使获得了节点的属性信息，也很难保　证信息的可靠性，即属性是否反映了节点的真实情　况，如在线社交网络中，很多用户的注册信息都是　ｓｉｔｅｓ）的预测中。此外，文献［４］提出一个回归模型在　文献引用网络中预测科学文献的引用关系，方法不　仅用到了引文网络的信息，还有作者信息、期刊信　息以及文章内容等外部信息。应用节点属性的预测　收稿Ｉｔ期：２０１０—０７—１８　虚假的。更进一步，在能够得到节点属性的精确信　息的情况下，如何鉴别出哪些信息对网络的链路预　基金项目：瑞士国家科￣（２０００２０．１２１８４８）；国家自然科学基金（１　１０７５０３１）　作者简介：吕琳媛（１９８４一），女，博士生，主要从事信息物理，包括链路预测、推荐算法以及网络结点排序等方面的研究　６５２　电子科技大学学报　第３９卷　测是有用的，哪些信息是没用的，仍然是个问题。　最近几年，基于网络结构的链路预测方法受到　个手机用户是否产生了切换运营商（如从移动到联　通）的念头Ｌ１引。另外文献［１０】所提出的对网络中的错　越来越多的关注。相比节点的属性信息而言，网络　的结构更容易获得，也更加可靠。同时，该类方法　对于结构相似的网络具有普适性，从而避免了对不　同网络需要机器学习获得一些特定的参数组合。文　误链接的预测，对于网络重组和结构功能优化也有　重要的应用价值，如在很多构建生物网络的实验中　存在暧昧不清甚至自相矛盾的数据【ｌ　，就有可能应　用链路预测的方法对其进行纠正。　献［７］提出了基于网络拓扑结构的相似性定义方法，　并分析了若干指标对社会合作网络中链路预测的效　链路预测研究不仅具有广泛的实际应用价值，　也具有重要的理论研究意义，特别是对一些相关领　果。另外～类链路预测方法是基于网络结构的最大　似然估计。２００８年，文献［８］提出了一种利用网络的　层次结构进行链路预测的方法，并在具有明显层次　结构的网络中表现很好。此外，利用随机分块模型　Ｊ预测网络缺失边和错误边的链路预测方法。值得　一提的是，该篇文章第一次提到网络错误连边　（ｓｐｕｒｉｏｕｓ　ｌｉｎｋｓ）的概念，即在网络已知的链接中很可　能存在一些错误的链接，比如人们对蛋白质相互作　用关系的错误认知。　链路预测问题受到来自不同领域、拥有不同背　景的科学家的广泛关注，首先是因其重大的实际应　用价值。如在生物领域研究中，蛋白质相互作用网　络和新陈代谢网络，节点之间是否存在链接，或者　说是否存在相互作用关系，是需要通过大量实验结　果进行推断的。已知的实验结果仅仅揭示了巨大网　络的冰山一角。仅以蛋白质相互作用网络为例，酵　母菌蛋白质之间８　０％的相互作用不为人们所　知【】”，而对于人类自身，人们知道的仅有可怜的　Ｏ．３％【　引。由于揭示该类网络中隐而未现的链接需　要耗费高额的实验成本，如果能够事先在已知网络　结构的基础上设计出足够精确的链路预测算法，再　利用预测的结果指导试验，就有可能提高实验的成　功率，从而降低实验成本，并加快揭开该类网络真　实面目的步伐。实际上，社会网络分析中也会遇到　数据不全的问题，链路预测同样可以作为准确分析　社会网络结构的有力的辅助工具【ｌ¨　。除了帮助分　析数据缺失的网络，链路预测算法还可以用于分析　演化网络。如近几年在线社交网络发展非常迅速【Ｊ　ｂＪ，　链路预测可以基于当前的网络结构预测哪些现在尚　未结交的用户“应该是朋友”，并将此结果作为“朋　友推荐”发送给用户。如果预测足够准确，显然有　助于提高相关网站在用户心目中的地位，从而提高　用户对该网站的忠诚度。另外，链路预测的思想和　方法，还可以用于在已知部分节点类型的网络　（ｐａｒｔｉａｌｌｙ　ｌａｂｅｌｅｄ　ｎｅｔｗｏｒｋｓ）中预测未标签节点的类　型，如用于判断一篇学术论文的类型Ｌｌ　或者判断一　域理论方面的推动和贡献。近年来，随着网络科学　的快速发展，其理论上的成果为链路预测搭建了一　个研究的平台，使得链路预测的研究与网络的结构　与演化紧密联系起来。因此，对于预测的结果更能　够从理论的角度进行解释。与此同时，链路预测的　研究也可以从理论上帮助人们认识复杂网络演化的　机制。针对同一个或者同一类网络，很多模型都提　供了可能的网络演化机制【２ｍ　¨。由于刻画网络结构　特征的统计量非常多，很难比较不同的机制孰优孰　劣。链路预测机制有望为演化网络提供～个简单统　一且较为公平的比较平台，从而大大推动复杂网络　演化模型的理论研究。另外，如何刻画网络中节点　的相似性也是一个重大的理论问题【２　，该问题和网　络聚类等应用息息相关【２引。类似，相似性的度量指　标数不胜数，只有能够快速准确地评估某种相似性　定义是否能够很好地刻画一个给定网络节点间的关　系，才能进一步研究网络特征对相似性指标选择的　影响，因此，链路预测可以起到核心技术的作用。　链路预测问题本身也带来了有趣且有重要价值的理　论问题，就是通过构造网络系综（ｎｅｔｗｏｒｋ　ｅｎｓｅｍｂｌｅ），　并借此利用最大似然估计方法进行链路预测的可能　性和可行性研究，对链路预测本身以及复杂网络研　究的理论基础的建立和完善起到推动和借鉴作用。　１　问题描述与评价方法　定义Ｇ（Ｖ，Ｅ）为一个无向网络，其中　节点集　合，Ｅ为边集合。网络总的节点数为Ⅳ，边数为　该网络共有Ｎ（Ｎ一１）／２个节点对，即全集　。给定　一种链路预测的方法，对每对没有连边的节点对　，　（∈　＼Ｅ）赋予一个分数值　，然后将所有未连接　的节点对按照该分数值从大到小排序，排在最前面　的节点对出现连边的概率最大。　为了测试算法的准确性，将已知的连边Ｅ分为训　练集　和测试集　两部分。在计算分数值时只能使　用测试集中的信息。显然，Ｅ＝Ｅ　ＵＥ　，且　ｎ　Ｅ　＝（２ｊ。在此，将属于　不属于Ｅ的边定义为不　第５期　吕琳嫒：复杂网络链路预测　６５３　存在的边。衡量链路预测算法精确度的指标有ＡＵＣ、　简单直接的方法就是利用节点的属性，如果两个人　具有相同的年龄、性别、职业、兴趣等等，就说他　Ｐｒｅｃｉｓｉｏｎ￣ＨＲａｎｋｉｎｇ　Ｓｃｏｒｅ共３种。它们对预测精确度　衡量的侧重点不同：ＡＵＣ（ａｒｅａ　ｕｎｄｅｒ　ｔｈｅ　ｒｅｃｅｉｖｅｒ　ｏｐｅｒａｔｉｎｇ　ｃｈａｒａｃｔｅｒｉｓｔｉｃ　ｃｕｒｖｅ）从整体上衡量算法的精　确度【　】；Ｐｒｅｃｉｓｉｏｎ只考虑对排在前三位的边是否预测　准确【　１；而Ｒａｎｋｉｎｇ　Ｓｃｏｒｅ更多考虑对所预测的边的　排序　。　们俩很相似。利用节点属性的相似性进行链路预测　的前提，就是网络中的边本身代表着相似。另外一　类相似性的定义完全基于网络的结构信息，称为结　构相似性。基于结构相似性的链路预测精度的高低　取决于该种结构相似性的定义是否能够很好地抓住　目标网络的结构特征。如基于共同邻居的相似性指　ＡＵＣ可以理解为在测试集中的边的分数值有比　随机选择的一个不存在的边的分数值高的概率，也　就是说，每次随机从测试集中选取一条边与随机选　择的不存在的边进行比较，如果测试集中的边的分　数值大于不存在的边的分数值，就加１分；如果两个　分数值相等，就３ｎ０．５分。独立地比较　次，如果有ｒｔ　次测试集中的边的分数值大于不存在的边的分数，　有ｎ　次两分数值相等，则ＡＵＣ定义为：　Ａｕｃ：竺：±　：　ｎ　显然，如果所有分数都是随机产生的，ＡＵＣ＝Ｏ．５。　因此ＡＵＣ大于０．５的程度衡量了算法在多大程度上　比随机选择的方法精确。　Ｐｒｅｃｉｓｉｏｎ定义为在前三个预测边中被预测准确　的比例。如果有ｍ个预测准确，即排在前三的边中有　ｍ个在测试集中，￣３ＪＰｒｅｃｉｓｉｏｎ定义为：　ＰｒｅｃｉｓｉＯｎ：一ｍ　显然，Ｐｒｅｃｉｓｉｏｎ越大预测越准确。如果两个算法ＡＵＣ　相同，而算法ｌ的Ｐｒｅｃｉｓｉｏｎ大于算法２，说明算法ｌ更　好，因为其倾向于把真正连边的节点对排在前面。　Ｒａｎｋｉｎｇ　Ｓｃｏｒｅ主要考虑测试集中的边在最终排　序中的位置。令Ｈ＝Ｕ—Ｅ　为未知边的集合（相当于　测试集中的边和不存在的边的集合），　表示未知边　ｉ∈Ｅ　在排序中的排名。则该条未知边的Ｒａｎｋｉｎｇ　Ｓｃｏｒｅ值为ＲＳ　＝，：／ｌ　Ｉ，其中１　ｌ表示集合日中元素　的个数遍历所有在测试集中的边，得到系统的　Ｒａｎｋｉｎｇ　Ｓｃｏｒｅ值为：　Ｒｓ　南　南　￣，上Ｉ　Ｈ　Ｉ　２基于相似性的链路预测　应用节点间的相似性进行链路预测的一个重要　前提假设就是两个节点之间相似性（或者相近性）越　大，它们之间存在链接的可能性就越大。应注意，　相似性并非一般意义上的相似性，而是指一种接近　程度（ｐｒｏｘｉｍｉｔｙ）。刻画节点的相似性有多种方法，最　标，即两个节点如果有更多的共同邻居就更可能连　边，在集聚系数较高的网络中表现非常好，有时甚　至超过一些更复杂的算法。然而对于集聚系数较低　的网络如路由器网络或电力网络等，预测精度就差　很多。　２．１基于局部信息的相似性指标　基于局部信息的最简单的相似性指标是共同邻　居（ｃｏｍｍｏｎ　ｎｅｉｇｈｂｏｒｓ），也就是说两个节点如果有更　多的共同邻居，则它们更倾向于连边。在共同邻居　的基础上考虑两端节点度的影响，从不同的角度以　不同的方式又可产生６种相似性指标，分别是Ｓａｌｔｏｎ　指标　（也叫做余弦相似性）、Ｊａｃｃａｒｄ指标　、　ＳｏｒｅｎｓｏＭＲ标【２　１、大度节点有利指标（ｈｕｂ　ｐｒｏｍｏｔｅｄ　ｉｎｄｅｘ）　】、大度节点不利指标（ｈｕｂ　ｄｅｐｒｅｓｓｅｄ　ｉｎｄｅｘ）　和ＬＨＮ－Ｉ指标ｔ　（由Ｌｅｉｃｈｔ，Ｈｏｌｍｅ和Ｎｅｗｍａｎ提出　而得名１，称这一类指标为基于共同邻居的相似性。　另一个只考虑节点度的相似性为优先连接指标　（ｐｒｅｆｅｒｅｎｔｉａｌ　ａ￣ａｃｈｍｅｎｔ）。应用优先连接的方法可以　产生无标度的网络结构，在该网络中，一条即将加　入的新边连接到节点　的概率正比于节点　的度　）Ｄ¨，因此新边连接节点　和ｙ的概率正比于两节点　度的乘积。该算法的复杂度较其他算法低，因为需　要的信息量最少。　如果考虑两节点共同邻居的度信息，有Ａｄａｍｉｃ—　Ａｄａｒ（ＡＡ）￣ｇ【３引，其思想是度小的共同邻居节点的　贡献大于度大的共同邻居节点。因此根据共同邻居　节点的度为每个节点赋予一个权重值，该权重等于　该节点的度的对数分之一，即１／ｌｇ　ｋ。　文献［３３１从网络资源分配（ｒｅｓｏｕｒｃｅ　ａｌｌｏｃａｔｉｏｎ）的　角度提出一种新的指标，简称ＲＡ。考虑网络中没有　直接相连的两个节点　和ｙ，从　可以传递一些资源到　Ｙ，而在此过程中，它们的共同邻居就成为传递的媒　介。假设每个媒介都有一个单位的资源并且将平均　分配传给它的邻居，则），可以接收到的资源数就定义　为节点　和ｙ的相似度。ＲＡ和ＡＡ指标最大的区别在　于赋予共同邻居节点权重的方式不同，前者以１／ｋ的　６５４　电子科技大学学报　第３９卷　形式递减，后者以ｌ／ｌｇ　ｋ的形式递减。可见，当网络　表３　１０种基于节点局部信息的相似性　的平均度较小时ＲＡ和ＡＡ差别不大，但是当平均度较　大时，就有很大的区别了。　表１总结了以上１Ｏ种基于局部信息的相似性指　标的定义公式。对于网络中的节点　，定义它的邻居　在６个网络链路预测中的精度比较　０　９３７　０．８９８　０．９０１　０．９０２　为厂　），七（　）＝Ｉ厂（　）Ｉ为节点　的度。　表１　１Ｏ种基于节点局部信息的相似性指标　一Ｏ　Ｏ　０　Ｏ　Ｏ　Ｏ　Ｏ　Ｏ　Ｏ　Ｏ　—一９　罟昌　罟９　８　昌３８　８　宕　骢　跎鼹鲫　８　６　８　８　Ｏ　文献［３３］将上述ｌ０种基于节点局部信息的相似　一Ｏ　Ｏ　Ｏ　Ｏ　０　０　Ｏ　Ｏ　Ｏ　０　性指标在６个实际网络中进行实验，并比较其预测精　—　一３　１　３　３●３　ｌ　３　２　３　确度【３引。６个网络分别为：蛋白质相互作用网络　１一（一　一Ｏ　５　鼹　Ｏ　Ｏ　０　５　０　Ｏ　Ｏ　５　鳃　Ｏ　６　Ｏ　Ｏ　０　０　Ｏ　（ＰＰＩ）、科学家合作网络　Ｓ）、美国电力网络（Ｇｒｉｄ）、　政治博客网络（ＰＢ）、路由器网络（　Ｔ）以及美国航空　陋一一　５　Ｏ　４　０　肿２２　２　０　罨罟Ｏ　罨　Ｏ　７　Ｏ　２　刀册　Ｏ　７　Ｏ　２　Ｏ　Ｏ　网络（ＵＳＡｉｒ），它们的统计性质如表２所示。其中Ⅳ、　分别表示网络的节点数和边数，Ｎｃ为网络的最大　联通集团，如２　３７５／Ｔ～一　９２表示ＰＰＩ网络中有９２个联通集　团，最大联通集包含２　３７５个节点，　为网络的效率，　Ｃ为网络集聚系数，，．为同配系数，日为网络度异质　性。预测结果如表３所示。所有结果均以ＡＵＣ为预测　精度评价指标。可见在ｌ０种算法中，ＲＡ表现最好，　其次是ＣＮ，再次是ＡＡ。总的来说，ＰＡ表现最差，　特别是在电力网络和路由器网络中，预测精度还不　Ｎｏ．５，意味着ＰＡ算法在这两个网络中预测精度还不　如完全随机预测的好。　表２　６个实验网络的拓扑性质　Ｎｅｔｗｏｒｋｓ　Ｎ　Ｍ　Ｎｃ　ｅ　Ｃ　ｒ　Ｈ　ＰＰＩ　２　６１７　１　１　８５５　２　３７５／９２　０．１８Ｏ　０．３８７　０．４６１　３．７３　ＮＳ　ｌ　４６１　２　７４２　３７９／２６８　０．０１６　０．８７８　０　４６２　１　８５　Ｇｒｉｄ　４　９４１　６　５９４　４　９４１／１　０　０６３　０．１０７　０　００３　ｌ　４５　ＰＢ　ｌ　２２４　１９　０９０　１　２２２／２　０　３９７　０。３６１－ｏ．０７９　３．１３　ＩＮＴ　５　０２２　６　２５８　５　０２２／１　０．１６７　０．０３３－－０．１３８　５．Ｏ５　ＵＳＡｉｒ　３３２　２　１　２６　３３２／１　０．４０６　０．７４９－０．２０８　３．４６　０．８５７　０　８９５　０．７５８　０　８８６　０　９２５　０　９５５　２．２基于路径的相似性指标　基于路径的相似性指标有３个，分别是局部路径　指标（ＬＰ）［３４］、Ｋａｔｚ￣＇ｇ［　］￣ＨＬＨＮ．ＩＩ［　】于旨标（与ＬＨＮ，Ｉ　在同一篇文章中提出）。　（１）局部路径指标（１ｏｃａｌ　ｐａｔｈ），ＬＰ是在共同邻居　指标的基础上考虑三阶邻居的贡献，其定义为　Ｓ＝Ａ　＋　／４　，其中　为可调节参数，用于控制三　阶路径的作用，当　＝０时，ＬＰ指标就等于ＣＮ；Ａ　为网络的邻接矩阵。注意，（　）　，表示节点　和），之　间长度为，？的路径数。　（２）Ｋａｔｚ￣标考虑的是所有的路径数，且对于短　路径赋予较大的权重，而长路径赋予较小的权重，　它定义为Ｓ＝　＋　Ａ　＋　Ａ　…＝（，一ｆｌＡ）～一１，　其中　为权重衰减因子，为了保证数列的收敛性，　的取值须小于邻接矩阵　最大特征值的倒数。　（３）ＬＨＮ—ＩＩ指标￣ｌｌＫａｔｚ参数类似，也是考虑所有　路径，所不同的是ＬＨＮ．ＩＩ中每一项不再是（　）　而变为（Ａ　）　／Ｅ［（Ａ　）　】，其中Ｅ【　）　］＝　』　为节点　和ｙ之间长度为　的路径数的期望值。整理后　得到ＬＨＮ—ＩＩ的最终表达式为Ｓ＝　／－　＾Ｊ　１　Ｍ＆Ｄ　ｌ　一　／Ｉ　Ｄ～，其中　为　的最大特征值，‘　　为参数取值小于１（具体推导过程参见文献［２２１）。　运用上述３种基于路径的相似性指标进行链路　预测，分别用ＡＵＣ￣ｌｌＰｒｅｃｉｓｉｏｎ（Ｌ＝１００）进行评价，结　果如表４和表５所示。ＬＰ的结果是在最优参数　时得　到的；ＬＰ　的结果是在固定参数　＝０．０１时得到的。　由于美国航空网络特殊的层次结构，在ＵＳＡｉｒ网络中　设定　＝－０．０１　１。从表中可以看出，运用ＡＵＣ作为　评价指标时，基于全局信息的Ｋａｔｚ￣标表现最好，　特别是在电力网络￣ｌｌｌｎｔｅｍｅｔ路由器网络中，ＡＵＣ可　达Ｎｏ．９５以上。其次，局部路径算法表现也不错，　比如在ＰＰＩ￣ＩＩＰＢ网络中，可以达到与Ｋａｔｚ指标差不多　好的预测精度，甚至在ＰＢ和ＵＳＡｉｒ网络中表现比　第５期　吕琳媛：复杂网络链路预测　６５５　Ｋａｔｚ￣标还好。其原因在于ＰＢ和ＵＳＡｉｒ网络的平均　此相隔较近的节点更容易连边。由此定义基于ＡＣＴ　最短距离很小，因此基于三阶路径的Ｌ时旨标比基于　全部路径的Ｋａｔｚ指标能够更好地符合网络的结构特　点。同理，在电力网络中，平均最短路径为１６，此　时只考虑三阶路径的ＬＰ指标就不够精确了。关于平　的相似性为（在此可忽略常数Ｊ）ｌ　：　ＡＣＴｍ—南　（２）基于随机游走的余弦相似性（Ｃｏｓ＋）。在由向　量１，　＝Ａ２Ｕ　ｅ　展开的欧式空间内，　中的元素　，可　均最短路径和最优路径长度的关系在文献［３６］中有　详细讨论。　表４基于路径的相似性指标在使用ＡＵＣ衡量时　的预测精度Ｅ匕较　ＡＵＣ　ＬＰ　表示为两个向量　和　的内积，即　＝　Ｔ＇，　，其中　是一个标准正交矩阵，是由　特征向量按照对应　的特征根从大到小排列所得，　为以特征根为对角　元素的对角矩阵，上标Ｔ表示矩阵转置，ｅ　表示一　个一维向量且只有第　个元素为１，其他都为０。由此　定义余弦相似性【３８Ｊ为：　，　ＣＯＳ　ＰＰＩ　０．９７０　ＮＳ　０．９８８　Ｇｒｉｄ　０　６９７　ＰＢ　０　９４１　Ｄ　Ｔ　０　９４３　ＵＳＡ　０．９６０　ＬＰ＊Ｋａｔｚ　ＬＨＮ．Ⅱ０．９７０　０．９７２　０．９６８　０９８８　０　９８８　０．９８６　０６９７　０　９５２　０．９４７　０．９３９　０　９３６　０．７６９　０　９４１　０　９７５　０　９５９　０　９５９　０　９５６　０　７７８　＝ｃｏｓ（ｘ，　）　＝　表５基于路径的相似性指标在使用Ｐｒｅｃｉｓｉｏｎ衡量时　ｘｖ／ｌ　＋ｌ　＋　（３）重启的随机游走（ｒａｎｄｏｍ　ｗａｌｋ　ｗｉｔｈ　ｒｅｓｔａｒｔ）　简称ＲＷＲ。该指标可以看成是网页排序算法　（ＰａｇｅＲａｎｋ）的拓展应用　，其假设随机游走粒子每　走一步时都以一定概率返回初始位置。设粒子返回　概率为ｌ＿ｃ，Ｐ为网络的马尔科夫概率转移矩阵，其　的预测精度比较　Ｐｒｅｃｉｓｉｏｎ　ＬＰ　ＬＰ＊Ｋａｔｚ　ＰＰＩ　０．７３４　０．７３４　０．７１９　ＮＳ　０　２９２　０．２９２　０．２９０　Ｇｒｉｄ　‘０．１３２　０．１３２　０　０６３　ＰＢ　０．５１９　０．４６９　０．４５６　ＩＮＴ　０．５５７　０．１２ｌ　０．３６８　ＵＳＡｔｒ　０．６２７　０．６２７　０　６２３　ＬＨＮ一Ⅱ　Ｏ　０　０６０　０００５　０　０　０．００５　元素　＝　／　表示节点　处的粒子下一步走到节　另外，在计算复杂度方面，由于ＬＰ指标只考虑局　部信息，其计算复杂度比考虑全局信息的　她和　的概率。如果　相连则ａｘｙ＝ｌ，否则为０。某一　粒子初始时刻在节点ｘ处，则　１时刻该粒子到达网　络各个节点的概率向量为：　ｑｘ（ｔ＋１）＝ｃＰ　（ｆ）＋（１一ｃ）ｅｘ　ＬＨＮ—ＩＩ要小很多。ＬＰ的计算复杂度约为Ｄ（ＪＶ（七）。），　而Ｋａｔｚ￣标和ＬＨＮ一Ⅱ指标的计算复杂度均为Ｏ（Ｎ’）。　可见，对于规模巨大（Ⅳ大）且较稀疏（平均度（七）小）的　网络，ＬＰ指标在计算速度上具有明显的优势。　２．３基于随机游走的相似性指标　式中　ｅ　表示初始状态（其定义与ｃｏｓ＋中相同）。不难　得到上式的稳态解为　＝（１一ｃ）（　一ｃＰ　）　，其中　有一类相似性算法是基于随机游走定义的，包　括平均通勤时间（ａｖｅｒａｇｅ　ｃｏｍｍｕｔｅ　ｔｉｍｅ）［　Ｊ、Ｃｏｓ＋指　标【３８ｊ、有重启的随机游走（ｒａｎｄｏｍ　ｗａｌｋ　ｗｉｔｈ　元素ｇ　，为从节点　出发的粒子最终以多少概率走到　节点ｙ。由此定义ＲＷＲ相似性为：　＝‰＋ｇ　ｒｅｓｔａｒｔ）［。　、ＳｉｍＲａｎｋ指标　们，以及新提出的两种基　于局部随机游走的指标ｐ引。　关于ＲＷＲ的一种快速算法参见文献【４１】，该指　标已被应用于推荐系统的算法研究中　１。　（４）ＳｉｍＲａｎｋ￣标简称ＳｉｍＲ。它的基本假设是，　如果两节点所连接的节点相似，则该两节点相似　。　它的自洽定义式为：　（１）平均通勤时间（ａｖｅｒａｇｅ　ｃｏｍｍｕｔｅ　ｔｉｍｅ）简称　ＡＣＴ。设ｍ（ｘ，ｙ）为一个随机粒子从节点　到节点　需　．要走的平均步数，则节点　和Ｙ的平均通勤时间定　义为：　ｎ（ｘ，　）＝ｍ（ｘ，　）＋ｍ（ｙ，　）　曼　ＳｉｍＲ＿Ｃ型　一　其数值解可通过求该网络拉普拉斯矩阵的伪逆　获得Ｉ　Ｊ，即：　式中假定Ｓ　＝１；ｃ∈［Ｏ，１］为相似性传递时的衰减　参数。ＳｉｍＲ￣标可以用于描述两个分别从节点　和ｙ　出发的粒子何时相遇。　ｎ（ｘ，　）＝　（　＋，ｗ十一２　）　式中　，　表示矩阵　中相应位置的元素。可以说，　如果两个节点的平均通勤时间越小，则两个节点越　（５）局部随机游走指标（１ｏｃａｌ　ｒａｎｄｏｍ　ｗａｌｋ）简　称ＬＲＷ【３引。该指标与上述４种基于随机游走的相似　性不同，其只考虑有限步数的随机游走过程。一个　接近。通常，网络被观察到有普遍的集聚效应，因　６５６　电子科技大学学报　第３９卷　粒子ｔ时刻从节点　出发，定义　，（ｆ）为件１时刻这个　粒子正好走到节点Ｙ的概率，那么可得到系统演化　方程：　ｘｘ（ｔ＋１）＝Ｐ　（ｆ）　ｆ≥０　复杂度为Ｏ（Ｎ。），而ＬＲｗ和ＳＲｗ为０（Ⅳ（七）　），其中　刀为随机游走步数。由此可以推算，对于ＮＳ网络来　说，计算ＲＷＲ的时间复杂度要ＬＬＳＲＷ慢ｌ　０００多倍，　而ＡＵＣ只提高了千分之一。　表７　４种基于随机游走的算法在使用ＡＵＣ衡量时　的预测精度比较　式中　石　（０）为一个Ｎｘ１的向量，只有第　个元素为　１，其他为０，即万　（０）＝ｅ　。设定各个节点的初始资　源分布为ｇ　，基于ｆ步随机游走的相似性为：　（ｆ）＝　・　（ｆ）＋ｇ　・刀　（ｆ）　文献【３６］给出了一种与度分布一致的初始资源　分布，即ｑ　＝　／Ｍ，并在此基础上进行了大量实　验，实验结果如表７和表８所示。ＬＲＷ相似性由于只　考虑了有限步数的随机游走，该算法的计算复杂度　相比较基于全局随机游走的ＡＣＴ、ＲＷＲ、Ｃｏｓ＋以及　ＳｉｍＲ算法都要小很多，因此对于规模较大、较稀疏　的网络非常适用。　（６）叠加的局部随机游走指标（ｓｕｐｅｒｐｏｓｅｄ　ｒａｎｄｏｍ　ｗａｌｋ）￣，ＳＲＷ【３６Ｊ。在ＬＲＷ的基础上将　步及　其以前的结果加总便得到ＳＲＷ的值，即：　ＳＲＷ（ｆ）＝∑　（１＝１　，）＝　∑　（１＝１　，）＋　∑　（１＝ｔ　，）　这个指标的目的就是给邻近目标节点的点更多　的机会与目标节点相连。　文献［３６］比较了上述两种基于局部随机游走和　基于全局随机游走的ＡＣＴ和ＲＷＲ指标在５个不同领　域的网络中的链路预测效果。该５个网络分别为美国　航空网络（ＵＳＡｉｒ）、科学家合作网　Ｓ）、电力网络　（Ｇｒｉｄ）、蛋白质相互作用网络（ＰＰＩ）和线虫神经网络　（Ｃ．ｅｌｅｇａｎｓ），其拓扑结构的统计特性展现于表６。注　意，与节３．１中数据不同的是，这里只考虑了最大联　通集。（七）和（　）分别表示平均度和平均最短距离。　表６　ｓｔ网络最大连通集的统计特征　Ｎｅｔｗｏｒｋｓ　Ｎ　Ｍ　（七）　（　）　Ｃ　ｒ　Ｈ　ＵＳＡｉｒ　３３２　２１２６　１２．８０７　２　４６　０　７４９　－－０　２０８　３　４６４　ＮＳ　３７９　９４１　４．８２３　４　９３　０．７９８　－４）．０８２　１．６６３　Ｇｒｉｄ　４９４ｌ　６５９４　２．６６９　ｌ５．８７　０　ｌ０７　０．００３　１．４５０　ＰＰＩ　２３７５　ｌ１６９３　９．８４７　４．５９　０．３８８　０．４５４　３　４７６　Ｃ　ｅｌｅｇａｎｓ　２９７　２１４８　１４．４５６　２　４６　０　３０８　－４３　１６３　１．８０１　表７和表８总结了４种基于随机游走的相似性的　链路预测精度，分别用ＡＵＣ和Ｐｒｅｃｉｓｉｏｎ衡量。括号　中的数字表示ＬＲＷ和Ｓ　Ⅳ指标所对应的最优行走　步数。可见，除了ＮＳ网络以外，ＬＲＷ和ＳＲＷ指标无　论ＡＵＣ还是Ｐｒｅｃｉｓｉｏｎ都好于ＡＣＴ和ＲＷＲ指标。而在　ＮＳ网络中，虽然Ｒ、　Ｒ表现稍好，但是其计算复杂度　远远大于ＬＲＷ和ＳＲＷ指标。由于ＡＣＴ和ＲＷＲ的计算　ＡＵＣ　ＵＳＡｉｒ　ＮＳ　Ｇｒｉｄ　ＰＰ１　Ｃ．ｅｌｅｇａｎｓ　ＡＣＴ　０　９０ｌ　０．９３４　０．８９５　０．９００　０．７４７　ＲＷ霹　０．９７７　０　９９３　０，７６０　０．９７８　０．８８９　ＬＲＷ　Ｏ．９７２（２）　Ｏ　９８９（４）Ｏ．９５３（１６）Ｏ．９７４（７）　０　８９９（３）　ＳＲＷ　０．９７８　ｆ３１　０　９９２ｆ３１　０．９６３ｆ１６１　０　９８０ｆ８、　０９０６ｆ３、　表８　４种基于随机游走的算法在使用Ｐｒｅｃｉｓｉｏｎ衡量时　的预测精度比较　２．４权重在链路预测中的作用　含权网络的链路预测是一个较重要的方向，但　到目前为止还没有系统的研究工作，对于如何更好　地运用权重的信息以提高链路预测的精确度还没有　明确的答案。文献【４３］将３种局部算法ＣＮ、ＡＡ和ＲＡ　拓展为含权形式，定义如下：　。　＝　ｗ（　，ｚ）　＋ｗ（ｚ，ｊ，）　ｚ　ｒ　【ｙ　ＷＡＡ—　ｗ（ｘ，ｚ）　＋ｗ（ｚ，　）　厂　厂ｌ（　）ｌｇ（１＋　（ｚ））　ｗＣＮ—　ｗ（ｘ，ｚ）　＋ｗ（ｚ，．ｙ）　一ｚ厶：Ｅ　ｒ（　ｘ）ｆｌｒ（ｙ）　。＼（ｚ）　　式中　ｗ（ｘ，Ｙ）为连接节点　和Ｙ的连边的权重；　（　）：　ｗ（ｘ，　）　为节点　的强度；　参数用于调　＝　）　节权重在预测中的作用。当　＝０时，ＷＣＮ、ＷＡＡ　和ＷＲＡ指标分别回到各自不含权的形式（参见节３．１　中的定义）。在３个实际网络中，运用３种含权指标进　行链路预测，结果发现在链路预测中也存在弱连接　效应【４引，即给原来权重较低的边赋予较大的权重，　而原来权重大的边赋予较小的权重（ｒｅｄｉｓｔｒｉｂｕｔｉｏｎ），　用新的权重会得到更好的预测效果。美国航空网络　的预测结果如图１所示。在美国航空网络中，城市机　场代表节点，航线代表边，边的权重由两机场间航　班的飞行频次决定。从图中得到３种含权算法的最优　参数　均小于０，意味着原来权重大的边在链路预测　中的作用变小了，而原来权重小的边作用反而增大　了，即所谓的弱连接效应。　第５期　吕琳媛：复杂网络链路预测　６５７　图１　美国航空网络预测精度与参数　的关系　此外，在科学家合作网中也发现了弱连接效应。　但是在Ｃ．ｅｌｅｇａｎｓ线虫神经网络中结果恰恰相反，其　最优参数值均大于１，意味着只有更加强调强连接，　弱化弱连接，可称为链路预测的强连接效应，才能　得到更好的预测结果。文献［４３】随后运用ｍｏｔｉｆ￣析　方法定性解释了造成差异的原因，但是还不能进行　定量的描述。含权网络的预测方法研究还具有很大　的拓展空间，同样的网络结构，不同的含权方式在　实际预测中起到的作用也可能不一样。要搞清这些　问题，还需要更加深入细致的研究工作。　３基于最大似然估计的链路预测　链路预测的另一类方法是基于最大似然估计　的。文献【８］认为，很多网络的连接可以看作某种内　在的层次结构的反映，基于此，文献【８】提出了一种　最大似然估计算法进行链路预测，该方法在处理具　有明显层次组织的网络ｆ如恐怖袭击网络和草原食　物链）时具有较好的精确度。但是，由于每次预测要　生成很多个样本网络，因此其计算复杂度非常高，　只能处理规模不太大的网络。文献【１Ｏ］假设观察到的　网络是一个随机分块模型（ｓｔｏｃｈａｓｔｉｃ　ｂｌｏｃｋ　ｍｏｄｅ１）［　１　的一次实现，在该模型中节点被分为若干集合，两　个节点间连接的概率只与相应的集合有关。文献【１０］　所提出的基于随机分块模型的链路预测方法，可以　得到更好的结果。同时，该方法不仅可以预测缺失　边，还可以预测网络的错误链接，如纠正蛋白质相　互作用网络中的错误链接。基于最大似然估计方法　的一个最大问题是计算复杂度太高，因此并不适合　在规模较大的网络中应用。　３．１层次结构模型１　１　对实际网络结构的实证研究表明，在很多情况　下，网络具有一定的层次结构［３０，４５－４６１。因此，某个　含有Ⅳ个节点的网络可以由一个含有Ⅳ个叶子节点　￣ＨＮ－１个内部节点的树状图表示。每个内部节点赋　予一个概率值Ｐ，（∈【０，１］），而两个节点相连接的概率　就等于距离它们最近的共同祖先节点所赋予的概　率。一个用树形结构表示的含有５个节点的网络层次　结构如图２所示。由图可见节点１和节点２连接的概率　为０．５，节点ｌ和节点３连接的概率为０．３，节点３与节　点４连接的概率为０．４。　Ｏ　３　图２用树形图表示网络的层次结构示例　给定一个网络Ｇ及和它相对应的一个树形图Ｄ，　则这个树形图对目标网络Ｇ的似然估计值为：　Ｌ（Ｄ，｛　））＝丌　（１一Ｐｒ）　肆一　式中　三，和Ｒ分别表示以内部节点，．为根的左子树　和右子树的叶子节点数目；Ｅ表示以ｒ为最近共同祖　先的节点对在Ｇ中已形成连边的节点对数目；对于　给定的Ｄ，使似然估计值最大的最优概率　Ｐ：＝Ｅ／（Ｌ　），并按此给Ｄ的每个内部节点赋概率ｒ￣　值；对于网络Ｇ的多个树形图，Ｌ（Ｄ，｛　））越大表示　该树形图对网络的刻画越真切。由于能够得到最大　似然估计值的树形图不止一个，因此要考虑多个树　形图的平均结果。采用马尔科夫链蒙特卡洛算法可　得到一组可用于链路预测的树形图，具体步骤如下：　（１）首先给定一个树形图，并按照公式　Ｐ．＿Ｅ／（　Ｒ）给每个内部节点赋概率值。　（２）随机选择一个内部节点厂并考虑以其兄弟　节点为根节点的子树集合　和以其儿女节点为根节　点的子树集合Ｃ。　（３）通过交换子树集合　和Ｃ中的子树获得新　的树状图Ｄ　，注意Ｄ和Ｄ　不同。　（４）从所有可能的Ｄ　中随机选择一个，当　ＩｇＬ（Ｄ＇）≥ｌｇｔ（Ｄ）时接受新树状图　，否则以　Ｌ（Ｄ　）／　（Ｄ）的概率接受Ｄ　。然后重新回到第（２）步。　（５）当该马尔科夫链收敛于平稳时，开始生成可　６５８　电子科技大学学报　第３９卷　用的树形图，如５　０００个。　最终，网络中未连边的两个节点　和ｙ可能连边　结构模型好，尤其是在预测错误连边时。但是它与　层次模型同样都存在计算时间复杂度高的问题。　的概率为所有树形图中两节点连接概率的平均值　（　，）。然后将所有未连边的节点对按照连接概率从　大到小排列，排在最前面的出现连边的概率越大。　实验结果显示，该方法对于有明显层次结构的　网络表现尚好，如恐怖袭击网络和草原食物链网络，　而对于层次结构不明显的网络，如科学家合作网和　４概率模型　运用概率模型进行链路预测的基本思路就是建　立一个含有一组可调参数的模型，然后使用优化策　略寻找最优的参数值，使得所得到的模型能够更好　地再现真实网络的结构和关系特征，网络中两个未　线虫神经网络，表现还不如最简单的共同邻居算法，　具体比较参见文献［３６】。另外，从链路预测实用性的　角度来讲，该方法的计算时间复杂度较大，通常使　马尔科夫链收敛需要Ｏ（Ｎ　）步，而每一步都至少要　执行上述步骤（２）至步骤（４）一次。因此不适用于规模　较大的网络。　３．２随机分块模型【ｌ　随机分块模型也是一种基于最大似然估计的方　法，其基本思想是根据网络具有模块性的特点，将　网络的节点分组，而每两个节点是否连边是由它们　所在的组决定的。已知目标网络的节点数为Ⅳ，运用　随机分块模型进行链路预测，首先需将　个节点分　组，然后给每个组对赋予一个连接概率Ｑ　（∈【０，ｌ】），　由此建立一个分块模型　。根据该分块模型可以得　到在组　内的节点ｆ和在组　内的节点，连接的概率　ｐ（　＝１ＩＭ）＝　。该分块模型对目标网络的可靠　性为：　ｐ（Ａｌ　）＝兀　（西　１一　）　式中　为目标网络的邻接矩阵；　为原网络中组　内的节点与组　内的节点连边的数量；　为组　内的节点与组　内的节点一共可连边的数量。可见　该方法与层次结构模型的公式基本一致，其最优概　率　＝　。按上述方法生成所有可能的分块模　型　最终由贝叶斯定理得到节点　阳节点，的连边的　可信度为：　＝ｐ（　＝１ｆＡ）＝　，　Ｉ　』　ｐ（　＝１ｌＭ）ｐ（ＡＩＭ）ｐ（Ｍ）ｄＭ　，　Ｉ　ｊ　ｐ（Ａ　ｌ　Ｍ　）ｐ（　）ｄＭ　式中　为所有可能的分块模型集合（实际运算中　并不需要真正考虑所有的）。为方便计算，可将　（　）　设定为一个常数。可信度越高表示越可能连边。随　机分块模型不仅可以预测缺失边，还可以根据可信　度判断哪些边是错误连边，如对蛋白质相互作用关　系的错误认识。随机分块模型平均而言表现比层次　连边的节点对连边的概率就等于在该组最优参数下　它们之间产生连边的条件概率。如果将边的存在性　（存在或不存在）看成是边的一种属性，那么链路预测　问题就转变为预测边的属性问题【４　】。两个常用的框　架为概率关系模型框架（ｐｒｏｂａｂｉｌｉｓｔｉｃ　ｒｅｌａｔｉｏｎａｌ　ｍｏｄｅｌｓ）［４８１和有向无环概率实体关系框架（ｄｉｒｅｃｔｅｄ　ａｃｙｃｌｉｃ　ｐｒｏｂａｂｉｌｉｓｔｉｃ　ｅｎｔｉｔｙ　ｒｅｌａｔｉｏｎｓｈｉｐ）ｔ４９１。它们的区　别在于对数据库的表达方式不同，前者基于关系模　型（ｒｅｌａｔｉｏｎａｌ　ｍｏｄｅｌｓ），后者基于实体关系模型（ｅｎｔｉｙｔ．　ｒｅｌａｔｉｏｎｓｈｉｐ　ｍｏｄｅ１）。　概率模型的优势在于较高的预测精确度，它不　仅使用了网络的结构信息还涉及节点的属性信息。　但是计算的复杂度以及非普适性的参数使其应用范　围受到限制。　４．１概率关系模型０＇ＲｌＶＩｓ）　概率关系模型是将概率模型和关系模型相结合　的一种预测模型。概率关系模型包括３个网络：（１）数　据网络（ｄａｔａ　ｇｒａｐｈ）ｔｉＰ所谓的训练集，包含原始的数　据信息；（２）模型网络（ｍｏｄｅｌ　ｇｒａｐｈ），分析数据网络　得到的用于刻画网络主体属性之间的关系，该种关　系既包括一类主体内部属性之间的关系，也包括不　同主体属性之间的关系；（３）推理网络（ｉｎｆｅｒｅｎｃｅ　ｇｒａｐｈ），是将模型网络与目标网络（测试集）相结合的　网络，用于对目标网络的预测。根据模型网络的不　同构造方法又可将概率关系模型分为贝叶斯网络关　系模型（ｒｅｌａｔｉｏｎａｌ　ｂａｙｅｓｉａｎ　ｎｅｔｗｏｒｋｓ）ｔ　Ｊ、马尔科夫网　络关系模型（ｒｅｌａｔｉｏｎａｌ　ｍａｒｋｏｖ　ｎｅｔｗｏｒｋｓ）［５￣１和关系依　赖网络模型（ｒｅｌａｔｉｏｎａｌ　ｄｅｐｅｎｄｅｎｃｙ　ｎｅｔｗｏｒｋｓ）ｐ　弱】。　（１）贝叶斯网络模型　ＢＮ）　川。贝叶斯网络　Ｇ（Ｖ，Ｅ，ｐ）为一有向无环图，由条件概率分布和网络　结构两部分组成。其中Ｖ＝｛　，ｖ３，…，　＞为节点集合，　每个节点代表一个变量，即数据网络中所涉及的属　性变量，Ｅ为有向边集合，表示变量之间的关系；Ｐ　为一组条件概率，ｐ（ｖ　Ｉ　（　））表示节点ｖ的父亲节点　ｐａ（ｖ）点对其的影响。如果一条有向边从节点对旨向　第５期　吕琳嫒：复杂网络链路预测　６５９　节点ｙ，则节点　可视为节　的父亲，于是该贝叶斯　网络的联合概率分布为：　０　ＥＣｏｕｒｓｅ￣…＜　［ｃｏｕｒｓｅ　凰　ｃｏｕｒｓｅ［Ｇｒ　ａｄｅ　Ｉ　】ｒ　１ｐ（ｖｌ，ｖ２，…，ｖ）＝ＩＩ百　　Ｐ（Ｖｉ　Ｉ　ｐ口（　））　（２）马尔科夫网络模型　）　。马尔科夫网　络Ｇ（Ｖ，Ｅ，　）为一无向图，允许环存在。其中　ⅡＥ　◇…辜　Ｑ＿Ｇｒａｄｅ．￣）　．ｓｅ　［１）ｃｏｕｒ＼　ｒｓｅ“　Ⅱ　＇洲∞　眦Ｌ　　。…　＂仍表示变量和变量关系集合，　表示潜能函数。定　义ｃ为网络中完全子图的集合，每一个完全子图对应　ｓｔｕｄｅｎｔ［Ｇｒａｄｅ　ｓｔ￣ａ．ｅｎｔ！　Ｃ　ＩＱ　｛　】：　ｌＩＱ】＝　Ｅ　兰　咖　ｍ删司　ｂ．ＰＲＭＳ模型　ａ．ＤＡＰＥＲ模型　图３　以大学数据中学生和课程为例的　一个潜能函数　，于是网络的联合概率分布为　１——　ｐ（ｖｌ，　，…，　）＝专几　（厶　　），其中　表示完全子图　ｃ中的节点，ｚ为标准归一化函数。　（３）关系依赖网络模型　ＤＮ）　引。关系依赖网络　模型与上述两个模型的最大区别在于其不用优化整　个联合概率分布，而是运用伪似然估计（ｐｓｅｕｄｏ．　１ｉｋｅｌｉｈｏｏｄ）［５４１方法分别对每个变量的条件概率进行　估计，也就是说在估计条件概率ｐ（ｖ　Ｉ　ｐａ（ｖ））时并不　考虑条件概率ｐ（ｐａ（ｖ）Ｉ　ｖ）。由于对变量的估计是独　立的，相比Ｉ　Ｎ和ＲＭＮ模型其计算复杂度降低很　多。ＲＤＮ与ＲＢＮ相似，也是用有向图表示属性之间　的依赖关系，但是其允许环的存在。　４．２　有向无环概率实体关系模型（ＤＡＰＥＲ）　叫　ＤＡＰＥＲ是以实体关系模型为基础所建立的模　型，它将实体之间的关系也看成和实体一样重要。　ＤＡＰＥＲ模型包括６类组成成分。　（１）实体类（ｅｎｔｉｔｙ　ｃｌａｓｓｅｓ），即网络的实体，如大　学数据库中的学生类和课程类。　（２）关系类（ｒｅｌａｔｉｏｎｓｈｉｐ　ｃｌａｓｓｅｓ），即描述实体问　的关系，如学生选择课程中的选择关系。　（３）属性类（ａｔｔｒｉｂｕｔｅ　ｃｌａｓｓｅｓ），即实体或者关系的　属性，如学生的智商，课程的难易程度等。　（４）弧线类（ａｒｃ　ｃｌａｓｓｅｓ），用于描述各个属性之间　的关系，如学生的课程分数受到学生智商和课程难　度的影响。属性关系构成的网络为有向无环网络ｆ与　ＲＢＮ类似）。　（５）局部概率分布类（１ｏｃａｌ　ｄｉｓｔｒｉｂｕｔｉｏｎ　ｃｌａｓｓｅｓ），　对某一属性类的条件概率分布，与ＰＲＭｓ中的条件概　率类似。　（６）限制条件类（ｃｏｎｓｔｒａｉｎｔ　ｃｌａｓｓｅｓ），衡量属性关　系之间的限制条件。　文献［４９】比较了该模型与ＰＲＭｓ模型的区别和联　系。图３展现了在学生选择课程的例子中分别用　ＤＡＰＥＲ和ＰＩ　Ｍｓ建立的模型，分别如图３ａ和３ｂ所示。　ＤＡＰＥＲ模型和ＰＲＭｓ模型　５总结与展望　综上所述，无论是基于结构的相似性预测方法　还是基于最大似然估计的方法，或是概率模型本质　上都是通过对已知数据的尽可能真切的刻画的方法　实现预测，但是它们的角度各自不同。基于结构相　似性的方法只涉及网络的结构信息，主要从某一个　角度对于网络的某一方面的结构特点进行刻画，如　果目标网络的结构在该方面特征显著，即可得到较　好的预测效果。虽然基于网络结构相似性的方法比　较简单，计算复杂度相对较低，特别是基于局部结　构的算法，但是各个方法在不同网络中的预测能力　大不相同。目前还没有对算法性能和网络结构特征　之间关系较深入的研究。对于比较复杂的网络，如　含权网络、有向网络、多部分网络以及含有异质边　的网络，如何通过结构信息进行预测的讨论甚少且　不系统［４３，５５－５６１。基于最大似然估计的方法虽然也是　基于网络结构的，但是其针对的是整个网络结构而　不仅仅局限于某一方面。该类方法由于计算复杂度　较高，不可能应用于规模较大的网络。实验显示该　类方法的预测精度也不是很高。概率模型是数据挖　掘的传统模型，它可以同时考虑网络的结构信息和　节点的属性信息，以求得到更好的预测效果。　但是　计算的复杂性以及节点外在属性信息在获取上的难　度，造成该类方法应用的局限性。　最近十年，复杂网络研究在很多科学分支，包　括物理、生物、计算机等掀起高潮　１，其中相当一　部分研究立足于揭示网络演化的内在驱动因素。仅　以无标度网络（ｓｃａｌｅ．ｆｒｅｅ　ｎｅｔｗｏｒｋｓ）Ｎ｛￣Ｊ］ｐ圳，已经报道　的可以产生幂律度分布的机制就包括了富者愈富　（ｒｉｃｈ—ｇｅｔ．ｒｉｃｈｅｒ）机制１３１１、好者变富（ｇｏｏｄ—ｇｅｔ－ｒｉｃｈｅｒ）　机制　、优化设计（ｏｐｔｉｍａｌ　ｄｅｓ　ｎ）驱动ｌ　、哈密顿　动力学（ｈａｍｉｌｔｏｎｉａｎ　ｄｙｎａｍｉｃｓ）驱动【６“、聚生（ｍｅｒｇｉｎｇ　ａｎｄ　ｒｅｇｅｎｅｒａｔｉｏｎ）机制【６　、稳定性限制（ｓｔａｂｉｌｉｙｔ　ｃｏｎｓ仃ａｉｎｔＳ）驱动【∞】，等等。可是，由于刻画网络结　电子科技大学学报　第３９卷　构特征的统计指标非常多，很难比较和判定什么样　１０９．１３７．　的机制能够更好再现真实网络的生长特性。利用链　路预测有望建立简单的比较平台，能够在知道目标　网络演化情况的基础上，量化比较各种不同机制对　于真实生长行为的预测能力，从而可以大大推动复　杂网络演化机制的相关研究。　与此同时，受益于复杂网络研究的快速发展，　基于网络结构的链路预测方法有望在网络理论的帮　『１　０１　ＧＵＩＭＥＲＡ　Ｒ，ＳＡＬＥＳ一　ＬＲＤ０　Ｍ．Ｍｉｓｓｉｎｇ　ａｎｄ　ｓｐｕｒｉｏｕｓ　ｉｎｔｅｒａｃｔｉｏｎｓ　ａｎｄ　ｔｈｅ　ｒｅｃｏｎｓｔｒｕｃｔｉｏｎ　ｏｆ　ｃｏｍｐｌｅｘ　ｎｅｗｏｒｔｋｓ［Ｊ１．　Ｐｒｏｃ　Ｎａｔｌ　Ｓｃｉ　Ａｃａｄ　ＵＳＡ．２００９．１　０６（５２）：２２０７３．２２０７８．　【１１】Ｙｕ　Ｈ，ＢＲＡＵＮ　Ｙ１ＬＤＩ砌Ｍ　Ｍ　Ａ，ｅｔ　ａｌ　Ｈｊ　一ｑｕａ】ｊｔｙ　ｂｉｎａｒｙ　ｐｒｏｔｅｉｎ　ｉｎｔｅｒａｃｔｉｏｎ　ｍａｐ　ｏｆ　ｔｈｅ　ｙｅａｓｔ　ｉｎｔｅｒａｃｔｏｍｅ　ｎｅｔｗｏｒｋ『Ｊ１．Ｓｃｉｅｎｃｅ，２００８，３２２（５８９８）：１０４．１　ｌＯ　『１２１　ＳＴＵＭＰＦ　Ｍ　Ｐ　Ｈ，ＴＨＯＲＮＥ　ＳＩＬ　～Ｅ　ｄｅ，ｅｔ　ａ１．　Ｅｓｔｉｍａｔｉｎｇ　ｈｅ　ｔｓｉｚｅ　ｏｆ　ｈｅｔ　ｈｕｍａｎ　ｉｎｔｅｒａｃｔｏｍｅ［Ｊ］．Ｐｒｏｃ　Ｎａｔｌ　Ｓｃｉ　Ａｃａｄ　ＵＳＡ。２００８，ｌ０５（１９）：６９５９　６９６４．　助下得到发展和完善。一方面是如何以网络系综理　论为基础，建立网络链路预测的理论框架，并产生　对实际预测有指导作用的理论结论，如通过对网络　结构的统计分析估算各个方法的可预测的极限，从　而指导选择最佳的预测方法等：另一方面是如何通　过网络的结构信息，借助复杂网络的分析工具，设　计高效的算法处理大规模网络的链路预测问题。　尽管已有一些论文讨论了如何将链路预测的方　法和思想与一些应用问题（如部分标号网络的节点　类型预测【１９’　】与信息推荐问题【。　，　）相联系的可　能性与方法，但是，目前尚缺乏对于大规模真实数　据在应用层面的深入分析和研究。这方面的研究不　仅仅具有实用价值，而且有助于揭示链路预测问题　本身存在的优势与局限性。　参考文献　【ｌ】ＧＥＴＯＯＲ　Ｌ，ＤＩＥＨＬ　ｃ　Ｐ　Ｌｉｎｋ　ｍｉｎｉｎｇ：ａ　ｓｕｒｖｅｙ［Ｊ］．ＡＣＭ　ＳＩＧＫＤＤ　Ｅｘｐｌｏｒａｔｉｏｎｓ　Ｎｅｗｓｌｅｔｔｅｒ，２００５，７（２）：３．１　２．　【２】ＳＡＲＩ　ＫＡＩ　Ｒ　Ｒ．Ｌｉｎｋ　ｐｒｅｄｉｃｔｉｏｎ　ａｎｄ　ｐａｔｈ　ａｎａｌｙｓｉｓ　ｕｓｉｎｇ　ｍａｒｋｏｖ　ｃｈａｉｎｓ［Ｊ］．Ｃｏｍｐｕｔｅｒ　Ｎｅｔｗｏｒｋｓ，２０００，３３（１—６）：　３７７　３８６．　［３】ｚＨＵ　Ｊ，Ｈ０ＮＧ　Ｊ，ＨｕＧＨＥＳ　Ｊ　Ｇ　Ｕｓｉｎｇ　ｍａｒｋｏｖ　ｃｈａｉｎｓ　ｆｏｒ　ｌｉｎｋ　ｐｒｅｄｉｃｔｉｏｎ　ｉｎ　ａｄａｐｔｉｖｅ　ｗｅｂ　ｓｉｔｅｓ［Ｊ］．Ｌｅｃｔ　Ｎｏｔｅｓ　Ｃｏｍｐｕｔ　Ｓｃｉ．２００２．２３　ｌｌ：６０．７３．　『４１４　ＰＯＰＥＳＣＵＬ　Ａ，【ＪＮＧＡＲ　Ｌ．Ｓｔａｔｉｓｔｉｃａｌ　ｒｅｌａｔｉｏｎａｌＪｅａｒｎｉｎｇ　ｆｏｒ　ｌｉｎｋ　ｐｒｅｄｉｃｔｉｏｎ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　Ｗｏｒｋｓｈｏｐ　ｏｎ　Ｌｅａｒｎｉｎｇ　Ｓｔａｔｉｓｔｉｃａｌ　Ｍｏｄｅｌｓ　ｆｒｏｍ　Ｒｅｌａｔｉｏｎａｌ　Ｄａｍ．Ｎｅｗ　Ｙ＿０ｒｋ　ＡＣＭ　Ｐｒｅｓｓ．２００３：８１－８７．　『５１　Ｏ’ＭＡＤＡＤＨＡＩＮ　Ｊ，ＨＵＴＣＨｒＮＳ　Ｊ，ＳＭＹＴＨ　Ｐ　Ｐｒｅｄｉｃｔｉｏｎ　ａｎｄ　ｒａｎｋｉｎｇ　ａｌｇｏｒｉｔｈｍｓ　ｆｏｒ　ｅｖｅｎｔ．ｂａｓｅｄ　ｎｅｔｗｏｒｋ　ｄａｔａ［Ｃｌ＃　Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　ＡＣＭ　ＳＩＧＫＤＤ　２００５．Ｎｅｗ　Ｙｏｒｋ：ＡＣＭ　Ｐｒｅｓｓ．２００５：２３．３Ｏ．　【６】ＬＩＮ　Ｄ．Ａｎ　ｉｎｆｏｒｍａｔｉｏｎ－ｈｔｅｏｒｅｔｉｃ　ｄｅｆｉｎｉｔｉｏｎ　ｏｆ　ｓｉｍｉｌａｒｉｔｙ［Ｃ】／／　Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　１　５ｔｈ　Ｉｎｆｌ　Ｃｏｎｆ　Ｍａｃｈ．Ｌｅａｒｎ．．Ｓａｎ　Ｆｒａｎｃｉｓｃｏ．Ｍｏｒｇａｎ　Ｋａｕｆｍａｎ　Ｐｕｂｌｉｓｈｅｒｓ。ｌ９９８：２９６．３０４．　『７１　ＬＩＢＥＮ．Ｎ０ＷＥＬＬ　Ｄ，ＫＬＥＩＮＢＥＲＧ　Ｊ．Ｔｈｅ　ｌｉｎｋ．ｐｒｅｄｉｃｔｉｏｎ　ｐｒｏｂｌｅｍ　ｆｏｒ　ｓｏｃｉａｌ　ｎｅｔｗｏｒｋｓ［Ｊ１．Ｊ　Ａｍ　Ｓｏｃ　ＩｎｆｏＦｉｎ　Ｓｃｉ　Ｔｅｃｈｎｏｌ，２００７，５８（７）：１０１９．１０３１．　ｆ８１　ＣＬＡＵＳＥＴ　Ａ，Ｍ００ＲＢ　Ｃ，ＮＥ　ＡＮ　Ｍ　Ｅ　Ｊ．Ｈｉｅｒａｒｃｈｉｃａｌ　ｓｔｒｕｃｔｕｒｅ　ａｎｄ　ｈｔｅ　ｐｒｅｄｉｃｔｉｏｎ　ｏｆ　ｍｉｓｓｉｎｇ　ｌｉｎｋｓ　ｉｎ　ｎｅｔｗｏｒｋｓ［Ｊ］．　Ｎａｔｕｒｅ　２００８．４５３：９８．１０１．　『９１　ＨＯＬＬＡＮＤ　Ｐ　Ｗ　ＬＡＳＫＥＹ　Ｋ　Ｂ，ＬＥＩＮＨＡＲＤ　Ｓ．Ｓｔｏｃｈａｓｔｉｃ　ｂｌｏｃｋｍｏｄｅｌｓ：Ｆｉｒｓｔ　ｓｔｅｐｓ［Ｊ１．Ｓｏｃｉａｌ　Ｎｅｗｔｏｒｋｓ，ｌ　９８３，５：　【１３】ＡＭＡＲＡＬ　Ｌ　Ａ　Ｎ．Ａ　ｔｒｕｅｒ　ｍｅａｓｕｒｅ　ｏｆ　ｏｕｒ　ｉｇｎｏｒｎａｃｅ［Ｊ］．　Ｐｒｏｃ　Ｎａ廿Ｓｃｉ　Ａｃａｄ　ＵＳＡ，２００８。１　０５（１　９　：６７９５．６７９６．　ｆ　ｌ４１　ＳＣＨＡＦＥＲ　Ｌ，ＧＲＡＨＡＭ　Ｊ　Ｗ　Ｍｉｓｓｉｎｇ　ｄａｔａ：０ｕｒ　ｖｉｅｗ　ｏｆ　ｔｈｅ　ｓａｔｔｅ　ｏｆ　ｔｈｅ　ａｒｔ［Ｊ］Ｐｓｙｃｈｏｌ　Ｍｅｔｈｏｄｓ，２００２，７（２）：　ｌ４７．１７７．　『１　５１　Ｋ０ＳＳＩＮＥＴＳ　Ｇ　Ｅｆｆｅｃｔｓ　ｏｆ　ｍｉｓｓｉｎｇ　ｄａｔａ　ｉｎ　ｓｏｃｉａｌ　ｎｅｔｗｏｒｋｓ［Ｊ１．Ｓｏｃｉａｌ　Ｎｅｗｔｏｒｋｓ，２００６，２８（３）：２４７－２６８．　『ｌ　６１　ＫＩ　ＭＡＲ　Ｒ，ＮＯＶ久Ｋ　Ｊ，ＴＯＭＫＩＮＳ　Ａ．Ｓｔｒｕｃｔｕｒｅ　ａｎｄ　ｅｖｏｌｕｔｉｏｎ　ｏｆ　ｏｎｌｉｎｅ　ｓｏｃｉａｌ　ｎｅｔｗｏｒｋｓ［Ｃ］＃Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｈｔｅ　ＡＣＭ　ＳＩＧＫＤＤ　２００６．Ｎｅｗ　Ｙｏｒｋ：ＡＣＭ　Ｐｒｅｓｓ．２００６：　６ｌ１．６１７．　【ｌ　７】ＧＡＬＬＡＧＨＥＲ　Ｂ，Ｔ０ＮＧ　Ｈ，ＥＬＩＡＳＳＩ－ＲＡＤ　Ｔ，ｅｔ　ａ１．Ｕｓｉｎｇ　ｇｈｏｓｔ　ｅｄｇｅｓ　ｆｏｒ　ｃｌａｓｓｉｆｉｃａｔｉｏｎ　ｉｎ　ｓｐａｒｓｅｌｙ　ｌａｂｅｌｅｄ　ｎｅｔｗｏｒｋｓＩＣｌ／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　ＡＣＭ　ＳＩＧＫＤＤ　２００８．　Ｎｅｗ　Ｙｏｒｋ：ＡＣＭ　Ｐｒｅｓｓ．２００８：２５６．２６４．　『１　８１　ＤＡＳＧＵＰＴＡ　Ｋ，ＳＩＮＧＨ　Ｒ，ＶＩＳ　ＡＮＡＴＨＡＮ　Ｂ，ｅｔ　ａ１．　Ｓｏｃｉａｌ　ｔｉｅｓ　ａｎｄ　ｔｈｅｉｒ　ｒｅｌｅｖａｎｃｅ　ｔｏ　ｃｈｕｍ　ｉｎ　ｍｏｂｉｌｅ　ｔｅｌｅｃｏｍ　ｎｅｔｗｏｒｋｓ［Ｃｌ＃Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　ＥＤＢＴ’０８．Ｎｅｗ　Ｙｏｒｋ：　ＡＣＭ　Ｐｒｅｓｓ．２００８：６６８—６７７．　『ｌ９１　ＭＥＲＩＮＧ　Ｃ、‘ＫＲＡＵＳＥ　Ｉ　ＳＮＥＬ　Ｂ，ｅｔ　ａ１．Ｃｏｍｐａｒａｔｉｖｅ　ａｓｓｅｓｓｍｅｎｔ　ｏｆ　ｌａｒｇｅ．ｓｃａｌｅ　ｄａｔａ　ｓｅｔｓ　ｏｆ　ｐｒｏｔｅｉｎ．ｐｒｏｔｅｉｎ　ｉｎｔｅｒａｃｔｉｏｎｓ［Ｊ］．Ｎａｔｕｒｅ．２００２．４１７：３９９．４０３．　『２０１　ＡＬＢＥＲＴ　Ｉ　ＢＡＲ　ＡＢＡＳＩ　Ｌ．Ｓｔａｔｉｓｔｉｃａｌ　ｍｅｃｈａｎｉｃｓ　ｏｆ　ｃｏｍｐｌｅｘ　ｎｅｔｗｏｒｋｓ［Ｊ］．Ｒｅｖ　Ｍｏｄ　Ｐｈｙｓ，２００２，７４（１）：４７－９７．　『２　ｌ　１　ＤＯＲＯＧＯＶＴＳＥＶ　Ｓ　Ｎ，ＭＥＮＤＥＳ　Ｊ　Ｆ　Ｆ　Ｅｖｏｌｕｔｉｏｎ　ｏｆ　ｎｅｔｗｏｒｋｓ［Ｊ］．Ａｄｖ　Ｐｈｙｓ，２００２，５１（４）：１０７９一ｌ１８７．　『２２１　ＬＥＩＣＨＴ　Ｅ　Ａ。ＨＯＬＭＥ　Ｐ＇ＮＥＷＭＡＮ　Ｍ　Ｅ　Ｊ．Ｖ＿ｅｒｔｅｘ　ｓｉｍｉｌａｒｉｔｙ　ｉｎ　ｎｅｔｗｏｒｋｓ［Ｊ１．Ｐｈｙｓ　Ｒｅｖ　Ｅ，２００６，７３：０２６　ｌ　２０．　【２３】ＰＡＮ　ＬＩ　Ｄ　Ｈ，ＬＩＵ　Ｊ　Ｇ　ｅｔ　ａ１．Ｄｅｔｅｃｔｉｎｇ　ｃｏｍｍｕｎｉｔｙ　ｓｔｒｕｃｔｕｒｅ　ｉｎ　ｃｏｍｐｌｅｘ　ｎｅｔｗｏｒｋｓ　ｖｉａ　ｎｏｄｅ　ｓｉｍｉｌａｒｉｔｙ［Ｊ１．　Ｐｈｙｓｉｃａ八２０１０．３８９（１４　：２８４９．２８５７．　『２４１　ＨＡＮＥＬＹ　Ｊ　Ａ，ＭＣＮＥＩＬ　Ｂ　Ｊ．Ｔｈｅ　ｍｅａｎｉｎｇ　ａｎｄ　ｕｓｅ　ｏｆ　ｔｈｅ　ｒａｅａ　ｕｎｄｅｒ　ａ　ｒｅｃｅｉｖｅｒ　ｏｐｅｒａｔｉｎｇ　ｃｈａｒａｃｔｅｒｉｓｔｉｃ（ＲＯＣ）　ｃｕｒｖｅ［Ｊ１．Ｒａｄｉｏｌｏｇｙ，１９８２，ｌ４３：２９．３６．　『２５１　ＨＥＲＬ０ＣＫＥＲ　Ｊ　Ｌ，Ｋ０ＮＳＴＡＮＮ　Ｊ　Ａ，ＴＥＲＶＥＥＮ　Ｋ，ｅｔ　ａ１．　Ｅｖａｌｕａｔｉｎｇ　ｃｏｌｌａｂｏｒａｔｉｖｅ　ｉｆｌｔｅｒｉｎｇ　ｒｅｃｏｍｍｅｎｄｅｒ　ｓｙｓｔｅｍｓ［Ｊ］．　ＡＣＭ　Ｔｒａｎｓ　Ｉｎｆ　Ｓｙｓｔ，２００４，２２（１）：５．５３．　『２６１　ＺＨＯＵ　Ｔ’ＲＥＮ　Ｊ。ＭＥＤＯ　Ｍ，ｅｔ　ａ１．Ｂｉｐａｒｔｉｔｅ　ｎｅｔｗｏｒｋ　ｐｒｏｊｅｃｔｉｏｎ　ａｎｄ　ｐｅｒｓｏｎａｌ　ｒｅｃｏｍｍｅｎｄａｔｉｏｎ［Ｊ］．Ｐｈｙｓ　Ｒｅｖ　Ｅ，　２００７．７６：０４６ｌ１５．　『２７１　ＳＡ【　０Ｎ　Ｇ　ＭＣＧＩＬＬ　Ｍ　Ｊ．Ｉｎｔｒｏｄｕｃｔｉｏｎ　ｔｏ　ｍｏｄｅｒｎ　ｉｎｆｏｒｍａｔｉｏｎ　ｒｅｔｒｉｅｖａｌ［Ｍ１．Ａｕｃｋｌｎａｄ：ＭｕＧｒａｗ－Ｈｉｌｌ，１９８３．　ｆ２８１　ＪＡＣＣＡＲＤ　Ｒ　Ｅｔｕｄｅ　ｃｏｍｐａｒａｔｉｖｅ　ｄｅ　ｌａ　ｄｉｓｔｒｉｂｕｔｉｏｎ　ｆｌｏｒａｌｅ　ｄａｎｓ　ｕｎｅ　ｐｏｒｔｉｏｎ　ｄｅｓ　ＡＩｐｅｓ　ｅｔ　ｄｅｓ　Ｊｕｒａ［Ｊ］．Ｂｕｌｌｅｔｉｎ　ｄｅ　Ｊａ　Ｓｏｃｉ６ｔ６　Ｖａｕｄｏｉｓｅ　ｄｅｓ　Ｓｃｉｅｎｃｅ　Ｎａｔｕｒｅｌｌｅｓ，１９０１，３７：　５４７．５７９．　【２９】ＳＯＲＥＮＳＥＮ　Ａ　ｍｅｈｔｏｄ　ｏｆ　ｅｓｔａｂｌｉｓｈｉｎｇ　ｇｒｏｕｐｓ　ｏｆ　ｅｑｕａｌ　第５期　吕琳媛：复杂网络链路预测　６６１　ａｍｐｌｉｔｕｄｅ　ｉｎ　ｐｌａｎｔ　ｓｏｃｉｏｌｏｇｙ　ｂａｓｅｄ　ｏｎ　ｓｉｍｉｌａｒｉｔｙ　ｏｆ　ｓｐｅｃｉｅｓ　ｃｏｎｔｅｎｔ　ａｎｄ　ｉｔｓ　ａｐｐｌｉｃａｔｉｏｎ　ｔｏ　ａｎ￣ｙｓｅｓ　ｏｆ　ｔｈｅ　ｖｅｇｅｔａｔｉｏｎ　ｏｎ　Ｄａｎｉｓｈ　ｃｏｍｍｏｎｓ［Ｊ１．Ｂｉｏｌ　Ｓｋｒ，ｌ９４８，５（４）：１—３４．　ｆ３０１　ＲＡ　ＳＺ　Ｅ，Ｓ０ＭＥＲＡ　Ａ　Ｌ，ＭＯＮＧＲＵ　Ｄ　Ａ，ｅｔ　ａ１．　Ｈｉｅｒａｒｃｈｉｃａｌ　ｏｒｇａｎｉｚａｔｉｏｎ　ｏｆ　ｍｏｄｕｌａｒｉｔｙ　ｉｎ　ｍｅｔａｂｏｌｉｃ　ｎｅｔｗｏｒｋｓ［Ｊ１．Ｓｃｉｅｎｃｅ，２００２。２９７（５５８６）：１　５５３．１　５５５．　『３　１　１　ＢＡＲ　ＡＢＡＳＩ　Ａ　Ｌ，ＡＬＢＥＲＴ　Ｒ．Ｅｍｅｒｇｅｎｃｅ　ｏｆ　ｓｃａｌｉｎｇ　ｉｎ　ｒａｎｄｏｍ　ｎｅｔｗｏｒｋｓ［Ｊ１．Ｓｃｉｅｎｃｅ，１９９９，２８６（５４３９）：５０９．５１２．　『３２１　ＡＤＡＭＩＣ　Ｌ　Ａ，ＡＤＡＲ　Ｅ．Ｆｒｉｅｎｄｓ　ａｎｄ　ｎｅｉｇｈｂｏｒｓ　ｏｎ　ｔｈｅ　ｗｅｂ［Ｊ１．Ｓｏｃｉａｌ　Ｎｅｔｗｏｒｋｓ，２００３，２５（３）：２　ｌ１．２３０．　【３３】ｚＨＯｕ　Ｔ，Ｌｕ　Ｌ，ｚＨＡＮＧ　Ｙ　Ｃ．Ｐｒｅｄｉｃｔｉｎｇ　ｍｉｓｓｉｎｇ　ｌｉｎｋｓ　ｖｉａ　ｌｏｃａｌｊｎｆｏｒｍａｔｉｏｎ［Ｊ１．Ｅｕｒ　Ｐｈｙｓ　Ｊ　Ｂ，２００９，７　ｌ（４）：６２３．６３０．　『３４１　ＬＵ　Ｌ，ＪＩＮ　Ｃ　Ｈ，ＺＨ０Ｕ　Ｓｉｍｉｌｒａｉｔｙ　ｉｎｄｅｘ　ｂａｓｅｄ　ｏｎ　ｌｏｃａｌ　ｐａｔｈｓ　ｆｏｒ　ｌｉｎｋ　ｐｒｅｄｉｃｔｉｏｎ　ｏｆｃｏｍｐｌｅｘ　ｎｅｔｗｏｒｋｓ［Ｊ］．Ｐｈｙｓ　Ｒｅｖ　Ｅ．２００９．８０：０４６１２２．　『３５１　ＫＡＴＺ　Ｌ．Ａ　ｎｅｗ　ｓｔａｔｕｓ　ｉｎｄｅｘ　ｄｅｒｉｖｅｄ　ｆｒｏｍ　ｓｏｃｉｏｍｅｔｒｉｃ　ｎａａｌｙｓｉｓ［Ｊ１．Ｐｓｙｃｈｏｍｅｔｒｉｋａ，１　９５３，ｌ　８（１）：３９．４３．　ｆ３６１　ＬＩＵ　Ｗ　ＬＵ　Ｌ．Ｌｉｎｋ　ｐｒｅｄｉｃｔｉｏｎ　ｂａｓｅｄ　ｏｎ　ｌｏｃａｌ　ｒａｎｄｏｍ　ｗａｌｋ［Ｊ］．Ｅｕｒｏｐｈｙｓ　Ｌｅｔｔ，２０１０，８９（５）：５８００７．　【３７】Ｋｌｅｉｎ　Ｄ　Ｊ，Ｒａｎｄｉｃ　Ｍ，Ｒｅｓｉｓｔａｎｃｅ　ｄｉｓｔａｎｃｅ［Ｊ］．Ｊ　Ｍａｔｈ　Ｃｈｅｍ，　ｌ９９３。１２（１１：８１－９５．　『３８１　ＦＯＵＳＳ　ＰＩＲＯＴＴＥ　Ａ，ＲＥＮＤＥＲＳ　Ｊ　Ｍ，　ｅｔ　ａ】．　Ｒａｎｄｏｍ．ｗａｌｋ　ｃｏｍｐｕｔａｔｉｏｎ　ｏｆ　ｓｉｍｉｌａｒｉｔｉｅｓ　ｂｅｔｗｅｅｎ　ｎｏｄｅｓ　ｏｆ　ａ　ｇｒａｐｈ　ｗｉｔｈ　ａｐｐｌｉｃａｔｉｏｎ　ｔｏ　ｃｏｌｌａｂｏｒａｔｉｖｅ　ｒｅｃｏｍｍｅｎｄａｔｉｏｎ［Ｊ］．ＩＥＥＥ　Ｔｒａｎｓ　Ｋｎｏｗｌ　Ｄａｔａ　Ｅｎｇ，２００７，　ｌ　９ｆ３　：３５５．３６９．　『３９１　ＢＲＩＮ　Ｓ，ＰＡＧＥ　Ｌ．　Ｔｈｅ　ａｎａｔｏｍｙ　ｏｆ　ａ　ｌａｒｇｅ．ｓｃａｌｅ　ｈｙｐｅｒｔｅｘｔｕａｌ　ｗｌｅｂ　ｓｅａｒｃｈ　ｅｎｇｉｎｅ［Ｊ］．Ｃｏｍｐｕｔ　Ｎｅｔｗ＆ＩＳＤＮ　Ｓｙｓｔ，１９９８．３０（Ｉ．７）：ｌ０７．１１７．　ｆ４０１　ＪＥＨ　Ｇ　ｗＩＤＯＭ　Ｊ．ＳｉｍＲａｎｋ：Ａ　ｍｅａｓｕｒｅ　ｏｆ　ｓｔｒｕｃｔｕｒａ１．　ｃｏｎｔｅｘｔ　ｓｉｍｉｌｒａｉｙｔｆＣ１／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｈｔｅ　ＡＣＭ　ＳＩＧＫＤＤ　２００２．Ｎｅｗ　Ｙｏｒｋ：ＡＣＭ　Ｐｒｅｓｓ．２００２：５３８．５４３．　『４ｌ１　ＴＯＮＧ　Ｈ，Ｆ＿ＡＬ０ＵＴＳＯＳ　Ｃ，ＰＡＮ　Ｊ　Ｙ　Ｆａｓｔ　ｒａｎｄｏｍ　ａｗｌｋ　ｗｉｔｈ　ｒｅｓｔａｒｔ　ａｎｄ　ｉｔｓ　ａｐｐｌｉｃａｔｉｏｎｓ［Ｃ］＃Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｈｔｅ　６ｔｈ　Ｉｎｔｌ　Ｃｏｎｆ　Ｄａｔａ　Ｍｉｎ，Ｗａｓｈｉｎｇｔｏｎ，Ｄ　Ｃ，ＵＳＡ：ＩＥＥＥ　Ｐｒｅｓｓ，　２００６：６ｌ３．６２２．　『４２１　ＳＨＡＮＧ　Ｍ　Ｓ，ＬＵ　Ｌ，ＺＥＮＧ　Ｗ　ｅｔ　ａ１．Ｒｅｌｅｖａｎｃｅ　ｉｓ　ｍｏｒｅ　ｓｉｇｎｉｉｆｃａｎｔ　ｔｈａｎ　ｃｏｒｒｅｌａｔｉｏｎ：Ｉｎｆｏｌ－ｍａｔｉｏｎ　ｆｉｌｔｅｒｉｎｇ　ｏｎ　ｓｐａｒｓｅ　ｄａｔａ［Ｊ］．Ｅｕｒｏｐｈｙｓ　Ｌｅｔ－ｔ，２００９，８８（６）：６８００８．　【４３】ＬＵ　Ｌ，ＺＨ０Ｕ　Ｌｉｋｎ　ｐｒｅｄｉｃｔｉｏｎ　ｉｎ　ｗｅｉｇｈｔｅｄ　ｎｅｔｗｏｒｋｓ：Ｔｈｅ　ＲｏｌｅｏｆＷｅａｋＴｉｅｓ［Ｊ］．ＥｕｒｏｐｈｙｓＬｅｔｔ，２０１０，８９（１）：１８００１．　【４４】ＧＲＡＮ０ＶＥＴＴＥＲ　Ｍ　Ｓ．Ｔｈｅ　ｓ￣ｅｎｇｔｈ　ｏｆｗｅａｋ　ｔｉｅｓ［Ｊ］．Ａｍ　Ｊ　Ｓｏｃｉｏｌｏｇｙ，１９７３，７８（６）：１３６０－１３８０．　『４５１　ＲＡ、，ＡＳＺ　Ｅ，ＢＡＲＡＢ缸ｓｉ　Ａ　Ｌ．Ｈｉｅｒａｒｃｈｉｃａｌ　ｏｒｇａｎｉｚａｔｉｏｎ　ｉｎ　ｃｏｍｐｌｅｘ　ｎｅｔｗｏｒｋｓ［Ｊ］．Ｐｈｙｓ　Ｒｅｖ　Ｅ．２００３．６７：０２６１１２．　【４６】ＺＨ０Ｕ　Ｃ，ＺＥＭＡＮＯＶｆｉ　Ｌ。ＺＡＭ０ＲＡ　Ｇ　ｅｔ　ａ１．Ｈｉｅｒａｒｃｈｉｃａｌ　ｏｒｇａｎｉａｚｔｉｏｎ　ｕｎｖｅｉｌｅｄ　ｂｙ　ｆｕｎｃｔｉｏｎａｌ　ｃｏｎｎｅｃｔｉｖｉｔｙ　ｉｎ　ｃｏｍｐｌｅｘ　ｂｒａｉｎ　ｎｅｔｗｏｒｋｓ［Ｊ］．Ｐｈｙｓ　Ｒｅｖ　Ｌｅｔｔ，２００６，９７：　２３８１０３．　【４７】１．ＡＳＫＡＲ　Ｂ，ＷＯＮＧ　Ｍ　ＡＢＢＥＥＬ　Ｐ：＇ｅｔ　ａ１．Ｌｉｎｋ　ｐｒｅｄｉｃｔｉｏｎ　ｉｎ　ｒｅｌａｔｉｏｎａｌ　ｄａｔａ［Ｃ］＃Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｈｔｅ　Ｎｅｕｒｌａ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｐｒｏｃｅｓｓｉｎｇ　Ｓｙｓｔｅｍｓ（ＮＩＰＳ’０３）．Ｃａｍｂｒｉｄｇｅ　ＭＡ：ＭＩＴ　Ｐｒｅｓｓ．２００４：６５９．６６６．　【４８】ＦＲＩＥＤＭ　ＡＮ　Ｎ，ＧＥＴＯＯＲ　Ｌ，ＫＯＬＬＥＲ　Ｄ，ｅｔ　ａ１．Ｌｅａｒｎｉｎｇ　ｐｒｏｂａｂｉｌｉｓｔｉｃ　ｒｅｌａｔｉｏｎａｌ　ｍｏｄｅｌｓ［Ｃ］＃Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆｔｈｅ　１６ｔｈ　Ｉｎｔｌ　Ｊｏｉｎｔ　Ｃｏｎｆ　Ａｒｔｉｆ　Ｉｎｔｅｌｌ（ＩＪＣＡＩ）．Ｓｔｏｃｋｈｏｌｍ．Ｓｗｅｄｅｎ：　『ｓ．ｎ．１。１９９９：ｌ３００．１３０７．　『４９１　ＨＥＣＫＥＩ　讧ＡＮ　Ｄ。ＭＥＥＫ　Ｃ，Ｋ０ＬＬＥＲ　Ｄ．Ｐｒｏｂａｂｉｌｉｓｔｉｃ　ｅｎｔｉｔｙ—ｒｅｌａｔｉｏｎｓｈｉｐ　ｍｏｄｅｌｓ，ＰＲＭｓ，ａｎｄ　ｐｌａｔｅ　ｍｏｄｅｌｓ［Ｃ］／／　Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　２１ｓｔ　Ｉｎｔｌ　Ｃｏｎｆ　Ｍａｃｈ　Ｌｅａｒｎ．Ｂａｎｉｆ，　Ｃａｎａｄａ：『ｓ．ｎ．１．２００４：５５．６Ｏ．　『５０１　ＨＥＣＫＥＲＭＡＮ　Ｄ，　ＧＥＩＧＥＲ　Ｄ，　ＣＨＩＣＫＥＲＩＮＧ　Ｄ．　Ｌｅａｒｎｉｎｇ　ｂａｙｅｓｉａｎ　ｎｅｔｗｏｒｋｓ：ｔｈｅ　ｃｏｍｂｉｎａｔｉｏｎ　ｏｆ　ｋｎｏｗｌｅｄｇｅ　ｎａｄ　ｓｔａｔｉｓｔｉｃａｌ　ｄａｔａ［Ｊ］．Ｍａｃｈ，Ｌｅａｒｎ，１　９９５，２Ｏ（３）：　１９７．２４３．　ｆ５　１　１　ＴＡＳＫ　ＡＲ　Ｂ，ＡＢＢＥＥＬ　Ｋ０ＬＬＥＲ　Ｄ．Ｄｉｓｃｒｉｍｉｎａｔｉｖｅ　ｐｒｏｂａｂｉｌｉｓｔｉｃ　ｍｏｄｅｌｓ　ｆｏｒ　ｒｅｌａｔｉｏｎａｌ　ｄａｔａ［Ｃ］＃Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　Ｕ　２００２．Ｅｄｍｏｎｔｏｎ，Ｃａｎａｄａ：『ｓ．ｎ．１，２００２：４８５．４９２．　『５２１　ＨＥＣＫＥＲＭＡＮ　Ｄ，ＣＨＩＣＫＥＲ【ＮＧ　Ｄ　Ｍ，ＭＥＥＫ　Ｃ，ｅｔ　ａ１．　Ｄｅｐｅｎｄｅｎｃｙ　ｎｅｔｗｏｒｋｓ　ｆｏｒ　ｉｎｆｅｒｅｎｃｅ．ｃｏｌｌａｂｏｒａｔｉｖｅ　ｆｉｌｔｅｒｉｎｇ．　ａｎｄ　ｄａｔａ　ｖｉｓｕａｌｉａｚｔｉｏｎ［Ｊ］．Ｊ　Ｍａｃｈ　Ｌｅａｒｎ　Ｒｅｓ，２０００．１：　４９．７５　『５３１　ＮＥＶＩＬＬＥ　Ｊ，　ＪＥＮＳＥＮ　Ｄ．　Ｒｅｌａｔｉｏｎａｌ　ｄｅｐｅｎｄｅｎｃｙ　ｎｅｔｗｏｒｋｓ［Ｊ１．Ｊ　Ｍａｃｈ　Ｌｅａｒｎ　Ｒｅｓ，２００７，８：６５３．６９２．　ｆ５４１　ＢＥＳＡＧ　Ｊ．Ｓｔａｔｉｓｔｉｃａｌ　ａｎａｌｙｓｉｓ　ｏｆ　ｎｏｎ．１ａｔｔｉｃｅ　ｄａｔａ［Ｊ］．Ｔｈｅ　Ｓｔａｔｉｓｔｉｃｉｎａ，１９７５，２４（３）：ｌ７９　１９５．　『５５１　ＬＥＳＫＯＶＥＣ　Ｊ，ＨＵＴＴＥＮＬ０ＣＨＥＲ　Ｄ，　ＫｌｅｉｎＢｅｒｇ　Ｊ．　Ｐｒｅｄｉｃｔｉｎｇ　ｐｏｓｉｔｉｖｅ　ａｎｄ　ｎｅｇａｔｉｖｅ　ｌｉｎｋｓ　ｉｎ　ｏｎｌｉｎｅ　ｓｏｃｉａｌ　ｎｅｔｗｏｒｋｓＩＣ］＃Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｈｔｅ　ＷＷＷ　２０１　０．Ｎｅｗ　Ｙｏｒｋ：　ＡＣＭ．２０ｌＯ：６４１．６５０．　『５６１　ＭＩ瓜ＡＴＡ　Ｌ　ＭＯＲＪＹＡＳＵ　Ｓ．Ｌｉｎｋ　ｐｒｅｄｉｃｔｉｏｎ　ｏｆ　ｓｏｃｉａｌ　ｎｅｔｗｏｒｋｓ　ｂａｓｅｄ　ｏｎ　ｗｅｉｇｈｔｅｄ　ｐｒｏｘｉｍｉｔｙ　ｍｅａｓｕｒｅｓ［Ｃｌ＃　Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　ＩＥＥＥ／ＷＩＣ，ＡＣＭ　Ｉｎｔｌ　Ｃｏｎｆ　Ｗｅｂ　Ｉｎｔｅｌｌｉｇｅｎｃｅ．Ｗａｓｈｉｎｇｔｏｎ，Ｄ　Ｃ，ＵＳＡ：ＩＥＥＥ　Ｐｒｅｓｓ，２００７：　８５．８８．　『５７１　ＢＡＲＡＢＡＳＩ　Ａ．Ｌ．Ｓｃａｌｅ．Ｆｒｅｅ　Ｎｅｔｗｏｒｋｓ：ａ　ｄｅｃａｄｅ　ａｎｄ　ｂｅｙｏｎｄ［Ｊ］．Ｓｃｉｅｎｃｅ，２００９，３２５（５９３９）：４１２－４１　３　『５８１　ＣＡＬＤＡＩ　ＬＬＩ　Ｇ　Ｓｃａｌｅ．Ｆｒｅｅ　Ｎｅｔｗｏｒｋｓ：ｃｏｍｐｌｅｘ　ｗｅｂｓ　ｉｎ　ｎａｔｕｒｅ　ｎａｄ　ｔｅｃｈｎｏｌｏｇｙ［Ｍ１．Ｎｅｗ　Ｙｏｒｋ：Ｏｘｆｏｒｄ　Ｐｒｅｓｓ。２００７．　『５９１　ＧＡＲＬＡＳＣＨＥＬＬＩ　Ｄ，ＣＡＰＯＣＣＩ　Ａ，ＣＡＬＤＡＲＥＬＬＩ　Ｇ　Ｓｅｌｆ－ｏｒｇａｎｉｚｅｄ　ｎｅｔｗｏｒｋ　ｅｖｏｌｕｔｉｏｎ　ｃｏｕｐｌｅｄ　ｔｏ　ｅｘｔｒｅｍａｌ　ｄｙｎａｍｉｃｓ［Ｊ］．Ｎａｔｕｒｅ　Ｐｈｙｓｉｃｓ，２００７，３：８１３．８１７．　ｆ６Ｏ１　ＶＡＩ　ＶＥＲＤＥ　Ｓ，ＣＡＮＣＨ０　Ｒ　Ｆ，ＳＯＬＥ　Ｒ　Ｖ　Ｓｃａｌｅ．ｆｒｅｅ　ｎｅｔｗｏｒｋｓ　ｆｒｏｍ　ｏｐｔｉｍａｌ　ｄｅｓｉｇｎ［Ｊ］．Ｅｕｒｏｐｈｙｓ　Ｌｅｔｔ，２００２，　６０（４）：５ｌ２．５１７．　【６１】ＢＡＪＥＳＩ　Ｍ，ＭＡＮＮＡ　Ｓ　Ｓ．Ｓｃａｌｅ．ｌｆｅｅ　ｎｅｔｗｏｒｋｓ　ｆｒｏｍ　ａ　Ｈａｍｉｌｔｏｎｉａｎ　ｄｙｎａｍｉｃｓ［Ｊ１．Ｐｈｙｓ　Ｒｅｖ　Ｅ，２００３，６８：０４７　１　Ｏ３．　【６２】　Ｍ　Ｂ　Ｊ＇ＴＲＵＳＩＮＡ　ＭＩＮＮＨＡＧＥＮ　ｅｔ　ａ１．Ｓｅｌｆ　ｏｒｇａｎｉｚｅｄ　ｓｃａｌｅ－ｆｒｅｅ　ｎｅｔｗｏｒｋｓ　ｆｒｏｍ　ｍｅｒｇｉｎｇ　ａｎｄ　ｒｅｇｅｎｅｒａｔｉｏｎ［Ｊ］．Ｅｕｒ　Ｐｈｙｓ　Ｊ　Ｂ，２００５，４３（３）：３６９—３７２．　『６３１　ＰＥＲＯＴＴＩ　Ｊ　Ｉ，ＢＩＬＬＯＮＩ　Ｏ　Ｖ　ＴＡＭＡＲＩＴ　Ｆ　Ａ，ｅｔ　ａ１．　Ｅｍｅｒｇｅｎｔ　ｓｅｌｆ－ｏｒｇａｎｉｅｚｄ　ｃｏｍｐｌｅｘ　ｎｅｔｗｏｒｋ　ｔｏｐｏｌｏｇｙ　ｏｕｔ　ｏｆ　ｓｔａｂｉｌｉｙｔ　ｃｏｎｓｔｒａｉｎｔｓ［Ｊ１．Ｐｈｙｓ　Ｒｅｖ　Ｌｅｔｔ，２００９，１　０３：ｌ　０８７０　１．　［６４】ｚＨＡＮＧ　Ｑ　Ｍ，ＳＨＡＮＧ　Ｍ　Ｓ，ＬＯ　Ｌ．Ｓｉｍｉｌｒａｉ￣－ｂａｓｅｄ　ｃｌａｓｓｉｉｆｃａｔｉｏｎ　ｉｎ　ｐａｒｔｉｌａｌｙ　ｌａｂｅｌｅｄ　ｎｅｔｗｏｒｋｓ［Ｊ１．Ｉｎｔ　Ｊ　Ｍｏｄ　Ｐｈｙｓ　Ｃ，２０１０。２ｌｆ６）：８ｌ３．８２４．　【６５】ＳＥＮ　ＮＡＭＡ］　Ｇ　ＢＩＬＧＩＣ　Ｍ，ｅｔ　ａ１．Ｃｏｌｌｅｃｔｉｖｅ　ｃｌｓａｓｉｉｆｃａｔｉｏｎ　ｉｎ　ｎｅｔｗｏｒｋ　ｄａｔａ［Ｊ］．ＡＩ　Ｍａｇａｚｉｎｅ，２００８，２９（３）：　９３．１Ｏ６．　【６６１　ＺＨ０Ｕ　Ｔ　Ｓｔａｔｉｓｔｉｃａｌ　ｍｅｃｈａｎｉｃｓ　ｏｆ　ｉｎｆｏｒｍａｔｉｏｎ　ｓｙｓｔｅｍｓ：　ｉｎｆｏｒｍａｔｉｏｎ　ｉｆｌｔｅｒｉｎｇ　ｏｎ　ｃｏｍｐｌｅｘ　ｎｅｔｗｏｒｋｓ［Ｄ］．Ｓｗｉｔｚｅｒｌｎａｄ：　Ｕｎｉｖｅｒｓｉｙｔ　ｏｆＦｒｉｂｏｕｒｇ，２０１０．　编辑蒋晓