论文部分内容阅读
复杂网络中的关键节点是指那些在网络结构和功能上起着重要作用的节点,学者们从不同的角度提出了许多节点重要性排序算法。但是在某些真实场景中,往往一组少量的节点起着关键的作用,称之为关键节点组。如在信息传播时,如何选取一组较少的节点使得信息的传播规模最大?在满足一定预算下,如何选取一组用户使得广告能够被更多的用户所知晓?近年有许多学者对该问题进行了深入研究,从影响力最大化,到挖掘最有影响力的传播者。算法形式则由早期的贪心算法及其改进,转变到近年较常见的启发式算法。本文根据近年的一些启发式算法思路,从节点重要性和节点间的距离两方面分析并提出了一种重要节点组挖掘的新算法。主要的研究内容和创新点有:(1)提出一种基于改进核数熵的节点重要性排序算法。本文认为节点的重要性不仅和节点的核数相关,而且和节点连接的核数多样性有关。而且为了消除核数熵受节点度的影响,本文在核数熵的基础上改进并提出了MKE算法。(2)通过分析节点的相似性,在基于中心点的社团划分算法的基础上,提出一种基于相似度的斥群距离指标,用于衡量节点与所有比此节点重要性更强的节点之间的平均相似性,并提出一种通用的节点选取算法——SNBS。(3)综合MKE算法以及SNBS算法,本文提出了一种关键节点组挖掘的混合启发式算法——HHA算法。通过实验分析,在全接触SIR和单点接触SIR模型下,HHA算法较VoteRank和DCC算法在相对比例指标Δ下,在不同网络中整体上均有较好的表现,并且Δ的最大提升的平均值为3%以上。并且HHA算法能有效的应用于真实场景中。通过实验分析,SNBS算法能够有效的增大选取节点间的距离,结合不同的排序算法时,其效果整体优于top-k选取方法;选取排序算法时,应优先考虑与度相似的排序算法和基于关键节点组的排序算法。在全接触SIR模型中,在选取较优的相似度计算参数时,可至多考虑3阶邻居的影响,并且可以得到一个统一的较优参数。若至多考虑2阶邻居,则需要调节相似度计算参数。本文并没有深入研究节点重要性和相似度的结合方式以及相似度的选取。后续工作应从网络结构上深入分析节点重要性和相似度的结合方式,及相似度的选取依据。