论文部分内容阅读
近年来,对于复杂网络的研究受到了广泛关注。现实世界中的许多系统,如社会关系网、互联网、生物网络、交通网络等等都可以建模成为复杂网络,用网络中的节点表示现实世界中的各个事物,而事物间的联系用网络中节点间的连接表示。社区结构是网络的重要特征之一,它表征着该网络中节点的不同划分。归于同一个网络社区的节点间联系较紧密,而不同社区中的节点之间联系较为稀疏。检测出网络中的社区,有助于我们分析该网络中各个事物间的关系,把握网络的整体结构。因此,对于网络社区检测方法的研究是一个非常有意义的课题。现有的很多网络社区检测算法需要预先设定社区数目,如基于谱方法的社区检测算法,而实际问题中,我们往往未知网络的社区数目,这就要求我们提出可以自动检测出所给网络中社区数目的方法。基于目标优化的社区检测算法通常可以解决这一问题。但是基于单目标优化算法的网络社区检测方法一次运行只能得到一个对网络的划分,而现实网络大多具有层次性,因此,可以输出对网络不同层次划分的社区检测方法更具有实用价值。本文提出一种基于多目标优化的社区检测方法,该算法利用了非支配邻域免疫算法(Non-dominated Neighbor Immune Algorithm, NNIA)对两个目标函数进行优化,从而检测出网络中的社区结构。同时,在演化聚类理论框架下提出动态网络社区检测方法,同样利用NNIA作为优化算法,对动态网络中的社区检测问题进行尝试性研究。本文的创新点如下：1.提出一种新的基于locus-based基因表示方式的种群初始化方法,实验证明该种群初始化方法较现有方法效率显著提高。2.提出了一种基于NNIA的网络社区检测方法(?)NIA-Net,该方法对两个目标函数进行优化,每次运行可产生一组解,这组解对应着对网络不同层次的划分,每个解可以自动确定网络中社区数目。3.在演化聚类框架下,提出一种动态网络社区检测方法DNNIA-Net,该方法对于逐步变化的动态网络,根据当前网络结构并结合其历史信息进行社区检测,得到较好的检测结果。融入对历史信息的分析,该方法的检测结果更能体现出网络动态演变的过程。本文的工作得到了国家自然科学基金(批准号：60703107),国家863项目(批准号：2009AA122210),教育部新世纪优秀人才支持计划(No.NCET-08-0811),陕西省科技新星支持计划(批准号：2010KJXX-03)和中央高校基本科研业务费重点项目(批准号：K50510020001)资助。