论文部分内容阅读
随着信息技术的快速发展和广泛使用,各种复杂网络大量涌现,对复杂网络的研究和分析已成为一个重要的多学科交叉领域。顶点的结构相似性计算是复杂网络分析中一个最基础而又非常重要的任务。本文研究了与结构相似性计算有关的两个问题。第一个问题是基于相似性的链接预测。链接预测根据已知的结构信息发现网络中丢失的链接或者预测将来可能出现的链接。基于相似性的链接预测是当前研究的一个主流,其核心是精确的相似性计算方法。本文对现有的基于相似性的链接预测方法进行了深入的分析,针对其存在的问题,提出了两个新的结构相似性计算方法,并应用于链接预测。(1)SAC：该方法利用两个顶点在其公共邻域内的活跃程度以及这两个顶点与它们邻居之间的连通性计算其相似性。活跃程度越高、连通性越强,则这两个顶点越相似。SAC能很好地区分路径对相似性的贡献、并能融合端点自身对相似性的影响,取得了很好的预测结果。(2) Scope:该方法定义了路径对其端点相似性的贡献以及顶点自身对其相似性的影响。结合这两个部分,Scope定义了顶点间的相似性。Scope能够很好地区分不同路径的贡献程度,能取得很好的预测效果。为了验证这两个方法的性能,论文在10个真实网络数据集上进行了实验,实验结果显示,SAC和Scope的预测精度明显好于其它6个对比方法。第二个问题是顶点的角色相似性计算。顶点的角色相似性不依赖于两个顶点间的公共邻居或者路径,而只与它们在网络中的角色有关。RoleSim是一个真实值的角色相似性计算方法,能够较好地检索到对等顶点。但是,该方法的精度还不够高,并且时间性能很低。针对RoleSim的不足,本文提出了两个新的角色相似性计算方法。(1) CentSim:顶点在网络中的角色与它所在的位置有关,而顶点的中心性度量可以泛化地描述顶点在网络中的位置。CentSim利用顶点的中心性度量计算顶点间的角色相似性,取得了很高的时间性能和计算精度。CentSim满足所有角色相似性的公理性质,是一个可接受的角色相似性计量方法。(2) Simon:该方法通过比较两个顶点的直接邻居的PageRank值以及顶点自身的PageRank值来对这两个顶点的角色相似性进行判断,不但提高了运行效率而且能够准确地度量两个顶点的角色相似程度。Simon是一个可接受的角色相似性计量方法,具有很高的应用价值。为了验证这两个方法的性能,论文在5个真实网络数据集上进行了实验。与其它5个方法相比,CentSim和Simon能够快速地、更加精确地计算顶点间的角色相似度,因此,它们都是高质量的角色相似性计算方法。