复杂网络中社团结构发现算法的研究与实现

《复杂网络中社团结构发现算法的研究与实现》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、声明尸明本学位论文是我在导师的指导下取得的研究成果，尽我所知，在本学位论文中，除了加以标注和致谢的部分外，不包含其他人已经发表或公布过的研究成果，也不包含我为获得任何教育机构的学位或学历而使用过的材料。与我一同工作的同事对本学位论文做出的贡献均已在论文中作了明确的说明。研究生签名：班涟连卫忡年弓月卫日学位论文使用授权声明南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅或上网公布本学位论文的部分或全部内容，可以向有关部门或机构送交并授权其保存、借阅或上网公布本学位论文的部分或全部内容。对于保密论文，按保密的有关规定

2、和程序处理。研究生签名：弘坚嗌261十年弓月女日硕士学位论文复杂网络中社团结构发现算法的研究与实现摘要复杂网络涉及到多个学科，近年来得到越来越多的重视，逐步成为研究的焦点。社团结构作为复杂网络的一个重要特征，对认识与剖析复杂网络具有举足轻重的作用，因此探测复杂网络中的社团结构对研究整个网络的布局与性质显得十分必要。已往人们已经提出了许多算法用于探测网络中的社团结构，本文研究了其中两种经典的社团发现算法并在其基础上进行改进，提出了两种改进的社团结构发现算法，主要工作如下：(1)复杂网络聚类算法是网络中用于探测社团的一种有效

3、方法。已往的复杂网络聚类算法的结果依赖于初始化的选择，极易导致局部最优解，因此不适用于规模较大、结构复杂、社团结构不明显的网络。为了解决上述问题，本文提出基于蚁群聚类的社团结构发现算法，算法首先使用改进的谱平分法将网络中将节点及节点问的关系转换为供聚类分析的数据对象，再运用蚁群聚类算法对得到的数据对象进行分析，最终根据网络的模块度选择最佳划分。最后，将本文算法进行扩展用于探测加权网中的社团结构。实验表明，该算法克服了已往聚类算法的缺点，具有较好的执行效率，得到了较为理想的划分结果。(2)随着时代的发展，现实中的网络规模越

4、来越大，因此发现整个网络的所有社团变的复杂且耗时耗力。而另一方面，人们往往只关注某个节点所在的局部社团，于是用于探测局部社团结构的算法逐渐受到人们热捧。已往的局部社团发现算法执行结果依赖于初始节点的选择，而且需要给出局部社团节点数。针对以上问题，本文提出基于局部网络信息的复杂网络局部社团发现算法。算法利用网络自身的局部连接特点，从网络中指定节点出发，通过不断搜索邻居节点，将与社团连接最紧密的邻居节点加入社团，从而将初始节点所在的社团划分出来。最后，将算法进行扩展，扩展算法不但能探测整个网络的社团结构，而且能够得到网络中的

5、重叠节点。实验表明本文算法克服了已往局部社团发现算法的缺点，具备良好的划分效果。关键词：社团结构，谱平分法，蚁群聚类，NgN圣．a信息，局部社团发现Abstract硕上学位论文Complexnetworksrelatetovariousdisciplines．Inrecentyearstheyhaveattractedmoreandmoreattentionandgraduallybecomethefocusoflatelyresearch．Asanimportantfeatureofcomplexnetworks，co

6、mmunitystructureplaysadecisiveroleinnetworkanalysis．Sothediscoveryofcommunitystructureincomplexnetworksisverynecessaryinthestutyofnetworkstructureandfunction．Peoplehaveproposedmanyalgorithmsforfmdingcommunitystructureincomplexnetworks．ThisPaDerstudiestheclassicco

7、rrtmunitystructurediscoveryalgorithm，thenweproposetwonewcommunitystructurealgorithmbasedontheseformeralgorithms．Themaintaskoftiffspaperisasfollows：(1)Complexnetworkcluster-algorithmisaneffectivemethodincommunitystructurediscovery．Mostoftheproposedcomplexnetworkcl

8、uster-algorithmsalesensitivetotheinitializationandareeasytogetlocaloptimalsolution，SOtheyarenotapplicablefornetworkswhosestructureiscomplexandcommunityisnotobv