基于PageRank算法的二分网络社区划分

发布时间：2017-08-14 10:15

  本文关键词：基于PageRank算法的二分网络社区划分

  更多相关文章： 二分网络 社区划分 PageRank算法 模块度

【摘要】：随着网络发展,网上发帖在人们日常生活中日益普及。根据发帖行为对网民和帖子进行社区划分,对判断网络中的水军和垃圾信息具有重要意义。网民与帖子构成了的二分网络是复杂网络的一种。二分网络社区划分是复杂网络社区划分重要的分支。二分网络社区划分最原始的算法是利用投影法将二分网络映射成单分网络,然后利用比较成熟的单分网络社区划分算法来进行研究。本文第一章节绪论主要介绍了复杂网络的相关知识和当前的研究现状,阐述了复杂网络在日常生活中的应用以及复杂网络的统计描述。第二章介绍了复杂网络及其特性。第三章详细地介绍了PageRank算法、随机游走的思想以及马尔可夫链。第四章介绍了基于PageRank算法的二分网络社区划分算法以及该算法在经典网络中进行实验得出的结论。并在最后介绍了社区划分的评价准则—模块度Q函数。最后一章是总结和展望,对本文的算法进行了总结,对社区划分进行了展望。基于信息在网络中的PageRank算法和模块度思想,本文提出了一个针对二分网络单侧节点的社区划分聚类算法。该算法通过模拟信息在网络中扩散的过程,利用各个节点的信息量在网络中扩散后,每个节点收到其他节点的信息量作为社区之间合并的依据,并引入模块度作为社区划分优劣判断的依据。该算法首先将二分网络转化为转移概率矩阵的形式,然后利用二分网络中单侧节点的关系进行概率转移,这样会得到单侧节点的概率转移关系,利用这个关系可以进行二分网络社区划分。最后算法在典型网络上测试结果表明,该算法能够获得比较高质量的社区划分效果。
【关键词】：二分网络 社区划分 PageRank算法 模块度
【学位授予单位】：沈阳航空航天大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：O157.5;TP301.6
【目录】：

• 摘要6-7
• Abstract7-11
• 第1章 绪论11-16
• 1.1 研究背景和意义11-15
• 1.2 本文的主要内容15
• 1.3 本文组织结构15-16
• 第2章 复杂网络及其特性的概述16-24
• 2.1 复杂网络简介16-18
• 2.2 复杂网络的统计描述18-20
• 2.2.1 节点的度18-19
• 2.2.2 平均路径长度19
• 2.2.3 介数19-20
• 2.3 Kernighan-Lin算法20-21
• 2.4 GN算法21-22
• 2.5 FN算法22-24
• 第3章 PageRank算法分析24-35
• 3.1 PageRank算法的简介24-25
• 3.2 PageRank算法分析25-27
• 3.2.1 PageRank算法实现26-27
• 3.3 随机游走模型27-29
• 3.4 随机游走搜索策略29-33
• 3.4.1 URW搜索策略29-30
• 3.4.2 NRRW搜索策略30
• 3.4.3 SARW搜索策略30
• 3.4.4 URW、NRRW、SARW之间的仿真与分析30-33
• 3.5 马尔可夫链33-35
• 第4章 基于PageRank算法的二分网络社区划分算法35-46
• 4.1 算法简介35
• 4.2 节点的信息扩散理论35-36
• 4.3 信息扩散概率模型36-37
• 4.4 合并判定原则37-38
• 4.5 划分原则的选择38-40
• 4.6 信息传递实例40-41
• 4.7 算法复杂度分析41-42
• 4.8 在经典网络Southern Women数据集上的实验42-43
• 4.9 在Davis女子俱乐部数据集上的测试43-44
• 4.10 迭代次数对算法的影响44-45
• 4.11 实验总结45-46
• 结论46-48
• 参考文献48-52
• 致谢52-53
• 攻读硕士期间发表（含录用）的学术论文53

【相似文献】

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

1 邵晶晶;冯波;李波;;PageRank排名技术的新算法[J];华中师范大学学报(自然科学版);2008年04期

