论文部分内容阅读
现实生活中很多问题都可以建模为复杂网络上的源点定位问题,如确定流行病的传染源,找出谣言的源头等等,这些现象往往会在网络中产生级联效应,因此如何能够准确快速的定位网络上的信息源,对于传染病控制、舆论控制等具有重要的意义。在源点定位问题上,一种典型的方法是通过在网络上部署观察点,根据观察点记录的传播信息来估计网络中的信息源点,但是该方法的定位准确率受观察点的部署影响较大,而且对于大规模网络其定位效率较低。针对以上问题,本文基于复杂网络相关理论,完成了以下两方面的工作。首先,研究了不同观察点部署策略对于源点定位准确率的影响。根据网络中节点的中心性指标选用了六种观察点部署策略,分别在模型网络和实际网络中进行信息源定位实验,结果发现,随观察点比例升高,定位准确率显著提升;在网络平均度较高时,定位准确率较低。进一步实验表明,信息源点到观察点距离的方差与定位准确率具有直接关系,在信息源点到观察点距离的方差较大时,定位准确率可以维持在较高水平,这为观察点部署策略的优化提供了实验依据。其次,现有源点定位算法时间复杂度为O(n3),在大规模网络上其定位效率难以接受。针对源点定位算法时间复杂度高的问题,提出了一种信息源点快速定位算法,算法依据候选源点估计值在网络中的分布规律,采用局部搜索策略,减少了候选源点的遍历个数,降低了算法的复杂度。通过实验证明,与现有算法相比,改进后的算法在大规模网络中其快速定位的优势更加明显。定位准确率和定位效率对于任何定位算法都是十分重要的,本文探讨了不同观察点部署策略对于定位准确率的影响,并对观察点部署的优化提出了意见。最后通过对原有算法的改进,在保证定位准确率的情况下提高了定位效率。