基于数据挖掘的社团划分算法研究与实现

• 作 者: 于磊
• 机 构: 北京邮电大学
• 出 处: 北京邮电大学
• 发表日期: 2015年01期
• 关键词: 社团挖掘 标签传播 重叠社团 复杂网络

随着信息技术的快速发展,网络社团研究逐渐成为了热点问题。网络社团划分对深入理解网络拓扑结构和进一步挖掘网络特性具有重要意义。近年来提出的标签传播算法,具有简单高效、不受模块度分辨率限制等特点,是目前最快的社团划分算法之一,在大规模稀疏网络中得到了广泛应用。然而,标签传播算法也存在一些不足。在其划分结果中,可能出现极大规模的社团,即所谓的“怪物”社团问题。此外,标签传播算法挖掘重叠社团能力有限,不能有效发现网络中的重叠社团特征。本论文在标签传播算法基础上做出进一步改进,力图解决“怪物”社团问题和重叠社团挖掘能力较低的问题。针对标签传播算法的“怪物”社团问题,本论文提出了Booming-LPA(Booming-Label Propagation Algorithm)算法。研究发现,衰减IPA(Label Propagation Algorithm)算法标签传播过程中的社团激增现象是出现“怪物”社团的重要原因。基于社团激增现象,Booming-LPA及时停止算法迭代,有效避免了“怪物”社团的出现,提高了挖掘社团的质量,并降低了算法的时间复杂度。实验表明,Booming-LPA算法挖掘的社团是衰减LPA算法挖掘结果的子社团,具有很高的准确率。针对标签传播算法挖掘重叠社团能力较低的问题,本论文提出了AOLPA(Attenuated Overlapping Label Propagation Algorithm)算法。在COPRA(Community Overlap Propagation Algorithm)算法基础上,AOLPA算法通过在模型中加入衰减因子使其快速收敛,通过重构重叠社团挖掘模型避免标签被过早去除,进而增强了重叠社团挖掘能力。实验表明,AOLPA算法在算法的时间复杂度、空间复杂度和重叠社团挖掘能力方面均有较大改进。