论文部分内容阅读
近年来，复杂网络逐渐成为社会学、生物学和计算机等学科研究的热点。复杂网络将自然界中的人或实体抽象为网络中的节点，人或实体之间的关系抽象为网络中的边。复杂网络在自然界中广泛存在，如万维网、人际关系网和蛋白质交互网等。研究发现，复杂网络往往具有社区结构这一重要特征，表现在网络中的节点呈现聚集化，即社区内部的节点连接紧密，而社区之间的节点连接则比较稀疏。社区结构的合理发现，不但有助于简化复杂网络，而且可以凸显出网络中潜在的结构和关系，为人们理解网络拓扑和功能结构提供帮助，为利用和改造网络提供支持。 目前，对社区结构的研究得到了广泛关注，众多社区发现算法被提出。然而传统的社区发现算法均是串行算法，时间和空间复杂度较高。在如今大规模复杂网络场景下，算法在时间和空间上都受到了巨大的考验，无法快速准确的处理大规模复杂网络。因此，如何在大规模复杂网络中正确而稳定地发现社区结构是一个十分重要的问题和挑战。 为了解决这一难题，本文基于Flink Gelly分布式图计算平台完成了传统社区发现算法的并行化设计与实现。这样，利用集群所具有的计算优势来处理海量的复杂网络数据，降低算法执行所消耗的时间。本文的关键技术有:(1)提出了一种社区发现算法的特征分析方法，该方法从计算模式、数据依赖、计算顺序、计算性质和时序依赖五个维度分析传统社区发现算法的特征，总结了实现传统社区发现算法并行化的三个要求;(2)提出了一种社区发现算法的并行化方法，该方法通过特征分析、并行化设计和并行化实现三个步骤，实现传统社区发现算法并行化。其中，并行化设计是基于BSP计算模型和TLAV编程模型，包含图划分策略、顶点状态、顶点状态更新函数和消息状态及其发送函数的设计;(3)提出了一种基于最大独立子集的图划分策略，该策略通过避免相邻顶点同时计算，解决了由计算顺序和时序依赖特征产生的并行化问题。 在上述关键技术的研究基础上，本文完成了SCAN、Semi-Clustering、MLPA、KCore、SCC和ClosenessCentrality六个典型社区发现算法的并行化设计与实现。实验结果表明，这六个算法在准确性和扩展性两个方面均表现优异。