基于地理位置的网络加权化社团发现算法

《基于地理位置的网络加权化社团发现算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、万方数据分类号UDC密级学位论文基于地理位置的网络加权化社团发现算法作者姓名：王彭指导教师：赵海教授东北大学信息科学与工程学院申请学位级别：硕士学科类别：工学学科专业名称：计算机软件与理论论文提交日期：2014年6月论文答辩日期：2014年6月学位授予日期：2014年7月答辩委员△摘：高福祥评阅人：徐久强杜庆东东北大学2014年6月万方数据AThesisinComputerSoftwareandTheoryCommunityDetectionAlgorithmImprovedbyNetworkWeightingBasedonGeographyLocationsByWangPen

2、gSupervisor：ProfessorZhaoHaiNortheasternUniversityJulle2014万方数据独创性声明本人声明，所呈交的学位论文是在导师的指导下完成的。论文中取得的研究成果除加以标注和致谢的地方外，不包含其他人己经发表或撰写过的研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示谢意。学位论文作者签名：王彭日期：2D陴．0‘．2J学位论文版权使用授权书本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和

3、磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部或部分内容编入有关数据库进行检索、交流。作者和导师同意网上交流的时间为作者获得学位后：半年口一年口一年半口两学位论文作者签名：王彭导师签名：签字日期：2D忤．D6．2(签宁日期：万方数据东北大学硕士学位论文摘要基于地理位置的网络加权化社团发现算法摘要自然界中存在的大量复杂系统都可以通过复杂网络加以描述，而社团结构是继小世界特性和无标度特性之后发现的最为重要的复杂网络特性。社团是网络中关联紧密的一群节点，往往具有某些共同特征，具有一定的实际物理意义。互联网是典型的复杂网络，深入研究互联网的社团结构可以帮助我们以分而治

4、之的方式研究网络的功能及演化过程，更加准确的理解互联网的组织原则、拓扑结构等。目前针对互联网网络特性的社团发现研究还不足，传统社团发现算法并不能很好的反映互联网独有的特性。同时传统的社团发现算法大多数不能同时发现社团的重叠性和层次性。本文在局部适应度值最优化算法(LFM)思想的基础上，提出了基于共同邻居加权的社团发现算法(称之为CNW-LFM算法)。算法中通过共同邻居信息对边进行加权，其权值大小表示节点之问的紧密程度，并将适应度函数以网络中边的权值重新定义。然后在多个不同类型和不同规模的真实网络进行实验，发现CNW-LFM算法的重叠模块度高于原LFM算法，说明CNW-LFM算法

5、优于原算法，使得社团划分结果更加合理，而且该算法可以同时发现社团的重叠性以及层次性。从而证明了结合网络特性进行加权的方法是可以提高社团结构发现的准确度以及合理性，为本文重点研究互联网社团结构打下了坚实的基础。针对互联网的宏观拓扑结构下的社团研究，在CNW-LFM算法的基础上，本文提出了基于地理位置加权的社团发现算法(称之为BGW-LFM算法)。针对互联网数据量庞大的问题，算法中提出了网络规模的缩减方法，从而明显地提高了时间效率。同时该算法充分考虑了互联网的地理特性，将地理位置信息和共同邻居信息相结合对边进行加权，边的权值依然表示节点之间联系的紧密程度。然后在多个不同规模的互联网

6、网络进行实验，总结了算法中参数对社团划分结果的影响规律。对比实验中发现BGW-LFM算法的重叠模块度最高，其次是CNW-LFM算法，说明BGW-LFM算法使得社团划分结果更加合理。最后对比分析了社团结构的地理分布情况，发现BGW-LFM算泫使得社团结构的地理分布更为紧凑。通过两方面的对比说明BGW-LFM算法使得对于互联网的社团结构发现更加准确，地理分布更为合理。而且该算法可以同时发现社团的重叠性以及层次一阵。关键词：社团发现；社团重叠；互联例；地理位置；I叫络规模缩减万方数据东北大学硕士学位论文AbstractACommunityDetectionAlgorithmhnpro

7、vedbyNetworkWeightingBasedOilGeographyLocationsAbstractAlargenumberofcomplexsystemsinnaturecanbedescribedbycomplexnetwork．Communitystructureisthemostimportantfeatureofcomplexnetworkinadditiontothesmall—worldandscale-freefeature．Communityisagroupofc