随机游走社区划分算法的优化技术研究

发布时间：2017-09-25 12:26

  本文关键词：随机游走社区划分算法的优化技术研究

  更多相关文章： 复杂网络 社区划分 稀疏矩阵 随机游走

【摘要】：无论是在自然界还是在人类社会中,随处都可以见到复杂网络的身影,例如,人类社会网络,生物网络,电路网络等。为研究这些网络下蕴含的意义和价值,就需要对网络结构进行合理的系统性的分析。目前,对于复杂网络的研究已经渗透到各个领域中,社区划分算法的研究是复杂网络研究领域中的重要内容。随着社会网络和web技术的发展,网络规模逐渐增加,需要复杂网络社区划分算法在大型的复杂网络数据上可以进行高效快捷的社区划分,这也是目前社区划分领域的研究热点。为了实现这一目的,本文从Page Rank算法获得启发,利用随机游走思想,设网络中的每个节点都具有能量,网络中节点的能量通过能量转移概率矩阵进行相互传递。整个网络中的节点经过能量的相互传递达到稳定状态后,获得能量矩阵,在能量矩阵中分析提取相互之间能量传递最多的两个节点划分到同一个社区中,逐渐实现整个划分原则,直到整个网络划分为一个社区时终止,并且利用Q值来获取最优的划分结果,这是整个算法的核心思想。随着网络规模的增大,算法在执行过程中需要大量的存储空间,当网络规模达到一定程度,算法因存储空间不足而导致无法有效执行。我们知道社交网络中节点的度是服从幂律分布的,从大规模社交网络中抽象出的邻接矩阵和能量转移概率矩阵具有稀疏性。为了进一步优化算法,利用稀疏矩阵压缩存储来降低算法执行过程中需要的存储空间。但是,在能量传递过程中,随着迭代次数的增加,矩阵的稀疏性降低。为了保持矩阵的稀疏性,本文根据矩阵的维度设定阈值来维持矩阵的稀疏性,并且通过实验来说明设定阈值的必要性以及如何设定阈值来保持矩阵的稀疏性,从而提高算法的执行效率。为了验证本文提出的算法的精确性,将算法在已知划分结果的经典小样本数据集上做了测试,获得了精确的划分结果;并将该算法在大规模网络数据集进行验证,在得到较好划分结构的基础上提高了计算效率。
【关键词】：复杂网络 社区划分 稀疏矩阵 随机游走
【学位授予单位】：沈阳航空航天大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：O157.5
【目录】：

• 摘要6-7
• Abstract7-11
• 第1章 绪论11-17
• 1.1 论文的研究背景与意义11-13
• 1.2 国内外研究现状13-15
• 1.3 相关工作和内容安排15-17
• 1.3.1 相关工作15-16
• 1.3.2 本文所做的内容安排16-17
• 第2章 随机游走思想17-24
• 2.1 图的若干概念和定义17
• 2.2 随机游走思想17-19
• 2.3 PAGERANK算法思想19-22
• 2.4 基于复杂网络的随机游走思想22-24
• 第3章 稀疏矩阵的压缩存储24-39
• 3.1 稀疏矩阵分析26-30
• 3.2 稀疏矩阵的压缩存储模式30-34
• 3.2.1 Coordinate(COO)存储模式31
• 3.2.2 Compressed Sparse Row(CSR)存储模式31-32
• 3.2.3 ELLPACK (ELL)存储模式32-33
• 3.2.4 Diagonal (DIA)存储模式33-34
• 3.3 稀疏矩阵压缩存储模式的分析34-39
• 3.3.1 数据分析34-37
• 3.3.2 复杂网络中的稀疏矩阵37-39
• 第4章 基于随机游走思想的社区划分算法39-55
• 4.1 经典社区划分算法39-43
• 4.1.1 GN算法40-42
• 4.1.2 FN算法42-43
• 4.2 基于随机游走思想进行社区划分算法43-48
• 4.2.1 基于随机游走思想进行社区划分算法描述44-46
• 4.2.2 社区划分算法的评价指标46
• 4.2.3 大规模复杂网络的社区划分算法46-48
• 4.3 实验48-55
• 4.3.1 复杂网络中重要指标介绍48-49
• 4.3.2 阈值设置的具体分析49-51
• 4.3.3 实验结果与分析51-55
• 结论55-57
• 参考文献57-60
• 致谢60-62
• 攻读硕士期间发表（含录用）的学术论文62

【参考文献】

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

1 唐杰;陈文光;;面向大社交数据的深度分析与挖掘[J];科学通报;2015年Z1期

2 李佳佳;张秀霞;谭光明;陈明宇;;选择稀疏矩阵乘法最优存储格式的研究[J];计算机研究与发展;2014年04期

3 平宇;向阳;张波;黄寅飞;;基于MapReduce的并行PageRank算法实现[J];计算机工程;2014年02期

4 易成岐;鲍媛媛;薛一波;;社会网络大数据分析框架及其关键技术[J];中兴通讯技术;2014年01期

5 陈德华;周蒙;孙延青;郑亮亮;;MR-GSpar:一种基于MapReduce的大图稀疏化算法[J];计算机科学;2013年10期

6 吴志川;毛琛;韩蕾;陈立军;;高度可伸缩的稀疏矩阵乘法[J];计算机科学与探索;2013年11期

7 向林泓;陈芋文;张昱琳;;基于Hadoop平台的高阶矩阵相乘MapReduce算法研究[J];计算机科学;2013年S1期

8 张骏;;一种基于MapReduce并行框架的大规模矩阵乘法运算的实现[J];计算机应用与软件;2012年06期

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

，

本文编号：917385