论文部分内容阅读
二分网络是复杂网络的一种重要的表现形式。网络中的社团定义为内部连接紧密对外连接稀疏的节点集合,发现网络中的社团结构,对于了解网络结构和分析网络特性具有重要意义。二分网络中的社团发现方法最初是基于投影法来实现的,其主要思想是将二分网络投影为单分网络,进而利用已经比较成熟的单分网络的社团发现算法来进行研究。但投影法存在造成信息丢失等不足,因此直接在二分网路上进行划分的方法被相继提出。Barber基于由单分网络模块度矩阵拓展而来的二分网络模块度理论提出了BRIM算法。该算法虽然对二分网络做出了有效的划分,但在初始化阶段需要额外的输入参数,使得应用时有较大的局限性。本文的MAB算法是基于Barber的二分网络模块度理论,提出的一种基于模块度的凝聚算法用来对二分网络进行社团划分。该算法无需输入额外的参数,而是将网络中每个节点看作一个独立社团,沿着最大化模块度增量的方向对社团进行凝聚,该算法已在实际网络上验证了其有效性。但是MAB算法缺陷是算法在执行过程中有大量的冗余计算,特别是在对网络的模块度矩阵的构建过程中,每次合并都需要重建整个网络的模块度矩阵,因此本文进一步提出一种基于模块度堆的二分网络社团发现算法,从时间上对MAB算法进行了改进,并通过实验验证该算法划分有效,且降低了执行时间消耗。