2 彭珠;;一种求解PageRank问题的修正乘幂法(英文)[J];徐州师范大学学报(自然科学版);2009年04期

3 王福海;;基于PageRank的主题过滤算法改进[J];科技信息;2011年15期

4 邵晶晶;;PageRank算法的阻尼因子值[J];华中师范大学学报(自然科学版);2011年04期

5 于庆;黄迎富;;PageRank高阶导向量的数学性质及其算法研究[J];徐州师范大学学报(自然科学版);2012年01期

6 刘红;;PageRank在图书推荐技术中的应用研究[J];科技通报;2013年04期

7 顾传青;王磊;;一类修正的幂外推法加速PageRank计算[J];上海大学学报(自然科学版);2013年02期

8 李凯,赫枫龄,左万利;PageRank-Pro——一种改进的网页排序算法[J];吉林大学学报(理学版);2003年02期

9 王毅;江小玲;;基于PageRank算法的引擎搜索优化策略研究[J];科技资讯;2008年11期

10 县小平;;一种改进的PageRank算法[J];太原师范学院学报(自然科学版);2011年01期

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

1 ;Key Nodes Mining in Transport Networks Based on PageRank Algorithm[A];2009中国控制与决策会议论文集（3）[C];2009年

2 刘松彬;都云程;施水才;;基于分解转移矩阵的PageRank迭代计算方法[A];内容计算的研究与应用前沿——第九届全国计算语言学学术会议论文集[C];2007年

3 蔺继国;徐锡山;;一种基于用户点击数据的个性化PageRank算法[A];第六届全国信息检索学术会议论文集[C];2010年

4 李文;李淼;张建;朱海;陈雷;;基于混淆网络和PageRank的Nbest重排序[A];少数民族青年自然语言处理技术研究与进展——第三届全国少数民族青年自然语言信息处理、第二届全国多语言知识库建设联合学术研讨会论文集[C];2010年

5 陈小飞;王轶彤;冯小军;;一种基于网页质量的PageRank算法改进[A];第26届中国数据库学术会议论文集（B辑）[C];2009年

6 刘菁菁;林鸿飞;杨志豪;;基于PageRank和锚文本的网页排序研究[A];第三届学生计算语言学研讨会论文集[C];2006年

7 李洋涛;李川;许超;雷晓;徐洪宇;唐常杰;杨宁;;空间评分:基于PageRank的信息网络可视化中节点重要性度量[A];第29届中国数据库学术会议论文集（B辑）（NDBC2012）[C];2012年

8 Jonathan J.H.Zhu;;PPS Sampling of Web Graph Using Preferential Jumping Strategy[A];Proceedings 2010 IEEE 2nd Symposium on Web Society[C];2010年

9 刘建毅;王菁华;王枞;;基于语言网络的关键词抽取[A];第三届全国信息检索与内容安全学术会议论文集[C];2007年

10 ;Thinking with simple computer models:Modeling of social-economic systems[A];全国复杂系统研究论坛论文集（一）[C];2005年

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

1 何逍;复杂网络的可视化显示[D];电子科技大学;2015年

2 李金圻;基于Hadoop的微博舆情分析[D];北京邮电大学;2015年

3 孙乐天;基于PageRank和对象关系的聚类算法研究[D];兰州大学;2016年

4 刘卓然;基于改进PageRank算法的舆情引导技术研究[D];昆明理工大学;2016年

5 王文文;深度重启的Arnoldi加速的PageRank方法[D];上海大学;2016年

6 孟德鑫;基于MapReduce计算模型的PageRank算法的优化与实现[D];南京邮电大学;2016年

7 吴恒超;基于PageRank算法的二分网络社区划分[D];沈阳航空航天大学;2016年

8 杨硕;PageRank算法在社区划分中的应用研究[D];沈阳航空航天大学;2016年

9 蔡建超;基于PageRank算法的搜索引擎优化研究[D];江南大学;2008年

10 邵晶晶;基于PageRank排序算法改进的若干研究[D];华中师范大学;2009年

，

本文编号：672147