论文部分内容阅读
复杂网络作为描述真实世界的一种建模工具,已广泛应用于物理学、生物学、社会学等各领域。社团结构是复杂网络的一个重要特征。传统的社团发现方法大多只关注静态网络,然而真实网络是海量且动态变化的。因此,在大规模动态复杂网络中有效地抽取社团结构,是一项亟待解决的重要问题。本文针对复杂网络的动态性,提出了两种增量式的社团发现方法;针对复杂网络的海量性,实现了一种在Hadoop平台上的社团发现方法。第一种增量式方法首先通过分析连接密度的变化检测所影响的区域,再利用局部社团扩张的策略快速更新社团结构;第二种增量式方法设计了一种两阶段社团发现的方案,在线阶段维护网络的核连通聚类连,离线阶段在该链上自动选取最优密度参数,以更准确地发现社团结构;在Hadoop平台上的社团发现方法利用MapReduce编程模型实现了算法的并行化,进一步提高了算法可扩展性。在真实网络和生成网络上的实验表明:本文提出的两种增量式方法可以高效、准确地发现动态复杂网络中任意形状的社团结构;在Hadoop平台上实现的社团发现方法在大规模数据上具有良好的可扩展性和可靠性。