复杂网络重叠社区发现算法研究

复杂网络中社区发现算法的研究具有非常重要的理论和实际意义,因此得到了包括计算机科学、数学、物理学、生物学、社会学以及经济学等各个领域的研究者的广泛关注。他们的研究已经取得了一些重要的成果,如以GN算法为代表的非重叠社区发现方法和以派系过滤方法为代表的允许节点重叠的重叠社区发现算法等。在如何评价社区发现算法结果的优劣方面,Newman等提出了模块度的概念,学者们把模块度概念扩展到包括重叠社区网络的各种网络中,并得到了相应的不同表达形式。 本文首先介绍复杂网络重叠社区发现的研究背景和意义,以及复杂网络社区发现算法的研究现状。其次对复杂网络理论的基本知识进行了阐述,包括复杂网络的历史进展,网络的图模型表示方法,复杂网络的多种结构特性,以及对复杂网络的各种网络拓扑模型。再次,本文对社区的概念进行了探讨,并对社区划分的评价标准——模块度,进行了深入研究。并且对当前社区发现算法,尤其是重叠社区发现算法进行较深入探讨,发现当前算法还存在许多不足之处,例如重叠社区发现的LFK算法虽能够覆盖整个网络,但是不能保证多次运行的稳定性,并且容易导致重叠度过大的问题等。 针对当前算法存在的不足,本文借鉴自然社区形成思想,并对自然社区形成的判断标准进行了修改,得到了本文自然社区的形成算法。我们对社区重叠性进行考察,发现影响社区重叠的因素中,社区邻居的重叠性对社区的重叠的判断占有较大的比重,因此本文在总结社区度量的标准的前提下给出了本文中社区重叠性的判断标准重叠度COD的概念。对自然社区划分后的一个许多自然社区存在重叠太大的特性,考虑到实际情况,这些自然社区可能是被错误划分成的多个社区,因此本文增加了自然社区合并过程,采用COD作为判断自然社区合并的标准,得到了我们的可调适应度和共近邻的重叠社区发现算法OCNF。实验结果证明本算法通过调节不同的参数可以得到比较好的划分结果。 本文提出的重叠社区划分算法OCNF能够成功探测到网络中重叠节点,然而还存在一些需要改进的地方,在如何降低时间运行的复杂度、算法运行结果图形化展示等多个方面还需要进一步的完善。