网络划分的算法

论文摘要

实际中的网络一般具有社团网络性质,弄清它们的社团性质对于更好的理解很多网络现象有很大的帮助。本文主要围绕着网络划分算法进行了详细的探讨。第一章对网络的社团性做了初步的介绍,并且综述了一些网络划分算法的历史和发展历程。第二章主要是理论知识的阐述,是阅读本文所需要的理论基础。第三章中介绍了谱分解算法的基本原理和算法。第四章引入了模块度的概念,并介绍了两种基于模块度的网络划分算法:Newman快速算法和CNM算法。第五章在算法的时间复杂度和算法准确性两个方面分析和比较了谱分解算法和CNM算法,并籍此提出一个新的网络划分算法的框架。在第六章中,给出了一些开放性问题的探讨。第七章是全文的总结。

论文目录

• 摘要
• ABSTRACT
• 插图索引
• 表格索引
• 第一章 引言
• 1.1 什么是网络划分
• 1.2 网络划分的应用
• 1.2.1 搜索引擎
• 1.2.2 市场营销
• 1.2.3 并行计算
• 1.3 网络划分算法综述
• 第二章 术语和定义
• 2.1 基本记号
• 2.2 Laplacian矩阵及其性质
• 第三章 谱分解方法
• 3.1 基本思想
• 3.2 谱方法的理论基础
• 3.3 算法概述
• 第四章 模块度理论
• 4.1 模块度定义
• 4.2 Newman 快速算法
• 4.3 CNM 算法
• 第五章 新的算法
• 5.1 算法分析
• 5.1.1 复杂度分析
• 5.1.2 算法准确性分析
• 5.2 一种新算法框架
• 5.2.1 K-CNM 算法
• 5.2.2 框架
• 5.2.3 划分数K的选取
• 5.2.4 如何度量网络模块性
• 第六章 开放性问题研究
• 6.1 如何构建网络
• 6.2 划分结果的可解释性
• 第七章 总结
• 参考文献
• 致谢