复杂网络重叠社区结构的研究

作     者：赵焕成 

作者单位：西安理工大学 

学位级别：硕士

导师姓名：王林

授予年度：2010年

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

主      题：重叠社区结构 模块度 复杂网络 极大社区 

摘      要：本文从复杂网络的研究背景、意义出发,介绍了复杂网络当前的研究现状,并通过介绍基本理论知识,引进该领域的一个研究热点—复杂网络的社区结构,探测网络的社区结构是一个非常具有挑战性和前瞻性的工作,对于理解网络的结构和功能特性有着深刻的理论意义和重要的实用价值。 目前,关于网络的社区结构取得了一定的成果,提出了许多社区结构的发现算法。然而,大多数算法都是对网络的一个硬性划分,假定所发现的社区是彼此不重叠的,一个节点只能属于一个社区。这对结构清晰的网络十分有效,在实际网络中,社区结构往往并非如此显著。在由众多节点构成的连接混乱的网络中,社区间的过度是平滑的,存在重叠的社区结构。 本文较为详细地综述了近年来复杂网络重叠社区结构的研究成果,介绍了几种较为典型的算法,如派系过滤算法、基于重叠模块度的优化算法、能够同时探测层次性和重叠性的算法等等,对以后的发展能够提供帮助和借鉴。 最后,本文对企业网络、人造网络、BBS用户兴趣网络加以实证分析,结果表明：这些网络在某种程度上存在重叠的社区结构。对企业网络进行分析,我们发现,适当的人为增加网络的重叠性,可以促进企业内部员工的交流,有助于企业的健康发展。对人造网络进行分析,结果显示,该网络具有很好的层次性和重叠性,这给我们一种启示,对有层次性的网络逐层划分,可以更有效的挖掘网络的潜在信息。对BBS用户兴趣网络的实证研究表明,该网络是一个无标度网络,度分布、社区大小分布都服从幂率分布,社区大小分布极不均匀,存在少数规模很大的社区,这就是所谓的极大社区,且社区间存在重叠的部分。