论文部分内容阅读
近些年,复杂网络的演化逐渐成为研究的热点,而链路预测作为复杂网络研究中的关键分支,是解决网络演化建模的关键所在,具有重要的理论研究价值和广泛的军民应用前景。本文重点研究复杂网络上的链路预测算法,针对当前链路预测算法缺乏对局部网络特殊结构的考虑,从网络结构模式挖掘角度出发,依托子图、模体等概念,综合运用矩阵论、概率论、统计学等多个学科领域知识,设计链路预测算法。论文的主要工作和创新点如下:(1)从复杂网络局部的特殊结构出发,提出基于局部子图相似性指标的无监督排序链路预测算法。当前主流的基于相似性指标的链路预测算法,大多依据网络的节点度、路径、邻居节点信息刻画节点间相似性,缺乏对网络局部特殊结构的考虑。针对这一问题,本文通过局部子图定义节点间的相似性,提出适用于在线计算的局部三角子图(LTS)相似度,并以此为基础拓展,得到局部矩形子图(LRS)、局部混合子图(LMS)、局部加权混合子图(LWMS)这三个高阶相似性指标。实验仿真结果表明,基于本文提出的局部子图相似性指标设计的无监督排序链路预测算法,在标准测试集USAir、Political blog上,precision指标要比经典链路预测算法平均高出10%。(2)甄选出以局部子图为代表的六个适用于有监督分类链路预测算法的网络拓扑结构特征。针对无监督排序链路预测算法在高聚类系数网络中表现性能欠佳的问题,本文通过有监督学习的方式,提高链路预测算法准确性。将链路预测抽象为一个二分类问题,基于网络拓扑结构信息,提取能充分刻画节点相似度的特征。综合考虑比较结果,甄选出以局部三角子图为代表的六个通用性强的拓扑结构特征。实验仿真结果表明,基于局部子图特征的有监督链路预测算法,在USAir等六个标准测试集上,AUC指标要比无监督排序模型平均高出1%。(3)分析了基于随机分块模型的网络重构算法的局限性,提出面向网络重构过程的子图保护算法。针对基于随机分块模型的网络重构算法会破坏社团间局部子图的问题,本文提出基于模拟退火思想的网络重构算法。重构中,通过以一定概率跳过对“异常边”删除的策略,保护对网络结构功能特性有重要影响的社团间局部子图。实验仿真结果表明,通过改进后算法得到的重构网络,在聚类系数、平均路径长度、同步性等众多网络拓扑结构属性上,更加接近真实网络的特性。