基于动态社交网络的高效核维护方法

在现实世界中,社交网络图的结构是动态变化的,导致顶点的核数发生变化。核维护是指当图发生动态变化时动态更新图中所有顶点的核数。现有的最先进的核维护方法是基于遍历的核维护算法和基于顺序的核维护算法,针对现有核维护方法在大规模动态图中执行效率较低的问题,该文提出了基于动态社交网络的高效核维护方法。首先分析了基于遍历的核维护方法和基于顺序的核维护方法的不足,提出了新的kn-order索引来维护顶点的顺序和邻居信息,通过改进的遍历查询方式来高效获取图动态变化后核数变化的顶点集,并提出了基于边插入的核维护算法和基于边删除的核维护算法来高效维护顶点的核数。最后,在4个真实数据集的验证表明,该算法有效提高了基于动态社交网络的核维护的效率,较基于顺序的核维护方法,执行效率提升了3~4倍,访问图中顶点的比例平均下降了2%左右,加速比提升了至少2倍。