基于标签传播的社区发现算法的研究

发布时间：2017-08-23 01:25

  本文关键词：基于标签传播的社区发现算法的研究

  更多相关文章： 社区发现 标签传播算法 节点相似度 关键节点

【摘要】：过去的十年时间见证了互联网的快速发展和改变,许多的社交网络媒体,包括博客、论坛、微博等一些社交媒体如雨后春笋般的出现,这些社交网络媒体把人们聚集在了一起并赋予了相互协作和相互交流新的形式。从数据挖掘的观点来看,社交网络由数量庞大的用户以及用户之间的联系聚集到一起形成了一张巨大的由许多个社区构成的网络。随着互联网技术的快速发展,社区发现技术正在迅速向前迈进。在现实生活中,社区发现技术也得到了广泛的应用,例如,网上商店根据用户的购物行为以及购物后的评论互动的这些集体智慧来更加精确有效的推荐商品；政治运动也可以从社交网络媒体所带来的新的参与方式和协作方式中获得利益；再比如微博中的某一个用户散布了一个谣言,最后谣言信息在微博上病毒式地扩散,怎样根据这样一个信息的动态传递而在最快时间内找到造谣者或者怎样利用社交网络结构更好的抑制谣言的传播?这些实实在在的场景都需要社交网络方面的知识来进行社区发现。本文首先对社区发现技术以及相关理论进行了介绍,主要包括数据抓取技术中的爬虫技术、一些早期的比较经典的社区发现算法以及有关于社区质量评价的一些方法,并对原始的标签传播算法进行了比较透彻的研究,标签传播算法与其它一些社区发现算法相比,具有计算简单和容易实现的优点以致于标签传播算法被广泛的利用。但是基本的标签传播算法存在稳定性低的问题,为了解决这种由随机选择最大数目标签的节点而引起的不稳定性的问题,这篇文章提出了基于节点相似度的标签传播算法和基于关键节点的标签传播算法,并将基于节点相似度的标签传播算法和基于关键节点的标签传播算法对dolphins、lesmis、polbooks、football以及所采集的豆瓣数据集进行了实验,通过实验结果,我们验证了基于节点相似度的标签传播算法和基于关键节点的标签传播算法对于基本的标签传播算法中的稳定性不足的问题有所改进。
【关键词】：社区发现 标签传播算法 节点相似度 关键节点
【学位授予单位】：西安电子科技大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：TP393.09;TP311.13
【目录】：

• 摘要5-6
• ABSTRACT6-10
• 符号对照表10-11
• 缩略语对照表11-14
• 第一章 绪论14-20
• 1.1 研究背景14-15
• 1.2 研究意义15-16
• 1.3 研究现状16-17
• 1.4 本文的组织结构17-20
• 第二章 复杂网络处理相关技术及理论20-32
• 2.1 爬虫技术20-22
• 2.1.1 防止被Ban处理20-21
• 2.1.2 模拟登录和Cookie处理21-22
• 2.1.3 验证码处理22
• 2.1.4 数据抽取技术22
• 2.1.5 其他爬虫扩展技术22
• 2.2 社区定义22-24
• 2.2.1 社交网络特点23-24
• 2.3 图论基础知识24-25
• 2.4 传统的社区发现算法25-27
• 2.4.1 GN算法25-26
• 2.4.2 FN算法26
• 2.4.3 KL算法26-27
• 2.5 标签传播算法27-29
• 2.6 社区质量评价29-31
• 2.6.1 模块度29-30
• 2.6.2 聚密度30
• 2.6.3 聚类系数30-31
• 2.6.4 互信息31
• 2.7 本章小结31-32
• 第三章 改进的标签传播算法32-44
• 3.1 原始的标签传播算法存在的问题32-33
• 3.2 基于节点相似度的标签传播算法33-36
• 3.2.1 节点相似度33-34
• 3.2.2 算法实现34-35
• 3.2.3 算法分析35-36
• 3.3 基于关键节点的标签传播算法36-43
• 3.3.1 PageRank排序算法36-37
• 3.3.2 简单PageRank计算37-39
• 3.3.3 LeaderRank排序算法39-40
• 3.3.4 简单LeaderRank计算40
• 3.3.5 关键的K个节点的选择40-42
• 3.3.6 标签传播的改进42-43
• 3.4 本章小结43-44
• 第四章 实验及结果分析44-62
• 4.1 实验相关数据集44-46
• 4.1.1 真实网络数据集44-45
• 4.1.2 人工抓取数据集45-46
• 4.2 NSLPA结果分析46-52
• 4.2.1 对dolphins数据集进行测试46
• 4.2.2 对dolphins数据集模块度评价46-47
• 4.2.3 对dolphins数据集聚密度评价47-49
• 4.2.4 对football、lesmis、polbooks数据集进行测试49-51
• 4.2.5 NSLPA对豆瓣数据集测试和评价51-52
• 4.3 KNLPA结果分析52-60
• 4.3.1 对dolphins等数据集的测试53-60
• 4.4 本章小结60-62
• 第五章 工作总结与展望62-64
• 5.1 主要工作62-63
• 5.2 工作展望63-64
• 参考文献64-66
• 致谢66-68
• 作者简介68

【参考文献】

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

1 王娜;李霞;徐红英;;社会网络分析之社区发现研究[J];深圳大学学报(理工版);2014年01期

2 康旭彬;贾彩燕;;一种改进的标签传播快速社区发现方法[J];合肥工业大学学报(自然科学版);2013年01期

3 金弟;杨博;刘杰;刘大有;何东晓;;复杂网络簇结构探测——基于随机游走的蚁群算法[J];软件学报;2012年03期

4 淦文燕;赫南;李德毅;王建民;;一种基于拓扑势的网络社区发现方法[J];软件学报;2009年08期

5 谭跃进;吴俊;邓宏钟;;复杂网络中节点重要度评估的节点收缩方法[J];系统工程理论与实践;2006年11期

，

本文编号：722205