网络社区发现技术研究

《网络社区发现技术研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、劣参京交硕士学位论文网络社区发现技术研究ResearchontheTechniquesofCommunityDetectioninNetworks作者：钟新斌导师：刘云北京交通大学2013年3月学位论文版权使用授权书本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索，提供阅览服务，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国家有关部门或机构送交论文的复印件和磁盘。(保密的学位论文在解密后适用本授权说明)靴敝储撇：钠嘁签字目期：。?口B年；月∥日导师签名：吲≥签字日期：

2、a口J；年；月∥目、中图分类号：TP301．6UDC：004．77学校代码：10004密级：公开北京交通大学硕士学位论文网络社区发现技术研究ResearchontheTechniquesofCommunityDetectioninNetworks作者姓名：钟新斌导师姓名：刘云学号：10120204职称：教授学位类别：工学学位级别：硕士学科专业：通信与信息系统研究方向：计算机网与信息系统北京交通大学2013年3月致谢转眼又到了毕业的季节，回首这两年多来研究生生活的点点滴滴，有太多的人和事让我终生难忘。值此论文完成之际，我要向多年来关心和帮助我的人表达我的感激之情，是他们的鼓励和

3、帮助使我不断成长和进步。本论文的工作是在我的导师刘云教授的悉心指导下完成的，在论文的选题、研究和撰写过程中，刘老师倾注了大量心血，提出了许多宝贵的意见。刘老师渊博的学识、严谨的治学态度和平易近人的风范让我无比钦佩。在学业中，刘老师不仅传授我们系统的学术知识，更秉承“授人以鱼，不如授之以渔”的原则指导我们学习正确开展学术和科研工作的方式方法。刘老师还注重理论与实践的结合，指导我参与了多个科研项目，使我在应用系统设计和开发方面得到了很好的锻炼。在生活中，刘老师言传身教，让我树立了正确的世界观和价值观，明白了许多做人的道理，这些都是我今后的学习生活中宝贵的财富。在此向刘云老师表达我

4、最崇高的敬意和最诚挚的感谢!其次，要向两年多来在实验室指导科研工作的张振江副教授表达我由衷的谢意。两年多来，张老师努力为我们营造良好的科研环境，悉心指导我们完成相关科研工作。从本论文的研究到完成阶段，张老师给我提出来许多宝贵的意见和建议，让我受益匪浅，在此向张老师表示衷心的感谢!同时还要感谢实验室的沈波副教授，博士研究生程军军、程辉、邓磊等学长在论文的研究和撰写过程中给予的热情帮助。在研究生的学习生活中，实验室的师兄师姐和同学对我提供了大力的支持和帮助，在此一并向他们表示感谢!此外，我还要特别感谢我的家人，多年来他们一直在背后支持和鼓励着我，使我能够顺利完成学业。“落其实者思

5、其树，饮其流者怀其源”，我还要感谢培育、教育我的母校——北京交通大学，是这里让我度过了终生难忘的美好时光。最后，衷心感谢百忙之中抽出时间评审论文的各位专家、老师，感谢所有关心和帮助我的人!中文摘要摘要：除幂律分布、小世界效应和无标度特征外，复杂网络还往往呈现一定的社区结构特征。社区结构揭示了网络的重要结构和拓扑特征，探测其中的社区结构对社会网络分析、信息推荐、犯罪网络侦测等方面具有重要的意义。本文从复杂网络的相关理论出发，介绍了当前各种重要的社区发现算法，比较分析了它们各自的特点和存在的不足，并以此为基础，提出了偏好选择标签传播算法PSLPA和基于多种群遗传算法的重叠社区发现

6、算法。PSLPA是一种非重叠社区发现算法，算法通过衡量一对节点之间的边作为社区边界的可能性和广度优先搜索算法获取网络的初始社区结构用于初始化节点的社区标签，并在标签传播过程中采用有别于LPA算法的偏好选择策略，使得社区探测结果具有较LPA算法更好的稳定性和准确性。结合Karate真实网络数据和Newman人工网络数据验证了算法的可行性和有效性。基于多种群遗传算法的重叠社区发现算法允许网络中出现“骑墙"节点。算法将社区的划分方案编码成不同的染色体，通过种群的逐代进化过程搜索具有最佳适应度的社区划分。为了避免传统的单一种群遗传算法容易导致个体早熟的缺陷，算法采用多种群进化方案。各

7、个种群在相对独立的条件下进化一定的代数，并逐步用相邻种群之间的最优个体交换本种群的最差个体，共同搜索全局最优解。算法采用LFR基准网络进行仿真和测试，验证了在不同类型的网络中算法的可行性和有效性。最后，本文将社区发现的相关技术应用于网络的舆论分析当中，设计并实现了一个基于网络社区发现技术的网络舆论分析系统。系统构建并抽取了Web2．0环境下用户的关系网络，结合社区发现技术和舆论分析的相关技术分析了网络用户的群体结构特征、社区舆论热点、社区兴趣爱好等内容。系统采用网络中的实证数据进行了运行测试，测试结果表