复杂网络的非重叠与重叠社区检测方法

摘要

网络社区检测是复杂网络研究中非常重要的问题之一,过去十年里,有众多解决该问题的算法被提出,这些算法主要包括层次聚类的算法以及基于函数优化的算法。研究的网络类型主要包括:静态非重叠网络,重叠网络以及层次结构网络。在本文中,我们对以上三种网络进行了研究,并提出了两种解决以上网络社区检测问题的算法。本文所做的主要工作如下:
　　(1)针对传统进化算法在解决网络社区检测问题时收敛速度慢,以及容易陷入局部最优等缺点,提出一种结合模拟退火算法的密母算法。该算法将遗传算法作为全局搜索策略,模拟退火算法作为局部搜索策略,既加快了算法收敛速度,同时增强了算法跳出局部最优的能力。另外,针对传统模块度优化具有的分辨率限制问题,采用了扩展的模块度密度函数作为适应度函数,通过调节可调参数,可以以不同分辨率对网络进行分析。
　　(2)提出了一种基于两阶段策略的非重叠,重叠以及等级结构复杂网络社区检测算法。算法第一阶段采用Clauset、Newman和Moore等人提出的快速模块度(fast modularity)算法,检测得到非重叠的等级网络社区结构。在第二阶段提出了一个基于局部社区概念的影响系数函数,利用该函数通过调节可调参数可以在不同重叠程度上获得重叠的网络社区结构。同时,当可调参数为0.5时,可以对第一阶段划分错误的节点进行纠错。实验结果及分析表明我们所提的算法及评价函数是可行且有效的。
　　本文工作得到如下基金资助:
　　国家自然科学基金(61003199),中央高校基本科研业务费专项资金资助项目(K50510020015和K5051202019)。

目录

封面

声明

中文摘要

英文摘要

目录

第一章 绪论

1.1 引言

1.2 复杂网络的基本概念

1.3 复杂网络社区检测

1.4 网络社区检测的研究进展与趋势

1.5 本文工作及内容安排

第二章 复杂网络社区检测典型方法

2.1 非重叠网络社区检测

2.2 重叠网络社区检测

2.3 本章小结

第三章 结合模拟退火策略的密母算法用于复杂网络社区检测

3.1 引言

3.2 目标函数

3.3 算法流程

3.4 密母算法设计的几个关键问题

3.5 密母算法实验结果及分析

3.6 本章小结

第四章 基于两阶段策略的非重叠、重叠以及等级结构复杂网络社区检测方法

4.1 引言

4.2 算法流程

4.3 实验结果及分析

4.4 本章小结

第五章 总结和展望

5.1 总结

5.2 展望

致谢

参考文献

攻读硕士研究生期间的成果