检测最大密度子图的局部广度优先扩张与收缩方法

最大密度子图检测是一个重要的图挖掘问题,目前已经应用在诸如互联网、生物科学及图像处理等多个领域.在传统的最大密度子图检测算法基础上,提出一种新的基于局部广度优先扩张与收缩算法.首先,选定图中的最优结点,并从该结点出发做广度优先扩张;其次,对上面所得到的扩张结点集合进行收缩,从而得到当前迭代过程的局部最大密度子图;最后,在该局部最大密度子图相对于原图的补图上不断进行上述迭代,每次记录当前平均密度最大的子图,直至补图为空.该算法利用局部邻域优势,有效地提升了最大密度子图的平均密度.通过实验结果表明,与同类算法相比,利用该算法所得到的最大密度子图的平均密度更大.此外,通过实验表明,该算法与同类算法相比还具有更好的稳定性和适应性.