基于局部相似性的社团检测算法研究

摘要

现实生活中的很多网络,如互联网,电力系统网,神经网,人际关系网,都可以看成是复杂网络。这些网络共同的特点就是具有小世界,无标度,社团结构等特性。其中社团结构是复杂网络最重要的特性之一,寻找和分析社团结构有助于更好地了解网络的内部结构,分析网络的性质。所以,复杂网络的社团结构研究近年来成为人们研究的热点问题,大量的复杂网络社团挖掘算法陆续被提出来。本文从社团的相似性定义出发,研究了现有的节点相似性度量指标,提出了一种新的局部相似性指数,结合现有的基于相似性的社团检测算法对网络社团进行划分。主要工作如下:
　　(1)研究经典的复杂网络社团结构检测算法,分析了研究复杂网络社团结构的一般方法。
　　(2)在研究现有的网络节点的相似性指标的基础上,定义了一种新的局部相似性指数,从理论上证明了该局部相似性指数在社团检测方面比其它局部相似性指数更具优势。
　　(3)提出了一种基于局部相似性的K-means谱聚类算法,该算法采用网络节点相似性矩阵的前 K个最大特征值所对应的特征向量为坐标,将网络节点映射到欧式空间,再采用 K-means谱聚类算法对其进行社团划分,算法根据最大特征值间距预测社团个数,再采用模块度进行验证。在计算机生成的网络和大量的实际网络验证该算法的可行性和有效性。
　　(4)提出了一种基于局部相似性的AP聚类算法,该算法以节点的局部相似性矩阵作为基础,起初将所有的节点视为聚类中心,通过对每个节点的“吸引度”和“归属度”不断修改,来确定最优的聚类中心和每个节点的社团归属。在计算机生成的网络和大量的实际网络上验证了算法的可行性和有效性。
　　(5)将定义的局部相似性指数和现有的基于相似性的聚类算法相结合对计算机生成的网络和大量的实际网络进行社团划分,并和GN算法,快速算法等做了比较,结果表明,所定义的相似性指数和传统局部相似性指数相比,能够更为准确的刻画网络节点的相似性,该相似性和大多数基于相似性的算法相结合都能够较为准确的检测网络的社团结构,因此,所提相似性指数是一种比较有竞争力的相似性指标。

目录

封面

声明

中文摘要

英文摘要

目录

1绪论

1.1研究背景和意义

1.2 国内外研究现状

1.3论文的研究内容和结构框架

2社团结构检测

2.1复杂网络概述

2.2社团的定义

2.3复杂网络中社团划分的评判标准

2.4社团检测结果的比较

2.5 计算复杂度

2.6社团检测基准网络

2.7社团发现的经典算法

2.8本章小结

3基于局部相似性的K-means谱聚类算法

3.1相似性度量

3.2基于相似性的聚类算法

3.3基于局部相似性的K-means谱聚类算法设计

3.4本章小结

4基于局部相似性的近邻传播聚类算法

4.1近邻传播算法

4.2基于局部相似性AP算法设计

4.3本章小结

5结论

5.1全文总结

5.2后续研究工作展望

致谢

参考文献