基于社团结构核心区域集的凝聚图聚类算法

摘要

复杂网络是对现实世界中存在的大型复杂系统的高度抽象，具有不同于传统研究领域常见的规则网络和随机网络的统计特征，其中比较有代表性的有小世界效应，无标度特性，聚集性，网络传递性和社团结构等。近年来，以交互作用图建模并通过各种图聚类技术发现复杂网络内部隐含的社团结构已成为研究热点。凝聚聚类是主要的图聚类方法之一，图的凝聚聚类是从完全离散的原始结点开始自底向上粒度不断增大的过程，一般凝聚聚类算法在初始时并不直接显式地考虑网络的聚类核心的存在性，从而可能影响聚类精度。
　　本文利用核心区域集的概念对凝聚图聚类算法进行了深入研究，主要研究成果如下:
　　(1)针对现实世界的大型网络，提出了社团结构核心区域概念，现实世界的大型网络系统具有社团结构特性，社团内部结构紧密，社团之间结构松散。根据社团结构核心区域概念，从结构出发定位网络中结构紧密区域，使得划分更明确，克服了凝聚聚类算法必须从单结点作为单独一类并逐渐合并造成的执行效率上的浪费，并且为提高聚类精度提供了优化的初始条件。
　　(2)从网络结构出发，提出了一种新的相似性度量方法，该度量方法能够精确地度量核心区域与未分类结点与之间的相似性，从而有效地改进了凝聚图聚类算法。
　　(3)在Visual Studio2008+Matlab R2009a平台上，实现了相关算法并对时间复杂度进行了分析。通过对多个标准数据集进行测试并给出了划分结果和实验分析，实验结果表明该算法能够提高聚类的准确性。
　　总之，本文从网络的整体结构出发，通过定义合理的社团结构核心区域和未分类结点的距离度量，提出了一种新的凝聚图聚类方法，进行了实验并给出简单例证，通过对实验结果的对比分析和聚类结果评测，表明其可有效地提高聚类的质量，具有一定的理论意义。

目录

摘要

第一章 引言

1．1 论文的研究背景及意义

1．2 网络社团发现算法概述

1．3 本文主要工作及论文组织

第二章 社团结构核心区域

2．1 类中心选取

2．1．1 传统初始类中心

2．1．2 结点重要度算法介绍

2．1．3 最大最小距离法

2．2 社团结构核心区域的定义及求取

2．3 社团结构核心区域算法设计

2．4 本章小结

第三章 改进的凝聚算法

3．1 传统凝聚算法

3．1．1 传统凝聚算法概述

3．1．2 典型的凝聚算法—Newman贪婪算法

3．2 改进的凝聚算法

3．2．1 凝聚过程原理

3．2．2 类的合并原理及方法

3．3 凝聚算法设计与描述

3．4 本章小结

第四章 实验分析

4．1 聚类质量衡量标准

4．2 实验

4．2．1 Karate俱乐部数据及实验结果

4．2．2 Football俱乐部数据及实验结果

4．3 本章小结

第五章 结论与展望

参考文献

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

攻读硕士学位期间参加的科研项目

致谢

个人简况及联系方式

声明