基于中心性与路由特征的多粒度社团发现算法

摘要

自然界中存在的大量复杂系统都可以通过复杂网络加以描述，而社团结构是继小世界特性和无标度特性之后发现的最为重要的复杂网络特性。社团是网络中关联紧密的一群节点，往往具有某些共同特征或者指示网络中的功能实体。面对网络中大量的目标对象，常常需要将这些对象多粒度地分类以进行研究或处理，这就需要有效的多粒度社团发现工具，因此复杂网络多粒度社团发现算法的研究具有重要意义。
　　传统的社团发现算法大多数基于社团无重叠的假设，且少有能发现层次的多粒度社团结构的算法，而现有的研究发现，许多真实网络存在社团重叠现象和社团层次结构，因此，传统社团发现算法并不能很好的反映真实复杂网络的社团特征。边聚簇社团发现算法以边聚簇为基本聚类方法，能够发现有重叠的多粒度社团结构。
　　基于边聚簇算法思想，本文使用四种不同的复杂网络中心性指标重新定义算法中的边相似性，改造算法中的关键聚簇过程，提出基于中心性的边聚簇社团发现算法，对比不同中心性对应的社团发现结果，发现基于紧密度中心性的边聚簇得到最大的分割密度，在互联网以及其他类型网络上能比原算法更好地发现社团结构。
　　目前针对互联网拓扑的社团结构的研究比较少，网络中连接不同社团的边往往是探测边频很大的边，基于边聚簇算法思想，本文提出基于路由特征的多粒度社团发现算法，以探测边频为影响因子定义边相似性，改造算法中的关键聚簇过程，得到比原算法更高的分割密度。边介数有类似于探测边频的性质，以边介数替代探测边频使该算法可以应用在其他类型网络中，同样取得较好的效果。
　　本文提出一种综合四种国际常用的社团算法评价指标的综合评价方法，并选取了八个不同类型和不同规模的真实网络拓扑作为测试数据集，使用该综合评价方法对算法进行评价并得出结论:基于中心性和路由特征的多粒度社团发现算法能够比原算法更好地发现社团结构。

目录

声明

摘要

第1章 绪论

1．1 课题研究的背景与意义

1．1．1 课题背景及意义

1．1．2 本文的研究意义

1．2 社团结构研究现状

1．2．1 社团结构

1．2．2 社团发现算法

1．2．3 社团可视化

1．3 本文研究内容

1．4 本文组织结构

第2章 边聚簇社团发现算法模型

2．1 构建树图

2．2 社团划分：树图的分割

2．2．1 分割密度

2．2．2 使用分割密度分割树图

2．3 边聚簇算法的测试数据集

2．4 本章小结

第3章 基于中心性的边聚簇

3．1 复杂网络中心性概述

3．1．1 度中心性指标

3．1．2 特征向量中心性指标

3．1．3 紧密度中心性指标

3．1．4 介数中心性指标

3．2 基于复杂网络中心性的边聚簇设计与实现

3．3 基于复杂网络中心性的边聚簇

3．3．1 基于度中心性的边聚簇

3．3．2 基于特征向量中心性的边聚簇

3．3．3 基于紧密度中心性的边聚簇

3．3．4 基于介数中心性的边聚簇

3．4 真实网络数据集上的测试

3．5 本章小结

第4章 基于路由特征的边聚簇

4．1 复杂网络与互联网

4．2 基于路由特征的边相似性

4．3 在真实数据集上的测试

4．4 本章小结

第5章 社团发现算法评价体系

5．1 传统社团发现算法的评价方法

5．2 重叠社团模块度

5．3 社团划分算法综合评价体系

5．4 本章小结

第6章 总结与展望

6．1 本文所做的工作

6．2 不足及展望

参考文献

致谢

攻读硕士学位期间发表的论文