聚类算法在社团划分中的研究与应用

《聚类算法在社团划分中的研究与应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、中图分类号：TP391单位代码：11414学号：2012215062题目聚类算法在社团划分中的研究与应用学科专业计算机科学与技术研究方向数据挖掘及知识发现硕士生周静指导教师吴卫江副教授入学时间：2012年9月论文完成时间：2016年5月硕士学位论文独创性声明郑重声明：本硕士学位论文是作者个人在导师的指导下，独立进行研究工作所取得的成果。除了文中特别加以标注和致谢的地方外，论文中不包含其他个人和集体己经发表或撰写的研宄成果，也不包含为获得中国石油大学或者其它单位的学彳立或证书所使用过的材料。对本研宄做出贡献的个人

2、和集体，均已在论文中做了明确的说明并表示了谢意。作者和导师完全意识到本声明产生的法律后果并承担相应责任。作者签名）：＾日期：民轉Ｊ导师签名￣：日期：ｆ）、ｊ硕士学位论文版权使用授权书本学位论文作者及指导教师完全了解中国石油大学（北京）学位论文版权使？用的有关规定？，使用方式包括但不限于学校有权保留并向有关部门和机构送交学位论文的复印件和电子版；允许学位论文被查阅和借阅；学校可以公布学位论、文的全部或部分内容，可以采用影印缩印或扫描等复制手段保存和汇编学位论内容编入有关数据库进行检索。

3、文；可以将本学位论文的全部或部分保密期限〇年，解密后适用本授权书。本学位论文属于保密范围，本学位论文作者如需公开出版学位论文的部分或全部内容，必须征得导师书一署名单位石油大学（北京）为第。面同意，且须以中国日期：作者签名：ＩＳＪ１＿＿＿日—州“、－．导师签名：—飞＂ＩＩ摘要摘要复杂网络是近年来兴起的一个研究热点，人们除了研究它的小世界性和无标度性外，还格外关注它所包含的社团结构。同社团结构内部节点联系紧密，社团间的节点联系较少，本文基于社团结构这一特性展开研究。通过挖掘复杂网络中存在的社团

4、结构，可以分析整个复杂网络的拓扑结构和功能，发现网络中隐藏的规律。受到谱平分算法的启发，定义了网络的节点重要度矩阵，结合聚类分析算法，提出了一种基于节点重要度的社团划分算法(ACommunityDiscoveryAlgorithmbasedonNodeImportanceMatrix，简称CDNIM算法)，该方法将节点重要度矩阵和图的特征谱平分法相结合，对数据进行处理，利用K-means算法对网络中的节点进行分类，基于模块度函数查找网络中最佳社团数目，当模块度值最大时，对应的社团结构即为网络的最佳社团划分结果。通过在空手道俱乐

5、部网络、海豚关系网、足球队网络等数据集上的应用，验证了CDNIM算法的准确性和有效性。实验也表明，在准确率方面CDNIM算法比K-L、GN等经典算法划分社团的准确率高。关键词：社团结构；谱平分；聚类算法；模块度-II-ABSTRACTTheResearchandApplicationofCommunityDetectionbyUsingClusteringAlgorithmABSTRACTComplexnetworkisaresearchhotspotinrecentyears,peoplealsopayattentionto

6、thecommunitystructurebesidesthesmallworldandscale-freenetworkfeatures.Thenodeswithinthesamecommunityconnectclosely,whilebetweenthecommunitiesconnectloosely.Basedonthecharacteristicsofcommunitystructure,thispaperhasproposedtheCDNIMalgorithm.Throughvalidlyminingthecom

7、munityexistedincomplexnetworks,thetopologicalstructureandfunctionofcomplexnetworkscanbeanalyzed,andhiddenrulescanbefoundaswell.Basedontheelicitationofspectralbisectionmethod,nodeimportantmatrixisdefinedinthispaper,andcombinedwiththeclusteringalgorithm,ancommunitypar

8、titionalgorithm(ACommunityDiscoveryAlgorithmbasedonNodeImportanceMatrix,simplycalledCDNIM)basedonnodeimportanceisproposed.Thismethodcombin