复杂网络上的非回溯随机游走与基于局部贝叶斯链路预测

发布时间：2021-01-12 09:53

　　复杂网络作为一种理论框架,受到越来越多学者的关注。而复杂网络中的随机游走作为最基本的一种动力学,不仅推动概率论、计算科学、统计物理等学科的发展,也应用到许多实际问题中,如计算机网络上路由策略、社团结构、核心-边缘结构等中尺度结构划分、链路预测和观点动力学等问题。与此同时,复杂网络上的链路预测问题,也成为了生物学,计算机科学,社会科学等领域的热门问题。例如,在生物信息学中,它已用于预测“蛋白质-蛋白质”的相互作用（PPI）。在与安全相关的应用程序中,它可以用来识别恐怖分子和罪犯的隐藏群体。而且链路预测算法也可以帮助分析社交网络的发展。本文研究工作如下:（1）在一般随机游走的基础上,通过二阶马尔可夫模型研究了复杂网络上非回溯随机游走,推导出了网络上任意两个节点之间的平均首达时间的表达式和节点的稳态占据概率计算公式。和一般随机游走结果相比,发现这两种随机游走模型中的节点稳态占据概率是完全相同的,但非回溯随机游走的平均首达时间短于一般随机游走的平均首达时间。这体现了非回溯随机游走在解决网络搜索、路由等问题上比一般随机游走更加有效,也意味着对解决链路预测问题会有很大的帮助。（2）提出一种广义的朴... 

【文章来源】：安徽大学安徽省 211工程院校

【文章页数】：49 页

【学位级别】：硕士

【部分图文】：

非回溯随机游走的非马尔可夫性可以通过二阶马尔可夫模型来代替

第四章基于广义聚类系数的广义朴素贝叶斯链路预测方法研究24图4.2广义的聚类系数拆分图。（a）共用节点的邻居集中所有可能组成三角形个数可以分成两个部分：（b）至少共用,,yx中一条边的所有可能组成三角形的个数（所有红色节点与其它节点（包括红色节点）可能组成三角形的个数）如3221kkk；（c）不共用,,yx中任一条边的所有可能组成三角形的个数（连接节点ω邻居集的蓝色节点的绿色连接，除了节点x和节点y），如22k。共用节点所有组成三角形个数可以拆分成（b）中红色边数以及（c）中绿色边数。因此，通过上述准备工作，我们假设条件概率,1,APyx类似于三元组,,yx的广义聚类系数yxEC,,（其中是节点对yx,的共同邻居），其可以定义为：322132,,,,,,,,,1,kkACNCNkACNCNECAPyxyxyxyxyxyx（4.3）我们称1,,yxEC为三元组,,yx的边的聚类系数（LCC），0,,yxEC为三元组,,yx的点的聚类系数（NCC）。可以看出三元组的广义聚类系数是边聚类系数和点聚类系数的线性组合，值越大，则边聚类系数就越大，反之亦然。如图4.1通过广义聚类系数的定义，18161161922,0,1EC，4,0,512196EC1239。下面给出三元组,,yx的广义聚类系数yxEC,,的两个定理：


本文编号：2972640