微博网络中的重叠社区发现算法研究

发布时间：2017-05-19 10:22

  本文关键词：微博网络中的重叠社区发现算法研究，，由笔耕文化传播整理发布。

【摘要】：随着互联网和移动通信技术的快速发展,越来越多的用户开始使用社交系统进行信息交换和共享,形成了越来越庞大的社交网络。这种形成于物理网络之上的逻辑网络反映了人们的偏好和社会关系,如何发现社交网络的特征和潜在价值已成为研究者们广泛关注的问题。作为网络(特别是社交网络)研究的内容之一社区发现对于研究网络内部的结构特征有着十分重要的意义。本文以微博网络为对象,研究具有重叠结构的网络,并提出了一种重叠社区发现算法。论文的主要工作包括以下几个方面：· 从三个方面入手,研究了社区发现方法的发展与现状：从复杂网络理论的角度出发,分析讨论了传统的复杂网络框架下的社区发现算法的原理、特点和优劣；分析归纳了微博网络的特性,并总结了利用该类特性进行传统社区发现算法改进的各类算法和方案；概括总结了复杂网络中利用遗传算法进行社区发现的关键技术。· 提出了一种基于遗传算法的重叠社区发现算法(Overlapping Community Detection based on GA for Weighting Weibo Network, WOGA)。WOGA算法主要分两大部分：微博网络的加权算法(Weibo Network Weighting Method,WNWM);基于遗传算法的重叠社区发现(Overlapping Community Detection based on GA, OCDGA)。WNWM综合考虑微博用户间显性关系、交互频率、主题兴趣相似度、用户标签相似度等因素,建立了一个用户关系强度评价模型,进而对微博网络中用户间的连接边进行加权。OCDGA通过改进自适应迁移策略的多种群遗传算法原有的矩阵编码方案,对个体进行编码；利用加权网络改进重叠模块度函数,用作个体适应度函数；建立了基于节点中心性原则和节点相似度原则的种群初始化方案；构建了基于重叠社区和矩阵编码方式的交叉和变异运算,并设计了部分精英保留策略的选择算法。此外,OCDGA还引入了自适应种群迁移策略以保证算法执行效率的同时提高其准确度。·给出了基于MapReduce的WNWM算法和OCDGA算法的分布式实现方案。在OCDGA算法的分布式实现过程中,提出使用粗粒度-粗粒度的层次PGA (Parallel Genetic Algorithms,并行遗传算法)模型来设计种群间的迁移规则。本文分别在人工网络、经典的真实网络和微博网络三种类型的网络上测试了WOGA算法的实验结果,并与传统的社区发现算法进行比较。实验结果证明了本文提出的算法具有较高的准确度,特别是在微博网络的用户交互行为和网络结构的分析中,WOGA算法有较好的效果。
【关键词】：复杂网络 微博网络 重叠社区发现 加权策略 多种群遗传算法 MapReduce
【学位授予单位】：北京交通大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：O157.5;TP393.092
【目录】：

• 致谢5-6
• 摘要6-8
• ABSTRACT8-13
• 1 绪论13-19
• 1.1 研究背景与意义13-15
• 1.2 论文研究内容15-16
• 1.3 论文结构安排16-19
• 2 复杂网络与社区发现19-33
• 2.1 引言19
• 2.2 复杂网络19-22
• 2.2.1 复杂网络的概念与表示方法19-20
• 2.2.2 复杂网络的特征度量20-21
• 2.2.3 复杂网络的特性21-22
• 2.3 社区发现22-25
• 2.3.1 复杂网络的社区结构22-23
• 2.3.2 社区结构评价函数23-24
• 2.3.3 复杂网络的社区发现算法24-25
• 2.4 微博网络的社区发现25-29
• 2.4.1 基于微博主题的社区发现25-26
• 2.4.2 基于用户属性的社区发现26-27
• 2.4.3 基于交互行为的社区发现27-29
• 2.5 遗传算法29-32
• 2.5.1 遗传算法原理29-30
• 2.5.2 遗传算法在社区发现中的应用30-32
• 2.6 本章小结32-33
• 3 微博网络的用户关系评估33-43
• 3.1 引言33
• 3.2 基于用户显性关系的静态拓扑结构33-34
• 3.3 基于交互信息的用户关系评价34-36
• 3.4 基于主题兴趣的用户关系评价36-39
• 3.4.1 中文分词与特征词提取36-37
• 3.4.2 基于微博的用户关系评价37-38
• 3.4.3 基于标签的用户关系评价38-39
• 3.5 微博用户关系强度评估模型39-41
• 3.6 本章小结41-43
• 4 基于遗传算法的重叠社区发现43-57
• 4.1 引言43
• 4.2 编码方式与个体适应度函数43-45
• 4.3 种群初始化45-49
• 4.3.1 社区中心节点的生成46-47
• 4.3.2 初始社区的生成47-49
• 4.4 交叉算子49-51
• 4.5 变异算子51-52
• 4.6 选择算子52-53
• 4.7 种群迁移策略53-55
• 4.8 算法整体描述55-56
• 4.9 本章小结56-57
• 5 大数据环境下算法的分布式实现57-71
• 5.1 引言57
• 5.2 HADOOP分布式计算框架57-60
• 5.2.1 MapReduce分布式计算模型57-59
• 5.2.2 Hadoop分布式运行环境59-60
• 5.3 微博网络加权策略的分布式实现60-63
• 5.4 多种群遗传算法的分布式实现63-69
• 5.4.1 并行遗传算法63-65
• 5.4.2 OCDGA算法的分布式实现65-69
• 5.5 本章小结69-71
• 6 实验结果与分析71-81
• 6.1 引言71-72
• 6.2 人工网络结果分析72-73
• 6.3 经典真实网络结果分析73-75
• 6.4 微博网络结果与分析75-80
• 6.4.1 微博网络数据的采集75-76
• 6.4.2 社区发现结果与分析76-80
• 6.5 本章小结80-81
• 7 总结与展望81-83
• 7.1 总结81-82
• 7.2 展望82-83
• 参考文献83-87
• 作者简历及攻读硕士学位期间取得的研究成果87-91
• 学位论文数据集91

