有向图上的链接预测研究

发布时间：2020-07-09 23:43

【摘要】：伴随着科技社会的迅速发展和网络信息技术的进步,复杂网络的链接预测的研究有重要的现实和理论研究意义,已经成为近年来的研究热点,广泛应用到多种领域中,如社会科学、计算机科学、复杂系统等一些领域。链接预测的含义是通过已知的网络的拓扑结构来对缺失的链接和未来可能产生的链接进行预测。这种预测既包含了对未知链接(网络中实际存在但尚未被我们探测到的链路)的预测也包含了对未来链接(网络中目前不存在,但应该存在或者未来很可能存在的链路)的预测。链路预测相关研究不仅能够推动网络科学和信息科学理论上的发展,而且具有巨大的实际应用价值,譬如可以进行在线社交推荐、指导蛋白质的相互作用实验、找出交通传输网络中有特别重要作用的路径等。在现实世界中,目前大多数的链接预测算法都是基于无向网络的,但是现在许多社会网络中的连接都是有方向的。社交网络正在不断融入人们的日常生活,近年来facebook、Twitter、新浪微博等社交网站层出不穷,成为信息分享和传播的重要途径。对于类似Twitter的社交网络,用户关系的有向性是普遍存在的,因此预测连接是否存在的同时,也有必要预测链接的方向。本文针对有向网络的特性,融合网络的拓扑结构信息和关系的相似性,设计精准高效的链接预测算法。本文的主要研究工作和成果如下:(1)提出了一种基于抽样的有向图的单源链接预测算法。我们通过设定适当的抽样大小,可以将相似度的误差限制在一个给定的阈值范围内。然后根据设定的抽样大小产生路径的样本集。然后基于抽样路径来计算给定顶点的相似性得分,对于每条路径中的每一个子路径在Katz指标上加上相应的值,以得到近似的Katz指标。由于只要基于抽样路径来计算给定顶点的相似性得分,该算法可以大大减少计算时间。通过在实际网络上的实验结果显示,我们的算法可以获得高精度的预测结果。(2)提出了一种基于遗传算法的有向网络的链接预测算法。我们拟对顶点的排序方式进行编码,作为遗传算法的个体表达形式。我们首先随机产生若干个初始个体,每一个个体代表一个排序方案,然后计算该排序方案的适应度,用赌轮法选取新一轮的该选个体集合,再使用交叉、变异操作,产生新一代的群体。重复上述操作,直至收敛到最优解。我们拟通过遗传算法得到顶点的排序分,然后通过比较两个顶点的排序分来确定它们间链接的方向,还可以根据两个顶点排序分之间的差异大小估计该链接出现的概率。通过在实际网络上的实验结果显示,我们的算法可以找出有向网络中顶点的最优的近似排序来解决顶点之间链接的方向预测,可以获得高精度的预测结果。(3)提出了一种基于生成树的有向图顶点排序的算法。我们试图找到一种排序方法,即对任一顶点定义一个序号,使得对任一有向边上开始点的序号都要小于终点的序号。为了计算这种序号,我们对该有向图构造相应的无向图,然后对每一顶点观察其为根顶点的在两个图上的生成树,最后通过用该顶点的两个的生成树的差异来衡量顶点的排序值。实验结果显示,我们的算法可以得到最优化的顶点排序,取得好的预测质量。
【学位授予单位】：扬州大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：O157.5
【图文】：

区域图,区域,随机数,概率

这些个体将按选择的数量被复制。在计算机辅助实现采用以下方法：根据个体的排序，按选择概率ＰＯＯ计算累计概率邋＝逦。算法产生？个随机数ｖ对每一个随机数，判断其是否落在是，则选择相应的；ｃ，进入下一代。这样，可以得到选择复制后的看出适应值越大的染色体被选中（复制）的概率也越大。逡逑）交叉操作逡逑是把两个父代个体的部分结构加以重组而生成新个体的操作。交叉的个体具有多样性，扩大解的搜索空间，使个体对应的解逐步逼定的概率凡选择一对个体ｘ和ｙ进行交叉，设ｘ＝（ｘｉ办．．．士），ｉｘ中随机选取要交叉的区域［／，／邋＋邋Ａ邋－１］，然后找出与ｘ，，；ｃ，＋１，．．．，合＾受它们依次为：＾：＾广？＾＾然后将＆与＾＾交换＊＾＾．】，．．：设ｘ＝（３，２，ｌ，５，４），尸（４，５，３，１，２），设要交换的区域为［３，４］，则凡．与／的阴影部分所示：逡逑Ａ

【相似文献】