基于最大团的层次化重叠社区发现算法

摘要

研究表明,很多真实网络具有层次结构和重叠结构.传统的层次聚类算法通常以节点为对象进行扩展形成层次树图从而得到网络的层次结构.这种做法存在两个问题,其一是算法的稳定性,主要体现在初始节点的选择上,少数情况下,初始节点的不同会导致算法最终结果的不同,即使算法的结果不依赖于初始节点,但算法的复杂度会随之变化;其二是不能发现网络中的重叠结构.针对以上问题,提出一种基于最大团的层次化重叠社区发现算法.该算法以最大团为扩展对象,然后利用最大团扩展策略生成层次树图,最后采用重叠模块度函数对层次树图进行剪枝得到社区划分结果.在真实网络以及LFR人工网络上的实验结果表明该算法能够有效地挖掘网络中的层次结构和重叠结构.