简论网络基于多目标优化算法网络社区检测策略

摘要：近年来,对于复杂网络的探讨受到了广泛关注。现实世界中的许多系统,如社会联系网、互联网、生物网络、交通网络等等都可以建模成为复杂网络,用网络中的节点表示现实世界中的各个事物,而事物间的联系用网络中节点间的连接表示。社区结构是网络的重要特点之一,它表征着该网络中节点的不同划分。归于同一个网络社区的节点间联系较紧密,而不同社区中的节点之间联系较为稀疏。检测出网络中的社区,有助于我们浅析该网络中各个事物间的联系,把握网络的整体结构。由此,对于网络社区检测策略的探讨是一个非常有作用的课题。现有的很多网络社区检测算法需要预先设定社区数目,如基于谱策略的社区检测算法,而实际不足中,我们往往未知网络的社区数目,这就要求我们提出可以自动检测出所给网络中社区数目的策略。基于目标优化的社区检测算法通常可以解决这一不足。但是基于单目标优化算法的网络社区检测策略一次运转只能得到一个对网络的划分,而现实网络大多具有层次性,由此,可以输出对网络不同层次划分的社区检测策略更具有实用价值。本论文提出一种基于多目标优化的社区检测策略,该算法利用了非支配邻域免疫算法(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)资助。关键词：复杂网络论文社区检测论文优化算法论文演化聚类论文动态网络论文

摘要3-5

Abstract5-9

第一章 绪论9-15

§1.1 课题探讨背景及作用9-10

§1.2 社区检测不足探讨历史和进展概述10-12

§1.3 基于优化的社区检测策略概述12-14

§1.4 论文的主要工作和内容安排14-15

第二章 多目标优化论述及进展15-23

§2.1 人工免疫算法概述15-16

§2.2 人工免疫系统的探讨近况及基本术语16-18

2.2.1 人工免疫网络模型的探讨16

2.2.2 人工免疫系统算法的探讨16-17

2.2.3 人工免疫算法基本术语介绍17-18

§2.3 多目标优化论述基础及进展18-20

§2.4 非支配邻域免疫算法介绍20-21

§2.5 本章小结21-23

第三章 基于NNIA的网络社区检测算法23-41

§3.1 网络常用基本概念23-26

3.1.1 Community Score (CS)24-26

3.1.2 Communi-Fitness (CF)26

§3.2 NNIA-Net算法流程26-29

3.2.1 Locus-based基因表示策略27

3.2.2 算法流程图及具体步骤27-29

§3.3 NNIA-Net中的主要算子29-32

3.3.1 种群初始化策略29-31

3.3.2 克隆算子31

3.3.3 交叉算子31

3.3.4 变异算子31-32

§3.4 NNIA-Net实验结果及浅析32-40

3.4.1 新种群初始化策略实验结果32-33

3.4.2 评价网络社区检测结果的两项标准33

3.4.3 NNIA-Net在真实网络上的实验结果33-37

3.4.4 NNIA-Net在GN Benchmark上的实验结果37-38

3.4.5 NNIA-Net在GN Benchmark扩展网络上的实验结果38-40

§3.5 本章小结40-41

第四章 基于NNIA的动态网络社区检测算法41-53

§4.1 动态网络探讨背景和进展概况41-42

§4.2 演化聚类框架介绍42-45

4.2.1 演化聚类框架运用背景42-43

4.2.2 演化聚类框架介绍43-45

§4.3 DNNIA-Net算法流程及具体步骤45-48

4.3.1 动态网络的表示策略45-46

4.3.2 DNNIA-Net算法流程46-48

§4.4 DNNIA-Net实验结果及浅析48-51

4.4.1 DNNIA-Net在合成数据集上的实验结果48-50

4.4.2 DNNIA-Net在真实动态网络上的实验结果50-51

§4.5 本章小结51-53

第五章 总结和展望53-55

§5.1 本论文工作总结53-54

§5.2 未来展望54-55