基于隶属函数的社团发现算法的研究与实现

摘要

复杂网络是一门与社会学、信息学和计算机科学等许多研究领域存在交集的研究科学。近年来，随着复杂网络研究的深入发展，复杂网络中越来越多的特征被大家发现和熟知，特别是复杂网络的社团特性，这一特性不仅可以帮助大家清晰地认识和分析网络功能，还是研究复杂网络其他特性的基础。
　　本文首先从复杂网络的研究背景和意义出发，依次介绍了复杂网络的理论基础，描述了目前复杂网络社团发现算法的国内外研究现状，概述了社团结构的定义并重点介绍了几种较典型的社团发现算法。
　　针对目前大多数社团划分算法考虑影响社团划分因素不全面以及社团定义具有模糊性的情况，本文首先定义了一种计算节点到社团隶属情况的隶属函数，该函数是根据模糊数学中隶属函数的定义以及社团的基本性质而确定的。在此基础上，提出了一种基于隶属函数的启发式社团发现算法(MCDA)。该算法以隶属函数作为社团划分的衡量标准，通过计算节点到社团的隶属度，可以找到节点所属的社团。通过结合模糊聚类的基本思想和隶属度函数，MCDA算法可以得到节点到各社团的具体隶属度大小，并且隶属度函数综合考虑了多种因素，使得MCDA算法具有较高的精确性，而且还具有较低的时间复杂度。
　　此外，在MCDA算法的基础上，针对现实世界的复杂网络总是不断变化的情况，设计并实现了一种动态算法(DMCDA)。该算法弥补了MCDA算法在解决动态问题时的不足，利用动态隶属度函数与增量式动态社团发现算法的思想，实现在初始社团结果的基础上对后续动态网络的社团划分。理论与实验均证明了该算法具有较好的划分效果和较快的运行效率。

目录

声明

摘要

第1章 绪论

1．1 研究背景与意义

1．1．1 研究背景

1．1．2 研究意义

1．2 国内外研究现状与挑战

1．2．1 国内外研究现状

1．2．2 社团发现面临的挑战

1．3 本文的主要内容

1．4 本文的组织结构

第2章 复杂网络的理论基础

2．1 复杂网络的概念与特性

2．2 复杂网络的相关度量

2．2．1 复杂网络的形式化表达

2．2．2 度与度分布

2．2．3 聚类系数

2．2．4 模块度

2．3 典型的复杂网络模型

2．3．1 ER随机模型

2．3．2 WS小世界模型

2．3．3 BA无标度模型

2．4 社团定义与社团发现算法

2．4．1 社团结构的定义

2．4．2 经典的社团发现算法

2．5 本章小结

第3章 MCDA算法的设计与实现

3．1 算法的提出

3．2 算法的思想基础

3．2．1 影响社团划分的因素

3．2．2 模糊聚类算法的相关思想

3．3 算法的实现

3．3．1 相关变量

3．3．2 算法的实现过程

3．3．3 算法的思想验证

3．4 复杂度分析

3．4．1 时间复杂度分析

3．4．2 空间复杂度分析

3．5 本章小结

第4章 DMCDA算法的设计与实现

4．1 DMCDA算法的提出

4．2 算法的实现

4．2．1 相关概念

4．2．2 算法的具体实现

4．3 简单动态网络的理论验证

4．4 本章小结

第5章 实验分析

5．1 实验环境

5．2 实验数据

5．2．1 经典网络数据集

5．2．2 生成网络的数据集

5．3 实验结果与分析

5．3．1 静态算法的实验结果与分析

5．3．2 动态算法的实验结果与分析

5．4 算法评估

5．4．1 精确性指标

5．4．2 运行效率指标

5．5 本章小结

第6章 结论与展望

6．1 研究工作总结

6．2 工作展望

参考文献

致谢