PageRank算法在社区划分中的应用研究

发布时间：2019-07-13 15:00

【摘要】：网络节点的亲密程度或近似特征使社交网络往往呈现出特定的社区结构,因此,社区划分是社交网络结构研究的重要手段之一,研究划分后的网络社区可以获得网络的内部结构、作用关系以及规律特性,从而更好地理解和应用网络。现有的多种社区划分算法主要利用节点间连接的密切程度进行社区划分。本文把网络理解为一个信息随机扩散的系统,即节点信息扩散到其他节点的分布情况反映了他们之间的密切程度,这与PageRank算法的排序原理相一致。在此基础上,提出基于PageRank算法和信息扩散原理的社区划分算法(PR-DCS)。PR-DCS算法依据信息扩散的随机游走性质,将PageRank中的排序向量扩展为信息扩散矩阵,利用该矩阵反应出的节点间密切程度,分析得到社区结构。通过将PR-DCS算法与其他代表性社区划分算法进行实验对比分析,确定了PR-DCS算法能够准确的提取网络的社区结构。结合PageRank算法中的威望概念和PR-DCS算法中的主观意愿概念,对PR-DCS算法做了进一步的优化。算法的核心思想是同一社区节点间的信息交流更通畅,他们之间的信息交流比不同社区内节点间的交流更快达到稳定值。算法通过计算节点每次信息扩散之后的信息变化量来确定信息量率先稳定的节点关系,社区的核心节点在信息扩散过程中会先达到稳态,将先达到稳态的关系中的节点划分在一起能够更准确地提取社区结构。实验证明了社区核心节点扩散值达到稳态的速度高于其他节点,在对同一社区的划分中,优化算法的模块度更高,其结果也能更好地解释真实的社区划分。在对算法的探索中,分析了信息扩散次数对于划分结果的影响,将“六度分割”作为约束信息扩散次数的理论依据,保证了信息扩散矩阵中元素含义的正确性:既可以防止因扩散次数的增多而导致元素值转化为节点的威望值,同时也可以保证节点的基础交流行为。实验证明,将信息扩散次数定义为6能够客观地约束节点交流程度,准确提取社区结构。
文内图片：
图片说明： 沈阳航空航天大学硕士学位论文为 k 的概率。完全随机网络的度分布近似为泊松分布(Possion)，而大量研究表明许多实网络的度分布与泊松分布差异较大，以幂率分布形式出现，表示为 P(k)~k-r，例如影演员网络和电力网络[32]。幂率分布在双对数坐标系下绘制的结果近似一条斜率为负直线，当系数 r∈[2,3]时，表明网络中的绝大部分节点的度数很低，同时也存在少量度数较高的节点。图 2.1 表示具有 34 点的空手道网络的度数统计，横坐标表示节点的数，纵坐标表示度为 k 的节点占整个网络节点数的比例。图 2.2 是将统计值在对数坐中绘制的情况，这条曲线近似幂率分布。
文内图片：
图片说明： 沈阳航空航天大学硕士学位论文为 k 的概率。完全随机网络的度分布近似为泊松分布(Possion)，而大量研究表明许多实网络的度分布与泊松分布差异较大，以幂率分布形式出现，表示为 P(k)~k-r，例如影演员网络和电力网络[32]。幂率分布在双对数坐标系下绘制的结果近似一条斜率为负直线，当系数 r∈[2,3]时，表明网络中的绝大部分节点的度数很低，同时也存在少量度数较高的节点。图 2.1 表示具有 34 点的空手道网络的度数统计，横坐标表示节点的数，，纵坐标表示度为 k 的节点占整个网络节点数的比例。图 2.2 是将统计值在对数坐中绘制的情况，这条曲线近似幂率分布。
【学位授予单位】：沈阳航空航天大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TP393.02

【参考文献】

相关期刊论文 前6条

1 黄贤英;陈红阳;;基于用户兴趣度的PageRank改进算法[J];重庆理工大学学报(自然科学);2014年05期

2 周东浩;韩文报;;DiffRank:一种新型社会网络信息传播检测算法[J];计算机学报;2014年04期

3 杨博;陈贺昌;朱冠宇;赵学华;;基于超链接多样性分析的新型网页排名算法[J];计算机学报;2014年04期

4 张s

本文编号：2514072