数学建模——K-means聚类算法与社团发现

发布时间:2023-01-16 10:30

将之前的课程报告整理一下,以具体的应用案例介绍K-means算法与其他方法结合的应用场景。

let's go~

1  概述

复杂网络是指规模庞大,具有自组织、自相似、小世界以及无标度特性的网络[1]。随着对复杂网络的深入研究,人们发现许多实际网络都有一个共同的性质,即社团结构;换句话说,实际网络是有若干个群或者团构成。社团性质表现为社团内部之间边连接紧密,社团与社团之间联系稀疏[2][3]。复杂网络社团结构的研究对于疾病传播的控制、病毒传播等具有重大意义。

寻找复杂网络的社团结构的传统的算法是分级聚类算法。它基于网络中各个节点之间连接的相似度或者连接的强度,将网络划分为若干个子群,并且根据是向网络中添加还是移除边的方法将算法分为凝聚算法(Agglomerative method)和分裂方法(Divisive method)[4]。其中应用较为广泛分级聚类算法是由Girvan等人提出的基于边介数的分裂算法(GN算法)[5],GN算法是基于模块化优化的社团发现算法的代表,这个算法是2002年Girvan和Newman在PNAS上的一篇文章《Community structure in social and biological networks》中提出的,也是在这篇文章提出了复杂网络存在聚类特性即社团。GN算法通过不断删除介数值大的边来实现图的划分,但这一算法的复杂度太高,当节点较多时存在大量节点的重复计算,因此,在一定程度上并不适用与超大规模社交网络中的社团发现。

社交网络具有内容丰富、信息量大、节点多、随时间演化速度快等特点,在很多真实场景的研究和应用中,传统的社团发现和图划分算法并不适用,将K-means

ItVuer - 免责声明 - 关于我们 - 联系我们

本网站信息来源于互联网,如有侵权请联系:561261067@qq.com

桂ICP备16001015号