基于局部相似性的K—means谱聚类算法.pdf

《基于局部相似性的K—means谱聚类算法.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、西安理工大学学报JournalofXi’anUniversityofTechnology(2013)Vo1．29No．4455文章编号：1006-4710(2013)04-0455-05基于局部相似性的K—means谱聚类算法王林，高红艳，王佰超(1．西安理工大学自动化与信息工程学院，陕西西安710048；2．宝鸡文理学院物理与信息技术系，陕西宝鸡721016)摘要：定义科学的局部相似性指数是基于局部相似性社团发现算法的关键，根据共有邻居信息定义的局部形似性指数对直接相连接点对的相似性数值存在低估倾向，本研究将节点对的关联信息加入到sq,rensen局部相似性指

2、数的定义中，结合K．means谱聚类算法对网络节点进行聚类。本研究定义的局部相似性指数克服了传统局部相似性指数的缺点，且保持了原有的计算复杂性。在计算机生成网络和实际网络上运行，并和经典算法做了比较，实验证明，所提算法能够较为有效、准确地检测网络的社团结构。关键词：局部相似性；谱聚类；K．means聚类中图分类号：TP15文献标志码：AAlgorithmofK-meansSpectralClusteringBasedonLocalSimilarityWANGLin，GAOHongyan，WANGBaichao(1．FacultyofAutomationandIn

3、formationEngineering，Xi’anUniversityofTechnology，Xi’an710048，China；2．FacultyofPhysicsandInformationEngineering，BaojiUniversityofArtandScience，Baoji721016，China)Abstract：Thecorrelationinformationofnodepairsisincoporatedinthedefinitionofs+re~enIocaIsimi．1arityindex，networknodesareclust

4、eredbythissimilaritymeasurecombiningwithKmeansspectralclus—tering．Thesimilarityindexproposedbythepaperovercomestheshortcomingsoftraditionallocalsimilari—tyindex，andmaintainstheoriginalcomputationalcomplexity．Theproposedmethodistestedonbothcomputer-generatedandreal-worldnetworks，andis

5、comparedwiththetypicalalgorithmsincommunitydetection．Experimentalresultsverifyandconfirmthefeasibilityandvalidityoftheproposedmethodtomonitorcommunitystructureofrealinternetaccurately．Keywords：localsimilarity；spectralclustering；K—meansclustering社团结构是复杂网络的重要特性之一，研究社邻居的节点对具有零相似性，这显然是不合

6、适的。团结构有助于了解网络结构，分析网络特性，预测网因此，寻找一个计算简单，且能准确刻画网络结构的络功能引，所以社团检测近年来成为学者们研究相似性指数仍然是人们迫切需要解决的问题。的热点问题。基于上述问题，本研究提出了一种新的局部相基于相似性的算法是一类重要的社团检测算似性指数，该指数以sdprensen指数为原形，考虑了法，它利用网络的全局或者局部特性计算节点或边节点直接相连接对相似性的影响，采用K-means谱的相似性，再结合传统聚类算法社团划分。该聚类法对网络节点进行聚类，与基于传统的局部相算法的关键是定义合适的“相似性指数”。一类相似性指数的社团发现算法

7、和几种典型的社团发现算似性指数是全局的，考虑了网络的全局信息，计算准法做了比较，在计算机生成的网络和实际网络上验确，但运算复杂度高，而且引进了额外参数，实用性证，结果显示，所提的算法能够克服传统局部相似性不强。另一类相似性指数为局部指数，采用节的缺点，继承传统局部相似性计算量小的特点，能够点的共有邻居数或简单变形来衡量节点相似性，无准确，有效地检测人工合成网络和实际网络的社团视节点是否直接相连，从而使直接相连的但无共同结构。收稿日期：2013-04-20作者简介：王林，男，教授，研究方向为复杂网络、数据库等。E—mail：wanglin@xaut．edu．an。

8、456西安理工大学学报(