基于共同邻居的复杂网络社团检测算法研究

摘要

随着信息技术的发展，现实世界中的许多复杂系统能够以网络的形式呈现。网络中的节点表示系统中的实体，而节点之间的连接表示实体之间的联系。由于现实世界网络的统计特征不同于规则网络和随机网络，因而将描述它们的理论模型称为复杂网络。复杂网络的社团结构表现为：紧密联系的局部节点属于同一社团，属于不同社团的节点之间联系较少。研究网络的社团结构有助于分析网络的结构特点、功能模块、信息传递、演化过程等，以及解决工程应用中的相关问题。因此，有关复杂网络社团检测的研究一直是热点问题。 层次聚类方法能够实现多粒度的社团检测，揭示网络内部的层次化结构。但是，在部分应用中，非层次聚类方法给出的一种特定的社团划分方案就足以解决问题。社团划分的质量和速度一直是评价社团检测方法的关键。为了从复杂网络中挖掘出高质量的社团结构，同时保证较快的执行速度，本文提出了两个社团检测算法，分别是基于共同邻居的层次化社团结构检测算法和基于共同邻居约束标签传播的社团检测算法。本文的创新点如下： 1）根据均值聚类的思想，从简单的邻接关系中提取关于共同邻居的信息，定义了节点亲密度以衡量相邻节点的相似性。基于节点亲密度，本文提出了一种分裂算法以层次化的方式分析网络的社团结构。该算法采用堆存储数据及索引，能够快速实现搜索最小亲密度、更新局部亲密度。实验结果表明该算法在层次化社团结构检测方面的良好效果，以及在节点度分布较为均匀的网络中执行速度较快。 2）将社团检测问题用两个优化目标来描述：社团内的联系尽可能多，以及同一社团内的节点尽量共享邻居。在此基础上，本文提出了采用标签传播策略优化两个目标的算法。为了减弱过多节点标签趋于一致的倾向，引入了已有的关于社团内边数的约束和提出的关于社团内共同邻居数的约束。结合实验对比结果和理论分析，选择合适的约束强度和加权系数。实验结果验证了该算法在社团划分质量和速度方面的优势，特别是在社团结构模糊的情况下。

目录

声明

第一章 绪论

1.1 研究背景及意义

1.1.1 研究背景

1.1.2 研究意义

1.2 研究现状

1.2.1 层次聚类算法

1.2.2 谱算法

1.2.3 动态算法

1.2.4 其他方法

1.3 研究内容与主要工作

1.4 论文结构安排

第二章 相关理论及算法

2.1.1 图

2.1.2 复杂网络的统计特征

2.1.3 复杂网络的性质

2.2 社团检测的相关研究

2.2.1 社团的定义

2.2.2 社团划分质量的评估

2.2.3 基准网络

2.3 层次聚类算法

2.4 标签传播算法

2.5 本章小结

第三章 基于共同邻居的层次化社团结构检测算法

3.1 引言

3.2.1 分裂算法

3.2.2 均值聚类

3.3 算法设计

3.3.1 定义相邻节点亲密度

3.3.2 搜索最小亲密度

3.3.3 判断是否分裂

3.3.4 快速更新亲密度

3.3.5 算法流程与概述

3.4 实验验证与讨论

3.4.1 实验环境和数据集

3.4.2 关于计算机合成网络的实验

3.4.3 关于现实世界网络的实验

3.5 本章小结

第四章 基于共同邻居约束标签传播的社团检测算法

4.1 引言

4.2.1 标签传播

4.2.2 目标优化

4.3 算法设计

4.3.1 优化目标

4.3.2 约束强度

4.3.3 更新序列

4.3.4 更新规则

4.3.5 算法流程与概述

4.4 实验验证与讨论

4.4.1 实验环境和数据集

4.4.2 关于计算机合成网络的实验

4.4.3 关于现实世界网络的实验

4.5 本章小结

第五章 总结与展望

5.1 总结

5.1.1 主要工作

5.1.2 创新点

5.2 展望

致谢

参考文献

攻读硕士学位期间取得的成果