英语原文共 11 页，剩余内容已隐藏，支付完成后下载完整资料
基于模块化的置信传播在复杂网络中的链路预测
赖大荣，舒欣以及克里斯汀纳迪尼
计算机科学与工程学院，东南大学，南京，211189，中国
教育部计算机网络与信息整合重点实验室，东南大学，南京，210096，中国
信息科学与技术学院，南京农业大学，南京，210095，中国
CNR-IAC “Mauro Picone” Via dei Taurini 19, 罗马，00185 ,意大利
个人基因组学，Via delle Grazie，维罗纳，意大利
(收稿于2016年8月26日;修改稿收到于2016年11月25日;网上公布于2017年2月13日)
链接预测旨在检测一个网络链路的缺失，伪造或者演进，这是基于网络的拓扑信息
和节点的属性。在这个假设之下，即在两个节点之间存在节点的可能性能够通过节点的相似性来获取，目前已经有通过节点度的信息来直接或者间接的计算相似性的几种方法被提出来。然而，正确预测链路对于揭示链路信息机制也至关重要，从而为网络提供更准确的建模。我们在这里提出一种预测链路的新方法，通过合并具有节点度的随机块模型链路生成机制。这个提出的方法首先恢复基于模块化置信传播的网络的基础块结构，并且基于恢复的块结构信息，它模拟两个节点之间的链路可能性，以匹配网络的度数序列。一组现实世界网络和综合网络上进行的随机块模型生成的实验，表明我们提出的方法可以有效地检测网络的丢失，虚假或演进链路，这些链路可以通过随机的方式进行良好的建模。这种方法有效补充了复杂网络分析的工具箱，提供了一个新颖的工具用来在随机块模型网络中的链路建模，这种随机块模型网络是现实世界复杂网络建模的基础。
关键字：链路预测，复杂网络，置信传播，模块化。
PACS: 89.75.Hc, 02.50.Tt, 89.20.Ff DOI: 10.1088/1674-1056/26/3/038902
- 介绍
网络是强大的工具，它能够描述大量复杂的社会的，生物的，信息的系统，节点是系统的单元，节点之间的链路代表了它们相互作用和关系。比如，城市公交车系统可以通过不同类型的网络进一步建模分析。从网络结构到网络动态,复杂系统的功能和动态性分析能够通过网络分析来进行，由于使用复杂实体系统的有限知识代表网络，收集的数据总是部分或混合有噪音。比如，80％的酵母分子相互作用和超过99％的人类活动仍然是未知数。同样，在社会科学领域的信息不准确或抽样偏差往往导致社会网络重构缺少数据或充满噪音。另外，实验室实验还是用于验证链路的手动判断通常是昂贵的。幸好，对于盲目的检查所有可能的相互作用是无法接受的，这样的成本能够通过聚焦最可能的相互作用被大大的的减少，这个相互作用能够被有效的基于已知相互作用的计算算法预测。
基于观察到的链路和网络节点的属性，链路预测尝试估计两个节点之间存在链路的可能性。可靠的链接预测算法可以用来识别丢失的链路，预测未来可能出现的演进链接，过滤嘈杂网络中的虚假链接等等。基于相似性链路预测是将两个不存在连接的节点根据相似性来预测它们存在链路的可能性：更相似的节点应具有较高的被连接的可能性。如果可以有效地提取节点的属性，链路预测可以投射到欧几里得度量空间的节点对之间的计算相似性在计算框架中。不涉及节点的属性，但与唯一的网络结构相关。在网络中的一个节点可以表示为欧几里得的向量，它保持欧几里德通勤时间距离，以及两个节点之间的相似性是节点对应向量的内部产物。实际上，当网络拓扑结构可用时，节点的相似性不一定要映射节点成向量。旨在通过唯一网络结构，获取两个节点之间的相似性的拓扑相似度测量，产生了广泛的在复杂网络上的基于链路预测方法结构相似性的变化，例如基于计数公共邻居的方法。不依赖于结构相似性的方法包括寻找最佳拟合图的最大化可能性方法(预先指定的局部结构，如块，图案，层次结构，等等)来观察网络，然后给节点对给分，然后使用概率模型方法，就是使用参数化概率模型来推导一个链路存在的概率。虽然，各种链路预测方法依然继续被设计，直观而言，在这篇论文中，我们关注的基于结构相似性的链路预测方法，引起了对社区的兴趣。
这些方法可以大致分为三大类：全局，局部和中间。全局相似方法使用整个网络拓扑信息计算节点相似度。比如，Katz指数计算连接两个节点的所有路径，并加上更多权重在较短的路径上。其他全局相似方法包括有重新开始和平均通勤时间索引的随机方法。全局方法需要整体网络结构的信息，而且和局部方法以及中间方法比较之后，它的输出结果具有更高的特性和计算复杂度。局部相似度方法仅使用局部结构信息来定义节点相似度。比如，共同邻居算法(CN)计算两个节点之间共同邻居的个数，如果它们有更多的共同邻居，那么它们更有可能存在一个链路。存在正常化差异，共同邻居算法的扩展包括萨尔顿指数和杰卡德指数。建立在无增长的无规模网络生成机制的基础上，优先附件索引算法(PA)计算的两个节点之间存在链路的概率与其度数成比例。与CN和其变体比较，PA不需要有关邻居的信息，并因此降低计算复杂度。有关邻居及其度的信息，艾达米克-阿达算法(AA)和资源分配(RA)指数通过分配较少连接的节点更多的权重来计算结构相似性。AA和RA指数本质上是相似的，除了拥有度数大的节点的权重。最后，在全局和局部之间的中间方法包括本地路径索引及其变体算法，它们是基于局部随机步数，并在性能和复杂性之间做出很好的平衡。关于链接预测方法的各种状态的更多细节可以总结在一个优秀测量中。
链路预测方法的一个重要特征在于他们的特点，它与网络形成的潜在的机制有关。如果一个链路预测方法的原理与网络形成机制一致，那么方法表现良好，证明预测准确。相反，如果一个链路预测方法不能获取链路形成机制，那么它往往不能给出令人满意的预测。比如，如果观察到的网络组织具有层次性的话，那么，基于层次性的网络层次化组织的假设的随机图的链接预测框架有更高的预测准确性。同样的，如果观察网络被组织成块或不同的角色，那么基于随机块模型(SBM)框架将提供准确的链接预测。受这个事实启发。王等人将网络演进链路视为一种链接预测算法，并且使用可能性分析在给定的一系列网络中判断哪种机制更好，进而解释一个网络的演变。而张等人 应用可能性分析和链接预测方法进行定量测量多种机制是如何有助于网络形成的。在有针对性的网络案例中，张等人发现由潜在具有聚类和同质性机制的理论推导得出，如果一条链路产生更多可定义的子图(如由4个节点和4个定向链路组成的双风扇结构)，那么一个未曾观察到的链路将更有可能存在。
当网络中的节点被分成块和两个节点连接的概率只取决于他们所属的块，那么SBM非常适合捕获网络组织机制。实际上，SBM是一个用于生成各种网络的强大的模型，它可以捕获现实世界的网络无所不在的基本属性，总体上，更多具体的模型如下所示：模块化或块结构，核心外围，分级，多部分结构等。使用链路形成机制的SBM生成网络，两个节点之间的链路的存在性概率只依赖节点的块成员。然而，一组或一块节点并不总是均匀的，但通常是异构的，这是在大多数经验网络中发现的一个特征数据。因此，我们认为合理的真实网络建模过程可以通过考虑节点的具体特点来实现。根据观察，我们提出通过考虑块结构和节点度的信息来计算两个节点之间的结构相似度的算法。该方法应用基于模块化的置信传播算法来恢复网络的底层的块结构，然后计算在块中连路概率分布。我们将这个方法称为块模型
优先依附指数(BMPA)。
在这篇论文中，我们首先描述一个网络中的链路预测问题，并且介绍了几个最先进的基于相似性的算法作为基准。然后，我们提出我们的新的链接预测的方法和基于模块化的块结构恢复的置信传播算法。在一组现实世界的网络和由SBM生成的综合网络上的BMPA和基线方法之间的测试和比较最终被显示。
- 问题和基准方法。
我们专注于无向和未加权的网络G(V，E)的链接预测，它没有自连接或多重连接链接，其中V是节点集合，E是链接集合。对于缺失链接预测，链接集E被随机分割分为两组：用于相似度计算的训练集ET，和测试集EP进行性能测试。在这种情况下的链路，EP不允许包含在ET中，也就是说，ETcap;EP=Oslash;，ETcup;EP=E。链路集被强制划分来保持网络G(V，ET)连接。对于虚假的链路预测，额外的链路被随机添加到E中。结果而言，所有在测试集EP中添加的随机链路和训练集是ET=Ecup;EP。伪链路预测的目的是从G(V，ET)滤除也在测试集EP中的连路对，而缺失链接预测的目的是发现在G(V，ET)中未连接的链路对，除了在EP中的连接对。不断发展链接预测预测出来的链路未来可能随着时间的推移而变化。为了模仿这个发现，预测不断变化的链路的能力可以通过过滤随机添加的链接来揭示。而给出的观察网络是原始网络G(V，E)，它不同于缺失或伪链接预测算法。在这种情况下，训练集变为ET = E，EP是随机添加链路的集合。
为了量化预测链接算法的能力，我们使用接收工作特性曲线下的面积(AUC)指标。基于相似度的链路预测关联节点与链接存在的可能性相似。通过计算在U--ET中所有节点对的相似性(这里U是所有网络中可能的节点对的集合)，即在U--ET网络中的未观察到的链接的链路存在的可能性。，链路预测方法提供了缺失链路预测可能性的排名列表。在这个随机列表中，缺失链路预测的方法的AUC值是一个概率，它随机在EP中选取更高的范围比上随机的在U--E网络中选取不存在的链路。为了简化计算，我们这里采用了AUC计算方法计算每个未观察到的链接的分数(它的两端相似度)，而不是给出有序列表。在每一步中，在EP中缺失的链接和U--E中不存在的链接是随机抽取比较他们的分数。如果在K次独立比较中，K1次随机挑选具有较高分数的链接，K2次链接具有相同的得分的链路，AUC的值是
AUC值变化一般在0.5到1之间，当AUC=0.5时，表示随机猜测。当AUC=1时表示预测缺失链路方法的性能是完美的。
同样的，对于虚假或者演化链路预测，一种算法的AUC值可以通过比较在EP中随机挑选的杂散链接与在E集中随机选取链接的得分来进行计算。在虚假或不断变化的链路预测中，K1在EQ中，表示随机从EP中选择的虚假链接的分数低于由E中随机挑选的链接的分数的次数，而且K2是他们得分相同的次数。因此，对于虚假或演进的链接预测的AUC值可以解释为一个从EP中随机选择的虚假链路比E中随机选择存在的链接的概率更低。
对于给定的节点对i和j，链路预测方法通过参考训练集中的结构信息来计算节点之间的相似度分数。四大知名使用基于局部相似性的链路预测方法作为性能比较的基准。他们被选中是因为它们在链路预测中的有效性和直接或间接使用节点度信息。全局方法由于其计算复杂度高而不被选择，而且对于复杂的调谐参数，诸如本地路径索引之类的中间方法也是避免的。
对于节点i的度和它的邻域的集合N(i)的，CN方法通过对它们的共享邻居进行计数计算出节点i和j的相似度分数。
|.|表示集合中的元素的数量，而且表示节点i和j的公共邻居集合。
PA方法假设链接的概率是连接节点i和j与其度数di和dj成正比，并计算得分为
与CN相比，PA不需要有关节点邻域信息，因此具有较低的计算复杂度。
不同于CN算法给每一个节点相同的权重，AA算法分配更多的权重给更少连接邻居的节点，而且计算相似性得分为
资源配置动态激励了方法RA，和AA一样，它在计算常见的邻居时也使用不相等的权重，但更高惩罚度大邻居的节点。RA的相似性得分计算公式为
- BMPA相似性和基于模块化的置信传播
根据不同的机制，网络中的节点通常被组织成组(或块)。比如，人经常根据他们的年龄，性别，职业，种族等等与他人建立社会关系。如上所示，当预测这种网络链接的存在，它是至关重要，反映这个基础链接预测方法的形成机制。SBM可以很好捕捉到这样无所不在的基本属性。在SBM中，两个节点连接的可能性或概率只取决于他们所属的群体。因此，在SBM的框架中，一组中的所有节点具有连接到另一组中的所有节点的共同的概率。因此我们简单地称为两个节点连接的概率作为他们所属的组相连的概率，反映了SBM的特性，同一个小组所有节点的被平等对待。然而，在真实的网络世界中，所有组中的节点不总是均匀的。他们有他们的自己的特点或作用，按照节点度简单直接地特点。因此，为了更好捕获节点的相似性或链接存在的可能性，我们结合了这两个因素。
将A表示为网络的邻接矩阵，其中如果节点i和j之间存在链路，则= 1，否则= 0。度数di是与节点i相关链接的数量，即。假设网络有q个团体。让m表示网络中的连接数，同时，gi=r(1lt;=rlt;=q),表示节点i所在小组的成员数量。小组r和小组s的链路数量是(或者是当r=s时，链路数量的两倍)，而且，和小组r相关的链路数量是。在这里，如果gi=r，那么，否则。两组相连的概率被定义如下(也称为分组的链接分布，是这两个组中的两个节点连接的概率，它不考虑节点自身的特性，仅考虑组成员身份)。
当组合具有节点度节点组的连通概率时，节点i和j之间的新相似度指数,BMPA定义为
考虑到分区网络的程度异质性，BMPA的基本思想类似于脱脂模块模型。然而，连接概率在使用泊松分布的度块模型中建模，而BMPA被用作相似性措施来衡量存在链接的可能性。为了计算EQ中的节点相似性，首先必须回复组或者块的结构。最近提出的基于模块化的置信传播(Modbp)方法可以用来网络的重要划分。Modbp是非常有效的，通过迭代更新两个方程来找到网络的重要分区。如果表示从节点i送到节点j的一个消息或者可信度，这是边际概率的估计，该节点属于节点i与其邻居节点k(k!=j)之间基于相互作用的社区t(gi = t)。而且是基于节点i与其所有邻居之间的相互作用的属于社区t的节点i的边际概率。
更新可信度的两个方程是
<p
剩余内容已隐藏，支付完成后下载完整资料</p
资料编号：[25321]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
