论文部分内容阅读
伴随着世界互联网的发展，如合作网、社交网络以及学术引用网络，可以看到复杂网络在我们的日常生活中无处不在。随着人们对复杂网络的进一步研究，逐渐发现复杂网络具有许多重要的特性，如小世界性、无标度性、社团结构等基本统计特性。其中社团结构是指网络中的节点处于同一社团内连接紧密，处于不同社团之间连接稀疏。发现复杂网络的社团结构对于研究复杂网络的功能、拓扑结构和性质、隐藏规律以及预测网络行为具有非常重要的意义。因此，复杂网络的社团发现算法研究近年来倍受学者们关注，并且形成了复杂网络中的一个重要的研究方向。 准确率和时间复杂度是复杂网络社团结构分析一直存在的两个主要问题。近年来，随着网络规模越来越大，对经典的社团发现算法发出了冲击。一些经典的社团发现算法，如GN算法、谱分析法、基于信息论的方法，在时间复杂度上无法满足现在复杂网络的要求。出现了一批新颖的算法，如标签传播算法、随机游走算法，这些算法具有可接受的线性时间复杂度;但其在准确率上有所不足。因此，本文针对社团发现算法现存的两大主要问题提出一种基于覆盖的社团发现算法—CCD算法(Community Detection Algorithm base on Cover)，该算法能够在可接受的时间内得到高准确率的社团结构;同时再针对CCD算法存在的不足，提出一种邻居节点搜索社团发现算法—NSCD算法(Neighbor Search CommunityDetection)。 本文的主要工作包括: 首先，本论文沿着对网络研究的发展主线，介绍了复杂网络社团发现算法的研究背景及其意义;总结了关于社团发现算法的发展和研究现状。然后，对复杂网络社团发现算法中主要的基本概念作了简明扼要的阐述;详细介绍一些经典算法的思想，分析了各经典算法的优缺点以及相关的改进算法。最后，在此基础上，本论文提出了两种社团发现算法。 1)提出一种基于覆盖的社团发现算法（CCD算法）:CCD算法是通过预先自定义的覆盖来识别无重叠社团结构。该算法的时间复杂度低，得到的社团结构准确率高，并且有效避免了一些经典算法无法识别小于一定粒度社团的问题，算法的时间复杂度为O（n2）。 2)提出一种基于邻居节点搜索的社团发现算法(NSCD算法):NSCD算法是基于邻居节点搜索，并通过定义一些定量条件。NSCD算法不需要设置任何参数（参数值为固定值），并具有准确率高和时间复杂度低的特点。简单的邻居节点搜索大大降低了时间复杂度。该算法的时间复杂度为O（n+m），其中n，m分别是网络的节点数和边数。此外，不同于其它算法，该算法并没有使用全局模块性或局部模块性。