【相似文献】

中国期刊全文数据库 前10条

1 胡洪林;;截断思想在算法分析中的应用[J];科技风;2012年12期

2 陈际平;算法分析与优化程序的研究[J];西北大学学报(自然科学版);1994年05期

3 梁彦杰;徐坚;;算法分析中概率变化与图形生成[J];云南大学学报(自然科学版);2009年S2期

4 刘宁;邵晓艳;;算法分析与设计课程中多媒体技术的应用[J];科技风;2009年18期

5 海亚;张永平;;算法对学生解决问题能力的培养[J];黑龙江科技信息;2008年10期

6 李冰颖,夏利民,舒远仲;学分制模式下网上选课系统的算法探析[J];江西科学;2004年05期

7 Anany Levitin;Maria Levitin;;算法谜题[J];中国科技信息;2014年08期

8 杜刚;陆黎明;;一修路问题的算法解决分析[J];太原师范学院学报(自然科学版);2006年02期

9 许之民;;砝码称重问题的多种算法分析与探究[J];合肥学院学报(自然科学版);2011年01期

10 李亚楠;;菌群优化算法分析[J];贵州大学学报(自然科学版);2011年02期

中国重要会议论文全文数据库 前10条

1 俞洋;田亚菲;;一种新的变步长LMS算法及其仿真[A];通信理论与信号处理新进展——2005年通信理论与信号处理年会论文集[C];2005年

2 周颢;刘振华;赵保华;;构造型的D~2FA生成算法[A];中国通信学会通信软件技术委员会2009年学术会议论文集[C];2009年

3 赖桃桃;冯少荣;张东站;;一种基于划分和密度的快速聚类算法[A];第二十五届中国数据库学术会议论文集（一）[C];2008年

4 刘远新;邓飞其;罗艳辉;舒添慧;;ERP柔性平台下物流运输配送系统算法分析[A];第二十六届中国控制会议论文集[C];2007年

5 王树西;白硕;姜吉发;;模式合一的“减首去尾”算法[A];第二届全国学生计算语言学研讨会论文集[C];2004年

6 王万青;张晓辉;;改进的A~*算法的高效实现[A];2009全国测绘科技信息交流会暨首届测绘博客征文颁奖论文集[C];2009年

7 孙焕良;邱菲;刘俊岭;朱叶丽;;IncSNN——一种基于密度的增量聚类算法[A];第二十三届中国数据库学术会议论文集（研究报告篇）[C];2006年

8 韩建民;岑婷婷;于娟;;实现敏感属性l-多样性的l-MDAV算法[A];第二十七届中国控制会议论文集[C];2008年

9 张悦;尤枫;赵瑞莲;;利用蚁群算法实现基于程序结构的主变元分析[A];第五届中国测试学术会议论文集[C];2008年

10 王旭东;刘渝;邓振淼;;正弦波频率估计的修正Rife算法及其FPGA实现[A];全国第十届信号与信息处理、第四届DSP应用技术联合学术会议论文集[C];2006年

中国重要报纸全文数据库 前1条

1 科文;VIXD算法分析Web异常[N];中国计算机报;2008年

中国博士学位论文全文数据库 前10条

1 魏哲学;样本断点距离问题的算法与复杂性研究[D];山东大学;2015年

2 刘春明;基于增强学习和车辆动力学的高速公路自主驾驶研究[D];国防科学技术大学;2014年

3 张敏霞;生物地理学优化算法及其在应急交通规划中的应用研究[D];浙江工业大学;2015年

4 李红;流程挖掘算法研究[D];云南大学;2015年

5 盛歆漪;粒子群优化算法及其应用研究[D];江南大学;2015年

6 黄磊;高动态环境捷联惯导信号处理及高精度姿态速度算法研究[D];南京航空航天大学;2015年

7 刘新旺;多核学习算法研究[D];国防科学技术大学;2013年

8 于滨;城市公交系统模型与算法研究[D];大连理工大学;2006年

9 曾国强;改进的极值优化算法及其在组合优化问题中的应用研究[D];浙江大学;2011年

10 肖永豪;蜂群算法及在图像处理中的应用研究[D];华南理工大学;2011年

中国硕士学位论文全文数据库 前10条

1 黄厦;基于改进蚁群算法的柔性作业车间调度问题研究[D];昆明理工大学;2015年

2 李平;基于Hadoop的信息爬取与舆情检测算法研究[D];昆明理工大学;2015年

3 赵官宝;基于位表的关联规则挖掘算法研究[D];昆明理工大学;2015年

4 殷文华;移动容迟网络中基于社会感知的多播分发算法研究[D];内蒙古大学;2015年

5 徐翔燕;人工鱼群优化算法及其应用研究[D];西南交通大学;2015年

6 李德福;基于小世界模型的启发式寻路算法研究[D];华中师范大学;2015年

7 郑海彬;一种面向MAPREDUCE的DATASHUFFLE的优化方法[D];苏州大学;2015年

8 赵晓寒;轮换步长PSO算法及SMVSC参数优化[D];沈阳理工大学;2015年

9 安丰洋;基于无线网络的广播算法研究[D];曲阜师范大学;2015年

10 李智明;基于改进FastICA算法的混合语音盲分离[D];上海交通大学;2015年

  本文关键词：微博网络中的重叠社区发现算法研究，由笔耕文化传播整理发布。

本文编号：378448